Using Partial Global Plans to Coordinate Distributed Problem Solvers

Abstract

Communicating problem solvers can cooperate in various ways, such as negotiating over task assignments, exchanging partial solutions to converge on global results, and planning interactions that help each other perform their tasks better. We introduce a new framework that supports different styles of cooperation by using partial global plans to specify effective, coordinated actions for groups of problem solvers. In this framework, problem solvers summarize their local plans into node-plans that they selectively exchange to dynamically model network activity and to develop partial global plans. However, because network and problem characteristics can change and communication channels have delays and limited capacity, problem solvers' models and partial global plans may be incomplete, out-of-date, and inconsistent. Our mechanisms allow problem solvers to agree on consistent partial global plans when possible, and to locally form partial global plans that lead to satisfactory cooperation even in rapidly changing environments where complete agreement is impossible. In this paper, we describe the mechanisms, knowledge representations, and algorithms that we have developed for generating and maintaining partial global plans in a distributed system. We use experiments to illustrate how these mechanisms improve and promote cooperation in a variety of styles.