Clement, Bradley J. — Page 2

NASA NTRS2003

Abstract communication for coordinated planning

work offers evidence that distributed planning agents can greatly reduce communication costs by reasoning at abstract levels. While it is intuitive that improved search can reduce communication in such cases, there are other decisions about how to communicate plan information that greatly affect communication costs. This paper identifies cases independent of search where communicating at multiple levels of abstraction can exponentially decrease costs and where it can exponentially add costs. We conclude with a process for determining appropriate levels of communication based on characteristics of the domain.

coordination↗

NASA NTRS2003

Continual coordination through shared activities

Interacting agents that interleave planning and execution must reach consensus on their commitments to each other. In domains where agents have varying degrees of interaction and different constraints on communication and computation, agents will require different coordination protocols in order to efficiently reach consensus in real time. We briefly describe a largely unexplored class of realtime, distributed planning problems (inspired by interacting spacecraft missions), new challenges they pose, and a general approach to solving the problems. These problems involve self-interested agents that have infrequent communication but collaborate on joint activities. We describe a Shared Activity Coordination (SHAC) framework that provides a decentralized algorithm for negotiating the scheduling of shared activities over the lifetimes of separate missions, a soft, real-time approach to reaching consensus during execution with limited communication, and a foundation for customizing protocols for negotiating planner interactions. We apply SHAC to a realistic simulation of interacting Mars missions and illustrate the simplicity of protocol development.

planning↗