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

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

CLC Number:

TP 393

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.

References

［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]	BI Zhongqin, YU Xiaowan, WANG Baonan, HUANG Wentao, ZHANG Dan, DONG Zhen. Fast Fault Location Technology for Distribution Network Based on Quantum Ant Colony Algorithm [J]. Journal of Shanghai Jiao Tong University, 2024, 58(5): 693-708.
[2]	LI Erchao∗ (李二超), QI Kuankuan (齐款款). Ant Colony Algorithm Path Planning Based on Grid Feature Point Extraction [J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 86-99.
[3]	LIANG Fengyang, YANG Yijun, LIU Gonglong, WAN Bing, GAO Wangsheng. Research on Cooperative Reconnaissance Planning Algorithm of Multi-UAV System [J]. Air & Space Defense, 2021, 4(1): 103-108.
[4]	JIANG Xiaokang, ZHANG Peng, LÜ Youlong, ZHAO Xinming, ZHANG Jie. Hybrid Ant Colony Algorithm for Batch Scheduling in Semiconductor Furnace Operation [J]. Journal of Shanghai Jiaotong University, 2020, 54(8): 792-804.
[5]	LI Cuiming，GONG Jun，NIU Wancai，WANG Chong. Combinatorial Optimization of Spray Painting Robot Tool Trajectory Based on Improved Membership Cloud Models Ant Colony Algorithm [J]. Journal of Shanghai Jiaotong University, 2015, 49(03): 387-391.
[6]	WANG Shengwei,XU Xuesong,YAO Baoheng,LIAN Lian. Improved Ant Colony Optimization for Accelerations of Equal-length Paths of Riser Re-entry [J]. Journal of Shanghai Jiaotong University, 2013, 47(10): 1585-1590.
[7]	WANG Hui-Lin, RAN Cheng-Xin, HUANG Wei, MA Man-Hao. A Time Step Alterable and Predicative Electronic Reconnaissance Satellite Guiding Scheduling Technique [J]. Journal of Shanghai Jiaotong University, 2011, 45(07): 954-960.
[8]	GAO Shouwei1,2,YANG Yeqing1,ZHANG Weidong1 . Trajectory Planning for Cruise Missile in ThreeDimensional Space Based on Improved Ant Colony Algorithm [J]. Journal of Shanghai Jiaotong University, 2010, 44(09): 1292-1296.