article

Teleo-reactive programs for agent control

Author:

Nils J. NilssonAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 1, Issue 1

Pages 139 - 158

Published: 01 January 1994 Publication History

Abstract

A formalism is presented for computing and organizing actions for autonomous agents in dynamic environments. We introduce the notion of teleo-reactive (T-R) programs whose execution entails the construction of circuitry for the continuous computation of the parameters and conditions on which agent action is based. In addition to continuous feedback, T-R programs support parameter binding and recursion. A primary difference between T-R programs and many other circuit-based systems is that the circuitry of T-R programs is more compact; it is constructed at run time and thus does not have to anticipate all the contingencies that might arise over all possible runs. In addition, T-R programs are intuitive and easy to write and are written in a form that is compatible with automatic planning and learning methods. We briefly describe some experimental applications of T-R programs in the control of simulated and actual mobile robots.

References

[1]

Agre, P. (1989). The Dynamic Structure of Everyday Life. Tech. rep. TR 1085, AI Lab., Massachusetts Institute of Technology.

[2]

Benson, S. (1993). Unpublished working paper. Robotics Laboratory, Stanford University.

[3]

Berry, G., & Gonthier, G. (1992). The ESTEREL Synchronous Programming Language. Science of Computer Programming, 19, no. 2, 87-152, November.

Digital Library

[4]

Brooks, R. (1986). A Robust Layered Control System for a Mobile Robot. IEEE Journal of Robotics and Automation, March.

[5]

Brooks, R. (1989). The Behavior Language User's Guide. Seymour Implementation Note 2, AI Lab., Massachusetts Institute of Technology.

[6]

Chapman, D. (1990). Vision, Instruction and Action. Tech. rep. 1204, AI Lab., Massachusetts Institute of Technology.

[7]

Connell, J. (1993). SSS: A Hybrid Architecture Applied to Robot Navigation. Research Report, IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY 10598.

[8]

Dean, T., & Wellman, M. (1991). Planning and Control. San Francisco, CA: Morgan Kaufmann.

[9]

Drummond, M. (1989). Situated Control Rules. In Proc. First International Conf. on Principles of Knowledge Representation and Reasoning. San Francisco, CA: Morgan Kaufmann.

[10]

Fikes, R., Hart, P., & Nilsson, N. (1972). Learning and Executing Generalized Robot Plans. Artificial Intelligence, 3, 251-288.

Digital Library

[11]

Firby, R. (1987). An Investigation into Reactive Planning in Complex Domains. In Proc. AAAI-87. San Francisco, CA: Morgan Kaufmann.

[12]

Galles, D. (1993). Map Building and Following Using Teleo-Reactive Trees. In Intelligent Autonomous Systems: IAS-3, Groen, F. C. A., Hirose, S. & Thorpe, C. E. (Eds.), 90-398. Washington: IOS Press.

[13]

Gat, E. (1991). ALFA: A Language for Programming Reactive Robotic Control Systems. In Proceedings 1991 IEEE Robotics and Automation Conference.

[14]

Georgeff, M., & Lansky, A. (1989). Reactive Reasoning and Planning. In Proc. AAAI-87. San Francisco, CA: Morgan Kaufmann.

[15]

Ginsberg, M. L. (1989). Universal Planning: An (Almost) Universally Bad Idea. AAAI Magazine, 10, no. 4, 40-44, Winter.

Digital Library

[16]

