The Complexity in Complete Graphic Characterizations of Multiagent Controllability

IEEE Trans Cybern. 2021 Jan;51(1):64-76. doi: 10.1109/TCYB.2020.2972403. Epub 2020 Dec 22.

Abstract

Establishing the graph-based criterion for the selection of any location and any number of leaders is the main difficulty in the complete graphic characterization of multiagent controllability. This greatly increases the complexity of the study, compared with the results derived for only one or several classes of leaders. Through a detailed analysis of graphs of six nodes, this article presents a systematic design and identification process for the complete graphic characterization by taking advantage of controllability destructive nodes. The topologies obtained by the proposed method allow directly determining controllability at the network topology level. The results are not only applicable to any leader's selection but also reveal the difficulty and complexity in the study of complete controllability graphic characterizations. Moreover, by comparing graphs composed of five and six nodes, the results reveal the graph-theory-based controllability complexity caused by adding only one node. Finally, results are derived to show how to design topology structures to ensure the controllability under any selection of leaders.