Proactive Dynamic Distributed Constraint Optimization Problems
Authors: Khoi D. Hoang, Ferdinando Fioretto, Ping Hou, William Yeoh, Makoto Yokoo, Roie Zivan
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we empirically evaluate our PD-DCOP algorithms. Aside from evaluating the PD-DCOP algorithms in an offline manner, we also evaluate them in an online setting which simulates the environment of many real-life applications. In the online setting, we consider both how long it takes for the algorithms to solve the problem at a given time step and the time they have to adapt the solution that they have just found. As PD-DCOPs can be solved in an offline or an online manner, we report the experimental results for both settings. |
| Researcher Affiliation | Collaboration | Khoi D. Hoang EMAIL Department of Computer Science and Engineering Washington University in St. Louis Saint Louis, MO 63130, USA Ferdinando Fioretto EMAIL Department of Electrical Engineering and Computer Science Syracuse University Syracuse, NY 13244, USA Ping Hou EMAIL Aurora Innovation Pittsburgh, PA 15222, USA William Yeoh EMAIL Department of Computer Science and Engineering Washington University in St. Louis Saint Louis, MO 63130, USA Makoto Yokoo EMAIL Department of Informatics Kyushu University Fukuoka, 819-0395, Japan Roie Zivan EMAIL Department of Industrial Engineering and Management Ben-Gurion University of the Negev Beer Sheva, 849900, Israel |
| Pseudocode | Yes | Algorithm 1: Local Search() Procedure Calc Gain() Procedure When Receive VALUE( v0 s , v1 s , . . . , v h s ) Procedure When Receive GAIN( ˆu0 s, ˆu1 s, . . . , ˆu h s ) Function Calc Utils( v0 i , v1 i , . . . , v h i , x h+1 i ) Function Calc Cumulative Util( v0 i , v1 i , . . . , v h i , x h+1 i ) |
| Open Source Code | Yes | Our experiments are performed on a 2.1GHz machine with 16GB of RAM using JADE framework (Bellifemine et al., 2005), and the results report the average of 30 independent runs, each with a timeout of 30 minutes.10 10. https://github.com/khoihd/pd-dcop. |
| Open Datasets | No | In this experiment, we use random networks with constraint density p1 = 0.5 to evaluate the PD-DCOP algorithms on random instances that do not have a too dense or too sparse topology. Next, we evaluate our PD-DCOP algorithms on dynamic distributed meeting scheduling problems, which are a real world application with a specific network topology. We generate the underlying topology randomly with p1 = 0.5 and use the PEAV formulation (Maheswaran et al., 2004b). In this experiment, we evaluate our PD-DCOP algorithms on the Distributed Radar Coordination and Scheduling Problem (DRCSP), our motivating application described in Section 3. We use grid networks to represent the DRCSP where sensors are arranged in a rectangular grid. |
| Dataset Splits | No | The paper describes generating synthetic data (random networks, grid networks) and problems based on formulations (PEAV for meeting scheduling). It mentions performing "average of 30 independent runs" but does not specify any train/test/validation splits for a dataset, as it's not using a pre-existing dataset in the traditional sense for evaluation. The experimental setup details refer to problem parameters and how instances are generated, rather than how a dataset is partitioned. |
| Hardware Specification | Yes | Our experiments are performed on a 2.1GHz machine with 16GB of RAM using JADE framework (Bellifemine et al., 2005), and the results report the average of 30 independent runs, each with a timeout of 30 minutes. |
| Software Dependencies | No | Our experiments are performed on a 2.1GHz machine with 16GB of RAM using JADE framework (Bellifemine et al., 2005), and the results report the average of 30 independent runs, each with a timeout of 30 minutes. |
| Experiment Setup | Yes | We use the following default configuration: Number of agents and decision variables |A| = |X| = 10; number of random variables |Y| = 0.2 |X| = 0.2 10 = 2; domain size |Dx| = |Ωy| = 3; horizon h = 4; and switching cost c = 50.11 The utility values are sampled from the uniform distribution on [0, 10]. The initial probability distributions and the transition functions of random variables are randomly generated and normalized. |