一种基于航迹片段的多蚁群协同规划算法

doi:10.3969/j.issn.1000-3428.2014.11.029

计算机工程

一种基于航迹片段的多蚁群协同规划算法

刘慧娟,蔡　超,孙希霞

(华中科技大学自动化学院多谱信息处理技术国防科技重点实验室,武汉430074)

收稿日期:2013-12-19 出版日期:2014-11-15 发布日期:2014-11-13
作者简介:刘慧娟(1989 - ),女,硕士,主研方向:飞行器路径规划,计算机视觉;蔡　超,副教授、博士;孙希霞,博士研究生。
基金项目:
:国家部委基金资助项目。

A Multiple Ant Colony Collaborative Planning Algorithm Based on Trajectory Segment

LIU Huijuan,CAI Chao,SUN Xixia

(State Key Laboratory for Multi-spectral Information Processing Technologies,School of Automation,Huazhong University of Science and Technology,Wuhan 430074,China)

Received:2013-12-19 Online:2014-11-15 Published:2014-11-13

摘要/Abstract

摘要： 在协同航迹规划过程中,针对传统蚁群算法存在的收敛速度慢、航迹易冲突等问题,结合由航迹片段构成的网络图特点,提出一种基于多蚁群的飞行器协同航迹规划算法。将蚁群算法中的人工蚁群划分为与飞行器数量相对应的蚂蚁子群,通过引入异质信息素实现子群之间的竞争,采取基准长度协同进化的方法引导子群规划出满足时间协同要求的航迹,利用迷失蚂蚁信息素更新策略加快算法收敛速度。实验结果表明,针对不同规划任务,在多种复杂规划环境中,该算法都能生成满足时间和空间约束的协同飞行航迹。与传统蚁群算法相比,该算法能够将规划速度提高2 倍~3 倍,所规划出的航迹具有更好的时空协同性能。

关键词: 协同航迹规划, 网络图, 多子群, 蚁群算法, 异质信息素

Abstract: To solve the problem that the traditional ant colony algorithm is slow to converge and easy to conflict in the collaborative trajectory planning, considering the features of network graph consist of trajectory segments, a aircraft collaborative trajectory planning algorithm is proposed based on multi-subgroup ant colony coevolution. It divides the ant colony into subgroups with the same number of the aircrafts. Heterogeneous pheromone is introduced to simulate the competition among subgroups,reference length coevolution is adopted to guide the subgroups generating trajectory satisfying the temporal constraints,and the strategy of lost ants pheromone update is added to accelerate the convergence speed. Experimental results demonstrate that this algorithm can generate collaborative flight trajectorys satisfying the constraints of time and space in complex environments for different planning tasks. Compared with the traditional ant colony algorithm,it can generate better collaborative trajectorys,while the planning speed can be improved by 2 ~3 times.

Key words: collaborative trajectory planning, network graph, multi-subgroup, ant colony algorithm, heterogeneous pheromone

中图分类号:

TJ760

刘慧娟,蔡超,孙希霞. 一种基于航迹片段的多蚁群协同规划算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2014.11.029.

