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

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.