×

Planning control rules for reactive agents. (English) Zbl 0894.68138

Summary: A traditional approach for planning is to evaluate goal statements over state trajectories modeling predicted behaviors of an agent. This paper describes a powerful extension of this approach for handling complex goals for reactive agents. We describe goals by using a modal temporal logic that can express quite complex time, safety, and liveness constraints. Our method is based on an incremental planner algorithm that generates a reactive plan by computing a sequence of partially satisfactory reactive plans converging to a completely satisfactory one. Partial satisfaction means that an agent controlled by the plan accomplishes its goal only for some environment events. Complete satisfaction means that the agent accomplishes its goal whatever environment events occur during the execution of the plan. As such, our planner can be stopped at any time to yield a useful plan. An implemented prototype is used to evaluate our planner on empirical problems.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abadi, M.; Lamport, L.; Wolper, P., Realizable and unrealizable specifications of reactive systems, (Proceedings 16th International Colloquium on Automata, Languages and Programming. Proceedings 16th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 372 (1989), Springer: Springer Berlin), 1-17
[2] Alur, R.; Henzinger, T., Real-time logics: complexity and expressiveness, Inform. and Comput., 104, 35-77 (1993) · Zbl 0791.68103
[3] Bacchus, F., (TLPLAN user’s manual (1995), University of Waterloo: University of Waterloo Ont., Canada), anonymous
[4] Bacchus, F.; Kabanza, F., Applying decision theory to reactive planning, (Proceedings AAAI Decision-Theoretic Planning Spring Symposium (1994)), 1-5 · Zbl 0939.68827
[5] Bacchus, F.; Kabanza, F., Using temporal logic to control search in a forward chaining planner, (Proceedings 3rd European Workshop on Planning (EWSP). Proceedings 3rd European Workshop on Planning (EWSP), Assisi, Italy (1995)), 157-169
[6] Bacchus, F.; Kabanza, F., Planning for temporally extended goals, (Proceedings AAAI-96. Proceedings AAAI-96, Portland, OR (1996)), 1215-1222 · Zbl 1034.68549
[7] Barbeau, M.; Kabanza, F.; St-Denis, R., Synthesizing plant controllers using real-time goals, (Proceedings IJCAI-95. Proceedings IJCAI-95, Montreal, Que. (1995)), 791-798
[8] Courcoubetis, C.; Vardi, M. Y.; Wolper, P.; Yannakakis, M., Memory efficient algorithms for the verification of temporal properties, Formal Methods in System Design, 1, 275-288 (1992)
[9] Dean, T.; Kaelbling, L. P.; Kirman, J.; Nicholson, A., Planning under time constraints in stochastic domains, Artificial Intelligence, 76, 35-74 (1995)
[10] Drummond, M., Situated control rules, (Proceedings 1st International Conference on Principles of Knowledge Representation and Reasoning. Proceedings 1st International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ont. (1989)), 103-113 · Zbl 0709.68049
[11] Drummond, M.; Bresina, J., Anytime synthetic projection: maximizing probability of goal satisfaction, (Proceedings AAAI-90. Proceedings AAAI-90, Boston, MA (1990)), 138-144
[12] Drummond, M.; Swanson, K.; Bresina, J., Scheduling and execution for automatic telescopes, (Zweben, M.; Fox, M. S., Intelligent Scheduling (1994), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 341-369
[13] Emerson, E. A.; Sadler, T.; Srinivasan, J., Efficient temporal reasoning, (Proceedings 16th Annual ACM Symposium on Principles of Programming Languages. Proceedings 16th Annual ACM Symposium on Principles of Programming Languages, Austin, TX (1989)), 166-178
[14] Godefroid, P.; Kabanza, F., An efficient reactive planner for synthesizing reactive plans, (Proceedings AAAI-91. Proceedings AAAI-91, Anaheim, CA (1991)), 640-645
[15] Kabanza, F., Reactive planning of immediate actions, (Ph.D. Thesis (1992), Département d’Informatique, Université de Liège: Département d’Informatique, Université de Liège Belgium)
[16] Kabanza, F., Synchronizing multiagent plans using temporal logic specifications, (Proceedings 1st International Conference on Multi-Agent Systems (ICMAS-95) (1995)), 217-225
[17] Koymans, R., Specifying real-time properties with metric temporal logic, Real-time Systems, 2, 255-299 (1990)
[18] Manna, Z.; Pnueli, A., (The Temporal Logic of Reactive and Concurrent Systems (1991), Springer: Springer Berlin) · Zbl 0753.68003
[19] Pednault, E. P.D., ADL: Exploring the middle ground between STRIPS and the Situation Calculus, (Proceedings 1st International Conference on Principles of Knowledge Representation and Reasoning (KR-89). Proceedings 1st International Conference on Principles of Knowledge Representation and Reasoning (KR-89), Toronto, Ont. (1989)), 324-332
[20] Pnueli, A.; Rosner, R., On the synthesis of an asynchronous reactive module, (Proceedings 16th International Colloquium on Automata, Languages and Programming. Proceedings 16th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 372 (1989), Springer: Springer Berlin), 652-671
[21] Ramadge, P. J.G.; Wonham, W. M., The control of discrete event systems, (Proc. IEEE, 77 (1989)), 81-98
[22] Rao, A. S.; Georgeff, M. P., A model-theoretic approach to the verification of situated reasoning systems, (Proceedings IJCAI-93. Proceedings IJCAI-93, Chambery, France (1993)), 318-324
[23] Rich, E.; Knight, K., (Artificial Intelligence (1991), McGraw-Hill: McGraw-Hill New York)
[24] Schoppers, M. J., Universal plans for reactive robots in unpredictable environments, (Proceedings IJCAI-87. Proceedings IJCAI-87, Milan, Italy (1987)), 1039-1046
[25] Thomas, W., Automata on infinite objects, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. B (1990), Elsevier: Elsevier Amsterdam), 133-192 · Zbl 0900.68316
[26] Wolper, P., On the relation of programs and computations to models of temporal logic, (Proceedings Temporal Logic in Specification. Proceedings Temporal Logic in Specification, Lecture Notes in Computer Science, Vol. 398 (1989), Springer: Springer Berlin), 75-123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.