Decentralized algorithm for repeating pattern formation by multiple robots

Shan Jiang, Junbin Liang, Jiannong Cao, Jia Wang, Jinlin Chen, Zhixuan Liang

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


Recently, much attention is paid to multi-robot systems due to their widespread applications such as warehouse robotics, persistent surveillance, and exploration of unknown environments. Although urgently required by the applications, coordination among multiple robots remains to be challenging. Among the problems of multi-robot coordination, pattern formation serves a fundamental one. It aims to control a group of robots to form a desired shape with some certain goals such as best formation quality, minimum makespan or minimum total distance. Existing works mainly focus on the formation of certain patterns, such as repeating squares or a circle.Those approaches cannot be generalized to arbitrary pattern formation. In this paper, we propose a decentralized algorithm for a multi-robot system to generate a given formation with an arbitrary repeating pattern. We introduce basic pattern graph and assembling graph to define a repeating pattern and formation quality for measurement. Towards solving the repeating pattern formation problem, our approach is divided into two phases. The robots are grouped into multiple basic patterns in the first phase, and the patterns are assembled level by level in the second phase. Simulations and real-world experiments indicate the effectiveness and practicability of our approach.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 25th International Conference on Parallel and Distributed Systems, ICPADS 2019
PublisherIEEE Computer Society
Number of pages8
ISBN (Electronic)9781728125831
Publication statusPublished - Dec 2019
Event25th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2019 - Tianjin, China
Duration: 4 Dec 20196 Dec 2019

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
ISSN (Print)1521-9097


Conference25th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2019


  • Distributed algorithm
  • Multi-robot system
  • Pattern formation

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this