Relay-Based Coordination for Energy-Efficient Multi-Robot Pickup and Delivery
arXiv:2509.14127v3 Announce Type: replace Abstract: We consider the problem of delivering multiple packages from a single depot to distinct goal locations using a homogeneous fleet of robots with limited carrying capacity. We propose VCST-RCP, a Voronoi-Constrained Steiner Tree Relay Coordination Planning framework that explicitly treats inter-robot relays as a design primitive. The approach operates in two stages: (i) constructing a sparse relay backbone by combining Voronoi-derived exchange interfaces with Steiner tree optimization, and (ii) synthesizing robot-level pickup, relay, and delivery schedules under capacity and service-time constraints. Unlike traditional methods that rely on direct source-to-destination transport, our framework organizes package flow through a shared relay network, reducing redundant long-haul motion. Extensive experiments across multiple scales show that VCST-RCP reduces total fleet travel distance by an average of 31% (up to nearly 50%) compared to Hung

