[{"user_id":"38705","_id":"19899","type":"conference","uri_base":"https://ris.uni-paderborn.de","language":[{}],"department":[{"_id":"63","tree":[{"_id":"7"},{"_id":"34"},{"_id":"44"},{"_id":"43"}]}],"date_updated":"2022-01-06T06:54:14Z","editor":[{"last_name":"Devismes ","first_name":"Stéphane "},{"first_name":"Neeraj ","last_name":"Mittal"}],"abstract":[{"lang":"eng"}],"volume":12514,"status":"public","dini_type":"doc-type:conferenceObject","intvolume":" 12514","dc":{"creator":["Castenow, Jannik","Kling, Peter","Knollmann, Till","Meyer auf der Heide, Friedhelm","Devismes , Stéphane ","Mittal, Neeraj "],"date":["2020"],"title":["A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up"],"rights":["info:eu-repo/semantics/closedAccess"],"description":["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."],"language":["eng"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"identifier":["https://ris.uni-paderborn.de/record/19899"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-030-64348-5_6","info:eu-repo/semantics/altIdentifier/isbn/978-3-030-64347-8","info:eu-repo/semantics/altIdentifier/arxiv/2010.02043 "],"source":["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. *Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings*. Vol 12514. Lecture Notes in Computer Science (LNCS). Springer; 2020:65-80. doi:10.1007/978-3-030-64348-5_6"],"publisher":["Springer"]},"date_created":"2020-10-06T07:27:10Z","publication_status":"published","publication_identifier":{"isbn":[]},"creator":{"login":"janniksu","id":"38705"},"author":[{"first_name":"Jannik","id":"38705","last_name":"Castenow"},{"last_name":"Kling","first_name":"Peter"},{"last_name":"Knollmann","id":"39241","orcid":"0000-0003-2014-4696","first_name":"Till"},{"first_name":"Friedhelm","id":"15523","last_name":"Meyer auf der Heide"}],"publication":"Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings","external_id":{"arxiv":[]},"page":"65-80","series_title":"Lecture Notes in Computer Science (LNCS)","citation":{"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 *Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings*, edited by Stéphane Devismes and Neeraj Mittal, 12514:65–80. Lecture Notes in Computer Science (LNCS). Springer, 2020. https://doi.org/10.1007/978-3-030-64348-5_6.","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.","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 *Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings*, 2020, vol. 12514, pp. 65–80.","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={10.1007/978-3-030-64348-5_6}, 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)} }","mla":"Castenow, Jannik, et al. “A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up.” *Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings*, edited by Stéphane Devismes and Neeraj Mittal, vol. 12514, Springer, 2020, pp. 65–80, doi:10.1007/978-3-030-64348-5_6.","apa":"Castenow, J., Kling, P., Knollmann, T., & 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 & N. Mittal (Eds.), *Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings* (Vol. 12514, pp. 65–80). Springer. https://doi.org/10.1007/978-3-030-64348-5_6"}}]