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

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.