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

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.