Robot geodesics

There are typically very many feasible paths between a pair of robot configurations. Which ones are the best? We have studied the optimal trajectory problem for simple systems, particularly mobile robots in the plane, and shown that for these simple systems, we can design algorithms that can be much better than more general motion planning approaches, in terms of computational cost, optimality of results, and provable correctness. We are starting to extend these algorithms to more general systems, while retaining some of their best characteristics.

Differential drives and omni-directional vehicles. [Balkcom2002a] describes analytically the time-optimal trajectories for two-wheeled differential drive vehicles, analogously to work by Dubins that describes shortest paths for steered cars. [Balkcom2006a] characterizes the time-optimal trajectories for a common type of omnidirectional vehicle, and shows that in fact, it can be faster to parallel park an omnidirectional vehicle, if the vehicle moves more quickly in some directions than others. [Wang2012a] extends this work to show an analytical method for solving for an optimal trajectory given a particular start and goal. This movie shows a sequence of motions for an omni-directional robot; short subsections of this trajectory are time-optimal between their start and end configurations.

Generalized Dubins cars. Dubins and Reeds-Shepp steered cars, differential drives, and omni-directional vehicles can each be modeled as simple rigid bodies in the plane, with location and orientation. However, differences in mechanical designs lead to different constraints on velocities, and different optimal trajectories. [Furtuna2010] and Furtuna's Ph.D. thesis unify previous work in this area, by completely characterizing the time-optimal trajectories for a general model of rigid bodies in the plane, and developing general-purpose algorithms that can solve for optimal trajectories for these vehicles and variations. [Wang2012b] shows that the difficult inverse kinematics problems that sometimes arise in solving for optimal trajectories can be solved approximately with arbitrary precision.

Optimal trajectories with switching costs. A fundamental difficulty in optimal control is that for some systems, optimal trajectories may not even exist. Consider the problem of moving a heavy park bench. Imagine that we can lift the bench at either end, and rotate around the side that is still on the ground. We can move from one end of the bench to the other, rotating successively around either end. What's the fastest way to move the bench forwards? If there is no cost for switching between sides of the bench, the mover should run back and forth between the two ends infinitely many times, rotating the bench through infinitessimal angles with each move. Similar problems arise for the Reeds-Shepp car among obstacles. Chattering behavior exposes a weakness in the mathematical model of a system. [Lyu2015] shows that if a simple fixed cost is associated with switches between controls, optimal trajectories can still be characterized and computed, while avoiding chattering, even among obstacles.

Graph spanners. As greater and greater computational power is applied to motion planning problems, memory becomes a bottleneck. How can we capture the essential qualities of a configuration space in a small memory-efficient representation that can be stored or transmitted across a network? In the algorithms community, graph spanning algorithms have been developed that allow some edges to be removed from a graph while maintaining a constant approximation ratio between paths in the original graph and in the reduced graph (the spanner). Marble, Dobson, and Bekris showed that a spanner algorithm could be applied to filter the output of a Probabilistic Roadmap (PRM) algorithm, reducing the number of edges stored. [Wang2015a] shows how online spanner algorithms can be adapted to PRMs, allowing sparse roadmaps to be generated very quickly (amortized constant time per edge), while maintaining approximation properties.

Publications