article

Abstract reasoning for planning and coordination

Authors:

Bradley J. Clement,

Edmund H. Durfee,

Anthony C. BarrettAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 28, Issue 1

Pages 453 - 515

Published: 01 April 2007 Publication History

Abstract

The judicious use of abstraction can help planning agents to identify key interactions between actions, and resolve them, without getting bogged down in details. However, ignoring the wrong details can lead agents into building plans that do not work, or into costly backtracking and replanning once overlooked interdependencies come to light. We claim that associating systematically-generated summary information with plans' abstract operators can ensure plan correctness, even for asynchronously-executed plans that must be coordinated across multiple agents, while still achieving valuable efficiency gains. In this paper, we formally characterize hierarchical plans whose actions have temporal extent, and describe a principled method for deriving summarized state and metric resource information for such actions. We provide sound and complete algorithms, along with heuristics, to exploit summary information during hierarchical refinement planning and plan coordination. Our analyses and experiments show that, under clearcut and reasonable conditions, using summary information can speed planning as much as doubly exponentially even for plans involving interacting subproblems.

References

[1]

Allen, J., Kautz, H., Pelavin, R., & Tenenberg, J. (1991). Reasoning about plans. Morgan Kaufmann.

[2]

Allen, J. F. (1983). Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11), 832-843.

Digital Library

[3]

Allen, J. F., & Koomen, J. A. (1983). Planning using a temporal world model. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 741-747.

[4]

Bock, C. (1996). Unified process specification language: Requirements for modeling process. Tech. rep. NISTIR 5910, National Institute of Standards and Technology.

[5]

Castillo, L., Fdez-Olivares, J., García-Pérez, O., & Palao, F. (2006). Efficiently handling temporal knowledge in an HTN planner. In 16th International Conference on Automated Planning and Scheduling (ICAPS-06), pp. 63-72. AAAI.

[6]

Chien, S., Knight, R., Stechert, A., Sherwood, R., & Rabideau, G. (2000a). Using iterative repair to improve the responsiveness of planning and scheduling. In Proceedings of the International Conference on AI Planning and Scheduling, pp. 300-307.

[7]

Chien, S., Rabideu, G., Knight, R., Sherwood, R., Engelhardt, B., Mutz, D., Estlin, T., Smith, B., Fisher, F., Barrett, T., Stebbins, G., & Tran, D. (2000b). Automating space mission operations using automated planning and scheduling. In Proc. SpaceOps.

[8]

Clement, B. (2002). Abstract Reasoning for Multiagent Coordination and Planning. Ph.D. thesis, University of Michigan, Ann Arbor.

Digital Library

[9]

Clement, B., & Durfee, E. (1999). Top-down search for coordinating the hierarchical plans of multiple agents. In Proceedings of the International Conference on Autonomous Agents.

Digital Library

[10]

Corkill, D. (1979). Hierarchical planning in a distributed environment. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 168-175.

Digital Library

[11]

Cox, J. S., & Durfee, E. H. (2003). Discovering and exploiting synergy between hierarchical planning agents. In Proceedings of the International Joint Conference on Autonomous Agents and MultiAgent Systems, pp. 281-288.

Digital Library

[12]

Currie, K., & Tate, A. (1991). O-Plan: The open planning architecture. Artificial Intelligence, 52, 49-86.

Digital Library

[13]

Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49, 61-95.

Digital Library

[14]

Decker, K. (1995). Environment centered analysis and design of coordination mechanisms. Ph.D. thesis, University of Massachusetts.

Digital Library

[15]

desJardins, M., &Wolverton, M. (1999). Coordinating a distributed planning system. AI Magazine, 20(4), 45-53.

[16]

Drabble, B., & Tate, A. (1994). The use of optimistic and pessimistic resource profiles to inform search in an activity based planner. In Artificial Intelligence Planning Systems, pp. 243-248.

[17]

Durfee, E. H., & Montgomery, T. A. (1991). Coordination as distributed search in a hierarchical behavior space. IEEE Transactions of Systems, Man and Cybernetics, 21(6), 1363-1378.

[18]

Emerson, E., & Halpern, J. Y. (1985). Decision procedures and expressiveness in the temporal logic of branching time. Journal of Computer and System Sciences, 30(1), 1-24.

Digital Library

[19]

Ephrati, E., & Rosenschein, J. (1994). Divide and conquer in multi-agent planning. In Proceedings of the National Conference on Artificial Intelligence, pp. 375-380.

Digital Library

[20]

Erol, K., Hendler, J., & Nau, D. (1994a). Semantics for hierarchical task-network planning. Tech. rep. CS-TR-3239, University of Maryland.

[21]

