Recent Advances in Dynamic, Distributed Constraint Optimization

Constraint satisfaction/optimization is a powerful paradigm for solving numerous tasks in distributed AI, including planning, scheduling and resource allocation. 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 recently developed a series of new techniques for distributed constraint optimization, based on \textit{dynamic programming}. Unlike the methods that existed before, our techniques require a very small number of messages (\textit{linear in the size of the problem}). The maximal message size depends on a parameter of the problem graph, called the \textit{induced width}. Thus, these methods are likely to work very well on large but loose problems. We have proposed a whole range of techniques that deal with the most common problems in multiagent environments: efficiency, dynamics of the environment, privacy and the self interest of the agents involved. We believe that these methods are a particularly interesting foundation for distributed problem solving in dynamic, distributed environments.