Online Search with Maximum Clearance
Keywords:Constraint Optimization, Deterministic Planning, Motion and Path Planning
AbstractWe study the setting in which a mobile searcher must locate a hidden target in a bounded or unbounded search domain, with no information about the hider's position. In particular, we consider online search, in which the performance of the search strategy is evaluated by its worst case competitive ratio. We introduce a multi-criteria search problem in which the searcher has a budget on its allotted search time, and the objective is to design strategies that are competitively efficient, respect the budget, and maximize the total searched ground. We give analytically optimal strategies for the line and the star domains, and efficient heuristics for general networks.
How to Cite
Angelopoulos, S., & Voss, M. (2021). Online Search with Maximum Clearance. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3642-3650. https://doi.org/10.1609/aaai.v35i5.16480
AAAI Technical Track on Constraint Satisfaction and Optimization