Global path planning of mobile robots based on propagating interface technique

A global collision-free path planning method which employs the propagating interface technique is proposed. To implement the propagating interface method, a measurement function, called the collision probability, is derived to transform the workspace into a potential field. The probability is obtained by mapping the geometrical relationship between a robot and the obstacles into a Gaussian distribution. Therefore, each obstacle in the 2D workspace is modeled as a set of ellipses or circles to simplify the mathematical representation and ease geometric approximation. By means of a series of coordinate and scaling transformations between the mobile robot and the obstacles in the workspace, the collision detection problem in trajectory planning is reduced to testing whether a point representing the mobile robot falls outside or inside the transformed primary convex components of each obstacle. The collection of the associated probability on each grid in the working space forms a potential field. The propagating interface method can search a collision-free path by regarding the probability as a propagating speed by which the interface flows over that grid. Once the interface reaches the target, a gradient-based backward tracing algorithm is implemented to construct an optimal path which has the minimal accumulation of collision probability