AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Deterministic versus Probabilistic Methods for Searching for an Evasive Target
Sara Bernardini, Maria Fox, Derek Long, Chiara Piacentini

Last modified: 2017-02-12


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.


UAVs; planning; CP; probabilistic reasoning; POMDPs

Full Text: PDF