Large-scale, Dynamic and Distributed Coalition Formation with Spatial and Temporal Constraints
This addresses a multi-agent task allocation problem for applications like emergency response, though it appears incremental as it builds on existing CFSTP methods.
The paper tackles the Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) by proposing a compact formulation and D-CTS, a distributed algorithm, which in tests with up to 150 agents and 3000 tasks completes 3.79% more tasks and is one order of magnitude more efficient in communication and time compared to a state-of-the-art distributed algorithm.
The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task allocation problem in which few agents have to perform many tasks, each with its deadline and workload. To maximize the number of completed tasks, the agents need to cooperate by forming, disbanding and reforming coalitions. The original mathematical programming formulation of the CFSTP is difficult to implement, since it is lengthy and based on the problematic Big-M method. In this paper, we propose a compact and easy-to-implement formulation. Moreover, we design D-CTS, a distributed version of the state-of-the-art CFSTP algorithm. Using public London Fire Brigade records, we create a dataset with $347588$ tasks and a test framework that simulates the mobilization of firefighters in dynamic environments. In problems with up to $150$ agents and $3000$ tasks, compared to DSA-SDP, a state-of-the-art distributed algorithm, D-CTS completes $3.79\% \pm [42.22\%, 1.96\%]$ more tasks, and is one order of magnitude more efficient in terms of communication overhead and time complexity. D-CTS sets the first large-scale, dynamic and distributed CFSTP benchmark.