Distributed constraint optimization

Binary max-sum for multi-team task allocation in RoboCup Rescue

Publication Type:

Conference Paper

Source:

Optimisation in Multi-Agent Systems and Distributed Constraint Reasoning (OptMAS-DCR), Paris, France (2014)

Keywords:

RoboCup Rescue; Binary MaxSum

Abstract:

Coordination of agents involved in rescue missions is an important open research problem. We focus on the RoboCup Rescue Simulation (RCS) challenge, where different teams of agents perform urban rescue operations. Previous approaches typically cast such coordination problem as separate single-team allocation problems, and solve them separately. Our first key contribution is to focus on the max-sum approach, which has been successfully applied in this setting. We show that it is possible to reduce the computational complexity associated to max- sum from exponential to polynomial time. Our empirical evaluation shows that, by using our approach, the fire brigades team obtains significantly better results when compared to state-of- the-art approaches. Our second key contribution is a methodology that allows teams in RCS to make joint allocations. Specifically, our approach supports a modular design, where teams are independently modeled and subsequently connected via well-defined coordination points. To the best of our knowledge, this is the first task-assignment approach in the literature that enables teams in RCS to make simultaneous joint allocations. Experiments with fire brigades and police agents show that teams employing inter-team coordination are significantly more effective than uncoordinated teams.

On Binary Max-Sum and Tractable HOPs

Publication Type:

Conference Paper

Source:

11th European Workshop on Multi-agent Systems (EUMAS 2013), Volume 1113, Toulouse, France (2013)

Abstract:

The Max-Sum message-passing algorithm has been used to approximately solve several unconstrained optimization problems, specially in the distributed context. In general, the complexity of computing messages is exponential. However, if the problem is modeled using the so called Tractable HOPs (THOPs), binary MaxSum's messages can be computed in polynomial time. In this paper we review existing THOPs, and present new ones, aiming at providing an updated view of efficient message computation.

Connecting BnB-ADOPT with Soft Arc Consistency: Initial Results

Publication Type:

Conference Paper

Source:

Lecture Notes in Computer Science, Springer, Volume 6384, p.19-37 (2011)

Abstract:

Distributed constraint optimization problems with finite domains can be solved by asynchronous procedures. ADOPT is the reference algorithm for this kind of problems. Several versions of this algorithm have been proposed, one of them is BnB-ADOPT which changes the nature of the original algorithm from best-first to depth-first search. With BnB-ADOPT, we can assure in some cases that the value of a variable will not be used in the optimal solution. Then, this value can be deleted unconditionally. The contribution of this work consists in propagating these unconditionally deleted values using soft arc consistency techniques, in such a way that they can be known by other variables that share cost functions. When we propagate these unconditional deletions we may generate some new deletions that will also be propagated. The global effect is that we search in a smaller space, causing performance improvements. The effect of the propagation is evaluated on several benchmarks.

Global Constraints in Distributed Constraint Satisfaction

Publication Type:

Conference Paper

Source:

11th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2012), Valencia, Spain, p.1263-1264 (2012)

Abstract:

Global constraints have been crucial for the advancement of centralized constraint processing. Here, we propose the inclusion of global constraints in distributed constraint satisfaction. We detail how this inclusion can be done, considering different decompositions for global contraints. In the context of the ABT algorithm, we provide experimental evidence of their benefits on several benchmarks.

Improving BnB-ADOPT+-AC

Publication Type:

Conference Paper

Source:

11th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2012), Valencia, Spain, p.273-280 (2012)

Abstract:

Several multiagent tasks can be formulated and solved as DCOPs. BnB-ADOPT$^+$-AC is one of the most efficient algorithms for optimal DCOP solving. It is based on BnB-ADOPT, removing redundant messages and maintaining soft arc consistency during search. In this paper, we present several improvements for this algorithm, namely (i) a better implementation, (ii) processing exactly simultaneous deletions, and (iii) searching on arc consistent cost functions. We present empirical results showing the benefits of these improvements on several benchmarks.

Decomposing Global Cost Functions

Publication Type:

Conference Paper

Source:

CP 2011 workshop: Preferences and Soft Constraints, Perugia, Italy, p.16-30 (2011)

Abstract:

Similarly to what has been done with Global Constraints in Constraint Programming, different results have been recently published on Global Cost Functions in weighted CSPs, defining the premises of a Cost Function Programming paradigm.
In this paper, in the spirit of Berge-acyclic decompositions of global constraints such as Regular, we explore the possibility of decomposing Global Cost Functions in such a way that enforcing soft local consistencies on the decomposed cost function offers guarantees on the level of consistency enforced on the original global cost function. We show that an extension of Directional Arc Consistency to arbitrary arities and Virtual Arc Consistency offer specific guarantees. We conclude by preliminary experiments on WeightedRegular decompositions that show that decompositions may be very useful to easily integrate global cost functions in existing solvers with good efficiency.

Distributed Constraint Optimization Problems related with Soft Arc Consistency (Extended Abstract)

Publication Type:

Conference Paper

Source:

22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), Barcelona, Spain, p.2812-2813 (2011)

Abstract:

Distributed Constraint Optimization Problems (DCOPs) can be optimally solved by distributed search algorithms, such as ADOPT and BnB-ADOPT. In centralized solving, maintaining soft arc consistency during search has proved to be beneficial for performance. In this thesis we aim to explore the maintenance of different levels of soft arc consistency in distributed search when solving DCOPs.

Multi-Agent Coordination: DCOPs and Beyond

Publication Type:

Conference Paper

Source:

Twenty-Second International Joint Conference on Artificial Intelligence, AAAI Press, Volume 3, Barcelona, p.2838-2839 (2011)

ISBN:

978-1-57735-515-1

URL:

http://ijcai.org/papers11/contents.php

Abstract:

Distributed constraint optimization problems (DCOPs) are a model for representing multi-agent systems in which agents cooperate to optimize a global objective. The DCOP model has two main advantages: it can represent a wide range of problem domains, and it supports the development of generic algorithms to solve them. Firstly, this paper presents some advances in both complete and approximate DCOP algorithms. Secondly, it explains that the DCOP model makes a number of unrealistic assumptions that severely limit its range of application. Finally, it points out hints on how to tackle such limitations.

Improving function filtering for computationally demanding DCOPs

Publication Type:

Conference Paper

Source:

Workshop on Distributed Constraint Reasoning at IJCAI 2011, Barcelona, p.99-111 (2011)

Abstract:

In this paper we focus on solving DCOPs in computationally demanding scenarios. GDL optimally solves DCOPs, but requires exponentially large cost functions, being impractical in such settings. Function filtering is a technique that reduces the size of cost functions. We improve the effectiveness of function filtering to reduce the amount of resources required to optimally solve DCOPs. As a result, we enlarge the range of problems solvable by algorithms employing function filtering.

Enforcing Soft Local Consistency on Multiple Representations for DCOP Solving

Publication Type:

Conference Paper

Source:

CP 2010 workshop: Preferences and Soft Constraints, St. Andrews, Scotland, p.98-113 (2010)

Abstract:

Connecting soft arc consistency with distributed search in DCOP solving has been very beneficial for performance. However, including higher levels of soft arc consistency breaks usual privacy requirements. To avoid this issue, we propose to keep different representations of the same problem on each agent, on which soft arc consistencies are enforced respecting privacy. Deletions caused in one representation can be legally propagated to others. Experimentally, this causes significant benefits.

Syndicate content