Deterministic versus Probabilistic Methods for Searching for an Evasive Target. / Bernardini, Sara; Fox, Maria; Long, Derek; Piacentini, Chiara.

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17). 2017. p. 3709-3715.

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

Published

Documents

Links

Abstract

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)
Pages3709-3715
Number of pages7
Publication statusPublished - 12 Feb 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 28991747