A practical algorithm for robot path planning with imprecise environmental dimensions

Robot path planning problem arises in a variety of industrial application scenarios. In manufacturing automation, we often require a robot to quickly go to its home position from a given initial point while avoiding possible collisions with the environment. In hard disk drive testing, fast recovery following from a robot failure, for example, a motion stop or robot gripper sensor failure, is desired in order to reduce manual intervening and improve production efficiency. In the academic field, under the assumption that the environment dimension is completely known, the robot path planning problem has been solved theoretically using either the complete methods, or the probabilistic algorithms. However, in industrial fields, most commonly used path planning algorithms are still empirical, and are often based on human intuition. There is still a big gap between the state-of-the-art path planning techniques that are already developed in the academic field and the methods used in the industrial fields. This paper reports a practical approach for path planning with an intention to bridge the gap. This approach constructs a set of collision-free milestones iteratively, which gives rise to a partition of robot configuration space such that the collision-free portion of each cell is star-shaped. Then it is straightforward to draw a collision-free path from a point in robot configuration space to one of the collision-free milestones as well as constructing and verifying paths among these milestones.