A simple car

One of the easiest examples to understand is the simple car, which is shown in Figure 13.1. We all know that a car cannot drive sideways because the back wheels would have to slide instead of roll. This is why parallel parking is challenging. If all four wheels could be turned simultaneously toward the curb, it would be trivial to park a car. The complicated maneuvers for parking a simple car arise because of rolling constraints.

Figure 13.1: The simple car has three degrees of freedom, but the velocity space at any configuration is only two-dimensional.

The car can be imagined as a rigid body that moves in the plane. Therefore, its C-space is $ {\cal C}= {\mathbb{R}}^2 \times {\mathbb{S}}^1$. Figure 13.1 indicates several parameters associated with the car. A configuration is denoted by $ q = (x,y,\theta)$. The body frame of the car places the origin at the center of rear axle, and the $ x$-axis points along the main axis of the car. Let $ s$ denote the (signed) speed13.2 of the car. Let $ \phi $ denote the steering angle (it is negative for the wheel orientations shown in Figure 13.1). The distance between the front and rear axles is represented as $ L$. If the steering angle is fixed at $ \phi $, the car travels in a circular motion, in which the radius of the circle is $ \rho$. Note that $ \rho$ can be determined from the intersection of the two axes shown in Figure 13.1 (the angle between these axes is $ \vert\phi\vert$).

Using the current notation, the task is to represent the motion of the car as a set of equations of the form

\begin{displaymath}\begin{split}{\dot x}& = f_1(x,y,\theta,s,\phi)  {\dot y}& ...
...,\phi)  {\dot \theta}& = f_3(x,y,\theta,s,\phi) . \end{split}\end{displaymath} (13.11)

In a small time interval, $ \Delta t$, the car must move approximately in the direction that the rear wheels are pointing. In the limit as $ \Delta t$ tends to zero, this implies that $ dy/dx = \tan \theta$. Since $ dy/dx = {\dot y}/{\dot x}$ and $ \tan \theta = \sin\theta/\cos
\theta$, this condition can be written as a Pfaffian constraint (recall (13.5)):

$\displaystyle -{\dot x}\sin \theta + {\dot y}\cos \theta = 0 .$ (13.12)

The constraint is satisfied if $ {\dot x}= \cos \theta$ and $ {\dot y}= \sin
\theta$. Furthermore, any scalar multiple of this solution is also a solution; the scaling factor corresponds directly to the speed $ s$ of the car. Thus, the first two scalar components of the configuration transition equation are $ {\dot x}= s \cos \theta$ and $ {\dot y}= s \sin \theta$.

The next task is to derive the equation for $ {\dot \theta}$. Let $ w$ denote the distance traveled by the car (the integral of speed). As shown in Figure 13.1, $ \rho$ represents the radius of a circle that is traversed by the center of the rear axle, if the steering angle is fixed. Note that $ dw = \rho d\theta$. From trigonometry, $ \rho = L/\tan \phi$, which implies

$\displaystyle d\theta = {\tan \phi \over L} dw .$ (13.13)

Dividing both sides by $ dt$ and using the fact that $ {\dot w}= s$ yields

$\displaystyle {\dot \theta}= {s \over L}   \tan \phi .$ (13.14)

So far, the motion of the car has been modeled, but no action variables have been specified. Suppose that the speed $ s$ and steering angle $ \phi $ are directly specified by the action variables $ u_s$ and $ u_\phi$, respectively. The convention of using a $ u$ variable with the old variable name appearing as a subscript will be followed. This makes it easy to identify the actions in a configuration transition equation. A two-dimensional action vector, $ u = (u_s,u_\phi)$, is obtained. The configuration transition equation for the simple car is

\begin{displaymath}\begin{split}{\dot x}& = u_s \cos\theta  {\dot y}& = u_s \s...
...& = \displaystyle\strut {u_s \over L} \tan u_\phi . \end{split}\end{displaymath} (13.15)

As expressed in (13.15), the transition equation is not yet complete without specifying $ U$, the set of actions of the form $ u = (u_s,u_\phi)$. First suppose that any $ u_s \in {\mathbb{R}}$ is possible. What steering angles are possible? The interval $ [-\pi/2,\pi/2]$ is sufficiently large for the steering angle $ u_\phi$ because any other value is equivalent to one between $ -\pi/2$ and $ \pi/2$. Steering angles of $ \pi/2$ and $ -\pi/2$ are problematic. To derive the expressions for $ {\dot x}$ and $ {\dot y}$, it was assumed that the car moves in the direction that the rear wheels are pointing. Imagine you are sitting on a tricycle and turn the front wheel perpendicular to the rear wheels (assigning $ u_\phi = \pi/2$). If you are able to pedal, then the tricycle should rotate in place. This means that $ {\dot x}= {\dot y}= 0$ because the center of the rear axle does not translate.

