Thinking Ahead in Real-Time Search

Vol. 19 (2009): Nineteenth International Conference on Automated Planning and Scheduling

Volume

Vol. 19 (2009): Nineteenth International Conference on Automated Planning and Scheduling

Long Papers

We consider real-time planning problems in which some states are unsolvable, i.e., have no path to a goal. Such problems are difficult for real-time planning algorithms such as RTA* in which all states must be solvable. We identify a property called k-safeness, in which the consequences of a bad choice become apparent within k moves after the choice is made. When k is not too large, this makes it possible to identify unsolvable states in real time. We provide a modified version of RTA* that is provably complete on all k-safe problems. We derive k-safeness conditions for real-time deterministic versions of the well-known Tireworld and Racetrack domains, and provide experimental results showing that our modified version of RTA* works quite well in these domains.

10.1609/icaps.v19i1.13353