Title: Finding Curvature-Constrained Paths that Avoid Polygonal Obstacles
Speaker: Jonathan Backer
Abstract Robots that explore the surface of Mars and that assemble cars in factories must be autonomous. In exploration, the environment may be unknown or changing, and the effect of an action may be uncertain. In industry, the opposite is true: the relation between the robot and its environment is often known in great detail. The major challenges in such settings are the curse of dimensionality and nonholonomic constraints. Intuitively, the former means that there are too many actions from which to choose ( e.g. which joint of the Canadarm do you move first), and the latter means that slightly changing the relation between robot and environment may require a complicated action (e.g. moving 15 centimeters closer to the curb when parallel parking). The focus of our research is on this last difficulty: nonholonomic constraints.

The problem motivating our research is moving a car-like robot from one state (position and orientation) to another while avoiding obstacles. The midpoint of the rear axle of a car traces a two-dimensional curve as the car moves forward. This traced path has bounded-curvature ( i.e. its direction does not change too quickly relative to the distance traveled) because of the car's limited turning radius. To permit rigorous analysis, I plan bounded-curvature paths in a simplified setting: the robot is a point that can only move forward and it must avoid polygonal obstacles in the two-dimensional plane. The restriction to forward motion is common; it is made because reverse motion is symmetric to forward motion ( i.e. understanding one leads to understanding the other) and permitting reversals eases the nonholonomic constraint.

One motion-planning problem is determining feasibility: does a bounded-curvature path exist? The previous best known result for determining feasibility takes exponential time in the obstacle complexity. Moreover, a path is not returned, just a yes/no answer.

We describe an algorithm to .nd a unit-curvature path between speci.ed states in an arbitrary polygonal domain. Whenever such a path exists, the algorithm returns an explicit description of one such path in time that is polynomial in $n$ (the number of features of the domain), $m$ (the precision of the input) and $k$ (the number of turns on the simplest path between states).