Congestion-Aware Efficient Multi-Robot Task Planning via Invocation-Pruning Task Evaluation

In multi-robot collaborative task scenarios, congestion in bottleneck areas and the resulting execution delays can invalidate the solutions of task planning optimization, leading to potential instabilities and safety risks. This letter presents a congestion-aware invocation-pruning planning (CAIPP) method, which accurately quantifies the impact of congestion to ensure the effectiveness of task planning. For high-level task allocation, the congestion-aware method addresses the influence of inter-robot trajectories on task utility evaluation by invoking spatiotemporal path planning to reduce evaluation inaccuracy. Considering the computational burden of path planning, a conflict-free validation strategy and a pruning evaluation strategy are designed to schedule invocations for path planning, thereby reducing unnecessary computation. A channel graph is adopted to construct a lightweight representation of the accessible space, and building on this, spatial and spatiotemporal path planning methods are designed for the initial and corrected estimation of task utility, respectively. Simulation and experimental results verify that the presented method achieves efficient task planning and congestion avoidance, and outperforms the benchmark methods in terms of solution quality and planning efficiency.