Author name cluster

Luca Capezzuto

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

EUMAS Conference 2021 Conference Paper

Large-Scale, Dynamic and Distributed Coalition Formation with Spatial and Temporal Constraints

Luca Capezzuto
Danesh Tarapore
Sarvapali D. Ramchurn

Abstract 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.

Details

EUMAS Conference 2020 Conference Paper

Anytime and Efficient Coalition Formation with Spatial and Temporal Constraints

Luca Capezzuto
Danesh Tarapore
Sarvapali D. Ramchurn

Abstract The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task scheduling problem where the tasks are spatially distributed, with deadlines and workloads, and the number of agents is typically much smaller than the number of tasks. 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 ( \(\text {CFLA}2\) ), which achieves better performance. Since we cannot eliminate the limitations of CFLA in \(\text {CFLA}2\), we also develop a novel algorithm to solve the CFSTP, the first to be simultaneously anytime, efficient and with convergence guarantee, called Cluster-based Task Scheduling (CTS). In tests where the look-ahead technique is highly effective, CTS completes up to 30% (resp. 10%) more tasks than CFLA (resp. \(\text {CFLA}2\) ) while being up to four orders of magnitude faster. Our results affirm CTS as the new state-of-the-art algorithm to solve the CFSTP.

Details DOI