TR061: Controllability of Mobile Robots with Kinematic Constraints

We address the controllability problem for robot systems subject to kinematic constraints on the velocity and its application to path planning. We show that the well-known Controllability Rank Condition Theorem is applicable to these systems when there are inequality constraints on the velocity in addition to equality constraints, and/or when the constraints are non-linear instead of linear. This allows us to infer a whole set of new results on the controllability of robotic systems subject to non-integrable kinematic constraints (called nonholonomic systems). A car with limited steering angle is one example of such a system. For example, we show that:

1) An n-body car system, which consists of a car towing n — 1 trailers, is controllable for n < 4 even if the steering angle is limited.

2) An n-body car (n < 4) that can only turn left is still maneuverable on the right.

3) If there is a path for an n-body car system (n < 4) with limited steering angle in a given environment, then there is another path that uses only the extremal values of the steering angle. We conjecture that these results arc true for all n. However, we have only been able to prove them for n < 4.

The same kind of results as above can also be obtained for any nonholonomic system additionally subject to inequality constraints on the velocity.

We present experiments with simulated nonholonomic systems that illustrate these results. These experiments were conducted by using a general path planner previously described in [Barraquand and Latombe 89b].