Journal
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
Volume 62, Issue 10, Pages 5429-5436Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2017.2694547
Keywords
Complex behavior; consensus; dynamic graph; shortest path planning
Funding
- National Natural Science Foundation of China [61401385]
- Hong Kong Research Grants Council Early Career Scheme [25214015]
- Departmental General Research Fund of Hong Kong Polytechnic University [G.61.37.UA7L]
- PolyU Central Research Grant (G-YBMU)
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available