Balanced Collaborative Exploration via Distributed Topological Graph Voronoi Partition

Abstract--This work addresses the collaborative multi-robot autonomous online exploration problem, particularly focusing on distributed exploration planning for dynamically balanced exploration area partition and task allocation among a team of mobile robots operating in obstacle-dense non-convex environments. We present a novel topological map structure that simultaneously characterizes both spatial connectivity and global exploration completeness of the environment. The topological map is updated incrementally to utilize known spatial information for updating reachable spaces, while exploration targets are planned in a receding horizon fashion under global coverage guidance. A distributed weighted topological graph V oronoi algorithm is introduced implementing balanced graph space partitions of the fused topological maps. Theoretical guarantees are provided for distributed consensus convergence and equitable graph space partitions with constant bounds. A local planner optimizes the visitation sequence of exploration targets within the balanced partitioned graph space to minimize travel distance, while generating safe, smooth, and dynamically feasible motion trajectories. Comprehensive benchmarking against state-of-the-art methods demonstrates significant improvements in exploration efficiency, completeness, and workload balance across the robot team. Autonomous exploration via multi-robot systems, which leverages robotic systems to map unknown environments cooperatively, is a critical capability for applications such as inspection, search-and-rescue, and disaster response [1], [2], [3]. Multi-robot systems offer substantial advantages, including accelerated exploration and enhanced fault tolerance. Despite their potential, developing robust and efficient multi-robot exploration systems remains challenging due to suboptimal task allocation, and inefficient coordination strategies. Previous collaborative exploration approaches often rely on centralized controllers [4], [5], which are impractical in real-world scenarios with unreliable or range-limited connectivity. Decentralized coordination methods have been proposed to mitigate these issues [6], [7], [8] yet many multi-robot exploration approaches still suffer from critical inefficiencies.