Abstract
Traditional multi-robot motion planning (MMP) focuses on computing trajectories for multiple robots acting in an environment, such that the robots do not collide when the trajectories are taken simultaneously. In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. In this work, we propose a notion of explanation for a plan of MMP, based on visualization of the plan as a short sequence of images representing time segments, where in each time segment the trajectories of the agents are disjoint, clearly illustrating the safety of the plan. We show that standard notions of optimality (e.g., makespan) may create conflict with short explanations. Thus, we propose meta-algorithms, namely multi-agent plan segmenting-X (MAPS-X) and its lazy variant, that can be plugged on existing centralized sampling-based tree planners X to produce plans with good explanations using a desirable number of images. We demonstrate the efficacy of this explanation-planning scheme and extensively evaluate the performance of MAPS-X and its lazy variant in various environments and agent dynamics.
Introduction
Multi-robot motion planning (MMP) is a computationally hard problem, but for human supervisors, the primary hurdle is often verification. In complex environments like automated warehouses or air traffic control, a plan consisting of multiple overlapping trajectories can resemble a "bowl of spaghetti." For a human to be certain that no collisions occur at any point in time, they must mentally simulate the entire 4D (3D space + time) execution. This complexity often leads to the rejection of automated plans in favor of simpler, manually verifiable ones.
This research addresses the gap between algorithmic optimality and human understandability by introducing a framework for explainable MMP based on visual decomposition.
Methodology: Plan Segmentation
The authors define an "explanation" as a sequence of static images representing consecutive time intervals. The key constraint is that within each interval, the trajectories of all robots must be disjoint—their paths must not occupy the same physical space at any point during that window. This transforms a difficult temporal verification task into a simple 2D pattern recognition task that human vision is naturally optimized for.
To generate these plans, the paper introduces MAPS-X, a meta-algorithm that can be wrapped around existing sampling-based planners (like RRT). MAPS-X treats the "segment count" as a primary cost, ensuring that the final plan fits within a user-defined explainability budget $r$.
Key Insights: The Optimality-Explainability Trade-off
A critical finding is the conflict between standard optimality metrics, such as makespan, and explainability. The "fastest" plan often requires robots to move very close to one another simultaneously, which is hard to explain with few segments. MAPS-X may intentionally select a "sub-optimal" path—for instance, having one robot wait while another passes—to ensure the plan remains easily verifiable. This leverages the fact that humans are evolutionarily wired to detect line intersections quickly in the primary visual cortex.
Experimental Evaluation and Results
The framework was evaluated using the Open Motion Planning Library (OMPL) across various scenarios, including open spaces, congested areas, and narrow corridors.
In a three-robot hallway scenario, standard RRT produced a plan that was visually confusing. In contrast, MAPS-X produced a "cleaner" plan requiring only 3-4 images for full safety verification. While MAPS-X incurs a higher computational cost than standard planners (e.g., 28s vs 4s in the hallway task), it significantly outperforms the "Lazy" variant in complex environments and maintains high success rates even under strict explainability constraints ($r=1$ or $r=2$).
Conclusion and Future Directions
MAPS-X successfully bridges the gap between complex automated planning and human trust. By prioritizing visual disjointness, it allows supervisors to verify safety-critical plans rapidly. Future work will focus on scaling the system to larger robot swarms and extending the explainability framework to decentralized planning environments where collective explanations are required.
Summary updated