LIU Huijuan,CAI Chao,SUN Xixia. A Multiple Ant Colony Collaborative Planning Algorithm Based on Trajectory Segment[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2014.11.029.

参考文献

参考文献 [ 1 ]　郑昌文,严　平,丁明跃,等. 飞行器航迹规划研究现状与趋势[J]. 宇航学报,2007,28(6):1441-1446. [ 2 ]　唐　强,张翔伦,左　玲. 无人机航迹规划算法的初步研究[J]. 航空计算技术,2003,33(1):125-128. [ 3 ]　Li Shidong, Ding Mingyue, Cai Chao. A Novel Path Planning Method Based On Path Network [ C ]/ / Proceedings of the 6th International Symposium on Multispectral Image Processing and Pattern Recognition. Wuhan,China:[s. n. ],2009. [ 4 ]　McLain T,Beard R. Trajectory Planning for Coordinated Rendezvous of Unmanned Air Vehicles[C]/ / Proceedings of AIAA Guidance Navigation and Control Conference. Clearwater,USA:AIAA Press,2000:1247-1254. [ 5 ]　严　平,丁明跃,周成平. 航迹规划的一种路线图方法 [J]. 计算机工程与应用,2004,40(17):218-221. [ 6 ]　Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik,1959,1(1):269-271. [ 7 ]　王银年. 遗传算法的研究与应用[D]. 无锡:江南大学,2009. [ 8 ]　Colorni A, Dorigo M, Maniezzo V, et al. Distributed Optimization by Ant Colonies[C]/ / Proceedings of the 1st European Conference on Artificial Life. France, Paris: Elsevier Publishing,1991:134-142. [ 9 ]　李　季,孙秀霞. 基于改进A-star 算法的无人机航迹规划算法研究[J]. 兵工学报,2008,29(7):788-792. [10]　Shtovba S D. Ant Algorithms: Theory and Applications [J]. Programming and Computer Software,2005,31(4): 167-168. [11]　Dorigo M, Gambardella L M. Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem[J]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66. [12]　Nowé A,Verbeeck K,Vrancx P. Multi-type Ant Colony: The Edge Disjoint Paths Problem [ M ]/ / Dorigo M, Birattari M,Blum C,et al. Ant Colony Optimization and Swarm Intelligence. Berlin, Germany: Springer, 2004: 978-982. [13]　Dorigo M, Maniezzo V, Colorni A. Ant System: Optimization By a Colony of Cooperating Agents [J]. IEEE Transactions on Systems,Man and Cybernetics, 1996,26(1):29-41. 编辑　陆燕菲

[1]	东熠, 刘景发, 刘文杰. 基于多目标蚁群算法的主题爬虫策略[J]. 计算机工程, 2020, 46(9): 274-282.
[2]	蒋占军, 周涛, 杨永红. WSN中基于改进蚁群的能量优化路由算法[J]. 计算机工程, 2020, 46(4): 189-197.
[3]	魏新艳, 张琳. 物联网中基于信任的频谱资源分配机制[J]. 计算机工程, 2020, 46(4): 26-32,39.
[4]	党小超, 李月霞, 郝占军, 张彤. 一种基于改进蚁群算法的三维K-栅栏覆盖算法[J]. 计算机工程, 2020, 46(2): 221-229.
[5]	田纪尧, 刘广钟. WSN中基于多因素的能量优化分簇路由算法[J]. 计算机工程, 2020, 46(1): 179-186.
[6]	魏德宾, 刘健, 潘成胜, 邹启杰. 卫星网络中基于多QoS约束的蚁群优化路由算法[J]. 计算机工程, 2019, 45(7): 114-120.
[7]	杨力,刘蕴,魏德宾,蔡睿妍. 应用于卫星网络拓扑生成的快速收敛蚁群算法[J]. 计算机工程, 2019, 45(5): 93-98,104.
[8]	全力,傅明. 云计算中任务调度优化策略的研究[J]. 计算机工程, 2018, 44(8): 14-18.
[9]	王磊,乔莉,齐俊艳,刘志中. 基于蚁群算法的非均匀分簇水声传感网能量优化路由研究[J]. 计算机工程, 2018, 44(12): 150-155,162.
[10]	蔡美,刘波. 基于蚁群算法的异常数据检测方法[J]. 计算机工程, 2016, 42(8): 166-169,177.
[11]	张妍,傅秀芬. 基于三目标搜索的测试用例集约简方法[J]. 计算机工程, 2016, 42(3): 84-88.
[12]	刘治国,张自敬,李秦锋. 基于链路权重的分布式星群网络路由算法[J]. 计算机工程, 2015, 41(9): 145-149.
[13]	田冉,孙林夫,王楠,李斌勇. 求解多卸载点车载装箱问题的多信息素蚁群算法 [J]. 计算机工程, 2015, 41(8): 156-161.
[14]	彭诚,邹长春. 基于改进蚁群算法的成像测井裂缝自动提取方法[J]. 计算机工程, 2015, 41(8): 196-201.
[15]	魏赟,陈元元. 基于改进蚁群算法的云计算任务调度模型[J]. 计算机工程, 2015, 41(2): 12-16.

一种基于航迹片段的多蚁群协同规划算法

A Multiple Ant Colony Collaborative Planning Algorithm Based on Trajectory Segment

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10