LIPIcs.SoCG.2018.74.pdf
- Filesize: 6.55 MB
- 6 pages
Document
Coordinated Motion Planning: The Video (Multimedia Exposition)
Authors
-
Part of:
Volume:
34th International Symposium on Computational Geometry (SoCG 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-08
Cite AsGet BibTex
Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, and Christian Scheffer. Coordinated Motion Planning: The Video (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 74:1-74:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.74
https://doi.org/10.4230/LIPIcs.SoCG.2018.74
Abstract
We motivate, visualize and demonstrate recent work for minimizing the total execution time of a coordinated, parallel motion plan for a swarm of N robots in the absence of obstacles. Under relatively mild assumptions on the separability of robots, the algorithm achieves constant stretch: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d) steps; this implies constant-factor approximation for the optimization problem. Also mentioned is an NP-hardness result for finding an optimal schedule, even in the case in which robot positions are restricted to a regular grid. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) is required in the worst case; we establish an achievable stretch factor of O(N^{1/2}) even in this case. We also sketch geometric difficulties of computing optimal trajectories, even for just two unit disks.
Keywords
- Motion planning
- robot swarms
- complexity
- stretch
- approximation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Henk Meijer, and Christian Scheffer. Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. In Csaba Tóth and Bettina Speckmann, editors, 34th International Symposium on Computational Geometry (SoCG 2018, these proceedings), volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1-29:17, 2018. Full version at https://arxiv.org/abs/1801.01689. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2018.29.
-
Jacob T. Schwartz and Micha Sharir. On the piano movers' problem: III. Coordinating the motion of several independent bodies: the special case of circular bodies moving amidst polygonal barriers. Int. J. Robotics Research, 2(3):46-75, 1983.
