Can real-time search algorithms meet deadlines?

Babak Hamidzadeh, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings Tenth National Conference on Artificial Intelligence
PublisherPubl by AAAI
Number of pages6
ISBN (Print)0262510634
StatePublished - Dec 1 1992
EventProceedings Tenth National Conference on Artificial Intelligence - AAAI-92 - San Jose, CA, USA
Duration: Jul 12 1992Jul 16 1992


OtherProceedings Tenth National Conference on Artificial Intelligence - AAAI-92
CitySan Jose, CA, USA


Dive into the research topics of 'Can real-time search algorithms meet deadlines?'. Together they form a unique fingerprint.

Cite this