NDLI: Linear and Competitive Strategies for Continuous Robot Formation Problems

Please wait, while we are loading the content...

Linear and Competitive Strategies for Continuous Robot Formation Problems

Content Provider	ACM Digital Library
Author	Degener, Bastian Heide, Friedhelm Meyer Auf Der Kempkes, Barbara Kling, Peter
Copyright Year	2015
Abstract	We study a scenario in which $\textit{n}$ mobile robots with a limited viewing range are distributed in the Euclidean plane and have to solve a formation problem. The formation problems we consider are the Gathering problem and the Chain-Formation problem. In the Gathering problem, the robots have to gather in one (not predefined) point, while in the Chain-Formation problem they have to form a connected communication chain of minimal length between two stationary base stations. Each robot may base its decisions where to move only on the current relative positions of neighboring robots (that are within its viewing range); that is, besides having a limited viewing range, the robots are oblivious (they do not use information from the past), have none or only very limited identities, and they do not have a common sense of direction. Variants of these problems (especially for the Gathering problem) have been studied extensively in different discrete time models. In contrast, our work focuses on a continuous time model; that is, the robots continuously sense the positions of other robots within their viewing range and continuously adapt their speed and direction according to some simple, local rules. Hereby, we assume that the robots have a maximum movement speed of one. We show that this idealized idea of continuous sensing allows us to solve the mentioned formation problems in linear time $O(\textit{n})$ (which, given the maximum speed of one, immediately yields a maximum traveled distance of $O(\textit{n})).$ Note that in the more classical discrete time models, the best known strategies need at least $Θ(n^{2})$ or even $Θ(n^{2}logn)$ timesteps to solve these problems. For the Gathering problem, our analysis solves a problem left open by Gordon et al. [2004], where the authors could prove that gathering in a continuous model is possible in finite time, but were not able to give runtime bounds. Apart from these linear bounds, we also provide runtime bounds for both formation problems that relate the runtime of our strategies to the runtime of an optimal, global algorithm. Specifically, we show that our strategy for the Gathering problem is log OPT-competitive and the strategy for the Chain-Formation problem is $log \textit{n}-competitive.$ Here, by $\textit{c}-competitive,$ we mean that our (local) strategy is asymptotically by at most a factor of $\textit{c}$ slower than an optimal, global strategy.
Starting Page	1
Ending Page	18
Page Count	18
File Format	PDF
ISSN	23294949
e-ISSN	23294957
DOI	10.1145/2742341
Volume Number	2
Issue Number	1
Journal	ACM Transactions on Parallel Computing (TOPC)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-05-21
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Mobile robots Distributed algorithms Local algorithms Robot gathering
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Modeling and Simulation Computer Science Applications Software Computational Theory and Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimal and competitive runtime bounds for continuous, local gathering of mobile robots

Gathering of Mobile Robots Tolerating Multiple Crash Faults

Feasibility of Polynomial-Time Randomized Gathering for Oblivious Mobile Robots

Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification

A hierarchical computer architecture for distributed simulation

Distributed Algorithms for Cooperative Mobile Robots: A Survey

Programming Strategies for Irregular Algorithms on the Emu Chick

Fast Greedy Algorithms in MapReduce and Streaming

Collective Algorithms for Multiported Torus Networks

Linear and Competitive Strategies for Continuous Robot Formation Problems

Similar Documents

Optimal and competitive runtime bounds for continuous, local gathering of mobile robots

Gathering of Mobile Robots Tolerating Multiple Crash Faults

Feasibility of Polynomial-Time Randomized Gathering for Oblivious Mobile Robots

Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification

A hierarchical computer architecture for distributed simulation

Distributed Algorithms for Cooperative Mobile Robots: A Survey

Programming Strategies for Irregular Algorithms on the Emu Chick

Fast Greedy Algorithms in MapReduce and Streaming

Collective Algorithms for Multiported Torus Networks

Linear and Competitive Strategies for Continuous Robot Formation Problems