Speeding up distributed pseudo-tree optimization procedures with cross edge consistency to solve DCOPs
- PDF / 1,630,324 Bytes
- 14 Pages / 595.224 x 790.955 pts Page_size
- 50 Downloads / 168 Views
Speeding up distributed pseudo-tree optimization procedures with cross edge consistency to solve DCOPs Mashrur Rashik1 · Md. Musfiqur Rahman1 · Md. Mosaddek Khan1 · Md. Mamun-or-Rashid1 · Long Tran-Thanh2 · Nicholas R. Jennings3
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The Distributed Pseudo-tree Optimization Procedure (DPOP) is a well-known message passing algorithm that provides optimal solutions to Distributed Constraint Optimization Problems (DCOPs) in cooperative multi-agent systems. However, the traditional DCOP formulation does not consider constraints that must be satisfied (hard constraints), rather it concentrates only on constraints that place no restriction on satisfaction (soft constraints). This is a serious shortcoming as many realworld applications involve both types of constraints. Traditional DPOP algorithms are not able to benefit from the existence of hard constraints, where an additional calculation is required to handle such constraints. This results in longer runtimes. Thus scalability remains an issue. Additionally, in the standard DPOP, the agents are arranged as a Depth First Search (DFS) pseudo-tree, but recent work has shown that the construction of pseudo-trees in this way often leads to chain-like communication structures that greatly impair the algorithm’s performance. To address these issues, we develop an algorithm that speeds up the DPOP algorithm by reducing the size of the messages exchanged and increases parallelism in the pseudo tree. For this purpose, initially, we improve the path for exchanging messages. Next, we introduce a new form of constraint propagation, which we call cross-edge consistency. Our theoretical evaluation shows that our proposed algorithm is complete and correct. In empirical evaluations, our algorithm achieves a significant reduction in the runtime, ranging from 4% to 96%, compared to the state-of-the-art. Keywords Multiagent system · Distributed problem solving · Distributed constraint optimization · DPOP
1 Introduction Distributed Constraint Optimization Problems (DCOPs) is a commonly used framework involving multiple agents that interact with one another to achieve a common goal [23]. A number of real-world problems, such as distributed event scheduling [13], scheduling smart home devices [6] and allocating tasks in mobile sensor networks [11], can be modeled with this framework. Specifically, a DCOP consists of several distributed cost functions that collectively form a global objective function (i.e. the common goal). Each of these cost functions represents a constraint relationship among a set of variables that are controlled by the agents contributing to that constraint. In Mashrur Rashik
[email protected]
Extended author information available on the last page of the article.
more detail, each agent is responsible for setting the value(s) of its variable(s) from a finite domain(s). However, they can communicate with their neighboring agents, and thus can influence the value assignment of each other. Th
Data Loading...
