Real-Time Pathfinding in Unknown Terrain via Reconnection with an Ideal Tree

Abstract

In real-time pathfinding in unknown terrain an agent is required to solve a pathfinding problem by alternating a time-bounded deliberation phase with an action execution phase. Real-time heuristic search algorithms are designed for general search applications with time constraints but unfortunately in pathfinding they are known to produce poor-quality solutions. In this paper we propose pFRIT_RT, a real-time version of FRIT, a recently proposed algorithm able to produce very good-quality solutions in pathfinding under strict, but not fully real-time constraints. The idea underlying pFRIT_RT draws inspiration from bug algorithms, a family of pathfinding algorithms. Yet, as we show, pFRIT_RT is able to outperform a well-known bug algorithm and is able to solve graph search problems that are more general than pathfinding. pFRIT_RT also outperforms significantly—generating solutions six times shorter when time constraints are tight—a previously proposed real-time version of FRIT and the real-time heuristic search algorithm that is considered to have state-of-the-art performance in real-time pathfinding.