Skip to main navigation menu Skip to main content Skip to site footer


Vol. 2 No. 1 (2015)

On The Shortest Collision-Free Path Planning for Manipulator Based on Circular Obstacle Region

May 10, 2015


A model of collision-free path planning for manipulator¢‚¬„¢s end-effectors based on circular obstacle regions and its corresponding algorithm to search the shortest collision-free path are presented in this paper. As the shortest one, the shortest collision-free path can be found from all the relative shortest collision-free paths whose definition and properties are provided as well in this paper. In order to find the relative shortest collision-free path, some algorithms on finding the common tangent of two circles and checking whether it lies on a certain relative shortest collision-free path are given. The searching algorithm of the shortest collision-free path is formed by integration of the algorithms. The searching algorithm does not contain any iterative procedure, and consequently it can effectively establish shortest collision-free paths for an acceptable short time. The searching algorithm can also avoid the trap of local minimum, and obtain the shortest collision-free path represented by a smooth and continuous curve connecting starting point and target point of the manipulator¢‚¬„¢s end-effectors.In order to deal with the collision-free path planning based on non-circular obstacle regions, the concept of expanded circle is introduced, and the above-mentioned collision-free path planning method based on circular obstacle regions is generalized to non-circular obstacle regions. To resolve the intersection problem of the expanded circles, a method to surround an obstacle region by multi-circles and their common tangent segments is given in this paper.


  1. Evangelos P, Iakovos P and Ioannis P. Polynomial-based obstacle avoidance techniques for nonholonomic mobile manipulator systems J. Robotics and autonomous systems 2005; 51: 229-247.
  2. Ogren P, Leonard NE. A convergent dynamic window approach to obstacle avoidance
  3. Falen BR, Warren WH. Behavioral dynamics of steering, obstacle avoidance, and route selection
  4. Fajen BR, Warrem WH, Termizer S, et al. A dynamical model of steering, obstacle avoidance, and route selection
  5. Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths
  6. Tatsuya O, Pipaporn E, Liang Z, Hiroshi N. An A* Algorithm Framework for the Point-to-Point Time-Dependent Shortest Path Problem
  7. Takahashi O,Schilling RJ. Motion planning in a plane using generalized Voronoi diagrams
  8. Hou E, Zheng D. Mobile robot path planning based on hierarching hexagonal decomposition and artificial potential fields
  9. Schwartz JT, Sharir M. On the Piano Movers' problem: I. The case if a two-dimensional rigid polygonal body moving amidst polygonal barriers
  10. Valavanis KP, Hebert T, Kolluru R, Tsourveloudis N. Mobile robot navigation in 2-D dynamic environments using an electrostatic potential field
  11. Russell S, Norvig P. Artificial intelligence: a modern approach
  12. Dorigo M, Bonabeau E, Theraulaz G.. Ant algorithms and stigmergy[J
  13. Gemeinder M, Gerke M. GA-based path planning for mobile robot systems employing an active search algorithm. Applied soft computing 2003; 3: 149-158.
  14. Tian L, Collins C. An effective robot trajectory planning method using a genetic algorithm
  15. Huseyin C, Halim C. A hybrid harmony search and TRANSYT hill climbing algorithm for signalized stochastic equilibrium transportation networks J. Transportation research part C: emerging technologies 2012; 25(12): 152-167.
  16. Jonathan A and Manuel V. Steepest ascent hill climbing for portfolio selection J. Lecture notes in computer science 2012; 7248(1): 145-154.
  17. Krispin A, Davies A and Graeme N. Rapid control selection through hill-climbing methods J. Lecture notes in computer science 2012; 7507(1): 571-580.
  18. Mark de B, Otfried C, Marc van K, Mark O. Computational geometry: algorithms and applications M. Berlin Heidelberg: Springer-Verlag, 2008.
  19. Neaimeh M, Hill G, Hübner Y, et al. Routing systems to extend the driving range of electric vehicles J. IET Intelligent Transport Systems 2013; 7(3): 327-336.
  20. Klie T, Straub F. Integrating SNMP Agents with XML-based Management Systems J. IEEE Communications Magazine, 2004; 42(7): 76-83.
  21. An K, Zheng YL and, Qiu ZL. A New Algorithm Solution to the Shortest Path Problem of Weighting Directed GraphMethod of Forward Graph J. Journal of Hebei Normal University(Natural Science Edition) 2000; 24(1): 23-24.(in Chinese).