This strange behavior is not allowed for a standard automobile. A car with rear-wheel drive would probably skid the front wheels across the pavement. If a car with front-wheel drive attempted this, it should behave as a tricycle; however, this is usually not possible because the front wheels would collide with the front axle when turned to $ \phi = \pi/2$. Therefore, the simple car should have a maximum steering angle, $ \phi_{max} < \pi/2$, and we require that $ \vert\phi\vert \leq
\phi_{max}$. Observe from Figure 13.1 that a maximum steering angle implies a minimum turning radius, $ \rho_{min}$. For the case of a tricycle, $ \rho_{min} = 0$. You may have encountered the problem of a minimum turning radius while trying to make an illegal U-turn. It is sometimes difficult to turn a car around without driving it off of the road.

Now return to the speed $ u_s$. On level pavement, a real vehicle has a top speed, and its behavior should change dramatically depending on the speed. For example, if you want to drive along the minimum turning radius, you should not drive at 140km/hr. It seems that the maximum steering angle should reduce at higher speeds. This enters the realm of dynamics, which will be allowed after phase spaces are introduced in Section 13.2. Following this, some models of cars with dynamics will be covered in Sections 13.2.4 and 13.3.3.

It has been assumed implicitly that the simple car is moving slowly to safely neglect dynamics. A bound such as $ \vert u_s\vert \leq 1$ can be placed on the speed without affecting the configurations that it can reach. The speed can even be constrained as $ u_s \in \{-1,0,1\}$ without destroying reachability. Be careful, however, about a bound such as $ 0 \leq u_s \leq 1$. In this case, the car cannot drive in reverse! This clearly affects the set of reachable configurations. Imagine a car that is facing a wall and is unable to move in reverse. It may be forced to hit the wall as it moves.

Based on these considerations regarding the speed and steering angle, several interesting variations are possible:

  1. [] Tricycle: $ U = [-1,1] \times
[-\pi/2,\pi/2]$. Assuming front-wheel drive, the ``car'' can rotate in place if $ u_\phi = \pi/2$ or $ u_\phi = \pi/2$. This is unrealistic for a simple car. The resulting model is similar to that of the simple unicycle, which appears later in (13.18).
  2. [] Simple Car [596]: $ U = [-1,1] \times
(-\phi_{max},\phi_{max})$. By requiring that $ \vert u_\phi\vert \leq \phi_{max}
< \pi/2$, a car with minimum turning radius $ \rho_{min} =
L/\tan\phi_{max}$ is obtained.
  3. [] Reeds-Shepp Car [814,923]: Further restrict the speed of the simple car so that $ u_s \in \{-1,0,1\}$.13.3 This model intuitively makes $ u_s$ correspond to three discrete ``gears'': reverse, park, or forward. An interesting question under this model is: What is the shortest possible path (traversed in $ {\mathbb{R}}^2$ by the center of the rear axle) between two configurations in the absence of obstacles? This is answered in Section 15.3.
  4. [] Dubins Car [294]: Remove the reverse speed $ u_s = -1$ from the Reeds-Shepp car to obtain $ u_s \in \{0,1\}$ as the only possible speeds. The shortest paths in $ {\mathbb{R}}^2$ for this car are quite different than for the Reeds-Shepp car; see Section 15.3.
The car that was shown in Figure 1.12a of Section 1.2 is even more restricted than the Dubins car because it is additionally forced to turn left.

Basic controllability issues have been studied thoroughly for the simple car. These will be covered in Section 15.4, but it is helpful to develop intuitive notions here to assist in understanding the planning algorithms of Chapter 14. The simple car is considered nonholonomic because there are differential constraints that cannot be completely integrated. This means that the car configurations are not restricted to a lower dimensional subspace of $ {\cal C}$. The Reeds-Shepp car can be maneuvered into an arbitrarily small parking space, provided that a small amount of clearance exists. This property is called small-time local controllability and is presented in Section 15.1.3. The Dubins car is nonholonomic, but it does not possess this property. Imagine the difficulty of parallel parking without using the reverse gear. In an infinitely large parking lot without obstacles, however, the Dubins car can reach any configuration.

Steven M LaValle 2012-04-20