Relay-Based Coordination for Energy-Efficient Multi-Robot Pickup and Delivery

Researchers Alkesh K. Srivastava, Jared Michael Levin, and Philip Dames from Temple University have introduced VCST-RCP (Voronoi-Constrained Steiner Tree Relay Coordination Planning), a novel framework for coordinating homogeneous robot fleets delivering packages from a single depot to multiple destinations. Unlike traditional methods that send each robot on a direct source-to-destination route, VCST-RCP treats inter-robot relays as a fundamental design primitive, allowing robots to hand off packages to one another at designated exchange points. The framework operates in two stages: first, it constructs a sparse relay backbone using Voronoi-derived exchange interfaces combined with Steiner tree optimization to determine optimal relay locations; second, it synthesizes robot-level pickup, relay, and delivery schedules while respecting capacity and service-time constraints.

Extensive experiments across multiple scales demonstrate that VCST-RCP reduces total fleet travel distance by an average of 31%, with reductions reaching nearly 50% in some scenarios. These gains are statistically significant (p < 10^-3) compared to Hungarian assignment and significantly outperform OR-Tools CVRP. The efficiency translates into over 50% higher delivery efficiency (packages per kilometer), directly improving energy utilization. An ablation study revealed that optimizing relay placement yields substantially larger improvements than adapting spatial partitioning alone, establishing relay design as the dominant factor governing system performance. The results suggest that relay-based coordination provides a scalable and effective framework for energy-aware multi-robot delivery in real-world logistics settings.