Coordinated Motion Planning: The Video (Multimedia Exposition)

Becker, Aaron T.; Fekete, Sándor P.; Keldenich, Phillip; Konitzny, Matthias; Lin, Lillian; Scheffer, Christian

doi: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.

Cite As Get 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

Author Details

Aaron T. Becker

Sándor P. Fekete

Phillip Keldenich

Matthias Konitzny

Lillian Lin

Christian Scheffer

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.

Coordinated Motion Planning: The Video (Multimedia Exposition)

Authors Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, Christian Scheffer

File

Document Identifiers

Subject Classification

Keywords

Metrics

Abstract

Cite As Get BibTex

Author Details

References

Thanks for your feedback!

Could not send message