Well-Connected Set and Its Application to Multi-Robot Path Planning
<|reference_start|>Well-Connected Set and Its Application to Multi-Robot Path Planning: Parking lots and autonomous warehouses for accommodating many vehicles/robots adopt designs in which the underlying graphs are \emph{well-connected} to simplify planning and reduce congestion. In this study, we formulate and delve into the \emph{largest well-connected set} (LWCS) problem and explore its applications in layout design for multi-robot path planning. Roughly speaking, a well-connected set over a connected graph is a set of vertices such that there is a path on the graph connecting any pair of vertices in the set without passing through any additional vertices of the set. Identifying an LWCS has many potential high-utility applications, e.g., for determining parking garage layout and capacity, as prioritized planning can be shown to be complete when start/goal configurations belong to an LWCS. In this work, we establish that computing an LWCS is NP-complete. We further develop optimal and near-optimal LWCS algorithms, with the near-optimal algorithm targeting large maps. A complete prioritized planning method is given for planning paths for multiple robots residing on an LWCS.<|reference_end|>
@article{guo2024well-connected,
    title={Well-Connected Set and Its Application to Multi-Robot Path Planning},
    author={Teng Guo, Jingjin Yu},
    journal={arXiv preprint arXiv:2402.11766},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11766},
    primaryClass={cs.RO}
}