Deterministic versus Probabilistic Methods for Searching for an Evasive Target

Sara Bernardini, Maria Fox, Derek Long, Chiara Piacentini

Research output: Chapter in Book/Report/Conference proceedingConference contribution

117 Downloads (Pure)


Several advanced applications of autonomous aerial vehicles in civilian and military contexts involve a searching agent with imperfect sensors that seeks to locate a mobile target in a given region. Effectively managing uncertainty is key to solving the related search problem, which is why all methods devised so far hinge on a probabilistic formulation of the problem and solve it through branch-and-bound algorithms, Bayesian filtering or POMDP solvers. In this paper, we consider a class of hard search tasks involving a target that exhibits an intentional evasive behaviour and moves over a large geographical area, i.e., a target that is particularly difficult to track down and uncertain to locate. We show that, even for such a complex problem, it is advantageous to compile its probabilistic structure into a deterministic model and use standard deterministic solvers to find solutions. In particular, we formulate the search problem for our uncooperative target both as a deterministic automated planning task and as a constraint programming task and show that in both cases our solution outperforms POMDPs methods.
Original languageEnglish
Title of host publicationProceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
Number of pages7
Publication statusPublished - 12 Feb 2017

Cite this