Uniform circle formation by asynchronous robots: A fully-distributed approach

Shan Jiang, Jiannong Cao, Jia Wang, Milos Stojmenovic, Julien Bourgeois

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 Citations (Scopus)

Abstract

Recent advances in robotics technology have made it practical to deploy a large number of inexpensive robots in a wide range of application domains. In many of those applications, a group of autonomous robots is required to form a predefined geometric shape such as a line or a circle. This problem, namely pattern formation problem, is one of the most important coordination problems in multi-robot systems. A particular pattern extensively studied in literature is the uniform circle, and the corresponding problem is called uniform circle formation. In uniform circle formation, a set of simple mobile robots (asynchronous, autonomous), starting from arbitrary positions on the plane, have to arrange themselves on the vertices of a regular polygon eventually. Towards addressing the problem, existing works usually make conveniently strong assumptions, i.e., the robots are regarded as mass points and have unlimited sensing and communication range. The question of whether the robots with actual size and limited sensing and communication range could form a uniform circle, to our knowledge, has remained open. In this paper, we propose a new approach towards addressing this issue. Three phases, consensus on the circle, circle formation, and uniform transformation, constitute our approach. Inside our approach, there are some new distributed algorithms such as convex hull construction and cardinality estimation. Simulation result, theoretical analysis, and successful deployment have shown the effectiveness and practicability of our approach.

Original languageEnglish
Title of host publication2017 26th International Conference on Computer Communications and Networks, ICCCN 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509029914
DOIs
Publication statusPublished - 14 Sep 2017
Event26th International Conference on Computer Communications and Networks, ICCCN 2017 - Vancouver, Canada
Duration: 31 Jul 20173 Aug 2017

Publication series

Name2017 26th International Conference on Computer Communications and Networks, ICCCN 2017

Conference

Conference26th International Conference on Computer Communications and Networks, ICCCN 2017
Country/TerritoryCanada
CityVancouver
Period31/07/173/08/17

Keywords

  • Distributed algorithm
  • Multi-robot system
  • Uniform circle formation

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Software
  • Management of Technology and Innovation
  • Information Systems and Management
  • Safety, Risk, Reliability and Quality
  • Media Technology
  • Control and Optimization

Cite this