Multi-Agent Path Finding with Kinematic Constraints
Proceedings of the International Conference on Automated Planning and Scheduling · 30.03.2016 · 26 · 477-485
DOI: 10.1609/icaps.v26i1.13796 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 30.03.2016. Verfasst von Wolfgang Hoenig und 6 weiteren Autor:innen. Die Arbeit wurde bisher 78-mal zitiert (Crossref).
Abstract (Originalsprache)
Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as finite maximum velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST, a novel approach that makes use of a simple temporal network to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, takes their maximum translational and rotational velocities into account, provides a guaranteed safety distance between them, and exploits slack to absorb imperfect plan executions and avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.
Zitieren
APA
Hoenig, W., Kumar, T. K., Cohen, L., Ma, H., Xu, H., Ayanian, N., & Koenig, S. (2016). Multi-Agent Path Finding with Kinematic Constraints. Proceedings of the International Conference on Automated Planning and Scheduling, 26, 477-485. https://doi.org/10.1609/icaps.v26i1.13796
Vancouver
Hoenig W, Kumar TK, Cohen L, Ma H, Xu H, Ayanian N, et al. Multi-Agent Path Finding with Kinematic Constraints. Proceedings of the International Conference on Automated Planning and Scheduling. 2016;26:477-485. doi:10.1609/icaps.v26i1.13796
BibTeX
@article{Hoenig2016,
author = {Hoenig, Wolfgang and Kumar, T. K. and Cohen, Liron and Ma, Hang and Xu, Hong and Ayanian, Nora and Koenig, Sven},
title = {Multi-Agent Path Finding with Kinematic Constraints},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2016},
volume = {26},
pages = {477--485},
doi = {10.1609/icaps.v26i1.13796}
}
EUVIMED