From Space-Time to Space-Order: Directly Planning a Temporal Planning Graph by Redefining CBS
<|reference_start|>From Space-Time to Space-Order: Directly Planning a Temporal Planning Graph by Redefining CBS: The majority of multi-agent path finding (MAPF) methods compute collision-free space-time paths which require agents to be at a specific location at a specific discretized timestep. However, executing these space-time paths directly on robotic systems is infeasible due to real-time execution differences (e.g. delays) which can lead to collisions. To combat this, current methods translate the space-time paths into a temporal plan graph (TPG) that only requires that agents observe the order in which they navigate through locations where their paths cross. However, planning space-time paths and then post-processing them into a TPG does not reduce the required agent-to-agent coordination, which is fixed once the space-time paths are computed. To that end, we propose a novel algorithm Space-Order CBS that can directly plan a TPG and explicitly minimize coordination. Our main theoretical insight is our novel perspective on viewing a TPG as a set of space-visitation order paths where agents visit locations in relative orders (e.g. 1st vs 2nd) as opposed to specific timesteps. We redefine unique conflicts and constraints for adapting CBS for space-order planning. We experimentally validate how Space-Order CBS can return TPGs which significantly reduce coordination, thus subsequently reducing the amount of agent-agent communication and leading to more robustness to delays during execution.<|reference_end|>
@article{wu2024from,
    title={From Space-Time to Space-Order: Directly Planning a Temporal Planning
  Graph by Redefining CBS},
    author={Yu Wu, Rishi Veerapaneni, Jiaoyang Li, Maxim Likhachev},
    journal={arXiv preprint arXiv:2404.15137},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.15137},
    primaryClass={cs.MA cs.RO}
}