一种欧椋鸟群协同算法
|
摘要
针对当前基于控制策略解决群体协同问题的不足之处,受生物群集行为启发,提出一种欧椋鸟群协同算法(starling swarm coordination algorithm,SSCA)。该算法采用无中心自组织思想,利用智能体(agent)从其最邻近的6、7个邻居信息中寻找最优解,并通过智能体之间相互作用的10条简单行为规则,描述整个群体运动从无序行为到有序行为的演化过程。结合欧椋鸟群集行为最新研究成果,从局部感知、运动行为、安全规避、适应进化4个方面论述欧椋鸟群协同算法的基本机理。以无人机集群协同飞行为应用实例,分别采用粒子群算法和本文算法测试无人机集群执行任务效率,并采用本文算法模拟无人机集群聚合、分散、规避等行为。实验结果表明,本文算法在执行任务效率上优于传统粒子群算法,具有有效性与可靠性。
Focusing on the shortcomings of current solution based on control strategies to the group coordination problem, we propose a starling swarm coordination algorithm(SSCA) inspired by biological cluster behavior. The algorithm adopts the thought of centerlessness and self-organization and realizes the description of the behavior evolution process of group movement from disorder to order,through the way the agent searches for the optimal solution from its nearest 6 or 7 neighbors and also agents interact with each other from 10 simple behavior rules. Combining the latest research findings on cluster behavior of starlings, the paper presents intelligent group collaboration methodology which integrates the four aspects, i.e. local perception, motion behavior, safe avoidance and adaptive evolution. On this basis, the basic mechanism of starling swarm coordination algorithm is given. Taking UAVs collaborative flight as an example, we tested mission efficiency of UAVs between particle swarm optimization algorithm and SSCA, and the behaviors of aggregation, separation and avoidance were simulated by our algorithm. The experimental results show that our algorithm is better than the traditional particle swarm optimization algorithm in the aspect of collaborative efficiency and the effectiveness and reliability of our algorithm is verified in the paper.
Focusing on the shortcomings of current solution based on control strategies to the group coordination problem, we propose a starling swarm coordination algorithm(SSCA) inspired by biological cluster behavior. The algorithm adopts the thought of centerlessness and self-organization and realizes the description of the behavior evolution process of group movement from disorder to order,through the way the agent searches for the optimal solution from its nearest 6 or 7 neighbors and also agents interact with each other from 10 simple behavior rules. Combining the latest research findings on cluster behavior of starlings, the paper presents intelligent group collaboration methodology which integrates the four aspects, i.e. local perception, motion behavior, safe avoidance and adaptive evolution. On this basis, the basic mechanism of starling swarm coordination algorithm is given. Taking UAVs collaborative flight as an example, we tested mission efficiency of UAVs between particle swarm optimization algorithm and SSCA, and the behaviors of aggregation, separation and avoidance were simulated by our algorithm. The experimental results show that our algorithm is better than the traditional particle swarm optimization algorithm in the aspect of collaborative efficiency and the effectiveness and reliability of our algorithm is verified in the paper.
引文
[1]WANG Y,GARCIA E,CASBEER D,et al.Cooperative Control of Multi-agent Systems:Theory and Applications[M].New Jersey:Wiley,2017.
[2]REYNOLDS C W.Flocks,herds,and schools:A distributed behavioral model[J].Computer Graphics,1987,21(4):25-34.DOI:10.1145/37401.37406.
[3]KWONG H,JACOB C.Evolutionary exploration of dynamic swarm behavior[C]//Proceedings of the IEEECongress on Evolutionary Computation.New York:IEEE,2003:367-374.
[4]WANG L,SHI H,CHU T G.Flocking control of groups of mobile autonomous agents via local feedback[C]//Proceedings of the IEEE International Symposium on Intelligent Control.New York:IEEE Press,2005:441-446.
[5]CUCKER F,SMALE S.Emergent behavior in flocks[J].IEEE Transactions on Automatic Control,2007,52(5):852-862.DOI:10.1109/TAC.2007.895842.
[6]CAVAGNA A,GIARDINA I,GRIGERA T S,et al.Silent flocks:Constraints on signal propagation across biological groups[J].Physical Review Letters,2015,114(21):218101-1-218101-5.DOI:10.1103/PhysRevLett.114.218101.
[7]CAVAGNA A,CIMARELLI A,GIARDINA I,et al.Scale-free correlations in starling flocks[J].Proceedings of the National Academy of Sciences of the United States of America,2010,107(26):11865-11870.DOI:10.1073/pnas.1005766107.
[8]HEREFORD J,BLUM C.FlockOpt:A new swarm optimization algorithm based on collective behavior of starling birds[C]//Proceedings of 3rd World Congress on Nature and Biologically Inspired Computing.New York:IEEE Press,2011:17-22.
[9]NETJINDA N,ACHALAKU T,SIRINAOVAKU B.Particle swarm optimization inspired by starling flock behavior[J].Applied Soft Computing,2015,35:411-422.DOI:10.1016/j.asoc.2015.06.052.
[10]邱华鑫,段海滨.从鸟群群集飞行到无人机自主集群编队[J].工程科学学报,2017,39(3):317-322.DOI:10.13374/j.issn2095-9389.2017.03.001.QIU H X,DUAN H B.From collective flight in bird flocks to unmanned aerial vehicle autonomous swarm formation[J].Chinese Journal of Engineering,2017,39(3):317-322.DOI:10.13374/j.issn2095-9389.2017.03.001(Ch).
[11]MITCHELL M.An Introduction to Genetic Algorithms[M].MA:MIT Press,1996.
[12]KENNEDY J,EBERHART R.Particle Swarm Optimization[C]//Proceedings of IEEE International Conference on Neural Networks.New York:IEEE,1995:1942-1948.
[13]DORIGO M.Optimization,Learning and Natural Algorithms[D].Milano:Politecnico di Milano,1992.
[14]BALLERINI M,CABIBBO N,CANDELIER R,et al.Interaction ruling animal collective behavior depends on topological rather than metric distance:Evidence from a field study[J].Proceedings of the National Academy of Sciences of the United States of America,2008,105(4):1232-1237.DOI:1232-1237.10.1073/pnas.0711437105.
[15]KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.DOI:10.1109/ROBOT.1985.1087247.
[16]屈强,何新华,刘中晅.系统涌现的要素和动力学机制[J].系统科学学报,2017,25(3):25-29.DOI:CNKI:SUN:XTBZ.0.2017-03-006.QU Q,HE X H,LIU Z X.Essential factors and dynamic mechanism of the system emergence[J].Journal of System Science,2017,25(3):25-29.DOI:CNKI:SUN:XT-BZ.0.2017-03-006(Ch).
[2]REYNOLDS C W.Flocks,herds,and schools:A distributed behavioral model[J].Computer Graphics,1987,21(4):25-34.DOI:10.1145/37401.37406.
[3]KWONG H,JACOB C.Evolutionary exploration of dynamic swarm behavior[C]//Proceedings of the IEEECongress on Evolutionary Computation.New York:IEEE,2003:367-374.
[4]WANG L,SHI H,CHU T G.Flocking control of groups of mobile autonomous agents via local feedback[C]//Proceedings of the IEEE International Symposium on Intelligent Control.New York:IEEE Press,2005:441-446.
[5]CUCKER F,SMALE S.Emergent behavior in flocks[J].IEEE Transactions on Automatic Control,2007,52(5):852-862.DOI:10.1109/TAC.2007.895842.
[6]CAVAGNA A,GIARDINA I,GRIGERA T S,et al.Silent flocks:Constraints on signal propagation across biological groups[J].Physical Review Letters,2015,114(21):218101-1-218101-5.DOI:10.1103/PhysRevLett.114.218101.
[7]CAVAGNA A,CIMARELLI A,GIARDINA I,et al.Scale-free correlations in starling flocks[J].Proceedings of the National Academy of Sciences of the United States of America,2010,107(26):11865-11870.DOI:10.1073/pnas.1005766107.
[8]HEREFORD J,BLUM C.FlockOpt:A new swarm optimization algorithm based on collective behavior of starling birds[C]//Proceedings of 3rd World Congress on Nature and Biologically Inspired Computing.New York:IEEE Press,2011:17-22.
[9]NETJINDA N,ACHALAKU T,SIRINAOVAKU B.Particle swarm optimization inspired by starling flock behavior[J].Applied Soft Computing,2015,35:411-422.DOI:10.1016/j.asoc.2015.06.052.
[10]邱华鑫,段海滨.从鸟群群集飞行到无人机自主集群编队[J].工程科学学报,2017,39(3):317-322.DOI:10.13374/j.issn2095-9389.2017.03.001.QIU H X,DUAN H B.From collective flight in bird flocks to unmanned aerial vehicle autonomous swarm formation[J].Chinese Journal of Engineering,2017,39(3):317-322.DOI:10.13374/j.issn2095-9389.2017.03.001(Ch).
[11]MITCHELL M.An Introduction to Genetic Algorithms[M].MA:MIT Press,1996.
[12]KENNEDY J,EBERHART R.Particle Swarm Optimization[C]//Proceedings of IEEE International Conference on Neural Networks.New York:IEEE,1995:1942-1948.
[13]DORIGO M.Optimization,Learning and Natural Algorithms[D].Milano:Politecnico di Milano,1992.
[14]BALLERINI M,CABIBBO N,CANDELIER R,et al.Interaction ruling animal collective behavior depends on topological rather than metric distance:Evidence from a field study[J].Proceedings of the National Academy of Sciences of the United States of America,2008,105(4):1232-1237.DOI:1232-1237.10.1073/pnas.0711437105.
[15]KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.DOI:10.1109/ROBOT.1985.1087247.
[16]屈强,何新华,刘中晅.系统涌现的要素和动力学机制[J].系统科学学报,2017,25(3):25-29.DOI:CNKI:SUN:XTBZ.0.2017-03-006.QU Q,HE X H,LIU Z X.Essential factors and dynamic mechanism of the system emergence[J].Journal of System Science,2017,25(3):25-29.DOI:CNKI:SUN:XT-BZ.0.2017-03-006(Ch).