Lecture Notes in Computer Science 1 Distributed Problem Solving and Planning

Abstract. Distributed problem solving involves the collective effort of multiple problems solvers to combine their knowledge, information, and capabilities so as to develop solutions to problems that each could not have solved as well (if at all) alone. The challenge in distributed problem solving is thus in marshalling the distributed capabilities in the right ways so that the problem solving activities of each agent complement the activities of the others, so as to lead efficiently to effective solutions. Thus, while working together leads to distributed problem solving, there is also the distributed problem of how to work together that must be solved. We consider that problem to be a distributed planning problem, where each agent must formulate plans for what it will do that take into account (sufficiently well) the plans of other agents. In this paper, we characterize the variations of distributed problem solving and distributed planning, and summarize some of the basic techniques that have been developed to date.