Modularity and communication in multiagent planning

Abstract

Automation of planning techniques can potentially save a great deal of design and programming time, and can help robots design plans when human help is not available. Currently, the computational cost of machine planning algorithms prevents wide-spread use of these systems, and these costs are magnified in multiagent systems. The most expensive and time-consuming aspect of multiagent systems, communication, must be reduced if multiagent planning is to be practical. We propose a method by which agents may reduce both planning and communication costs by planning with stringent social laws, relaxing the laws as needed to find a solution. We provide and implement a practical model for representing and relaxing social laws, and show a method for learning laws in minimal time; we also present a method for generating and relaxing exclusive resource allocations in specific planning situations, and show that the method performs significantly better than random or no allocation in the average ca...