Journal of Artificial Intelligence Research, 28 (2007) 453-515. Submitted 8/06; published 4/07

© 2007 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Abstract Reasoning for Planning and Coordination

Bradley J. Clement
Jet Propulsion Laboratory, Mail Stop: 126-347
Pasadena, CA 91109 USA
brad.clement@jpl.nasa.gov

Edmund H. Durfee
Electrical Engineering and Computer Science Department
University of Michigan,Ann Arbor, MI 48109 USA
durfee@umich.edu

Anthony C. Barrett
Jet Propulsion Laboratory, Mail Stop: 126-347
Pasadena, CA 91109 USA
tony.barrett@jpl.nasa.gov

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.

all on one page

• 1 Introduction
  • A formal model of hierarchical plans with temporal extent, and of their execution.
  • Algorithms for deriving summary information about propositional and metric resource conditions and effects, and for using such information to determine potential and definite interactions between abstract tasks.
  • Sound and complete algorithms for hierarchical refinement planning and centralized plan coordination for actions with temporal extent, supporting flexible plan execution systems.
  • Search techniques and heuristics, including choose-fewest-threats-first (CFTF) and expand-most-threats-first (EMTF), that take advantage of summary information to prune the search space.
  • Complexity analyses and experiments showing potential doubly-exponential speedups in refinement and local search planning/scheduling using summary information.
  • 1.1 Manufacturing Example
  • 1.2 Overview
  
  
• 2 A Model of Hierarchical Plans and their Concurrent Execution
  • 2.1 Overview
  • 2.2 CHiPs
  • 2.3 Executions
  • 2.4 Histories and Runs
  • 2.5 Asserting, Clobbering, Achieving, and Undoing
  • 2.6 External Conditions
  
  
• 3 Plan Summary Information
  • 3.1 Overview
  • 3.2 Summary Conditions
  • 3.3 Summary condition relationships and algorithms
  • 3.4 Deriving Summary Conditions
  • 3.5 Summary Resource Usage
    • 3.5.1 Representation
    • 3.5.2 Resource Summarization Algorithm
  
  
• 4 Identifying Abstract Solutions
  • 4.1 Threats on Summary Conditions
  • 4.2 Summary Resource Usage Threats
  
  
• 5 Hierarchical Planning and Coordination Algorithm
  • 5.1 Top-Down Hierarchical Planning and Coordination
  • 5.2 Search Techniques and Heuristics
  
  
• 6 Complexity Analyses
  • 6.1 Complexity of Summarization
  • 6.2 Complexity of Finding Abstract Solutions
  • 6.3 Scheduling Complexity
  
  
• 7 Experiments
  • 7.1 Coordinated Planning Experiments
  • 7.2 Scheduling Experiments
    • 7.2.1 Problem Domains
    • 7.2.2 Empirical Results for Mars Rovers
  • 7.3 Communication Overhead
  
  
• 8 Other Related Work
• 9 Conclusion
• Appendix A: Algorithms for Computing Interval Relations
• Appendix B: Algorithms for Must/May Asserting Summary Conditions
• Bibliography
• About this document ...