Anytime and Efficient Coalition Formation with Spatial and Temporal Constraints

Thus, the agents have to form coalitions in order to maximise the number of completed tasks. The state-of-the-art CFSTP solver, the Coalition Formation with Look-Ahead (CFLA) algorithm, has two main limitations.

First, its time complexity is exponential with the number of agents. Second, as we show, 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. In this work, we study its design and define an extension, called Coalition Formation with Improved Look-Ahead ( ), which achieves better performance.