Cycle Clustering: An Algorithm for Multi-Depot Multi-Agent Collaborative Coverage in Structured Road Network
Ruochen Li, Junkai Jiang, Jiongqi Wang, Shaobing Xu, Jianqiang Wang
Abstract
Multi-depot multi-agent collaborative coverage is a representative problem in swarm intelligence, with broad applications in real-world scenarios. In this problem, multiple agents are initially located at different depots, which differs from the traditional problem setting, and are required to collaboratively cover a given region represented by a structured road network. The objective is to minimize the longest individual route among all agents. This problem is closely related to the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-Chinese Postman Problem (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-CPP), but is more complex due to the different depot constraint. This paper proposes a novel centralized algorithm, Cycle Clustering (CC), to solve this problem efficiently. The proposed method first transforms the original graph into an Eulerian graph, and then partitions the Eulerian graph into multiple small cycles, which are subsequently clustered and assigned to different agents. This design significantly reduces unnecessary route overhead. The algorithm's time complexity and completeness are theoretically analyzed. Experimental results demonstrate that the proposed algorithm performs better than existing methods, reducing the average gap to the theoretical lower bound from 29.10% to 10.29%.
BibTeX
@inproceedings{ral2026_cycleclusteringa,
title = {Cycle Clustering: An Algorithm for Multi-Depot Multi-Agent Collaborative Coverage in Structured Road Network},
author = {Ruochen Li and Junkai Jiang and Jiongqi Wang and Shaobing Xu and Jianqiang Wang},
booktitle = {RA-L 2026},
year = {2026}
}