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：
［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): 517.［4］Erickson L H, LaValle S M. A simple, but NPhard, motion planning problem ［C］∥In Proceedings of the TwentySeventh AAAI Conference on Artificial Intelligence (AAAI13), Urbana：AAAI，2013： 13881393.［5］McCarthy Z, Bretl T, Hutchinson S. Proving path nonexistence using sampling and alpha shapes［C］∥In Proceedings of the 2012 IEEE International Conference on Robotics and Automation. Saint Paul：IEEE，ICRA, 2012: 25632569.［6］Gbelbecker 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: 8188.［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: 605611.
［8］Hauser K. On responsiveness, safety, and completeness in realtime motion planning ［J］. Autonomous Robots, 2012, 32(1): 3548.［9］Hauser K. Minimum constraint displacement motion planning ［J］. Robotics: Science and Systems (RSS), 2013，10（2）：15.［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)：5366.［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): 358365.
