Distributed Biased Min-Consensus with Applications to Shortest Path Planning

Yinyan Zhang, Shuai Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

30 Citations (Scopus)

Abstract

Distributed consensus has been intensively studied in recent years as a means to mitigate state differences among dynamic nodes on a graph. It has been successfully employed in various applications, e.g., formation control of multirobots, load balancing, and clock synchronization. However, almost all the existing applications cast an impression of consensus as a simple process to iteratively reach agreement, without any clue on possibility to generate advanced complexity, say shortest path planning, which has been proved to be NP-hard. Counterintuitively, we show for the first time that the complexity of shortest path planning can emerge from a perturbed version of a min-consensus protocol, which as a case study may shed lights to researchers in the field of distributed control to rethink the nature of complexity and the distance between control and intelligence. Besides, we rigorously prove the convergence of graph dynamics and its equivalence to shortest path solutions. An illustrative simulation on a small-scale graph is provided to show the convergence of the biased min-consensus dynamics to shortest path solution over the graph. To demonstrate the scalability to large-scale problems, a graph with 43 826 nodes, which corresponds to a map of a maze in 2-D, is considered in the simulation study. Apart from possible applications in robot path planning, the result is further extended to robot complete coverage, showing its potential in real practice such as cleaning robots.

Original languageEnglish
Article number7902114
Pages (from-to)5429-5436
Number of pages8
JournalIEEE Transactions on Automatic Control
Volume62
Issue number10
DOIs
Publication statusPublished - 1 Oct 2017

Keywords

  • Complex behavior
  • consensus
  • dynamic graph
  • shortest path planning

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this