A Scalable Method for Multiagent Constraint Optimization

Boi Faltings, Adrian Petcu
2005
Report or working paper

We present in this paper a new complete method for distributed constraint optimization. This is a utility-propagation method, inspired by the sum-product algorithm (Kschischang et al 2001). The original algorithm requires fixed message sizes, linear memory and linear time in the size of the problem. However, it is correct only for tree-shaped constraint networks. In this paper, we show how to extend that algorithm to arbitrary topologies using a pseudotree arrangement of the problem graph. We compare our algorithm with "standard" backtracking algorithms, and present experimental results. For some problem types we report orders of magnitude less messages, and even the ability to deal with arbitrary large problems. Our algorithm is formulated for optimization problems, but can be easily applied to satisfaction problems as well.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Boi Faltings, Adrian Petcu
2005
Report or working paper

Abstract

Official source

https://infoscience.epfl.ch/record/52705?ln=en

About this result

Related concepts (15)

Related concepts

Related publications (76)

Related publications

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

Problem solving

Problem solving is the process of achieving a goal by overcoming obstacles, a frequent part of most activities. Problems in need of solutions range from simple personal tasks (e.g. how to turn on an a

Constrained optimization

In mathematical optimization, constrained optimization (in some contexts called constraint optimization) is the process of optimizing an objective function with respect to some variables in the pres

A Distributed, Complete Method for Multi-Agent Constraint Optimization

Boi Faltings, Adrian Petcu

We present in this paper a new complete method for distributed constraint optimization. This is a utility-propagation method, inspired by the sum-product algorithm. The original algorithm requires fixed message sizes, linear memory, and is time-linear in the size of the problem. However, it is correct only for tree-shaped constraint networks. In this paper, we show how to extend the algorithm to arbitrary topologies using cycle cutsets, while preserving the linear message size and memory requirements. We present some preliminary experimental results on randomly generated problems. The algorithm is formulated for optimization problems, but can be easily applied to satisfaction problems as well.

2004

Recent Advances in Dynamic, Distributed Constraint Optimization

Adrian Petcu

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.

2006

Distributed Generator Maintenance Scheduling

Boi Faltings, Adrian Petcu

In recent years the electricity sector has undergone a number of changes that all point in the direction of liberalization and decentralization of control. However, a number of technological challenges have to be addressed before the desired degree of decentralization is obtained. Currently, most of the decisions about the operation of a power system are still made in control centers in a centralized fashion. We present in this paper a distributed optimization method that allows several power plant operators to schedule preventive maintenance on their generation units in a distributed fashion. This method does not require the centralization of private data of the power plant operators (like available capacities, internal maintenance schedules, maintenance and operation costs, etc). Furthermore, the method guarantees globally optimal schedules while observing the power generation demand at all times. The problem is modeled as a constraint satisfaction/optimization problem, which is a powerful paradigm for solving numerous tasks in distributed AI, like planning, scheduling, resource allocation. The algorithm that we use is a complete method for distributed constraint optimization, based on dynamic programming. It requires a linear number of messages, whose maximal size depends on a parameter of the constraint graph, called induced width. This makes our algorithm well suited for large but loose problems. We conjecture that this method has applications in power systems well beyond this scheduling scenario.

2005