in which u ¼ (u
s
, u
/
) 2 U is the action; u
s
is the forward
speed, and u
/
is the steering angle. Now U must be
defined. Usually, the steering angle is bounded by some
/
max
< p=2 so that ju
/
j/
max
. For the possible speed
value u
s
, a simple bound is often made. For example
ju
s
j1 or equivalently, U ¼½1, 1, produces a car that
can travel no faster than unit speed. A finite set of values is
often used for planning problems that are taking into
account only the kinematic constraints due to rolling
wheels. Setting U ¼f1, 0, 1g produces what is called the
Reeds-Shepp car, which can travel forward at unit speed,
reverse at unit speed, or stop. By further restricting so that
U ¼f0, 1g, the Dubins car is obtained, which can only
travel forward or stop (this car cannot be parallel parked).
Numerous other models are widely used. Equations
similar to (2) arise for common differential drive robots
(for example, Roombas). Other examples include a car
pulling one or more trailers, three-dimensional (3-D) ball
rolling in the plane, and simple aircraft models.
Now consider how the planning problem has changed.
The transition equation f becomes the interface through
which solution paths must be constructed. We must com-
pute some function
~
u : ½0, t!U that indicates how to
apply actions, so that upon integration, the resulting trajec-
tory
~
q : ½0, t!C will satisfy:
~
q(0) ¼ q
I
,
~
q(t) ¼ q
G
, and
~
q(t
0
) 2C
free
for all t
0
2½0, t. Intuitively, we now have to
steer the configuration into the goal, thereby losing the
freedom of moving in any direction.
Moving to the State Space
The previous section considered what are called kinematic
differential constraints because they arise from the geometry
of rigid body interactions in world. More broadly, we must
consider the differential constraints that account for both
kinematics and dynamics of the robot. This allows velocity
and acceleration constraints to be appropriately modeled,
usually resulting in a transition equation of the form
€
q ¼ h(q,
_
q, u) in which
€
q ¼ d
_
q=dt. Differential equations
that involve higher-order derivatives are usually more diffi-
cult to handle; therefore, we employ a simple trick that con-
verts them into a form involving first derivatives only but at
the expense of introducing more variables and equations.
The simplest and most common case is called the
double integrator. Let C¼R and let
€
q ¼ h(q,
_
q, u) be the
special case
€
q ¼ u. This corresponds, for example, to a
Newtonian point mass accelerating due to an applied force
(recall Newton’s second law, F ¼ ma; here,
€
q ¼ a and
u ¼ F=m). We now convert h into two first-order equa-
tions. Let X ¼ R
2
denote a state space, with coordinates
(x
1
, x
2
) 2 X. Let x
1
¼ q and x
2
¼
_
q. Note that
_
x
1
¼ x
2
and,
using
€
q ¼ u, we have
_
x
2
¼ u. Using vector notation
_
x ¼ (
_
x
1
,
_
x
2
) and x ¼ðx
1
, x
2
Þ, we can interpret
_
x
1
¼ x
2
and
_
x
2
¼ u as a state-transition equation of the form
_
x ¼ f (x, u), (3)
which works the same way as (1) but applies to the new
state space X as opposed to C.
To see the structure more clearly, consider the example
shown in Figure 3. Here, C¼R
2
to account for the posi-
tions of the nonrotatable spacecraft. Three thrusters may
be turned on or off, each applying forces f
l
, f
r
, and f
u
.We
make three binary action variables u
l
, u
f
, and u
u
; each may
take on a value of zero or one to turn off or on the corre-
sponding thruster. Finally, lunar gravity applies a down-
ward force of mg. The following state-transition equation
corresponds to independent double integrators in the hori-
zontal and vertical directions:
_
x
1
¼ x
3
_
x
3
¼
f
s
m
(u
l
f
l
u
r
f
r
),
_
x
2
¼ x
4
_
x
4
¼
u
u
f
u
m
g, (4)
which is in the desired form,
_
x ¼ f (x, u). Here, we have
that x
1
¼ q
1
and x
2
¼ q
2
to account for the position in C.
The components x
3
and x
4
are the time derivatives of x
1
and x
2
, respectively.
For much more complicated robot systems, the basic
structureremainsthesame.Forann-dimensional C-space,
C,thestatespaceX becomes 2n-dimensional. For a state
x 2 X,thefirstn components are precisely the configuration
parameters and the next n components are their correspond-
ing time derivatives. We can hence imagine that x ¼ (q,
_
q).
Other state-space formulations are possible, including the
L
ρ
φ
θ
(x, y )
Figure 2. A simple car has three degrees of freedom, but the
velocity space at any configuration is only two dimensional.
mg
f
u
f
l
f
r
Figure 3. Attempt to land a lunar spacecraft with three
orthogonal thrusters that can be switched on or off. The 2-D
C-space leads to a four-dimensional state space.
110 •
IEEE ROBOTICS & AUTOMATION MAGAZINE
•
JUNE 2011
•