中国物理B ›› 2018, Vol. 27 ›› Issue (2): 28901-028901.doi: 10.1088/1674-1056/27/2/028901

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇    下一篇

Generation of optimal persistent formations for heterogeneous multi-agent systems with a leader constraint

Guo-Qiang Wang(王国强), He Luo(罗贺), Xiao-Xuan Hu(胡笑旋)   

  1. 1. School of Management, Hefei University of Technology, Hefei 230009, China;
    2. Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei 230009, China
  • 收稿日期:2017-07-18 修回日期:2017-10-09 出版日期:2018-02-05 发布日期:2018-02-05
  • 通讯作者: He Luo E-mail:luohe@hfut.edu.cn
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant Nos. 71671059, 71401048, 71521001, 71690230, 71690235, and 71472058) and the Anhui Provincial Natural Science Foundation, China (Grant No. 1508085MG140).

Generation of optimal persistent formations for heterogeneous multi-agent systems with a leader constraint

Guo-Qiang Wang(王国强)1,2, He Luo(罗贺)1,2, Xiao-Xuan Hu(胡笑旋)1,2   

  1. 1. School of Management, Hefei University of Technology, Hefei 230009, China;
    2. Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei 230009, China
  • Received:2017-07-18 Revised:2017-10-09 Online:2018-02-05 Published:2018-02-05
  • Contact: He Luo E-mail:luohe@hfut.edu.cn
  • About author:89.20.Ff; 87.85.St; 89.65.Ef; 02.30.Em
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant Nos. 71671059, 71401048, 71521001, 71690230, 71690235, and 71472058) and the Anhui Provincial Natural Science Foundation, China (Grant No. 1508085MG140).

摘要: In this study, we consider the generation of optimal persistent formations for heterogeneous multi-agent systems, with the leader constraint that only specific agents can act as leaders. We analyze three modes to control the optimal persistent formations in two-dimensional space, thereby establishing a model for their constrained generation. Then, we propose an algorithm for generating the optimal persistent formation for heterogeneous multi-agent systems with a leader constraint (LC-HMAS-OPFGA), which is the exact solution algorithm of the model, and we theoretically prove its validity. This algorithm includes two kernel sub-algorithms, which are optimal persistent graph generating algorithm based on a minimum cost arborescence and the shortest path (MCA-SP-OPGGA), and the optimal persistent graph adjusting algorithm based on the shortest path (SP-OPGAA). Under a given agent formation shape and leader constraint, LC-HMAS-OPFGA first generates the network topology and its optimal rigid graph corresponding to this formation shape. Then, LC-HMAS-OPFGA uses MCA-SP-OPGGA to direct the optimal rigid graph to generate the optimal persistent graph. Finally, LC-HMAS-OPFGA uses SP-OPGAA to adjust the optimal persistent graph until it satisfies the leader constraint. We also demonstrate the algorithm, LC-HMAS-OPFGA, with an example and verify its effectiveness.

关键词: leader constraint, heterogeneous multi-agent system, optimal persistent formation, minimum cost arborescence

Abstract: In this study, we consider the generation of optimal persistent formations for heterogeneous multi-agent systems, with the leader constraint that only specific agents can act as leaders. We analyze three modes to control the optimal persistent formations in two-dimensional space, thereby establishing a model for their constrained generation. Then, we propose an algorithm for generating the optimal persistent formation for heterogeneous multi-agent systems with a leader constraint (LC-HMAS-OPFGA), which is the exact solution algorithm of the model, and we theoretically prove its validity. This algorithm includes two kernel sub-algorithms, which are optimal persistent graph generating algorithm based on a minimum cost arborescence and the shortest path (MCA-SP-OPGGA), and the optimal persistent graph adjusting algorithm based on the shortest path (SP-OPGAA). Under a given agent formation shape and leader constraint, LC-HMAS-OPFGA first generates the network topology and its optimal rigid graph corresponding to this formation shape. Then, LC-HMAS-OPFGA uses MCA-SP-OPGGA to direct the optimal rigid graph to generate the optimal persistent graph. Finally, LC-HMAS-OPFGA uses SP-OPGAA to adjust the optimal persistent graph until it satisfies the leader constraint. We also demonstrate the algorithm, LC-HMAS-OPFGA, with an example and verify its effectiveness.

Key words: leader constraint, heterogeneous multi-agent system, optimal persistent formation, minimum cost arborescence

中图分类号:  (Computer science and technology)

  • 89.20.Ff
87.85.St (Robotics) 89.65.Ef (Social organizations; anthropology ?) 02.30.Em (Potential theory)