Idle robots stop being treated as obstacles: FOCBS hands yielding to min-cost flow and cuts lab fleet travel by 40.8%
Synopsis
In warehouses and laboratories, robots without tasks are often treated as static obstacles or all sent to parking spots, blocking passages or adding needless travel. FOCBS searches only over assigned-robot paths and uses min-cost flow to choose where unassigned robots yield and stop; when the chosen paths leave them no route, a minimum cut turns the blockers into constraints on assigned robots. On finite graphs it is proved to terminate and globally minimize assigned-robot sum of service time for feasible instances; in a three-robot chemistry laboratory, fleet travel fell 40.8% against a parking-based coordination baseline.
Interpretation
Robots without tasks no longer need predefined parking locations; the planner decides only when they yield and where they stop. Earlier treatments either fixed them as static obstacles, which could block narrow passages or force long detours, or assigned each robot a parking location, causing unnecessary travel and occupying workspace. On a three-robot chemistry laboratory platform, both methods completed the same four task sequences, 40 batches and 65 navigation tasks between workstations, and FOCBS reduced fleet travel by 40.8% relative to the parking-based coordination baseline, with savings in every sequence.
The search runs conflict-based search only over assigned robots, while a single min-cost flow assigns terminal vertices to unassigned robots. Placing both robot types in one constraint tree lets conflicts among unassigned robots add high-level search overhead, becoming a bottleneck as their number grows. Raising the unassigned-robot share from 0.05 to 0.95 on four standard maps, CBS-UA reached at most 43.9% overall success on any map, while FOCBS reached 94.1% to 100% across the four maps.
When the selected assigned-robot paths leave unassigned robots no collision-free route, a minimum cut identifies which reservations must be released and turns them into branching constraints on assigned robots. Discarding those paths would discard every feasible plan beneath them, and the failure alone does not say which path to revise. Among recorded instances whose first oracle call was infeasible, FOCBS recovered a solution within 60 s in 203 of 242 room instances and 80 of 482 warehouse instances; on one room-32-32-4 instance, delaying a single assigned path by one step sufficed, with FOCBS solving it in 0.39 s while the pruning variant failed within 60 s.
Perspective
The demonstrated scope is standard map benchmarks, a ROS 2/Gazebo warehouse simulation with 18 mobile robots and 40 workstations, and a three-robot chemistry laboratory platform; the laboratory evaluation covers mobile-base navigation only, excluding chemical experiments and reagent handling by robotic arms.
Unassigned-robot movement is minimized only conditional on the selected assigned-robot paths, with no global lexicographic optimality guarantee; termination is not guaranteed for infeasible instances; robustness to localization errors and motion uncertainty is outside the study.
