多运动体分布式最优编队构型形成算法
|
摘要
针对分布式通信条件下的多运动体编队构型形成问题进行研究.考虑到个体的有限通信与感知能力,传统集中式求解算法无法适应实际需求,提出一种基于分布式交替映射凸优化的分布式时间最优编队构型形成算法,使得个体间仅依赖局部通信与局部计算实现编队构型的快速形成;将该问题建模为含有等式约束的分布式Minimax凸优化问题,提出基于虚拟等式约束函数的分布式交替映射凸优化算法实现求解;根据求解结果,各运动体采用RVO避障策略实现最优构型形成.针对含有100个运动体的最优编队构型形成问题进行仿真,验证了所提出算法的有效性.
In this paper, we study the multi-agent distributed time-optimal formation shaping problem by proposing the time-optimal formation shaping distributed algorithm based on distributed convex alternating projection method, in which each individual only has limited communication range and sensing ability, where centralized algorithms failed. In the proposed algorithm, we model the problem as a equality-constraint distributed minimax convex optimization, which is further solved by proposing a novel virtual-equality-constraint based alternating projection method. According to the optimization results, multi-agent can achieve optimal shaping with the RVO avoidance strategy. Finally, the simulation of100 multi-agent optimal formation is demonstrated to verify the efficiency of the proposed algorithm.
In this paper, we study the multi-agent distributed time-optimal formation shaping problem by proposing the time-optimal formation shaping distributed algorithm based on distributed convex alternating projection method, in which each individual only has limited communication range and sensing ability, where centralized algorithms failed. In the proposed algorithm, we model the problem as a equality-constraint distributed minimax convex optimization, which is further solved by proposing a novel virtual-equality-constraint based alternating projection method. According to the optimization results, multi-agent can achieve optimal shaping with the RVO avoidance strategy. Finally, the simulation of100 multi-agent optimal formation is demonstrated to verify the efficiency of the proposed algorithm.
引文
[1]Rubenstein M, Cornejo A, Nagpal R. Programmable self-assembly in a thousand-robot swarm[J]. Science,2014, 345(6198):795-799.
[2]Oh K K, Park M C, Ahn H S. A survey of multi-agent formation control[J]. Automatica, 2015, 53(C):424-440.
[3]Zhao S, Zelazo D. Bearing rigidity and almost global bearing-only formation stabilization[J]. IEEE Trans on Automatic Control, 2016, 61(5):1255-1268.
[4]樊琼剑,杨忠,方挺,等.多无人机协同编队飞行控制的研究现状[J].航空学报, 2009, 30(4):683-691.(Fan Q J, Yang Z, Fang T, et al. Research status of coordinated formation flight control for multi-UAVs[J].Acta Aeronautica et Astronautica Sinica, 2009, 30(4):683-691.)
[5]Paunoen L, Seifert D. Asymptotic behaviour in the robot rendezvous problem[J]. Automatica, 2017, 79:127-130.
[6]Alonso-mora J, Breitenmoser A, Rufli M, et al.Optimal reciprocal collision avoidance for multiple non-holonomic robots[M]. Distributed Autonomous Robotic Systems. Berlin:Springer, 2013:203-216.
[7]Zhang X, Duan H. Altitude consensus based 3D flocking control for fixed-wing unmanned aerial vehicle swarm trajectory tracking[J]. Proc of the Institution of Mechanical Engineers Part G:J of Aerospace Engineering, 2016, 230(14):2628-2638.
[8]Derenick J C, Spletzer J R. Convex optimization strategies for coordinating large-scale robot formations[J]. IEEE Trans on Robotics, 2007, 23(6):1252-1259.
[9]Wang Y, Cheng L, Hou Z G, et al. Optimal formation of multirobot systems based on a recurrent neural network[J]. IEEE Trans on Neural Networks and Learning Systems, 2016, 27(2):322-333.
[10]Parikh N, Boyd S. Proximal algorithms[J]. Foundations and Trends in Optimization, 2014, 1(3):127-239.
[11]Du D Z, Pardalos P M. Minimax and applications[M].Berlin:Springer, 2013.
[12]Hu C, Chen Z. Distributed Min-max optimization application to time-optimal consensus:An alternating projection approach[C]. The AIAA Guidance,Navigation, and Control Conf. Kissimmee:AIAA,2015:1-11.
[13]Hu C, Chen Z. Helly-theorem-based time-optimal consensus for multi-agent systems[J]. J of Beijing University of Aeronautics and Astronautics, 2015, 41(9):1701-1707.
[14]Guerrero J, Oliver G, Valero O. Multi-robot coalitions formation with deadlines:Complexity analysis and solutions[J]. PloS one, 2017, 12(1):e0170659.
[15]Derenick J, Spletzer J, Kumar V. A semidefinite programming framework for controlling multi-robot systems in dynamic environments[C]. IEEE Conf on Decision and Control. Atlanta:IEEE, 2010:7172-7177.
[16]Zhu M, Mart S. On distributed convex optimization under inequality and equality constraints[J]. IEEE Trans on Automatic Control, 2012, 57(1):151-164.
[17]Boyd S, Vandenberghe L. Convex optimization[M].Cambridge:Cambridge University Press, 2004:215-231.
[18]Van J, Guy S, Lin M, et al. Reciprocal n-body collision avoidance[J]. Robotics Research, 2011(70):3-19.
[2]Oh K K, Park M C, Ahn H S. A survey of multi-agent formation control[J]. Automatica, 2015, 53(C):424-440.
[3]Zhao S, Zelazo D. Bearing rigidity and almost global bearing-only formation stabilization[J]. IEEE Trans on Automatic Control, 2016, 61(5):1255-1268.
[4]樊琼剑,杨忠,方挺,等.多无人机协同编队飞行控制的研究现状[J].航空学报, 2009, 30(4):683-691.(Fan Q J, Yang Z, Fang T, et al. Research status of coordinated formation flight control for multi-UAVs[J].Acta Aeronautica et Astronautica Sinica, 2009, 30(4):683-691.)
[5]Paunoen L, Seifert D. Asymptotic behaviour in the robot rendezvous problem[J]. Automatica, 2017, 79:127-130.
[6]Alonso-mora J, Breitenmoser A, Rufli M, et al.Optimal reciprocal collision avoidance for multiple non-holonomic robots[M]. Distributed Autonomous Robotic Systems. Berlin:Springer, 2013:203-216.
[7]Zhang X, Duan H. Altitude consensus based 3D flocking control for fixed-wing unmanned aerial vehicle swarm trajectory tracking[J]. Proc of the Institution of Mechanical Engineers Part G:J of Aerospace Engineering, 2016, 230(14):2628-2638.
[8]Derenick J C, Spletzer J R. Convex optimization strategies for coordinating large-scale robot formations[J]. IEEE Trans on Robotics, 2007, 23(6):1252-1259.
[9]Wang Y, Cheng L, Hou Z G, et al. Optimal formation of multirobot systems based on a recurrent neural network[J]. IEEE Trans on Neural Networks and Learning Systems, 2016, 27(2):322-333.
[10]Parikh N, Boyd S. Proximal algorithms[J]. Foundations and Trends in Optimization, 2014, 1(3):127-239.
[11]Du D Z, Pardalos P M. Minimax and applications[M].Berlin:Springer, 2013.
[12]Hu C, Chen Z. Distributed Min-max optimization application to time-optimal consensus:An alternating projection approach[C]. The AIAA Guidance,Navigation, and Control Conf. Kissimmee:AIAA,2015:1-11.
[13]Hu C, Chen Z. Helly-theorem-based time-optimal consensus for multi-agent systems[J]. J of Beijing University of Aeronautics and Astronautics, 2015, 41(9):1701-1707.
[14]Guerrero J, Oliver G, Valero O. Multi-robot coalitions formation with deadlines:Complexity analysis and solutions[J]. PloS one, 2017, 12(1):e0170659.
[15]Derenick J, Spletzer J, Kumar V. A semidefinite programming framework for controlling multi-robot systems in dynamic environments[C]. IEEE Conf on Decision and Control. Atlanta:IEEE, 2010:7172-7177.
[16]Zhu M, Mart S. On distributed convex optimization under inequality and equality constraints[J]. IEEE Trans on Automatic Control, 2012, 57(1):151-164.
[17]Boyd S, Vandenberghe L. Convex optimization[M].Cambridge:Cambridge University Press, 2004:215-231.
[18]Van J, Guy S, Lin M, et al. Reciprocal n-body collision avoidance[J]. Robotics Research, 2011(70):3-19.