High-Level Path Planning in Hostile Dynamic Environments

In this paper, we introduce and study a graph-based variant of the path planning problem arising in hostile environments. Here, the 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. Given a deadline to reach its goal, the robot must compute a path that maximizes its chances of survival. To solve this problem, which is proven to be NP-hard, we present a convex Mixed-Integer Nonlinear Program to compute optimal solutions and a more scalable heuristic algorithm.