Distributed Biased Min-Consensus with Applications to Shortest Path Planning

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.