2 Search Results for "Lin, Lillian"

Document
DOI: 10.4230/LIPIcs.ESA.2025.28
Sliding Squares in Parallel

Authors: Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given n square-shaped modules in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work has aimed at minimizing the total number of moves, resulting in fully sequential schedules that can perform reconfiguration in 𝒪(n²) moves, or 𝒪(nP) for arrangements of bounding box perimeter size P. We provide first results in the sliding square model that exploit parallel motion, performing reconfiguration in worst-case optimal makespan of 𝒪(P). We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan 1 is NP-complete in the unlabeled case. In the labeled variant, we note that deciding the same for makespan 2 is NP-complete, while makespan 1 is straightforward.
Cite as

Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner. Sliding Squares in Parallel. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2025.28,
  author =	{A. Akitaya, Hugo and Fekete, S\'{a}ndor P. and Kramer, Peter and Molaei, Saba and Rieck, Christian and Stock, Frederick and Wallner, Tobias},
  title =	{{Sliding Squares in Parallel}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.28},
  URN =		{urn:nbn:de:0030-drops-244961},
  doi =		{10.4230/LIPIcs.ESA.2025.28},
  annote =	{Keywords: Sliding squares, parallel motion, reconfigurability, motion planning, multi-agent path finding, makespan, swarm robotics, computational geometry}
}
Document
Multimedia Exposition
DOI: 10.4230/LIPIcs.SoCG.2018.74
Coordinated Motion Planning: The Video (Multimedia Exposition)

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

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

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

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)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2018.74,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Konitzny, Matthias and Lin, Lillian and Scheffer, Christian},
  title =	{{Coordinated Motion Planning: The Video}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{74:1--74:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.74},
  URN =		{urn:nbn:de:0030-drops-87872},
  doi =		{10.4230/LIPIcs.SoCG.2018.74},
  annote =	{Keywords: Motion planning, robot swarms, complexity, stretch, approximation}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018

  • Refine by Author
  • 2 Fekete, Sándor P.
  • 1 A. Akitaya, Hugo
  • 1 Becker, Aaron T.
  • 1 Keldenich, Phillip
  • 1 Konitzny, Matthias
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Computing methodologies → Motion path planning
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Motion planning
  • 1 Sliding squares
  • 1 approximation
  • 1 complexity
  • 1 computational geometry
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact