Communication-Aware Local Search for Distributed Constraint Optimization
Authors: Ben Rachmut, Roie Zivan, William Yeoh
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical results demonstrate that imperfect communication has a positive effect on distributed local search algorithms due to increased exploration. Furthermore, the asynchronous anytime framework we proposed allows one to benefit from algorithms with inherent explorative heuristics. |
| Researcher Affiliation | Academia | Ben Rachmut EMAIL Roie Zivan EMAIL Department of Industrial Engineering and Management Ben-Gurion University of the Negev Beer Sheva, Israel William Yeoh EMAIL Department of Computer Science and Engineering Washington University in St. Louis Saint Louis, United States |
| Pseudocode | Yes | Algorithm 1: Latency-Aware Monotonic Distributed Local Search (LAMDLS) Algorithm 2: Asynchronous Anytime Mechanism (AAM) |
| Open Source Code | Yes | 7. The simulation s code is available at https://github.com/benrachmut/CADCOP_2022_new |
| Open Datasets | No | We evaluated our algorithms on four different problem types. The first three problem types are commonly used in the DCOP literature and the last problem type is an Overlapped Solar Systems problem, which we describe later: Uniform Random Problems : These problems are random constraint graph topologies with density p1 = {0.2, 0.7}. Each variable has 10 values in its domain. The constraint costs were selected uniformly between 1 and 100. Graph Coloring Problems: These problems are random constraint graph topologies in which each variable has three values (i.e., colors), and all constraints are not-equal cost functions, where an equal assignment of neighbors in the graph incurs a random cost between 10 and 100 and non-equal value assignments incur zero cost. We set the density p1 = 0.05 similar to Zhang et al. (2005) and Farinelli et al. (2008). Scale-free Network Problems: These problems are generated using the Barabasi Albert model (Barabási & Albert, 1999). An initial set of 10 agents was randomly selected and connected. Additional agents were sequentially added and connected to 3 other agents with a probability proportional to the number of edges that the existing agents already had. The constraint costs were selected uniformly between 1 and 100. Each variable has 10 values in its domain. Similar problems were previously used to evaluate DCOP algorithms by Kiekintveld, Yin, Kumar, and Tambe (2010). In addition to the problem types presented above, we also explored Overlapped Solar Systems problems. |
| Dataset Splits | No | The paper mentions generating random problem instances for evaluation but does not specify train/test/validation splits typically used for model training or evaluation. The experiments involve running algorithms on these generated instances. |
| Hardware Specification | No | The paper states: "Agents in our asynchronous simulator were implemented using Java threads." It does not provide specific hardware details like CPU, GPU, or memory used for running the experiments. |
| Software Dependencies | No | The paper states: "Agents in our asynchronous simulator were implemented using Java threads." It does not provide specific version numbers for Java or any other software libraries or dependencies used. |
| Experiment Setup | Yes | In each experiment, we randomly generated 100 different problem instances with 50 agents and we report the average over these instances. To demonstrate the convergence of the algorithms, we present the sum of costs of the constraints involved in the assignment that would have been selected by each algorithm every 100 NCLOs. We performed t-tests to evaluate the statistical significance of differences between all presented results. In our simulator, message delays were simulated by passing all messages sent by agents to an abstract mailing agent. This abstract agent decides when to deliver the messages to their target agents, according to the selected pattern. The delay is selected in terms of the number of NCLO. Then, each agent has the opportunity to perform logic operations according to the algorithm instructions. In our implementation, each atomic logic operation was an evaluation of the cost of a combination of two value assignments (i.e., a constraint check). In all the experiments we performed, we used three types of communication scenarios: (1) Perfect communication; (2) Message latency selected from a uniform distribution tde U(0, UB) NCLOs, where UB is a parameter denoting the maximum latency; and (3) Message loss determined by p U(0, 1) such that a message is not delivered if p < ple, where ple is a parameter denoting the probability for message loss. Using the model described in Section 4.1, for each experimental scenario, an instance of a CCG was initiated, where tde and ple remain similar for all edges in the graph. The magnitude of communication degradation was monitored through the parameters UB and ple. We evaluated our algorithms on four different problem types. The first three problem types are commonly used in the DCOP literature and the last problem type is an Overlapped Solar Systems problem, which we describe later: Uniform Random Problems : These problems are random constraint graph topologies with density p1 = {0.2, 0.7}. Each variable has 10 values in its domain. The constraint costs were selected uniformly between 1 and 100. Graph Coloring Problems: These problems are random constraint graph topologies in which each variable has three values (i.e., colors), and all constraints are not-equal cost functions, where an equal assignment of neighbors in the graph incurs a random cost between 10 and 100 and non-equal value assignments incur zero cost. We set the density p1 = 0.05 similar to Zhang et al. (2005) and Farinelli et al. (2008). Scale-free Network Problems: These problems are generated using the Barabasi Albert model (Barabási & Albert, 1999). An initial set of 10 agents was randomly selected and connected. Additional agents were sequentially added and connected to 3 other agents with a probability proportional to the number of edges that the existing agents already had. The constraint costs were selected uniformly between 1 and 100. Each variable has 10 values in its domain. Similar problems were previously used to evaluate DCOP algorithms by Kiekintveld, Yin, Kumar, and Tambe (2010). In addition to the problem types presented above, we also explored Overlapped Solar Systems problems. Overlapped solar systems is a realistic problem, inspired by the Constant Speed Propagation Delay Model, implemented in the ns-3 simulator (Mayuga-Marcillo et al., 2018; Amewuda et al., 2018). One characteristic that differentiates this problem in comparison to the three commonly used problems described above is an additional attribute of geographical locations of agents. The geographical locations allow us to model a dependency between the communication quality and the Euclidean distance between two agents. Therefore, instead of setting the tde and ple to random values in the communication scenarios, we set them differently for this problem. Specifically, the tde is drawn from a Poisson distribution d Pois(Γ distanceij), where Γ is a constant and distanceij determine the latency magnitude. This is also in contrast to the constant speed propagation delay model implemented in ns-3, where the delays that were calculated as a function of the distance between the geographic locations of the nodes were fixed and never changes (Mayuga-Marcillo et al., 2018; Amewuda et al., 2018). Regarding message loss, we define the probability ple that a message sent on edge e between agents Ai and Aj is delivered as follows: ple = distanceij max Distanceij , where max Distanceij determines the distance of the furthest agents from Ai or Aj. The formation of connections between the agents in overlapped solar systems problems is location dependent. Five agents are randomly selected to be the centers of the solar systems and they are connected. Each of these agents Ac i is assigned two coordinates that are drawn from a continuous uniform distribution: xc i U(0, 1) and yc i U(0, 1). All other agents (i.e., stars in the solar systems) are randomly assigned to one of the solar systems. The index c represents the solar system in which the agent is assigned to, and it is equal to the index of the center agent of the solar system (i.e., if Ac i is the center of a solar system, then i = c). The coordinates for an assigned agent (Ac j where j = c) are drawn from a Normal distribution as follows: xc j N(µ = xc i, σ = 0.05) and yc j N(µ = yc i , σ = 0.05) based on the location of the center of the solar system that it was attached to. The probability that two arbitrary agents Ai and Aj will be neighbors is defined by pij = (1 distanceij max Distancei )β, where distanceij is the Euclidean distance between agents Ai and Aj, max Distancei is the Euclidean distance between agent Ai to the farthest agent, and β expresses the changes in the probability that both agents will be neighbors as a function of their distance (in our experiments we used β = 3). For each pair of agents, a random probability pr [0, 1] was generated, and two agents are considered as neighbors if pr < pij. The constraint costs were selected uniformly between 1 and 100. |