Track:
Contents
Downloads:
Abstract:
Constraint satisfaction/optimization is a powerful paradigm for solving numerous tasks in distributed AI, including planning and scheduling. However, up to now, distributed algorithms for constraint reasoning (especially optimization) have not been applied to large-scale systems due to their prohibitive complexity in terms of number of messages being exchanged. We have developed a series of new techniques for distributed constraint optimization, based on dynamic programming. These approaches require a linear number of messages, whose maximal size depends on a parameter of the problem graph, called the induced width. Thus, these methods are likely to work very well on large but loose problems. We believe that these methods have features that make them particularly interesting for solving planning and scheduling problems in dynamic, distributed environments.