Erol, K., Nau, D., & Hendler, J. (1994b). UMCP: A sound and complete planning procedure for hierarchical task-network planning. In Proceedings of the International Conference on AI Planning and Scheduling.

[22]

Fagin, R., Halpern, J., Moses, Y., & Vardi, M. (1995). Reasoning about knowledge. MIT Press.

Digital Library

[23]

Firby, J. (1989). Adaptive Execution in Complex Dynamic Domains. Ph.D. thesis, Yale University.

Digital Library

[24]

Georgeff, M. P. (1983). Communication and interaction in multiagent planning. In Proceedings of the National Conference on Artificial Intelligence, pp. 125-129.

[25]

Georgeff, M. P. (1984). A theory of action for multiagent planning. In Proceedings of the National Conference on Artificial Intelligence, pp. 121-125.

[26]

Georgeff, M. P., & Lansky, A. (1986). Procedural knowledge. Proceedings of IEEE, 74(10), 1383- 1398.

[27]

Giunchiglia, F., & Traverso, P. (1999). Planning as model checking. In Proceedings of the 5th European Conference on Planning, pp. 1-20, London, UK. Springer-Verlag.

Digital Library

[28]

Glabbeek, R. v. (1997). Notes on the methodology of CCS and CSP. Theoretical Computer Science, 177(2), 329-349. Originally appeared as Report CS-R8624, CWI, Amsterdam, 1986.

Digital Library

[29]

Grosz, B., & Kraus, S. (1996). Collaborative plans for complex group action. Artificial Intelligence, 86, 269-358.

Digital Library

[30]

Huber, M. (1999). JAM: A BDI-theoretic mobile agent architecture. In Proceedings of the International Conference on Autonomous Agents, pp. 236-243.

Digital Library

[31]

Knight, R., Rabideau, G., & Chien, S. (2000). Computing valid intervals for collections of activities with shared states and resources. In Proceedings of the International Conference on AI Planning and Scheduling, pp. 600-610.

[32]

Knoblock, C. (1991). Search reduction in hierarchical problem solving. In Proceedings of the National Conference on Artificial Intelligence, pp. 686-691.

[33]

Korf, R. (1987). Planning as search: A quantitative approach. Artificial Intelligence, 33, 65-88.

Digital Library

[34]

Laborie, P., & Ghallab, M. (1995). Planning with sharable resource constraints. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1643-1649.

Digital Library

[35]

Lansky, A. (1990). Localized search for controlling automated reasoning. In Proceedings of the DARPA Workshop on Innovative Approaches to Planning, Scheduling and Control, pp. 115- 125.

[36]

Lee, J., Huber, M. J., Durfee, E. H., & Kenny, P. G. (1994). UMPRS: An implementation of the procedural reasoning system for multirobot applications. In Proceedings of the AIAA/NASA Conference on Intelligent Robotics in Field, Factory, Service, and Space, pp. 842-849.

[37]

McAllester, D., & Rosenblitt, D. (1991). Systematic nonlinear planning. In Proceedings of the National Conference on Artificial Intelligence, pp. 634-639.

[38]

Muscettola, N. (1994). HSTS: Integrating planning scheduling. Intelligent Scheduling, 169-212.

[39]

Nau, D., Au, T., Ilghami, O., Kuter, U., Murdock, J., Wu, D., & Yaman, F. (2003). SHOP2: An HTN planning system. Journal of Artificial Intelligence Research, 20, 379-404.

Digital Library

[40]

Pappachan, P. (2001). Coordinating Plan Execution in Dynamic Multiagent Environments. Ph.D. thesis, University of Michigan, Ann Arbor.

Digital Library

[41]

Pratt, V. R. (1976). Semantical considerations on floyd-hoare logic. In 17th Annual IEEE Symposium on Foundations of Computer Science, pp. 109-121.

Digital Library

[42]

Rao, A. S., & Georgeff, M. P. (1995). BDI-agents: From theory to practice. In Proceedings of the International Conference on Multi-Agent Systems, San Francisco.

[43]

Sacerdoti, E. (1974). Planning in a hierarchy of abstraction spaces. Artificial Intelligence, 5(2), 115-135.

[44]

Sacerdoti, E. D. (1977). A Structure for Plans and Behavior. Elsevier-North Holland.

[45]

Schlenoff, C., Knutilla, A., & Ray, S. (2006). Interprocess communication in the process specification language. Tech. rep. NISTIR 7348, National Institute of Standards and Technology.

[46]

Tate, A. (1977). Generating project networks. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 888-893.

[47]

Thangarajah, J., Padgham, L., & Winikoff, M. (2003). Detecting & avoiding interference between goals in intelligent agents. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 721-726.

Digital Library

[48]

