×

zbMATH — the first resource for mathematics

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.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abadi, M.; Lamport, L.; Wolper, P., Realizable and unrealizable specifications of reactive systems, (), 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., (), anonymous
[4] Bacchus, F.; Kabanza, F., Applying decision theory to reactive planning, (), 1-5 · Zbl 0939.68827
[5] Bacchus, F.; Kabanza, F., Using temporal logic to control search in a forward chaining planner, (), 157-169
[6] Bacchus, F.; Kabanza, F., Planning for temporally extended goals, (), 1215-1222 · Zbl 1034.68549
[7] Barbeau, M.; Kabanza, F.; St-Denis, R., Synthesizing plant controllers using real-time goals, (), 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, (), 103-113
[11] Drummond, M.; Bresina, J., Anytime synthetic projection: maximizing probability of goal satisfaction, (), 138-144
[12] Drummond, M.; Swanson, K.; Bresina, J., Scheduling and execution for automatic telescopes, (), 341-369
[13] Emerson, E.A.; Sadler, T.; Srinivasan, J., Efficient temporal reasoning, (), 166-178
[14] Godefroid, P.; Kabanza, F., An efficient reactive planner for synthesizing reactive plans, (), 640-645
[15] Kabanza, F., Reactive planning of immediate actions, ()
[16] Kabanza, F., Synchronizing multiagent plans using temporal logic specifications, (), 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., ()
[19] Pednault, E.P.D., ADL: exploring the middle ground between STRIPS and the situation calculus, (), 324-332
[20] Pnueli, A.; Rosner, R., On the synthesis of an asynchronous reactive module, (), 652-671
[21] Ramadge, P.J.G.; Wonham, W.M., The control of discrete event systems, (), 81-98
[22] Rao, A.S.; Georgeff, M.P., A model-theoretic approach to the verification of situated reasoning systems, (), 318-324
[23] Rich, E.; Knight, K., ()
[24] Schoppers, M.J., Universal plans for reactive robots in unpredictable environments, (), 1039-1046
[25] Thomas, W., Automata on infinite objects, (), 133-192 · Zbl 0900.68316
[26] Wolper, P., On the relation of programs and computations to models of temporal logic, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.