Adrian Petcu

AAMAS Conference 2009 Conference Paper

Distributed Constraint Optimization with Structured Resource Constraints

• Akshat Kumar
• Boi Faltings
• Adrian Petcu

Distributed constraint optimization (DCOP) provides a framework for coordinated decision making by a team of agents. Often, during the decision making, capacity constraints on agents’ resource consumption must be taken into account. To address such scenarios, an extension of DCOP- Resource Constrained DCOP- has been proposed. However, certain type of resources have an additional structure associated with them and exploiting it can result in more efficient algorithms than possible with a general framework. An example of these are distribution networks, where the flow of a commodity from sources to sinks is limited by the flow capacity of edges. We present a new model of structured resource constraints that exploits the acyclicity and the flow conservation property of distribution networks. We show how this model can be used in efficient algorithms for finding the optimal flow configuration in distribution networks, an essential problem in managing power distribution networks. Experiments demonstrate the efficiency and scalability of our approach on publicly available benchmarks and compare favorably against a specialized solver for this task. Our results extend significantly the effectiveness of distributed constraint optimization for practical multi-agent settings.

AAMAS Conference 2008 Conference Paper

Decentralised Coordination of Low-Power Embedded Devices Using the Max-Sum Algorithm

• Alessandro Farinelli
• Alex Rogers
• Adrian Petcu
• NICK JENNINGS

This paper considers the problem of performing decentralised coordination of low-power embedded devices (as is required within many environmental sensing and surveillance applications). Specifically, we address the generic problem of maximising social welfare within a group of interacting agents. We propose a novel representation of the problem, as a cyclic bipartite factor graph, composed of variable and function nodes (representing the agents’ states and utilities respectively). We show that such representation allows us to use an extension of the max-sum algorithm to generate approximate solutions to this global optimisation problem through local decentralised message passing. We empirically evaluate this approach on a canonical coordination problem (graph colouring), and benchmark it against state of the art approximate and complete algorithms (DSA and DPOP). We show that our approach is robust to lossy communication, that it generates solutions closer to those of DPOP than DSA is able to, and that it does so with a communication cost (in terms of total messages size) that scales very well with the number of agents in the system (compared to the exponential increase of DPOP). Finally, we describe a hardware implementation of our algorithm operating on low-power Chipcon CC2431 System-on-Chip sensor nodes.

IJCAI Conference 2007 Conference Paper

• Adrian Petcu
• Boi Faltings

In distributed combinatorial optimization problems, dynamic programming algorithms like DPOP require only a linear number of messages, thus generating low communication overheads. However, DPOP's memory requirements are exponential in the induced width of the constraint graph, which may be prohibitive for problems with large width. We present MB-DPOP, a new hybrid algorithm that can operate with bounded memory. In areas of low width, MB-DPOP operates like standard DPOP (linear number of messages). Areas of high width are explored with bounded propagations using the idea of cycle-cuts. We introduce novel DFS-based mechanisms for determining the cycle-cutset, and for grouping cycle-cut nodes into clusters. We use caching between clusters to reduce the complexity to exponential in the largest number of cycle cuts in a single cluster. We compare MB-DPOP with ADOPT, the current state of the art in distributed search with bounded memory. MB-DPOP consistently outperforms ADOPT on 3 problem domains, with respect to 3 metrics, providing speedups of up to 5 orders of magnitude.

IJCAI Conference 2007 Conference Paper

• Adrian Petcu
• Boi Faltings
• Roger Mailler

Fully decentralized algorithms for distributed constraint optimization often require excessive amounts of communication when applied to complex problems. The OptAPO algorithm of Mailler and Lesser uses a strategy of partial centralization to mitigate this problem. We introduce PC-DPOP, a new partial centralization technique, based on the DPOP algorithm of Petcu and Faltings. PC-DPOP provides better control over what parts of the problem are centralized and allows this centralization to be optimal with respect to the chosen communication structure. Unlike OptAPO, PC-DPOP allows for a priory, exact predictions about privacy loss, communication, memory and computational requirements on all nodes and links in the network. Upper bounds on communication and memory requirements can be specified. We also report strong efficiency gains over OptAPO in experiments on three problem domains.

AAMAS Conference 2006 Conference Paper

MDPOP: Faithful Distributed Implementation of Efficient Social Choice Problems

• Adrian Petcu
• Boi Faltings
• David Parkes

AAAI Conference 2006 Conference Paper

ODPOP: An Algorithm for Open/Distributed Constraint Optimization

• Adrian Petcu

We propose ODPOP, a new distributed algorithm for open multiagent combinatorial optimization that feature unbounded domains (Faltings & Macho-Gonzalez 2005). The ODPOP algorithm explores the same search space as the dynamic programming algorithm DPOP (Petcu & Faltings 2005b) or ADOPT (Modi et al. 2005), but does so in an incremental, best-first fashion suitable for open problems. ODPOP has several advantages over DPOP. First, it uses messages whose size only grows linearly with the treewidth of the problem. Second, by letting agents explore values in a bestfirst order, it avoids incurring always the worst case complexity as DPOP, and on average it saves a significant amount of computation and information exchange. To show the merits of our approach, we report on experiments with practically sized distributed meeting scheduling problems in a multiagent system.

IJCAI Conference 2005 Conference Paper

A Scalable Method for Multiagent Constraint Optimization

• Adrian Petcu
• Boi

We present in this paper a new, complete method for distributed constraint optimization, based on dynamic programming. It is a utility propagation method, inspired by the sum-product algorithm, which 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. Our algorithm requires a linear number of messages, whose maximal size depends on the induced width along the particular pseudotree chosen. We compare our algorithm with backtracking algorithms, and present experimental results. For some problem types we report orders of magnitude fewer messages, and the ability to deal with arbitrarily large problems. Our algorithm is formulated for optimization problems, but can be easily applied to satisfaction problems as well.

AAAI Conference 2005 Conference Paper

Superstabilizing, Fault-Containing Multiagent Combinatorial Optimization

• Adrian Petcu

Self stabilization in distributed systems is the ability of a system to respond to transient failures by eventually reaching a legal state, and maintaining it afterwards. This makes such systems particularly interesting because they can tolerate faults, and are able to cope with dynamic environments. We propose the first self stabilizing mechanism for multiagent combinatorial optimization, which works on general networks and stabilizes in a state corresponding to the optimal solution of the optimization problem. Our algorithm is based on dynamic programming, and requires a linear number of messages to find the optimal solution in the absence of faults. We show how our algorithm can be made super-stabilizing, in the sense that while transiting from one stable state to the next, our system preserves the assignments from the previous optimal state, until the new optimal solution is found. We offer equal bounds for the stabilization and the superstabilization time. Furthermore, we describe a general scheme for fault containment and fast response time upon low impact failures. Multiple, isolated failures are handled effectively. To show the merits of our approach we report on experiments with practically sized distributed meeting scheduling problems in a multiagent system.

IJCAI Conference 2003 Conference Paper

Applying interchangeability techniques to the distributed breakout algorithm

• Adrian Petcu
• Boi Faltings

This paper presents two methods for improving the performance of the Distributed Breakout Algorithm using the notion of interchangeability. In particular, we use neighborhood partial and full interchangeability techniques to keep conflicts localized and avoid spreading them to neighboring areas. Our experiments on distributed sensor networks show that such techniques can significantly reduce the number of cycles required to solve the problems (therefore also reduce communication and time requirements), especially on difficult problems. Moreover, the improved algorithms are able to solve a higher proportion of the test problems.