Specification and Analysis of Real-time Problem Solvers

ABSTRACT

There had been recent rise in research on real-time probelm 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 satify 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 provided 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.

Keywords: Real-time, Problem Solving, Search

---

Please select the format you would like to view the paper
If your browser do not support the viewing of postscript file, it will save as a file instead


---

[HOME PAGE]

Design and Maintain by Julian Chow
Questions and Comments?

[mailto:] jchow@cs.umn.edu

[last Updated] Mon. July 24th 1995