[{"date_updated":"2022-01-06T06:54:14Z","author":[{"id":"38705","full_name":"Castenow, Jannik","last_name":"Castenow","first_name":"Jannik"},{"first_name":"Peter","full_name":"Kling, Peter","last_name":"Kling"},{"first_name":"Till","orcid":"0000-0003-2014-4696","last_name":"Knollmann","full_name":"Knollmann, Till","id":"39241"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"}],"volume":12514,"doi":"10.1007/978-3-030-64348-5_6","publication_status":"published","publication_identifier":{"isbn":["978-3-030-64347-8"]},"citation":{"apa":"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>","short":"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.","mla":"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>.","bibtex":"@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)} }","ieee":"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.","chicago":"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>.","ama":"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>"},"page":"65-80","intvolume":"     12514","_id":"19899","series_title":"Lecture Notes in Computer Science (LNCS)","user_id":"38705","department":[{"_id":"63"}],"type":"conference","editor":[{"full_name":"Devismes , Stéphane ","last_name":"Devismes ","first_name":"Stéphane "},{"last_name":"Mittal","full_name":"Mittal, Neeraj ","first_name":"Neeraj "}],"status":"public","publisher":"Springer","date_created":"2020-10-06T07:27:10Z","title":"A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up","year":"2020","external_id":{"arxiv":["2010.02043 "]},"language":[{"iso":"eng"}],"publication":"Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings","abstract":[{"lang":"eng","text":"Most existing robot formation problems seek a target formation of a certain\r\nminimal and, thus, efficient structure. Examples include the Gathering\r\nand the Chain-Formation problem. In this work, we study formation problems that\r\ntry to reach a maximal structure, supporting for example an efficient\r\ncoverage in exploration scenarios. A recent example is the NASA Shapeshifter\r\nproject, which describes how the robots form a relay chain along which gathered\r\ndata from extraterrestrial cave explorations may be sent to a home base.\r\n  As a first step towards understanding such maximization tasks, we introduce\r\nand study the Max-Chain-Formation problem, where $n$ robots are ordered along a\r\nwinding, potentially self-intersecting chain and must form a connected,\r\nstraight line of maximal length connecting its two endpoints. We propose and\r\nanalyze strategies in a discrete and in a continuous time model. In the\r\ndiscrete case, we give a complete analysis if all robots are initially\r\ncollinear, showing that the worst-case time to reach an\r\n$\\varepsilon$-approximation is upper bounded by $\\mathcal{O}(n^2 \\cdot \\log\r\n(n/\\varepsilon))$ and lower bounded by $\\Omega(n^2 \\cdot~\\log\r\n(1/\\varepsilon))$. If one endpoint of the chain remains stationary, this result\r\ncan be extended to the non-collinear case. If both endpoints move, we identify\r\na family of instances whose runtime is unbounded. For the continuous model, we\r\ngive a strategy with an optimal runtime bound of $\\Theta(n)$. Avoiding an\r\nunbounded runtime similar to the discrete case relies crucially on a\r\ncounter-intuitive aspect of the strategy: slowing down the endpoints while all\r\nother robots move at full speed. Surprisingly, we can show that a similar trick\r\ndoes not work in the discrete model."}]},{"editor":[{"first_name":"Stéphane ","full_name":"Devismes, Stéphane ","last_name":"Devismes"},{"last_name":" Mittal","full_name":" Mittal, Neeraj","first_name":"Neeraj"}],"status":"public","type":"conference","_id":"20185","department":[{"_id":"63"}],"series_title":"Lecture Notes in Computer Science (LNCS)","user_id":"38705","intvolume":"     12514","page":"60-64","citation":{"ama":"Castenow J, Harbig J, Jung D, Knollmann T, Meyer auf der Heide F. Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented &#38; Luminous Robots with Limited Visibility . 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:60-64. doi:<a href=\"https://doi.org/10.1007/978-3-030-64348-5_5\">10.1007/978-3-030-64348-5_5</a>","ieee":"J. Castenow, J. Harbig, D. Jung, T. Knollmann, and F. Meyer auf der Heide, “Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented &#38; Luminous Robots with Limited Visibility ,” 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. 60–64.","chicago":"Castenow, Jannik, Jonas Harbig, Daniel Jung, Till Knollmann, and Friedhelm Meyer auf der Heide. “Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented &#38; Luminous Robots with Limited Visibility .” 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:60–64. Lecture Notes in Computer Science (LNCS). Springer, 2020. <a href=\"https://doi.org/10.1007/978-3-030-64348-5_5\">https://doi.org/10.1007/978-3-030-64348-5_5</a>.","apa":"Castenow, J., Harbig, J., Jung, D., Knollmann, T., &#38; Meyer auf der Heide, F. (2020). Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented &#38; Luminous Robots with Limited Visibility . 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. 60–64). Springer. <a href=\"https://doi.org/10.1007/978-3-030-64348-5_5\">https://doi.org/10.1007/978-3-030-64348-5_5</a>","mla":"Castenow, Jannik, et al. “Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented &#38; Luminous Robots with Limited Visibility .” <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. 60–64, doi:<a href=\"https://doi.org/10.1007/978-3-030-64348-5_5\">10.1007/978-3-030-64348-5_5</a>.","bibtex":"@inproceedings{Castenow_Harbig_Jung_Knollmann_Meyer auf der Heide_2020, series={Lecture Notes in Computer Science (LNCS)}, title={Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented &#38; Luminous Robots with Limited Visibility }, volume={12514}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-64348-5_5\">10.1007/978-3-030-64348-5_5</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 Harbig, Jonas and Jung, Daniel and Knollmann, Till and Meyer auf der Heide, Friedhelm}, editor={Devismes, Stéphane  and  Mittal, NeerajEditors}, year={2020}, pages={60–64}, collection={Lecture Notes in Computer Science (LNCS)} }","short":"J. Castenow, J. Harbig, D. Jung, 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. 60–64."},"publication_identifier":{"isbn":["978-3-030-64347-8"]},"publication_status":"published","doi":"10.1007/978-3-030-64348-5_5","date_updated":"2022-01-06T06:54:21Z","volume":12514,"author":[{"first_name":"Jannik","last_name":"Castenow","full_name":"Castenow, Jannik","id":"38705"},{"full_name":"Harbig, Jonas","id":"47213","last_name":"Harbig","first_name":"Jonas"},{"first_name":"Daniel","last_name":"Jung","full_name":"Jung, Daniel","id":"37827"},{"id":"39241","full_name":"Knollmann, Till","orcid":"0000-0003-2014-4696","last_name":"Knollmann","first_name":"Till"},{"last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","first_name":"Friedhelm"}],"publication":"Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings ","language":[{"iso":"eng"}],"external_id":{"arxiv":["2010.04424 "]},"year":"2020","title":"Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented & Luminous Robots with Limited Visibility ","publisher":"Springer","date_created":"2020-10-23T08:50:28Z"}]