(Submitted on 30 Mar 2020)

Abstract: The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP)
is a multi-agent task allocation problem where the agents are cooperative and
few, the tasks are many, spatially distributed, with deadlines and workloads,
and the objective is to find a schedule that maximises the number of completed
tasks. The current state-of-the-art CFSTP solver, the Coalition Formation with
Look-Ahead (CFLA) algorithm, has two main limitations. First, its time
complexity is quadratic with the number of tasks and exponential with the
number of agents, which makes it not efficient. Second, its look-ahead
technique is not effective in real-world scenarios, such as open multi-agent
systems, where new tasks can appear at any time. Motivated by this, we propose
an extension of CFLA, which we call Coalition Formation with Improved
Look-Ahead (CFLA+). Since CFLA+ inherits the limitations of CFLA, we also
develop a novel algorithm to solve the CFSTP, the first to be both anytime and
efficient, which we call Clustered-based Coalition Formation (CCF). We
empirically show that, in settings where the look-ahead technique is highly
effective, CCF completes up to 20% (resp. 10%) more tasks than CFLA (resp.
CFLA+) while being up to four orders of magnitude faster. Our results affirm
CCF as the new state-of-the-art CFSTP solver.