Can Real-Time Search Algorithms Meet Deadlines?

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Real-Time

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.