What is the shortest or fastest path a mobile robot can follow between two configurations in the unobstructed plane? The answer to this fundamental question is only known analytically for a few planar mobile robots: the Dubins and Reeds-Shepp steered cars, the differential drive, and a particular omnidirectional robot. This paper explores the optimal trajectories for a general parameterized model of a mobile robot that includes each previously-studied vehicle as a special case. The model also allows characterization of the optimal trajectories for several other mobile robot designs for which the optimal trajectories have not been previously explored. The paper applies Pontryagin's Maximum Principle to the generalized robot to find necessary conditions that optimal trajectories must satisfy, and gives geometric interpretations of the conditions. We also present an algorithm that generates and classifies all optimal trajectories for a given design.

Computing optimal paths for mobile robots is an interesting and important problem. This paper presents a method to compute the shortest path for a differential-drive mobile robot, which is a disc, among piecewise smooth and convex obstacles. To obtain a well-defined notion of shortest, the total amount of wheel rotation is optimized. We use recent characterization of minimum wheel-rotation paths for differential-drive mobile robots with no obstacles. We reduce the search for the shortest path to the search on a finite nonholonomic visibility graph. Edges of the graph are either minimum wheel-rotation trajectories inside the free space or trajectories on the boundary of obstacle region. Vertices of the graph are initial and goal configurations and points on the boundary of obstacle region. We call the search graph a nonholonomic visibility graph because the jump condition of the Pontryagin maximum principle gives a necessary condition which is reminiscent of bitangency in well-known visibility graphs. To the best of our knowledge, this is the first progress on the problem

Characterizing optimal paths for mobile robots is an interesting, important, and challenging endeavor. Not only they are interesting with respect to the optimized criteria, but also they offer a family of motion primitives that can be used for motion planning in the presence of obstacles. This paper presents characterization of shortest paths for differential-drive mobile robots, with the goal of classifying solutions in the spirit of Dubins curves and Reeds-Shepp curves for car-like robots. To obtain a well-defined notion of shortest., the total amount of wheel rotation is optimized. Using Pontryagin maximum principle and other tools, we establish the existence of optimal trajectories, and derive the set of optimal paths. Some Reeds-Shepp curves appear in the set of optimal paths, whereas there are optimal paths which are different from Reeds-Shepp curves. To the best of our knowledge, this is the first progress on the problem

We present an algorithm that computes the complete set of Pareto-optimal coordination strategies for two translating polygonal robots in the plane. A collision-free acyclic roadmap of piecewise-linear paths is given on which the two robots move. The robots have a maximum speed and are capable of instantly switching between any two arbitrary speeds. Each robot would like to minimize its travel time independently. The Pareto-optimal solutions are the ones for which there exist no solutions that are better for both robots. The algorithm computes exact solutions in time O(mn/sup 2/ log n), in which m is the number of paths in the roadmap, n is the number of coordination space vertices. An implementation is presented.