Avoiding Dead Ends in Real-Time Heuristic Search


  • Bence Cserna University of New Hampshire
  • William Doyle University of New Hampshire
  • Jordan Ramsdell University of New Hampshire
  • Wheeler Ruml University of New Hampshire




heuristic search, real-time search, safety


Many systems, such as mobile robots, need to be controlled in real time. Real-time heuristic search is a popular on-line planning paradigm that supports concurrent planning and execution. However,existing methods do not incorporate a notion of safety and we show that they can perform poorly in domains that contain dead-end states from which a goal cannot be reached. We introduce new real-time heuristic search methods that can guarantee safety if the domain obeys certain properties. We test these new methods on two different simulated domains that contain dead ends, one that obeys the properties and one that does not. We find that empirically the new methods provide good performance. We hope this work encourages further efforts to widen the applicability of real-time planning.




How to Cite

Cserna, B., Doyle, W., Ramsdell, J., & Ruml, W. (2018). Avoiding Dead Ends in Real-Time Heuristic Search. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11533



AAAI Technical Track: Heuristic Search and Optimization