Perturbing consensus for complexity: A finite-time discrete biased min-consensus under time-delay and asynchronism

Yinyan Zhang, Shuai Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)


In this paper, we propose a discrete-time biased min-consensus protocol with finite-time convergence by perturbing an existing min-consensus protocol, and investigate its convergence under time-delay and a synchronous state update. It is shown that a complex behavior that can address shortest path planning on a graph emerges from this modified consensus protocol. Theoretical analysis shows that the proposed protocol converges in finite time. In real-world networked systems, there may exist inevitable time delay or asynchronism in state updates. The convergence of biased min-consensus under these non-ideal situations is also theoretically analyzed. To show the scalability and efficiency of the proposed protocol, it is applied to large-scale maze solving on a maze map containing 640 × 640 pixels, which corresponds to a graph with 42,185 nodes. In addition, we also present an application of the proposed protocol to address the complete coverage problem, which further demonstrates the potential of biased min-consensus in robotic applications.

Original languageEnglish
Pages (from-to)441-447
Number of pages7
Publication statusPublished - 1 Nov 2017


  • Asynchronism
  • Complete coverage
  • Consensus
  • Maze solving
  • Min-consensus
  • Shortest path planning
  • Time-delay

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Cite this