Back to Search Start Over

Planning High-Level Paths in Hostile, Dynamic, and Uncertain Environments.

Authors :
Banfi, Jacopo
Shree, Vikram
Campbell, Mark
Source :
Journal of Artificial Intelligence Research; 2020, Vol. 69, p297-342, 46p
Publication Year :
2020

Abstract

This paper introduces and studies a graph-based variant of the path planning problem arising in hostile environments. We consider a setting where an agent (e.g. a robot) must reach a given destination while avoiding being intercepted by probabilistic entities which exist in the graph with a given probability and move according to a probabilistic motion pattern known a priori. Given a goal vertex and a deadline to reach it, the agent must compute the path to the goal that maximizes its chances of survival. We study the computational complexity of the problem, and present two algorithms for computing high quality solutions in the general case: an exact algorithm based on Mixed-Integer Nonlinear Programming, working well in instances of moderate size, and a pseudo-polynomial time heuristic algorithm allowing to solve large scale problems in reasonable time. We also consider the two limit cases where the agent can survive with probability 0 or 1, and provide specialized algorithms to detect these kinds of situations more efficiently. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
10769757
Volume :
69
Database :
Supplemental Index
Journal :
Journal of Artificial Intelligence Research
Publication Type :
Academic Journal
Accession number :
146423744
Full Text :
https://doi.org/10.1613/jair.1.12077