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 next up previous
Next: 1 Introduction

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


next up previous
Next: 1 Introduction
Bradley Clement 2006-12-29