A polyhedral approach to some infinite sequencing problems
Abstract
Search problems are of paramount importance for protecting the safety and security of the United States and its allies. While search theory has made great strides, there remain fundamental unsolved problems, some of which have remained open for decades. This project focuses on search problems for which a target is located in one of a finite number of possible location sites but, if a target is present in a given location, a search of that location does not necessarily guarantee that the target will be found - that is, there is some overlook probability which determines the likelihood that the target is not found. For such problems, if the objective is to search the locations sequentially until the target has been found (or until the search is interrupted for some other reason), a feasible solution is an infinite sequence of searches. Two related but distinct settings will be considered. The first setting is concerned with finding searches that minimize the time or expected time to locate a hidden target. This type of search is appropriate if an attack (or cyberattack) is causing ongoing damage, and the objective is to stop it as soon as possible. The amount of damage being done may depend on the location of the target, and the time taken to search a location may vary with the location. The second setting considers search problems for which the target may be the survivor of a natural disaster or a prisoner held by an adversary, and there is a possibility that the search will be halted before the target has been found (for example if the searcher becomes trapped herself or captured by an adversary). In this second case, the objective is to maximize the probability of locating the target. It is assumed that, at each location, there is a given probability that the search will be terminated when that location is searched. The project will take a geometric approach to understanding the structure of feasible searches in both settings, and will focus on leveraging such understanding to finding optimal worst-case searches.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 07, 2024
- Source ID
- FA95502310556
Entities
People
- Thomas Lidbetter
Organizations
- Air Force Office of Scientific Research
- Rutgers University
- United States Air Force