There has been a recent rise in research on real- time problem solving algorithms in artificial intelligence (AI). A real-time AI problem solver performs a task or a set of tasks in two phases. During the first phase, the problem solver searches for a solution that, once executed, will satisfy the requirements of the task. We refer to this phase as the planning phase or the search phase. During the next phase, the problem solver executes the planned solution to achieve the desired results of the task. This phase is referred to as the execution phase. Under time constraints, a real-time AI problem solver must balance planning and execution to minimize total response times and to comply with deadlines. This paper provides a methodology for the specification of real-time AI problem solvers. Using this methodology, we provide a formal specification of a real-time problem. In addition, the paper presents a methodology for analyzing real-time AI problem solvers. This methodology is demonstrated via a case study of two real-time problem solvers, namely DYNORAII and RTA* , for the real-time path planning problem. We provide new results on worst-case and average-case complexity of the problem, and of the algorithms that solve it We also provide experimental evaluation of DYNORAII and RTA* for deadline compliance and response-time minimization.
Bibliographical noteFunding Information:
Manuscript received January 1992; revised May 1993. This work was supported by the Graduate School of the University of Minnesota and by the Minnesota Department of Transportation, under GUIDESTAR project. Recommended by R. Kemmerer. The authors are with the Computer Science Department, University of Minnesota, Minneapolis, MN 55455. IEEE Log Number 9211181.
- Problem solving
- real time search