Anytime algorithm development tools

ABSTRACT

Anytime algorithms are playing an increasingly important role in the construction of effective reasoning and planning systems. Early work on anytime algorithms concentrated on the construction of applications in such areas as medical diagnosis and mobile robot navigation. In this paper we describe a programming environment to support the development of such applications as well as larger applications in which several anytime algorithms are used. The widespread use of anytime algorithms depends largely on the availability of such programming tools for algorithm construction, performance measurement, composition of anytime algorithms, and monitoring of their execution. We present a prototype system that meets these needs. Created in lisp, this library of functions, graphical tools and monitoring modules will accelerate and simplify the process of programming with anytime algorithms.

REFERENCES

• 1: M. Boddy and T. L. Dean. Solving time-dependent planning problems. <i>Proceedings of the Eleventh International Joint Conference on Artificial Intelligence,</i> pp. 979--984, Detroit, Michigan, 1989.
• 2: T. L. Dean and M. Boddy. An analysis of time-dependent planning. <i>Proceedings of the Seventh National Conference on Artificial Intelligence,</i> pp. 49--54, Minneapolis, Minnesota, 1988.
• 3: C. Elkan. Incremental, approximate planning: Abductive default reasoning. <i>Proceedings of the AAAI Spring Symposium on Planning in Uncertain Environments,</i> Palo Alto, California, 1990.
• 4: B. Hayes-Roth, R. Washington, R. Hewett, M. Hewett and A. Siever. Intelligent monitoring and control. <i>Proceedings of the Eleventh International Joint Conference on Artificial Intelligence,</i> pp. 243--249, Detroit, Michigan, 1989.
• 5: E. J. Horvitz. Reasoning about beliefs and actions under computational resource constraints. <i>Proceedings of the 1987 Workshop on Uncertainty in Artificial Intelligence,</i> Seattle, Washington, 1987.
• 6: E. J. Horvitz and J. S. Breese. <i>Ideal partition of resources for metareasoning.</i> Technical Report KSL-90--26, Stanford Knowledge Systems Laboratory, Stanford, California, 1990.
• 7: K. J. Lin, S. Natarajan, J. W. S. Liu and T. Krauskopf. Concord: A system of imprecise computations. <i>Proceedings of COMPSAC '87,</i> pp. 75--81, Tokyo, Japan, 1987.
• 8: S. J. Russell and S. Zilberstein. Composing Real-Time Systems. <i>Proceedings of the Twelfth International Joint Conference on Artificial Intelligence,</i> pp. 212--217, Sydney, Australia, 1991.
• 9: K. P. Smith and J. W. S. Liu. Monotonically improving approximate answers to relational algebra queries. <i>COMPSAC-89,</i> Orlando, Florida, 1989.
• 10: Shlomo Zilberstein, Operational rationality through compilation of anytime algorithms, University of California at Berkeley, Berkeley, CA, 1993
• 11: S. Zilberstein Optimizing Decision Quality with Contract Algorithms. <i>Proceedings of the fourteenth International Joint Conference on AI,</i> pp. 1576--1582, Montreal, Canada, 1995.
• 12: Shlomo Zilberstein , Stuart J. Russell, Efficient resource-bounded reasoning in AT-RALPH, Proceedings of the first international conference on Artificial intelligence planning systems, p.260-266, May 1992, College Park, Maryland, United States
• 13: S. Zilberstein and S. J. Russell. Anytime sensing, planning and action: A practical model for robot control. In <i>Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence,</i> pp. 1402--1407, Chambery, France, 1993.
• 14: Shlomo Zilberstein , Stuart Russell, Optimal composition of real-time systems, Artificial Intelligence, v.82 n.1-2, p.181-213, April 1996 [doi>10.1016/0004-3702(94)00074-3]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Design, Measurement, Performance, Theory