Geodesic problems for mobile robots

As mobile robots operate with limited resources which they carry on-board in large obstructed environments, their success is dependent on how efficiently they move while they avoid collision with obstacles and other robots. Moving optimally is the ultimate efficiency a mobile robot can achieve. Therefore, planning optimal motions and devising optimal coordination strategies are two important and challenging fundamental problems in mobile robotics, which have received significant attention in the last couple of decades. Both of those problems can be reduced to shortest path, or equivalently geodesic, problems in appropriate geometric settings. Geodesic problems have been studied in two disciplines: (1) optimal control theory, and (2) computational geometry. Optimal control theory has focused on the differential constraints of robotic systems, while computational geometry has focused on shortest path problems in an environment with obstacles. Optimal control theory has historically disregarded obstacles in the environment, and computational geometry does not consider dynamics of the robotic system, various optimality criteria, or multi-objective optimality. While each discipline has its own powerful tools to address some geodesic problems, there is a large class of problems that cannot be solved using existing algorithms and methods. We introduce a unified approach that is inspired by main results in both disciplines. In this dissertation, we demonstrate our technique, which combines the celebrated Pontryagin Maximum Principle from optimal control theory with visibility graph methods from computational geometry, by solving three geodesic problems for mobile robots: (1) geodesics for the differential drive among obstacles, (2) geodesics for a kinematic airplane, and (3) optimal coordination of two polygonal robots moving on a predetermined network of paths.; We consider the differential drive because it is ubiquitous in mobile robotics. To obtain a well-defined notion of shortest, the total amount of wheel rotation is optimized. We analytically characterize minimum wheel- rotation trajectories in the absence of obstacles, and identify 52 different minimum wheel-rotation trajectories. In the presence of obstacles, every minimum wheel-rotation trajectory is composed of two kinds of subtrajectories: on the boundary of obstacles and in the interior of collision-free space. We prove those subtrajectories that lie in the interior of collision-free space are tangent to the obstacles at both ends. The bitangency condition yields a nonholonomic bitangency graph which is a network of collision-free trajectories in which the solution is sought. In general, our nonholonomic bitangency graph is a 2-dimensional subset of the 3-dimensional configuration space of the robot. Therefore, further optimization or a continuous search may be required to answer queries. However if obstacles are circular and far enough from one another, the graph is a 1-dimensional subset of the configuration space and any graph search algorithm, such as Dijkstra's algorithm, extracts the solution. In the second problem, we introduce a new kinematic airplane model. Our airplane is a natural extention of the Dubins car, and extends it with an additional configuration variable for the altitude. We use the Pontryagin Maximum Principle to analytically characterize geodesics for it. To obtain a notion of shortest, time is optimized. Finally, we present an algorithm for computing optimal coordination of two polygonal robots without differential constraints. Each robot has a reference point that must lie on a network of paths called a roadmap. Each robot wants to move from its given initial location to its goal location without colliding with the other one. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there...