Trajectory planning is one of the fundamental problems in mobile robotics. A wide variety of approaches have been proposed over the years to deal with the various issues of this problem.
This thesis presents an original and complete solution to tackle the motion planning problem for nonholonomic mobile robots in two-dimensional space. Given a set of obstacles, an initial and a goal configuration, the problem consists in computing efficiently a physically feasible trajectory that reaches the specified target as fast as possible.
One of the original aspects of this work lies in the decomposition of the general problem into several simpler subproblems, for which very efficient solutions are developed. Their combination provides a complete trajectory planning approach that is one of the most computationally effective method suited for the motion of cylindrically shaped wheeled mobile robots in the presence of polygonal obstacles.
This complete solution consists of three main steps. The first one is aimed at finding a short path that avoids obstacles and manages to reach the destination, without taking into account nonholonomic constraints of the robot. Our path planning method relies on an original refinement procedure of a constrained Delaunay triangulation of the obstacles, that outperforms other existing planning techniques.
The second step consists in interpolating paths into smooth curves that can be followed by a real robot without slowing down excessively. By joining only two arcs of clothoids for moving from one curvature to another, our approach is simpler and also computationally cheaper than other interpolation methods.
Finally, thanks to the introduction of an original discretization scheme, an efficient algorithm for computing a time-optimal speed profile for arbitrary paths is presented. The speed profile that results from this procedure not only allows the robot to follow the synthesized path as fast as possible while taking into account a broad class of velocity and accelerations constraints, but also provides the accurate advance information necessary to implementing coordinated actions during the displacement of the robot (e.g., between the locomotion system and other actuators).