Path-Constrained Search in Discrete Time and Space

Lawrence D. Stone, Johannes O. Royset and Alan R. Washburn
Additional contact information
Lawrence D. Stone: Metron, Inc.
Johannes O. Royset: Naval Postgraduate School
Alan R. Washburn: Naval Postgraduate School

Chapter Chapter 4 in Optimal Search for Moving Targets, 2016, pp 81-120 from Springer

Abstract: Abstract In some practical situations, a searcher might have difficulties with implementing an optimal search plan of the form stipulated in the previous chapters. The plan might call for an instantaneous shift of search effort from one time period to the next. If the searcher requires a significant amount of time to carry out this shift, a relatively fast moving target would “get ahead” of the searcher. This situation is especially prevalent in robotic searches of buildings, where transit from room to room accounts for the majority of time expenditure, and searches using low-speed unmanned aerial systems, where the ratio of searcher speed to target speed is low. In this chapter, we describe methods for computing optimal search plans while accounting for real-world constraints on the agility of the searcher. In fact, we consider multiple searchers, each providing a discrete search effort, as well as multiple targets. The chapter starts, however, with the simpler situation of a single searcher looking for a single target. We formulate the optimal search problem as that of finding the optimal searcher path and describe a branch-and-bound algorithm for its solution. We proceed by generalizing the formulation to account for a searcher that operates at different “altitudes” with a more complex sensor. We also describe algorithmic enhancements that both handle the more general situation and provide computational speed-ups. The chapter then addresses the situation with multiple searchers, first of identical types and second of different types and also with multiple targets. These generalizations are most easily handled within a mathematical programming framework, which facilitates the consideration of a multitude of constraints including those related to airspace deconflication and also allows the leverage of well-developed optimization solvers for the determination of optimal searcher plans. The chapter ends with a description of some algorithms behind these solvers, with an emphasis on cutting-plane methods. Throughout the chapter we remain in the context of discrete time and space search.

Keywords: Search Plan; Multiple Searchers; Longest-path Problem; Nondetection Probability; Time-expanded Network (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-319-26899-6_4

Ordering information: This item can be ordered from
http://www.springer.com/9783319268996

DOI: 10.1007/978-3-319-26899-6_4

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().