John, G. (1993). `SQUISH: A Preprocessing Method for Supervised Learning of T-R Trees from Solution Paths, (unpublished). Robotics Laboratory, Stanford University.

[17]

Kaelbling, L. P. (1988). Goals as Parallel Program Specifications. In Proceedings AAAI-88, 60-65. Menlo Park, CA: American Association for Artificial Intelligence.

[18]

Kaelbling, L. P., & Rosenschein, S. J. (1990). Action and Planning in Embedded Agents. Robotics and Autonomous Systems, 6, nos. 1 and 2, 35-48, June.

[19]

Karlsson, J. (1990). Building a Triangle Using Action Nets. Unpublished project paper. Computer Science Dept., Stanford University. June.

[20]

Kohavi, R., & Benson, S. (1993). Research Note on Decision Lists. Machine Learning, 13, 131-134.

Digital Library

[21]

Maes, P. (1989). How to Do the Right Thing. Connection Science, 1, no.3, 291-323.

[22]

Mitchell, T. M., Keller, R. M., & Kedar-Cabelli, S. T. (1986). Explanation-based Generalization: A Unifying View. Machine Learning, 1, 47-80.

Digital Library

[23]

Nilsson, N. J. (1980). Principles of Artificial Intelligence. San Francisco, CA: Morgan Kaufmann.

[24]

Nilsson, N. (Ed.) (1984). Shakey the Robot. Tech. Note 323, Artificial Intelligence Center, SRI International, Menlo Park, CA 94025.

[25]

Nilsson, N. (1992). Toward Agent Programs with Circuit Semantics. Tech. rep. STAN-CS-92-1412, Department of Computer Science, Stanford University.

[26]

Ramadge, P. J. G., & Wonham, W. M. (1989). The Control of Discrete Event Systems. Proceedings of the IEEE, 77, no. 1, 81-98, January.

[27]

Reisig, W. (1985). Petri Nets: An introduction, Springer Verlag.

[28]

Rivest, R. L. (1987). Learning Decision Lists. Machine Learning, 2, 229-246.

Digital Library

[29]

Rosenschein, S. J. & Kaelbling, L.P. (1986). The Synthesis of Machines with Provable Epistemic Properties. In Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning about Knowledge. Halpern, J. (Ed.), 83-98, San Francisco, CA: Morgan Kaufmann. (Updated version: Technical Note 412, Artificial Intelligence Center, SRI International, Menlo Park, CA.)

[30]

Saffotti, A., Ruspini, E., & Konolige, K. (1993). Integrating Reactivity and Goal-directedness in a Fuzzy Controller. In Proc. of the 2nd Fuzzy-IEEE Conference, San Francisco, CA.

[31]

Schoppers, M. J. (1987). Universal Plans for Reactive Robots in Unpredictable Domains. In Proceedings of IJCAI-87. San Francisco, CA: Morgan Kaufmann.

[32]

Selman, B. (1993). Near-Optimal Plans, Tractability, and Reactivity. Tech. rep., AI Dept., AT&T Bell Laboratories.

[33]

Teo, P. C-S. (1991). "Botworld," (unpublished). Robotics Laboratory, Computer Science Dept., Stanford University, December.

[34]

Teo, P. C-S. (1992). Botworld Structures, (unpublished). Robotics Laboratory, Computer Science Dept., Stanford University, June.

[35]

Waterman, D. A. & Hayes-Roth, F. (1978). An Overview of Pattern-Directed Inference Systems. In Pattern-Directed Inference Systems, Waterman, D. A. & Hayes-Roth, F. (Eds.), 3-22. New York:Academic Press.

[36]

Wilson, S. (1991). The Animat Path to AI. In From Animals to Animats; Proceedings of the First International Conference on the Simulation of Adaptive Behavior, Meyer, J. A., & Wilson, S. (Eds.). Cambridge, MA: The MIT Press/Bradford Books.

Cited By

Biggar OZamani MShames I(2022)On Modularity in Reactive Control Architectures, with an Application to Formal VerificationACM Transactions on Cyber-Physical Systems10.1145/35116066:2(1-36)Online publication date: 11-Apr-2022
https://dl.acm.org/doi/10.1145/3511606
Ma YZhang JWu YWang Y(2021)Follow Me: Hierarchical Parallel Execution Synchronization in Behavior Trees2021 IEEE International Conference on Robotics and Biomimetics (ROBIO)10.1109/ROBIO54168.2021.9739272(613-618)Online publication date: 27-Dec-2021
https://dl.acm.org/doi/10.1109/ROBIO54168.2021.9739272
Yang SMao XWang SBai Y(2021)Extending Behavior Trees for Representing and Planning Robot Adjoint Actions in Partially Observable EnvironmentsJournal of Intelligent and Robotic Systems10.1007/s10846-021-01396-0102:2Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10846-021-01396-0
Show More Cited By

Recommendations

Reasoning about goal-directed real-time teleo-reactive programs
Abstract
The teleo-reactive programming model is a high-level approach to developing real-time systems that supports hierarchical composition and durative actions. The model is different from frameworks such as action systems, timed automata and TLA⁺, and ...
Verifying heterogeneous multi-agent programs
AAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems

We present a new approach to verifying heterogeneous multi-agent programs --- multi-agent systems in which the agents are implemented in different (BDI-based) agent programming languages. Our approach is based on meta-APL, a BDI-based agent programming ...
Probabilistic agent programs

Agents are small programs that autonomously take actions based on changes in their environment or “state”. Over the last few years, there has been an increasing number of efforts to build agents that can interact and/or collaborate with other agents. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Artificial Intelligence Research

Journal of Artificial Intelligence Research Volume 1, Issue 1

August 1993

307 pages

ISSN:1076-9757

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 January 1994

Received: 01 September 1993

Published in JAIR Volume 1, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Biggar OZamani MShames I(2022)On Modularity in Reactive Control Architectures, with an Application to Formal VerificationACM Transactions on Cyber-Physical Systems10.1145/35116066:2(1-36)Online publication date: 11-Apr-2022
https://dl.acm.org/doi/10.1145/3511606
Ma YZhang JWu YWang Y(2021)Follow Me: Hierarchical Parallel Execution Synchronization in Behavior Trees2021 IEEE International Conference on Robotics and Biomimetics (ROBIO)10.1109/ROBIO54168.2021.9739272(613-618)Online publication date: 27-Dec-2021
https://dl.acm.org/doi/10.1109/ROBIO54168.2021.9739272
Yang SMao XWang SBai Y(2021)Extending Behavior Trees for Representing and Planning Robot Adjoint Actions in Partially Observable EnvironmentsJournal of Intelligent and Robotic Systems10.1007/s10846-021-01396-0102:2Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10846-021-01396-0
Özkahraman ÖÖgren P(2020)Combining Control Barrier Functions and Behavior Trees for Multi-Agent Underwater Coverage Missions2020 59th IEEE Conference on Decision and Control (CDC)10.1109/CDC42340.2020.9304151(5275-5282)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.1109/CDC42340.2020.9304151
Uliana EStathis KJago R(2019)MagnetDroidProceedings of the Seventeenth International Conference on Artificial Intelligence and Law10.1145/3322640.3326729(123-132)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3322640.3326729
Cropper AMuggleton S(2019)Learning efficient logic programsMachine Language10.1007/s10994-018-5712-6108:7(1063-1083)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s10994-018-5712-6
Anisimov AMarchenko OZemlianskyi V(2019)Evolutionary Method of Constructing Artificial Intelligence SystemsCybernetics and Systems Analysis10.1007/s10559-019-00106-x55:1(1-9)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10559-019-00106-x
Yang HRudin CSeltzer M(2017)Scalable Bayesian rule listsProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305890.3306086(3921-3930)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305890.3306086
Snchez Plvarez BMartnez RIborra A(2017)Embedding statecharts into Teleo-Reactive programs to model interactions between agentsJournal of Systems and Software10.1016/j.jss.2017.05.081131:C(78-97)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.jss.2017.05.081
Li QSmith G(2017)Refining autonomous agents with declarative beliefs and desiresFormal Aspects of Computing10.1007/s00165-016-0391-129:2(227-249)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s00165-016-0391-1
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents