Real-Time Heuristic Search in Dynamic Environments

Abstract

In dynamic environments, agents often do not have time to find a complete plan to reach a goal state, but rather must act quickly under changing circumstances. Real-time heuristic search models this setting by requiring that the agent's next action must be selected within a prespecified time bound. In this paper, we study real-time search algorithms that can tolerate a dynamic environment, in which action costs are not fully predictable. We propose a combination of two previously-proposed methods and study its behavior both theoretically and empirically on several different benchmark domains.