A discrete and continuous study of the MAX-CHAIN-FORMATION problem

Link:
Autor/in:
Erscheinungsjahr:
2022
Medientyp:
Text
Schlagworte:
  • Chain formation
  • Continuous time
  • Max-chain formation
  • Mobile robots
  • Runtime
Beschreibung:
  • We introduce and study the MAX-CHAIN-FORMATION problem, where n robots are ordered along a winding chain and must form a connected, straight line of maximal length connecting its two endpoints. We propose and analyze strategies in a discrete and a continuous time model. In the discrete case, we give a complete analysis if the positions of all robots are initially collinear, showing that the worst-case time to reach an ε-approximation is upper bounded by O(n2⋅log⁡(n/ε)) and lower bounded by Ω(n2⋅log⁡(1/ε)). In the non-collinear case, we identify a family of instances whose runtime is unbounded. The picture in the continuous case is different: we propose a strategy with an optimal runtime of Θ(n). Avoiding an unbounded runtime similar to the discrete case relies crucially on a counter-intuitive aspect: slowing down the endpoints while all other robots move at full speed.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/403c13b0-cd07-4a8a-bef6-51639728e55d