蚁群算法求解离散最小约束去除问题

上海交通大学学报（自然版） ›› 2015, Vol. 49 ›› Issue (03): 383-386.

• 自动化技术、计算机技术 • 上一篇下一篇

蚁群算法求解离散最小约束去除问题

许波，闵华清，肖芳雄

（华南理工大学软件学院，广州 510006）

收稿日期:2014-06-01 出版日期:2015-03-30 发布日期:2015-03-30
基金资助:
国家自然科学基金项目(6126200)，中国博士后科学基金（2014M562177）资助

Ant Colony Algorithm for Solving Discrete Minimum Constraint Removal (MCR) Problem

XU Bo，MIN Huaqing，XIAO Fangxiong

(School of Software Engineering, South China University of Technology, Guangzhou 510006, China)

Received:2014-06-01 Online:2015-03-30 Published:2015-03-30

摘要/Abstract

摘要：

摘要：引入蚁群算法解决最小约束去除运动规划问题，在求解过程中对蚁群算法的启发函数以及信息素更新策略进行改进，使其不再易于陷入局部极值并适合求解该问题.仿真实验结果表明，该算法在解的质量和收敛速度上优于精确搜索与贪心算法.

关键词: 离散最小约束去除, 运动规划问题, 机器人路径规划, 蚁群算法

Abstract:

Abstract： This paper introduces the ant colony algorithm to solve the minimum constraint removal (MCR) problem. The inspired function and pheromone update strategy of the ant colony algorithm(ACO) were improved in the solving process, so that it is no longer easy to fall into local extremum. The simulation results show that the solution quality and convergence rate of the algorithm is better than those of the precise search and greedy algorithm.
Key words：

Key words: discrete minimum constraint removal(MCR)； motion planning problem； robot path planning, ant colony algorithm

中图分类号:

TP 393

许波，闵华清，肖芳雄. 蚁群算法求解离散最小约束去除问题[J]. 上海交通大学学报（自然版）, 2015, 49(03): 383-386.

XU Bo，MIN Huaqing，XIAO Fangxiong. Ant Colony Algorithm for Solving Discrete Minimum Constraint Removal (MCR) Problem[J]. Journal of Shanghai Jiaotong University, 2015, 49(03): 383-386.

参考文献

［1］Canny J. The complexity of robot motion planning ［M］. Cambridge: MIT press, 1988.

［2］Hauser, K. The minimum constraint removal problem with three robotics applications［C］∥In Proceedings of Workshop on the Algorithmic Foundations of Robotics. New York：IEEE，2012.

［3］Hauser K. The minimum constraint removal problem with three robotics applications ［J］. The International Journal of Robotics Research, 2014, 33(1): 517.

［4］Erickson L H, LaValle S M. A simple, but NPhard, motion planning problem ［C］∥In Proceedings of the TwentySeventh AAAI Conference on Artificial Intelligence (AAAI13), Urbana：AAAI，2013： 13881393.

［5］McCarthy Z, Bretl T, Hutchinson S. Proving path nonexistence using sampling and alpha shapes［C］∥In Proceedings of the 2012 IEEE International Conference on Robotics and Automation. Saint Paul：IEEE，ICRA, 2012: 25632569.

［6］Gbelbecker M, Keller T, Eyerich P, et al. Coming up with good excuses: What to do when no plan can be found［C］ ∥In Proceedings of the International Conference on Automated Planning and Scheduling. Toronto：AAAI Press，2010: 8188.

［7］Johnson J, Hauser K. Optimal longitudinal control planning with moving obstacles［C］∥In Proceedings of 2013 IEEE Intelligent Vehicles Symposium (IV). Gold Coast, QLD：IEEE，2013: 605611.

［8］Hauser K. On responsiveness, safety, and completeness in realtime motion planning ［J］. Autonomous Robots, 2012, 32(1): 3548.

［9］Hauser K. Minimum constraint displacement motion planning ［J］. Robotics: Science and Systems (RSS), 2013，10（2）：15.

［10］Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem ［J］. IEEE Transactions on Evolutionary Computation, 1997, 1(1)：5366.

［11］Stützle T, Dorigo M. A short convergence proof for a class of ant colony optimization algorithms ［J］. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 358365.

[1]	梁烽杨, 杨毅钧, 刘功龙, 万兵, 高王升. 多无人机系统协同侦察规划算法研究[J]. 空天防御, 2021, 4(1): 103-108.
[2]	蒋小康, 张朋, 吕佑龙, 赵新明, 张洁. 基于混合蚁群算法的半导体生产线炉管区调度方法[J]. 上海交通大学学报, 2020, 54(8): 792-804.
[3]	许显杨，陈璐. 考虑设备可靠性与能耗的平行机调度[J]. 上海交通大学学报, 2020, 54(3): 247-255.
[4]	李翠明，龚俊，牛万才，王翀. 基于改进隶属云模型蚁群算法的喷涂机器人喷枪轨迹组合优化[J]. 上海交通大学学报（自然版）, 2015, 49(03): 387-391.
[5]	姜文英，林焰，陈明，于雁云. 基于粒子群和蚁群算法的船舶机舱规划方法[J]. 上海交通大学学报（自然版）, 2014, 48(04): 502-507.
[6]	王盛炜，徐雪松，姚宝恒，连琏. 针对立管重入井过程中等路径段加速度的改进型蚁群优化算法[J]. 上海交通大学学报（自然版）, 2013, 47(10): 1585-1590.
[7]	李真, 陈秀华, 汪海. 基于蚁群算法的复合材料层合板屈曲优化[J]. 上海交通大学学报（自然版）, 2012, 46(05): 768-773.
[8]	胡凯林, 李平. 基于改进蚁群算法的炼铁原料混匀过程调度优化[J]. 上海交通大学学报（自然版）, 2011, 45(08): 1105-112.
[9]	王慧林, 冉承新, 黄维, 马满好. 一种变步长前瞻性电子侦察卫星引导调度方法[J]. 上海交通大学学报（自然版）, 2011, 45(07): 954-960.
[10]	高守玮,杨叶青,张卫东. 基于改进蚁群算法的巡航导弹三维航迹规划 [J]. 上海交通大学学报（自然版）, 2010, 44(09): 1292-1296.
[11]	郭乘涛,江志斌. 应用混合蚁群算法求解并行批处理机组批与调度问题 [J]. 上海交通大学学报（自然版）, 2010, 44(08): 1068-1073.
[12]	胡燕海,严隽琪，马登哲，叶飞帆 . 基于智能算法的制造系统通用作业调度方法[J]. 上海交通大学学报（自然版）, 2008, 42(10): 1608-1612.
[13]	姚世清,江志斌,郭乘涛,胡鸿韬. 晶圆制造系统中Lot加工序列优化的蚁群算法[J]. 上海交通大学学报（自然版）, 2008, 42(10): 1655-1659.

蚁群算法求解离散最小约束去除问题

Ant Colony Algorithm for Solving Discrete Minimum Constraint Removal (MCR) Problem

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价