S. Garrido, L. Moreno, M. Abderrahim, and D. Blanco


Motion planning, Fast Marching, non-holonomic vehicles


The Fast Marching based algorithm proposed here solves the problem of finding Feedback Control Laws for mobile robots, including non-holonomic vehicles. It integrates in a single Real-Time Controller the global motion planning tasks and the collision avoidance capabilities required to efficiently move a mobile robot in a dynamic environment. The solution proposed is fast enough to be used in real time and to operate with a laser scanner system at the sensor rate frequency. The method combines map-based and sensor-based planning operations to provide a smooth and reliable motion plan. The method works in two steps: in the first, it uses a Fast Marching technique to propagate a wave from the walls and obstacles to determine a potential of slowness for the robot. In the second step, this slowness map is used as a refractive index to calculate the potential of the propagation of a wave from the robot pose to the goal with time as the last axis. The generated trajectory corresponds to the path of the light ray through a medium with non-homogeneous refraction index. The robot trajectory is calculated on the vector field associ- ated to the potential surface. The computational efficiency of the method allows the planner to operate at high rate sensor frequencies. For small- and medium-scale environments, the proposed method avoids the need for a collision avoidance algorithms plus a global motion planner. As the method works over a smooth vector field, it allows the simple introduction of non-holonomic constraints. This way, the method can be used directly to develop a control scheme for non- holonomic vehicles, e.g., for car-like robots. This enables simplification of the mobile robot architectures, while maintaining good time response, smooth and safe planned trajectories with continuous curvature. The trajectory generated by the planner is the fastest possible to reach the goal position, considering the best path according to the maximum acceptable velocity at each point in the trajectory (path plus velocity).

Important Links:

Go Back