Computing Convex Coverage Sets for Faster Multi-objective Coordination
Authors: Diederik Marijn Roijers, Shimon Whiteson, Frans A. Oliehoek
JAIR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We analyze the runtime and space complexities of these methods, prove their correctness, and compare them empirically against a naive baseline and an existing PCS method, both in terms of memory-usage and runtime. Our results show that, by focusing on the CCS, these methods achieve much better scalability in the number of agents than the current state of the art. (Abstract) ... 4.5 Empirical Evaluation ... 5.4 Empirical Evaluation ... 6.4 Empirical Evaluation |
| Researcher Affiliation | Academia | Diederik M. Roijers EMAIL Shimon Whiteson EMAIL Frans A. Oliehoek EMAIL Informatics Institute University of Amsterdam Amsterdam, The Netherlands |
| Pseudocode | Yes | Algorithm 1: elim VE(U, i) ... Algorithm 2: CPrune(U) ... Algorithm 3: PPrune(U) ... Algorithm 4: find Weight(u, U) ... Algorithm 5: CMOVE(U, prune1, prune2, prune3, q) ... Algorithm 6: elim(F, i, prune1, prune2) ... Algorithm 7: OLS(m, Solve Co G, ε) |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | To generate random MO-Co Gs, we employ a procedure that takes as input: n, the number of agents; d, the number of payoffdimensions; ρ the number of local payofffunctions; and |Ai|, the action space size of the agents, which is the same for all agents. (Section 4.5.1) ... To generate a Mining Day instance with v villages (agents), we randomly assign 2-5 workers to each village and connect it to 2-4 mines. (Section 4.5.2) The paper describes how problem instances were *generated* for experiments, not that they used an *open dataset* or made their generated datasets *publicly available*. |
| Dataset Splits | No | The paper describes generating multiple problem instances (e.g., 'averaged over 20 MO-Co Gs for each number of agents', 'averaged over 85 MO-Co Gs for each number of agents', 'averaged over 100 MO-Co Gs', 'We generated 30 Mining Day instances for increasing n and averaged the runtimes', 'Averaged over 25 instances per value of ε') rather than providing specific train/test/validation splits of a fixed dataset. |
| Hardware Specification | Yes | This experiment was run on a 2.4 GHz Intel Core i5 computer, with 4 GB memory. (Section 4.5.1) ... This and all remaining experiments described in this section were executed on a Xeon L5520 2.26 GHz computer with 24 GB memory. (Section 4.5.1) ... All experiments in this section were run on a 2.4 GHx Intel Core i5 computer, with 4 GB memory. (Section 5.4) |
| Software Dependencies | No | The paper does not provide specific software dependencies (e.g., library or solver names with version numbers) used for the experiments. |
| Experiment Setup | Yes | OLS also takes as input m, the MO-Co G to be solved, and ε, the maximal tolerable error in the result. (Section 5.1) ... Furthermore, the maximal relative increase in runtime as the number of agents increases is less for higher ε. Thus, an approximate version of TSLS is a highly attractive method for cases in which both memory and runtime are limited. (Section 6.4.1) ... At 65 agents, exact TSLS (ε = 0), had an average runtime of 106s, which is 51 times slower than VELS. However, for ε = 0.0001, the runtime was only 70s (33 times slower). For ε = 0.01 it is 11s (5.4 times slower), and for ε = 0.1 it is only 6s (2.9 times slower). (Section 6.4.1) |