conference paper published Jannik Castenow author 38705 Peter Kling author Till Knollmann author 392410000-0003-2014-4696 Friedhelm Meyer auf der Heide author 15523 Stéphane Devismes editor Neeraj Mittal editor 63 department Most existing robot formation problems seek a target formation of a certain minimal and, thus, efficient structure. Examples include the Gathering and the Chain-Formation problem. In this work, we study formation problems that try to reach a maximal structure, supporting for example an efficient coverage in exploration scenarios. A recent example is the NASA Shapeshifter project, which describes how the robots form a relay chain along which gathered data from extraterrestrial cave explorations may be sent to a home base. As a first step towards understanding such maximization tasks, we introduce and study the Max-Chain-Formation problem, where $n$ robots are ordered along a winding, potentially self-intersecting chain and must form a connected, straight line of maximal length connecting its two endpoints. We propose and analyze strategies in a discrete and in a continuous time model. In the discrete case, we give a complete analysis if all robots are initially collinear, showing that the worst-case time to reach an $\varepsilon$-approximation is upper bounded by $\mathcal{O}(n^2 \cdot \log (n/\varepsilon))$ and lower bounded by $\Omega(n^2 \cdot~\log (1/\varepsilon))$. If one endpoint of the chain remains stationary, this result can be extended to the non-collinear case. If both endpoints move, we identify a family of instances whose runtime is unbounded. For the continuous model, we give a strategy with an optimal runtime bound of $\Theta(n)$. Avoiding an unbounded runtime similar to the discrete case relies crucially on a counter-intuitive aspect of the strategy: slowing down the endpoints while all other robots move at full speed. Surprisingly, we can show that a similar trick does not work in the discrete model. Springer2020 eng 978-3-030-64347-8 2010.02043 10.1007/978-3-030-64348-5_6 1251465-80 Castenow, Jannik, et al. “A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up.” <i>Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings</i>, edited by Stéphane Devismes and Neeraj Mittal, vol. 12514, Springer, 2020, pp. 65–80, doi:<a href="https://doi.org/10.1007/978-3-030-64348-5_6">10.1007/978-3-030-64348-5_6</a>. @inproceedings{Castenow_Kling_Knollmann_Meyer auf der Heide_2020, series={Lecture Notes in Computer Science (LNCS)}, title={A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up}, volume={12514}, DOI={<a href="https://doi.org/10.1007/978-3-030-64348-5_6">10.1007/978-3-030-64348-5_6</a>}, booktitle={Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings}, publisher={Springer}, author={Castenow, Jannik and Kling, Peter and Knollmann, Till and Meyer auf der Heide, Friedhelm}, editor={Devismes , Stéphane and Mittal, Neeraj Editors}, year={2020}, pages={65–80}, collection={Lecture Notes in Computer Science (LNCS)} } J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide, in: S. Devismes , N. Mittal (Eds.), Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings, Springer, 2020, pp. 65–80. Castenow, J., Kling, P., Knollmann, T., &#38; Meyer auf der Heide, F. (2020). A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up. In S. Devismes &#38; N. Mittal (Eds.), <i>Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings</i> (Vol. 12514, pp. 65–80). Springer. <a href="https://doi.org/10.1007/978-3-030-64348-5_6">https://doi.org/10.1007/978-3-030-64348-5_6</a> Castenow J, Kling P, Knollmann T, Meyer auf der Heide F. A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up. In: Devismes S, Mittal N, eds. <i>Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings</i>. Vol 12514. Lecture Notes in Computer Science (LNCS). Springer; 2020:65-80. doi:<a href="https://doi.org/10.1007/978-3-030-64348-5_6">10.1007/978-3-030-64348-5_6</a> Castenow, Jannik, Peter Kling, Till Knollmann, and Friedhelm Meyer auf der Heide. “A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up.” In <i>Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings</i>, edited by Stéphane Devismes and Neeraj Mittal, 12514:65–80. Lecture Notes in Computer Science (LNCS). Springer, 2020. <a href="https://doi.org/10.1007/978-3-030-64348-5_6">https://doi.org/10.1007/978-3-030-64348-5_6</a>. J. Castenow, P. Kling, T. Knollmann, and F. Meyer auf der Heide, “A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up,” in <i>Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings</i>, 2020, vol. 12514, pp. 65–80. 198992020-10-06T07:27:10Z2022-01-06T06:54:14Z