Shortest paths synthesis for a car-like robot. (English) Zbl 0864.93076

Souères, Philippe; Laumond, Jean-Paul

IEEE Trans. Autom. Control 41, No. 5, 672-688 (1996).

The paper deals with the complete characterization of the shortest paths for a car-like robot.
The model for a car-like robot can be described by the kinematic constraints of a wheeled vehicle moving tangentially to its main axis on trajectories with a minimal turning radius. Only geometry of trajectories is studied – dynamics of the vehicle is ignored.
The paper first summarizes the results in the literature on the problem. The shortest path problem has been treated by a number of authors. It is known (Reeds and Shepp, 1990) that the shortest path may always be chosen among 48 simple paths constituted by at most five pieces which are straight line segments or arcs of a circle with minimal radius. Such simple paths contain at most two cusps. The sufficient family was later reduced to 46. The authors complete the study by providing a way to select inside this family an optimal path to link any two configurations. The construction presented in the paper provides a partition of the configuration space into a finite number of cells. To each cell corresponds an optimal path-type for linking the point to the origin. The partition provides a synthesis of optimal paths.
The solution is obtained by combining Pontryagin’s Maximum Principle (PMP) with geometric reasoning. PMP provides local information and geometric reasoning for global analysis of different wave fronts.

Reviewer: H.Koivo (Tampere)

MSC:

93C85	Automated systems (robots, etc.) in control theory
49N70	Differential games and control
49N75	Pursuit and evasion games

Keywords:

constrained control; Pontryagin’s maximum principle; shortest paths; car-like robot; wheeled vehicle; optimal path; geometric reasoning