Tsuneto, R., Hendler, J., & Nau, D. (1997). Space-size minimization in refinement planning. In Proceedings of the European Conference on Planning.

[49]

Tsuneto, R., Hendler, J., & Nau, D. (1998). Analyzing external conditions to improve the efficiency of HTN planning. In Proceedings of the National Conference on Artificial Intelligence, pp. 913-920.

Digital Library

[50]

Vilain, & Kautz, H. (1986). Constraint propagation algorithms for temporal reasoning. In Proceedings of the National Conference on Artificial Intelligence, pp. 377-382.

[51]

Weld, D. (1994). An introduction to least commitment planning. AI Magazine, 15(4), 27-61.

Digital Library

[52]

Wilkins, D. E. (1990). Can AI planners solve practical problems?. Computational Intelligence, 6(4), 232-246.

Digital Library

[53]

Wolverton, M., & desJardins, M. (1998). Controlling communication in distributed planning using irrelevance reasoning. In Proceedings of the National Conference on Artificial Intelligence, pp. 868-874.

Digital Library

[54]

Yang, Q. (1990). Formalizing planning knowledge for hierarchical planning. Computational Intelligence, 6(1), 12-24.

Digital Library

[55]

Yang, Q. (Ed.). (1997). Intelligent Planning: A Decomposition and Abstraction Based Approach. Springer.

Digital Library

[56]

Young, M., Pollack, M., & Moore, J. (1994). Decomposition and causality in partial-order planning. In Proceedings of the International Conference on AI Planning and Scheduling, pp. 188-193.

Cited By

Zhang YAgmon NAn BRicci AYeoh W(2023)From Abstractions to Grounded Languages for Robust Coordination of Task Planning RobotsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598993(2535-2537)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598993
Yao YAlechina NLogan BThangarajah JDignum FLomuscio AEndriss UNowé A(2021)Intention Progression using Quantitative Summary InformationProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464115(1416-1424)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464115
Dann MThangarajah JYao YLogan BEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)Intention-Aware Multiagent SchedulingProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398799(285-293)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398799
Show More Cited By

Recommendations

Abstract reasoning for multiagent coordination and planning
Planning for Coordination and Coordination for Planning
WI-IAT '08: Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 01

Except in very controlled or fortuitous circumstances, good coordination between agents does not spontaneously occur. In general, agents need to plan for coordination, anticipating how their activities can affect each other and choosing actions that ...
Approximate planning (extended abstract)
AIPS'94: Proceedings of the Second International Conference on Artificial Intelligence Planning Systems

This paper makes two linked contributions. First, we argue that planning systems, instead of being correct (every plan returned achieves the goal) and complete (all such plans are returned), should be approximately correct and complete, in that most ...

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 28, Issue 1

January 2007

550 pages

ISSN:1076-9757

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 April 2007

Received: 01 August 2006

Published in JAIR Volume 28, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YAgmon NAn BRicci AYeoh W(2023)From Abstractions to Grounded Languages for Robust Coordination of Task Planning RobotsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598993(2535-2537)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598993
Yao YAlechina NLogan BThangarajah JDignum FLomuscio AEndriss UNowé A(2021)Intention Progression using Quantitative Summary InformationProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464115(1416-1424)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464115
Dann MThangarajah JYao YLogan BEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)Intention-Aware Multiagent SchedulingProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398799(285-293)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398799
Durfee EThakur AGoldweber E(2020)Teammate-pattern-aware autonomy based on organizational self-design principlesAutonomous Agents and Multi-Agent Systems10.1007/s10458-020-09462-x34:2Online publication date: 16-May-2020
https://dl.acm.org/doi/10.1007/s10458-020-09462-x
Castle-Green SDewfall ALogan B(2020)The Intention Progression CompetitionEngineering Multi-Agent Systems10.1007/978-3-030-66534-0_10(144-151)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-66534-0_10
Logan BThangarajah JYorke-Smith NLarson KWinikoff MDas SDurfee E(2017)Progressing Intention ProgressionProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091234(768-772)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091234
de Silva LLarson KWinikoff MDas SDurfee E(2017)BDI Agent Reasoning with Guidance from HTN RecipesProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091233(759-767)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091233
Yao YLogan BJonker CMarsella SThangarajah JTuyls K(2016)Action-Level Intention Selection for BDI AgentsProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2937103(1227-1236)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2937103
de Silva LSardina SPadgham L(2016)Summary information for reasoning about hierarchical plansProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-1300(1300-1308)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.3233/978-1-61499-672-9-1300
Waters MPadgham LSardina S(2015)Improving domain-independent intention selection in BDI systemsAutonomous Agents and Multi-Agent Systems10.1007/s10458-015-9293-529:4(683-717)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s10458-015-9293-5
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