Incremental sampling-based algorithms for a class of pursuit-evasion games

Abstract Pursuit-evasion games have been used for modeling various forms of con-flict arising between two agents modeled as dynamical systems. Although analyt-ical solutions of some simple pursuit-evasion games are known, most interesting instances can only be solved using numerical methods requiring significant offline computation. In this paper, a novel incremental sampling-based algorithm is pre-sented to compute optimal open-loop solutions for the evader, assuming worst-case behavior for the pursuer. It is shown that the algorithm has probabilistic complete-ness and soundness guarantees. As opposed to many other numerical methods tai-lored to solve pursuit-evasion games, incremental sampling-based algorithms offer anytime properties, which allow their real-time implementations in online settings.