Moving Target Search with Subgoal Graphs∗

Moving Target Search (MTS) is a dynamic path plan-ning problem, where an agent is trying to reach a moving entity with a minimum path cost. Problems of this nature can be found in video games and dy-namic robotics, which require fast processing time (real time). In this work, we introduce a new algorithm for this problem- the Moving Target Search with Sub-goal Graphs (MTSub). MTSub is based on environment abstraction and uses Subgoal Graphs to speed up the searches for a minimal cost route to the target. The al-gorithm is optimal with respect to the knowledge that the agent has during the search. Experimental results show that MTSub can be used in real-time applications (e.g., applications requiring 5 microseconds response time per step). The experiments compared MTSub to G-FRA*, which is the best known dynamic algorithm so far, showing that MTSub is up to 29 times faster in average time per step, and up to 186 times faster in max-imum time per step