Local Strategies for Swarm Formations on a Grid

D. Jung, Local Strategies for Swarm Formations on a Grid, Universität Paderborn, 2018.

Download
No fulltext has been uploaded.
Dissertation | English
Abstract
My dissertation deals with the Gathering problem for swarms of n point-shaped robots on a grid, in which all robots of the swarm are supposed to gather at a previously undefined point. Special attention is paid to the strong limitation of robot capabilities. These include in particular the lack of global control, a global compass, global visibility and (global) communication skills. Furthermore, all robots are identical. The robots are given only local abilities. This includes a constant range of vision. The robots all work completely synchronously. In this work we present and analyze three different Gathering strategies in different robot models. We formally prove correctness and total running time: Chapter 4 focuses on minimizing the available robot capabilities. The underlying strategy completes the gathering in O(n^2) time. For the following Chapters 5 and 6, the aim is to optimize the total running time under using only local robot capabilities: We additionally allow a constant-sized memory and a constant number of locally visible statuses (lights, flags). For the strategies of both chapters we show an asymptotically optimal running time of O(n). Unlike in Chapters 4 and 5, we additionally restrict connectivity and vision to an initially given chain connectivity in Chapter 6, where two chain neighbors must have a distance of 1 from each other. A robot can only see and interact with a constant number of its direct chain neighbors.
Publishing Year
LibreCat-ID

Cite this

Jung D. Local Strategies for Swarm Formations on a Grid. Universität Paderborn; 2018. doi:10.17619/UNIPB/1-271
Jung, D. (2018). Local Strategies for Swarm Formations on a Grid. Universität Paderborn. https://doi.org/10.17619/UNIPB/1-271
@book{Jung_2018, title={Local Strategies for Swarm Formations on a Grid}, DOI={10.17619/UNIPB/1-271}, publisher={Universität Paderborn}, author={Jung, Daniel}, year={2018} }
Jung, Daniel. Local Strategies for Swarm Formations on a Grid. Universität Paderborn, 2018. https://doi.org/10.17619/UNIPB/1-271.
D. Jung, Local Strategies for Swarm Formations on a Grid. Universität Paderborn, 2018.
Jung, Daniel. Local Strategies for Swarm Formations on a Grid. Universität Paderborn, 2018, doi:10.17619/UNIPB/1-271.
External material:
Confirmation Letter

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search