Groupe d’études et de recherche en analyse des décisions

G-92-44

On Minimal Length Trajectories for Mobile Robots with Kinematic Constraints

et

The problem of finding a minimal length trajectory (MLT) for a mobile robot has changed in the last five years, as vehicle kinematics have come to be taken into account. The nonholonomic and minimal radius of curvature constraints are the most frequently encountered kinematic constraints. More recently, the possibility of executing backward motion has also been included in the problem. So far, very few algorithms that consider this feature have been developed. The purpose of this paper is to study the characteristics of a MLT for the problem with kinematic constraints and backward motion but without obstacles. We start by proving that a MLT consists only of line segments and arcs of a circle of minimal radius of curvature. Then we prove that, in a MLT, the total length of all clockwise oriented arcs of a circle and the total length of all counterclockwise oriented arcs of a circle are both less than or equal to radians. We also show that, except for one specific case, a MLT cannot contain more than one line segment. Finally, we enumerate all possible types of a MLT. These results will certainly be helpful for developing better algorithms for problems with and without obstacles.

, 36 pages