This chapter presents a new sensor-based path planner, which gives a fast local or global motion plan capable to incorporate new obstacles data. Within the first step, the safest areas in the environment are extracted by means of a Voronoi Diagram. Within the second step, the fast marching method is applied to the Voronoi extracted areas so as to get the trail. This strategy combines map-based and sensor-based designing operations to supply a reliable motion plan, whereas it operates at the frequency of the sensor. The most interesting characteristics are high speed and reliability, as the map dimensions are reduced to a virtually one-dimensional map and this map represents the safest areas within the environment.
TopIntroduction
Mobile robot motion planning has become a very important research topic since the 1980’s. Many researchers have worked extensively to get efficient ways to solve issues related to this topic. Two different ways can be followed to solve this problem. The first approach considers that the global map (surroundings and obstacle data) and the robot characteristics are known. The second one uses local sensor data and robot characteristics.
In recent years, sensor-based path planning has emerged as a compromise between efficient optimized trajectories and ability to react to unexpected environmental events. Different variations of the classical methods have been implemented to attain an operative sensor-based path planning. One among these techniques is the Voronoi-based path planning.
Many researchers have studied the Voronoi Diagrams. An advantage of Voronoi-based path planning is that it diminishes the problem to one dimension while the trajectories follow the most clearance map. This implies that the trajectories are the safest ones. Moreover, the Voronoi-based paths can be viewed as a type of topological navigation and, as a result of that, it is like the human one in some aspects. However, Voronoi-based strategies have the typical difficulties of drawing the Voronoi Diagram: finding out lines and polygons, finding the vertices and nodes, and making a tree to find the trail. As an alternative to unravel these issues, we propose the employment of image processing techniques.
In order to calculate the trajectory, the new motion planning technique relies on the mixture of a Voronoi Diagram and the expansion of a wave from the beginning point to the goal following the Voronoi Diagram. It uses local sensor data and also the known map of the surroundings.
The Voronoi Diagram is constructed using image processing methods (skeletonization) based on the Breu technique in 2D (Breu, 1995) and Gagvani (1997) in 3D. The Voronoi Diagram (skeleton) is dilated and inverted to get a road map. The following step is to calculate the trajectory within the image generated by the thick Voronoi Diagram employing a wave expansion. The wave expansion is calculated solving the Eikonal equation. The Fast Marching method has been implemented to solve this equation. There are other similar techniques that can also be used for the same purpose (Tsiksitlis, 1995), (Mauch, 2003). After that, the obtained path verifies the smoothness and safety considerations required for mobile robot path planning.
The approach implemented in this work relies on the potential field technique of the wave expansion, which repels a robot far away from obstacles and towards the goal employing a rigorously designed artificial potential function. Since the potential field is like a Lyapunov function, the stability of the system is assured.
Finally, this strategy has been extended to be used with non-holonomic robots. It associates a vector field that permits to use the strategy with non-holonomic robots (the Voronoi Diagram thread has become a road). This is done by employing a Voronoi Diagram thicker than the robot. In this thick diagram, a repulsive potential is made using the propagation of a wave that starts at the edges. This potential field is employed as a slowness or refraction index in a second wave propagation from the goal point up to the actual position of the robot. This potential field is attractive to the goal and repulsive from the perimeters of the thick Voronoi Diagram. There are no different local minima than the destination. This potential and its associated vector field permit the motion planning of the non-holonomic robot.
The main advantages of this technique are:
- •
It is straightforward to implement.
- •
The speed is very high.
- •
The trajectories are smooth.
- •
The trajectories are the safest ones.
- •
It works on-line.
- •
It works with non-holonomic robots.
- •
The technique is complete, i.e., the strategy is capable of finding a path if it exists.