Can real-time search algorithms meet deadlines?
Babak Hamidzadeh, Shashi Shekhar · National Conference on Artificial Intelligence · 1992
A real-time AI problem solver performs a task or a set of tasks in two phases: planning and execution. Under real-time constraints, a real-time AI problem solver must balance the planning and the execution phases of its operation to comply With deadlines. This paper provides a methodology for specification and analysis of real-time AI problems and problem solvers. This methodology is demonstrated via domain analysis of the real-time path planning problem and via algorithm analysis of DYNORAII and RTA* [1]. We provide new results on worst-case complexity of the problem. We also provide experimental evaluation of DYNORAII and RTA* for deadline compliance.