Velocity Constraints on the Configuration Space
In this section, it will be assumed that X = , which is a C-space of one or more rigid bodies, as defined in Section 4.2. Differential models in this section are all expressed as constraints on the set of allowable velocities at each point in . This results in first-order differential equations because only velocities are constrained, as opposed to accelerations or higher order derivatives.
C
C
To carefully discuss velocities, it will be assumed that is a smooth manifold, as defined in Section 8.3.2, in addition to a topological manifold, as defined in
C
Section 4.1.2. It may be helpful to keep the cases = R2 and = R3 in mind. The velocities are straightforward to define without resorting to manifold technicalities,
C C
and the dimension is low enough that the concepts can be visualized.
- Implicit vs. Parametric Representations
There are two general ways to represent differential constraints: parametric and implicit. Many parallels can be drawn to the parametric and implicit ways of specifying functions in general. Parametric representations are generally easier to understand and are simpler to use in applications. Implicit representations are more general but are often more difficult to utilize. The intuitive difference is that implicit representations express velocities that are prohibited, whereas parametric representations directly express the velocities that are allowed. In this chapter, a parametric representation is obtained wherever possible; nevertheless, it is impor- tant to understand both.
- Implicit representation
The planar case For purposes of illustration, suppose that = R2. A configu- ration is expressed as q = (x, y) R2, and a velocity is expressed as (x˙ , y˙). Each (x˙ , y˙) is an element of the tangent space Tq (R2), which is a two-dimensional vector space at every (x, y). Think about the kinds of constraints that could be imposed. At each q R2, restricting the set of velocities yields some set U(q) Tq (R2). The parametric and implicit representations will be alternative ways to express U(q) for all q R2.
∈
C
∈
∈ ⊂
Here are some interesting, simple constraints. Each yields a definition of U(q) as the subset of Tq (R2) that satisfies the constraints.
- x˙ > 0: In this case, imagine that you are paddling a boat on a swift river
that flows in the positive x direction. You can obtain any velocity you like in the y direction, but you can never flow against the current. This means that all integral curves increase monotonically in x over time.
- x˙ ≥ 0: This constraint allows you to stop moving in the x direction. A
velocity perpendicular to the current can be obtained (for example, (0, 1)
causes motion with unit speed in the positive y direction).
- x˙
> 0, y˙
> 0: Under this constraint, integral curves must monotonically
increase in both x and y.
- x˙ = 0: In the previous three examples, the set of allowable velocities re-
mained two-dimensional. Under the constraint x˙ = 0, the set of allowable
velocities is only one-dimensional. All vectors of the form (0, y˙) for any y˙ R are allowed. This means that no motion in the x direction is allowed. Start- ing at any (x0, y0), the integral curves will be of the form (x0, y(t)) for all
∈
t ∈ [0, ∞), which confines each one to a vertical line.
- ax˙ + by˙ = 0: This constraint is qualitatively the same as the previous one. The difference is that now the motions can be restricted along any collection of parallel lines by choosing a and b. For example, if a = b = 1, then only diagonal motions are allowed.
- ax˙ + by˙ + c = 0: This constraint is similar to the previous one, however
the behavior is quite different because the integral curves do not coincide. An entire half plane is reached. It also impossible to stop becasue x˙ = y˙ = 0 violates the constraint.
- x˙ 2 + y˙ 2 ≤ 1: This constraint was used in Chapter 8. It has no effect on the existence of solutions to the feasible motion planning problem be- cause motion in any direction is still allowed. The constraint only enforces a maximum speed.
- x˙ 2 + y˙ 2 ≥ 1: This constraint allows motions in any direction and at any speed greater than 1. It is impossible to stop or slow down below unit speed.
Many other constraints can be imagined, including some that define very com-
plicated regions in R2 for each U(q). Ignoring the fact that x˙
and y˙
represent
derivatives, the geometric modeling concepts from Section 3.1 can even be used to
define complicated constraints at each q. In fact, the constraints expressed above
in terms of x˙
and y˙
are simple examples of the semi-algebraic model, which was
introduced in Section 3.1.2. Just replace x and y from that section by x˙ here.
and y˙
If at every q there exists some open set O such that (0, 0) O and O U(q), then there is no effect on the existence of solutions to the feasible motion planning problem. Velocities in all directions are still allowed. This holds true for velocity constraints on any smooth manifold [924].
∈ ⊆
So far, the velocities have been constrained in the same way at every q ∈ R2, which means that U(q) is the same for all q ∈ R2. Constraints of this kind are of
the form g(x˙ , y˙) ⊲⊳ 0, in which ⊲⊳ could be =, <, >, , or , and gi is a function from R2 to R. Typically, the = relation drops the dimension of U(x) by one, and the others usually leave it unchanged.
≤ ≥
Now consider the constraint x˙ = x. This results in a different one-dimensional set, U(q), of allowable velocities at each q R2. At each q = (x, y), the set of allowable velocities must be of the form (x, y˙) for any y˙ R. This means that as x increases, the velocity in the x direction must increase proportionally. Starting
∈
∈
at any positive x value, there is no way to travel to the y-axis. However, starting on the y-axis, the integral curves will always remain on it! Constraints of this kind can generally be expressed as g(x, y, x˙ , y˙) ⊲⊳ 0, which allows the dependency on x or y.
General configuration spaces Velocity constraints can be considered in the same way on a general C-space. Assume that is a smooth manifold (a man- ifold was not required to be smooth in Chapter 4 because derivatives were not needed there). All constraints are expressed using a coordinate neighborhood, as defined in Section 8.3.2. For expressing differential models, this actually makes
C
an n-dimensional manifold look very much like Rn. It is implicitly understood that a change of coordinates may occasionally be needed; however, this does not
complicate the expression of constraints. This makes it possible to ignore many of the manifold technicalities and think about the constraints as if they are applied to Rn.
C
Now consider placing velocity constraints on . Imagine how complicated
velocity constraints could become if any semi-algebraic model is allowed. Velocity constraints on could be as complicated as any obs. It is not even necessary to use algebraic primitives. In general, the constraints can be expressed as
C C
g(q, q˙) ⊲⊳ 0, (13.1)
in which ⊲⊳ could once again be =, <, >, , or . The same expressive power can be maintained even after eliminating some of these relations. For example, any constraint of the form (13.1) can be expressed as a combination of constraints of the form g(q, q˙) = 0 and g(q, q˙) < 0. All of the relations are allowed here, however, to make the formulations simpler.
≤ ≥
Constraints expressed in the form shown in (13.1) are called implicit. As ex- plained in Chapters 3 and 4, it can be very complicated to obtain a parametric representation of the solutions of implicit equations. This was seen, for example, in Section 4.4, in which it was difficult to characterize the set of configurations that satisfy closure constraints. Nevertheless, we will be in a much better position in terms of developing planning algorithms if a parametric representation of the constraints can be obtained. Fortunately, most constraints that are derived from robots, vehicles, and other mechanical systems can be expressed in parametric form.
- Parametric constraints
The parametric way of expressing velocity constraints gives a different interpre- tation to U(q). Rather than directly corresponding to a velocity, each u ∈ U(q)
is interpreted as an abstract action vector. The set of allowable velocities is then obtained through a function that maps an action vector into Tq ( ). This yields the configuration transition equation (or system)
C
q˙ = f(q, u), (13.2)
in which f is a continuous-time version of the state transition function that was developed in Section 2.1. Note that (13.2) actually represents n scalar equations, in which n is the dimension of . The system will nevertheless be referred to as a single equation in the vector sense. Usually, U(q) is fixed for all q . This will be assumed unless otherwise stated. In this case, the fixed action set is denoted as U.
∈ C
C
There are two interesting ways to interpret (13.2):
- Subspace of the tangent space: If q is fixed, then f maps from U into Tq (C). This parameterizes the set of allowable velocities at q because a velocity vector, f(q, u), is obtained for every u ∈ U(q).
- Vector field: If u is fixed, then f can be considered as a function that maps each q ∈ C into Tq (C). This means that f defines a vector field over C for every fixed u ∈ U.
Example 13.1 (Two Interpetations of q˙ = f (q, u)) Suppose that = R2, which yields a two-dimensional velocity vector space at every q = (x, y) R2. Let U = R, and q˙ = f(q, u) be defined as x˙ = u and y˙ = x.
∈
C
To obtain the first interpretation of q˙ = f(q, u), hold q = (x, y) fixed; for each
u U, a velocity vector (x˙ , y˙) = (u, x) is obtained. The set of all allowable velocity vectors at q = (x, y) is
∈
{(x˙ , y˙) ∈ R | y˙ = x}. (13.3)
2
Suppose that q = (1, 2). In this case, any vector of the form (u, 1) for any u R
∈
is allowable.
To obtain the second interpretation, hold u fixed. For example, let u = 1. The vector field (x˙ , y˙) = (1, x) over R2 is obtained. ．
It is important to specify U when defining the configuration transition equation. We previously allowed, but discouraged, the action set to depend on q. Any
differential constraints expressed as q˙ expressed as q˙ = u by defining
= f(q, u) for any U can be alternatively
U(q) = {q˙ ∈ Rn | ∃u ∈ U such that q˙ = f(q, u)} (13.4)
for each q . In this definition, U(q) is not necessarily a subset of U. It is usually more convenient, however, to use the form q˙ = f(q, u) and keep the same U for all q. The common interpretation of U is that it is a set of fixed actions that can be applied from any point in the C-space.
∈ C
In the context of ordinary motion planning, a configuration transition equation did not need to be specifically mentioned. This issue was discussed in Section
8.4. Provided that U contains an open subset that contains the origin, motion in any direction is allowed. The configuration transition equation for basic motion planning was simply q˙ = u. Since this does not impose constraints on the direction, it was not explicitly mentioned. For the coming models in this chapter, constraints will be imposed on the velocities that restrict the possible directions. This requires planning algorithms that handle differential models and is the subject of Chapter 14.
- Conversion from implicit to parametric form
There are trade-offs between the implicit and parametric ways to express dif- ferential constraints. The implicit representation is more general; however, the parametric form is more useful because it explicitly gives the possible actions. For this reason, it is often desirable to derive a parametric representation from an implicit one. Under very general conditions, it is theoretically possible. As will be explained shortly, this is a result of the implicit function theorem. Unfortunately, the theoretical existence of such a conversion does not help in actually perform- ing the transformations. In many cases, it may not be practical to determine a parametric representation.
To model a mechanical system, it is simplest to express constraints in the implicit form and then derive the parametric representation q˙ = f(q, u). So far there has been no appearance of u in the implicit representation. Since u is interpreted as an action, it needs to be specified while deriving the parametric representation. To understand the issues, it is helpful to first assume that all constraints in implicit form are linear equations in q˙ of the form
g1(q)q˙1 + g2(q)q˙2 + · · · + gn(q)q˙n = 0, (13.5)
which are called Pfaffian constraints. These constraints are linear only under the assumption that q is known. It is helpful in the current discussion to imagine that q is fixed at some known value, which means that each of the gi(q) coefficients in (13.5) is a constant.
Suppose that k Pfaffian constraints are given for k n and that they are linearly independent.1 Recall the standard techniques for solving linear equations. If k = n, then a unique solution exists. If k < n, then a continuum of solutions exists, which forms an (n k)-dimensional hyperplane. It is impossible to have k > n because there can be no more than n linearly independent equations.
≤
−
If k = n, only one velocity vector satisfies the constraints for each q . A vector field can therefore be derived from the constraints, and the problem is not interesting from a planning perspective because there is no choice of velocities.
∈ C
If k < n, then n − k components of q˙
can be chosen independently, and then
1If the coefficients are placed into an k × n matrix, its rank is k.
the remaining k are computed to satisfy the Pfaffian constraints (this can be ac- complished using linear algebra techniques such as singular value decomposition [399, 961]). The components of q˙ that can be chosen independently can be con-
sidered as n − k scalar actions. Together these form an (n − k)-dimensional action
vector, u = (u1, . . . , un−k). Suppose without loss of generality that the first n k
−
components of q˙ are specified by u. The configuration transition equation can then
be written as
q˙1 = u1 q˙2 = u2
...
q˙n−k = un−k
q˙n−k+1 = fn−k+1(q, u) q˙n−k+2 = fn−k+2(q, u)
... (13.6)
q˙n = fn(q, u),
in which each fi is a linear function of u and is derived from the Pfaffian constraints
after substituting ui for q˙i for each i from 1 to n − k and then solving for the
remaining components of q˙. For some values of q, the constraints may become
linearly dependent. This only weakens the constraints, which means the dimension of u can be increased at any q for which independence is lost. Such points are usually isolated and will not be considered further.
Example 13.2 (Pfaffian Constraints) Suppose that = R3, and there is one constraint of the form (13.5)
C
2q˙1 − q˙2 − q˙3 = 0. (13.7)
For this problem, n = 3 and k = 1. There are two action variables because
n − k = 2. The configuration transition equation is
q˙1 = u1
q˙2 = u2
q˙3 = 2u1 − u2,
(13.8)
in which the last component was obtained by substituting u1 and u2, respectively, for q˙1 and q˙2 in (13.7) and then solving for q˙3.
The constraint given in (13.7) does not even depend on q. The same ideas apply for more general Pfaffian constraints, such as
(cos q3)q˙1 − (sin q3)q˙2 − q˙3 = 0. (13.9)
Following the same procedure, the configuration transition equation becomes
q˙1 = u1
q˙2 = u2
q˙3 = (cos q3)u1 − (sin q3)u2.
(13.10)
．
The ideas presented so far naturally extend to equality constraints that are not linear in x˙ . At each q, an (n − k)-dimensional set of actions, U(q), is guaranteed
to exist if the Jacobian ∂(g1, . . . , gk)/∂(q˙1, . . . , q˙n) (recall (6.28) or see [508]) of the constraint functions has rank k at q. This follows from the implicit function theorem [508].
Suppose that there are inequality constraints of the form g(q, q˙) 0, in addition to equality constraints. Using the previous concepts, the actions may once again be assigned directly as q˙i = ui for all i such that 1 i n k. Without inequality
≤
≤ ≤ −
constraints, there are no constraints on u, which means that U = Rn. Since u is
interpreted as an input to some physical system, U will often be constrained. In a
physical system, for example, the amount of energy consumed may be proportional to u. After performing the q˙i = ui substitutions, the inequality constraints indicate limits on u. These limits are expressed in terms of q and the remaining components of q˙, which are the variables q˙n−k+1, . . ., q˙n. For many problems, the inequality constraints are simple enough that constraints directly on U can be derived. For example, if u1 represents scalar acceleration applied to a car, then it may have a simple bound such as u1 1.
| | ≤
One final complication that sometimes occurs is that the action variables may already be specified in the equality constraints: g(q, q˙, u) = 0. In this case, imagine once again that q is fixed. If there are k independent constraints, then by the im- plicit function theorem, q˙ can be solved to yield q˙ = f(q, u) (although theoretically possible, it may be difficult in practice). If the Jacobian ∂(f1, . . . , fn)/∂(u1, . . . , uk) has rank k at q, then actions can be applied to yield any velocity on a k-dimensional
hyperplane in Tq (C). If k = n, then there are enough independent action variables
to overcome the constraints. Any velocity in Tq ( ) can be achieved through a choice of u. This is true only if there are no inequality constraints on U.
C
- Kinematics for Wheeled Systems
The most common family of examples in robotics arises from wheels that are required to roll in the direction they are pointing. Most wheels are not designed to slide sideways. This imposes velocity constraints on rolling vehicles. As a result, there are usually less action variables than degrees of freedom. Such systems are therefore called underactuated. It is interesting that, in many cases, vehicles can execute motions that overcome the constraint. For example, a car can parallel park itself anywhere that it could reach if all four wheels could turn to any orientation. This leads to formal concepts such as nonholonomic constraints and small-time local controllability, which are covered in Section 15.4.
- 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
Figure 13.1: The simple car has three degrees of freedom, but the velocity space at any configuration is only two-dimensional.
to park a car. The complicated maneuvers for parking a simple car arise because of rolling constraints.
The car can be imagined as a rigid body that moves in the plane. Therefore, its C-space is = R2 S1. Figure 13.1 indicates several parameters associated with the car. A configuration is denoted by q = (x, y, θ). 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) speed2 of the car. Let φ 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
C ×
angle is fixed at φ, the car travels in a circular motion, in which the radius of the circle is ρ. Note that ρ can be determined from the intersection of the two axes
shown in Figure 13.1 (the angle between these axes is |φ|).
Using the current notation, the task is to represent the motion of the car as a set of equations of the form
x˙ = f1(x, y, θ, s, φ)
y˙ = f2(x, y, θ, s, φ)
θ˙ = f3(x, y, θ, s, φ).
(13.11)
In a small time interval, ∆t, the car must move approximately in the direction that the rear wheels are pointing. In the limit as ∆t tends to zero, this implies that dy/dx = tan θ. Since dy/dx = y˙/x˙ and tan θ = sin θ/ cos θ, this condition can
2Having a signed speed is somewhat unorthodox. If the car moves in reverse, then s is
negative. A more correct name for s would be velocity in the x direction of the body frame, but this is too cumbersome.
be written as a Pfaffian constraint (recall (13.5)):
− x˙ sin θ + y˙ cos θ = 0. (13.12)
The constraint is satisfied if x˙
= cos θ and y˙
= sin θ. 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 x˙ = s cos θ and y˙ = s sin θ.
The next task is to derive the equation for θ˙. Let w denote the distance traveled by the car (the integral of speed). As shown in Figure 13.1, ρ 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 = ρdθ. From trigonometry, ρ = L/ tan φ, which implies
tan φ
dθ =
dw. (13.13)
L
Dividing both sides by dt and using the fact that w˙ = s yields
θ˙ = s
L
tan φ. (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 φ are directly specified by the action variables us and uφ, 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 = (us, uφ), is obtained. The configuration transition equation for the simple car is
x˙ = us cos θ y˙ = us sin θ
θ˙ = us tan u .
L φ
(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 = (us, uφ). First suppose that any
us ∈ R is possible. What steering angles are possible? The interval [−π/2, π/2]
is sufficiently large for the steering angle uφ because any other value is equivalent to one between −π/2 and π/2. Steering angles of π/2 and −π/2 are problematic.
To derive the expressions for x˙ and 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φ = π/2). If you are able to pedal, then the tricycle should rotate in place. This means that x˙ = 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 φ = π/2. Therefore, the simple car should have a maximum steering angle, φmax < π/2, and we require that |φ| ≤ φmax. Observe from Figure
13.1 that a maximum steering angle implies a minimum turning radius, ρmin. For the case of a tricycle, ρ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 us. 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 us 1 can be placed on the speed without affecting the configurations that it can reach. The speed can even be constrained
| | ≤
as us ∈ {−1, 0, 1} without destroying reachability. Be careful, however, about a
bound such as 0 us 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:
Tricycle: U = [−1, 1] × [−π/2, π/2]. Assuming front-wheel drive, the “car” can rotate in place if uφ = π/2 or uφ = π/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).
Simple Car [596]: U = [−1, 1] × (−φmax, φmax). By requiring that |uφ| ≤ φmax < π/2, a car with minimum turning radius ρmin = L/ tan φmax is obtained.
Reeds-Shepp Car [814, 923]: Further restrict the speed of the simple car so that us 1, 0, 1 .3 This model intuitively makes us correspond to three discrete “gears”: reverse, park, or forward. An interesting question under this model is: What is the shortest possible path (traversed in R2 by the center of the rear axle) between two configurations in the absence of obstacles? This is answered in Section 15.3.
∈ {− }
Dubins Car [294]: Remove the reverse speed us = −1 from the Reeds- Shepp car to obtain us 0, 1 as the only possible speeds. The shortest paths in R2 for this car are quite different than for the Reeds-Shepp car; see Section 15.3.
∈ { }
3In many works, the speed us = 0 is not included. It appears here so that a proper termination condition can be defined.
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 sim- ple 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 . The Reeds-Shepp car can be ma- neuvered into an arbitrarily small parking space, provided that a small amount of clearance exists. This property is called small-time local controllability and is pre- sented 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.
C
- A differential drive
Most indoor mobile robots do not move like a car. For example, consider the mobile robotics platform shown in Figure 13.2a. This is an example of the most popular way to drive indoor mobile robots. There are two main wheels, each of which is attached to its own motor. A third wheel (not visible in Figure 13.2a) is placed in the rear to passively roll along while preventing the robot from falling over.
To construct a simple model of the constraints that arise from the differential drive, only the distance L between the two wheels, and the wheel radius, r, are necessary. See Figure 13.2b. The action vector u = (ur, ul) directly specifies the two angular wheel velocities (e.g., in radians per second). Consider how the robot moves as different actions are applied. See Figure 13.3. If ul = ur > 0, then the robot moves forward in the direction that the wheels are pointing. The speed is proportional to r. In general, if ul = ur, then the distance traveled over a duration t of time is rtul (because tul is the total angular displacement of the wheels). If ul = ur = 0, then the robot rotates clockwise because the wheels are turning in opposite directions. This motivates the placement of the body-frame origin at the center of the axle between the wheels. By this assignment, no translation occurs if the wheels rotate at the same rate but in opposite directions.
− /
Based on these observations, the configuration transition equation is
r
x˙ = 2 (ul + ur) cos θ r
y˙ = (ul + ur) sin θ
2
(13.16)
θ˙ = r (u − u ). L r l
The translational part contains cos θ and sin θ parts, just like the simple car be- cause the differential drive moves in the direction that its drive wheels are pointing.
x
r
- (b)
Figure 13.2: (a) The Pioneer 3-DX8 (courtesy of ActivMedia Robotics: MobileR- obots.com), and many other mobile robots use a differential drive. In addition to the two drive wheels, a caster wheel (as on the bottom of an office chair) is placed in the rear center to prevent the robot from toppling over. (b) The parameters of a generic differential-drive robot.
(b)
Figure 13.3: (a) Pure translation occurs when both wheels move at the same angu- lar velocity; (b) pure rotation occurs when the wheels move at opposite velocities.
Figure 13.4: The shortest path traversed by the center of the axle is simply the line segment that connects the initial and goal positions in the plane. Rotations appear to be cost-free.
The translation speed depends on the average of the angular wheel velocities. To see this, consider the case in which one wheel is fixed and the other rotates. This initially causes the robot to translate at 1/2 of the speed in comparison to both wheels rotating. The rotational speed θ˙ is proportional to the change in angular wheel speeds. The robot’s rotation rate grows linearly with the wheel radius but reduces linearly with respect to the distance between the wheels.
It is sometimes preferable to transform the action space. Let uω = (ur + ul)/2 and uψ = ur − ul. In this case, uω can be interpreted as an action variable that
means “translate,” and uψ means “rotate.” Using these actions, the configuration transition equation becomes
x˙ = ruω cos θ
y˙ = ruω sin θ (13.17)
θ˙ = r u .
L ψ
In this form, the configuration transition equation resembles (13.15) for the simple car (try setting uψ = tan uφ and us = ruω ). A differential drive can easily simulate the motions of the simple car. For the differential drive, the rotation rate can be
set independently of the translational velocity. The simple car, however, has the speed us appearing in the θ˙ expression. Therefore, the rotation rate depends on the translational velocity.
Recall the question asked about shortest paths for the Reeds-Shepp and Dubins cars. The same question for the differential drive turns out to be uninteresting because the differential drive can cause the center of its axle to follow any con- tinuous path in R2. As depicted in Figure 13.4, it can move between any two configurations by: 1) first rotating itself to point the wheels to the goal position, which causes no translation; 2) translating itself to the goal position; and 3) rotat- ing itself to the desired orientation, which again causes no translation. The total distance traveled by the center of the axle is always the Euclidean distance in R2 between the two desired positions.
x
Figure 13.5: Viewed from above, the unicycle model has an action uω that changes the wheel orientation θ.
This may seem like a strange effect due to the placement of the coordinate origin. Rotations seem to have no cost. This can be fixed by optimizing the total amount of wheel rotation or time required, if the speed is held fixed [64]. Suppose that ur, ul 1, 0, 1 . Determining the minimum time required to travel between two configurations is quite interesting and is covered in Section
∈ {− }
15.3. This properly takes into account the cost of rotating the robot, even if it does not cause a translation.
- A simple unicycle
Consider the simple model of a unicycle, which is shown in Figure 13.5. Ignoring balancing concerns, there are two action variables. The rider of the unicycle can set the pedaling speed and the orientation of the wheel with respect to the z-axis. Let σ denote the pedaling angular velocity, and let r be the wheel radius. The speed of the unicycle is s = rσ. In this model, the speed is set directly by an action variable us (alternatively, the pedaling rate could be an action variable uσ , and the speed is derived as s = ruσ ). Let ω be the angular velocity of the unicycle orientation in the xy plane (hence, ω = θ˙). Let ω be directly set by an action variable uω . The configuration transition equation is
x˙ = us cos θ
y˙ = us sin θ θ˙ = uω .
(13.18)
This is just the differential drive equation (13.17) with L = 1 and the substitution us = ruσ . Thus, a differential drive can simulate a unicycle. This may seem strange; however, it is possible because these models do not consider dynamics.
Figure 13.6: The parameters for a car pulling trailers.
Note that the unicycle can also simulate the simple-car model. Therefore, the tricycle and unicycle models are similar.
- A car pulling trailers
An interesting extension of the simple car can be made by attaching one or more trailers. You may have seen a train of luggage carts on the tarmac at airports. There are many subtle issues for modeling the constraints for these models. The form of equations is very sensitive to the precise point at which the trailer is attached and also on the choice of body frames. One possibility for expressing the kinematics is to use the expressions in Section 3.3; however, these may lead to complications when analyzing the constraints. It is somewhat of an art to find a simple expression of the constraints. The model given here is adapted from [727].4
Consider a simple car that pulls k trailers as shown in Figure 13.6. Each trailer is attached to the center of the rear axle of the body in front of it. The important new parameter is the hitch length di which is the distance from the center of the rear axle of trailer i to the point at which the trailer is hitched to the next body.
Using concepts from Section 3.3.1, the car itself contributes R2 × S1 to C, and each trailer contributes an S1 component to C. The dimension of C is therefore k + 3.
Let θi denote the orientation of the ith trailer, expressed with respect to the world frame.
4The original model required a continuous steering angle.
The configuration transition equation is
x˙ = s cos θ0
y˙ = s sin θ0
θ˙0
s
= tan φ L
θ˙1
...
s
= sin(θ0
d1
s （i−1
n
− θ1)
＼
(13.19)
θ˙i =
di
...
cos(θj−1 − θj )
j=1
sin(θi−1 − θi)
θ˙k =
s
dk
k 1
cos(θj−1 − θj )
（ −
n
＼
j=1
sin(θk−1 − θk).
An interesting variation of this model is to allow the trailer wheels to be steered. For a single trailer, this leads to a model that resembles a firetruck [163].
- Other Examples of Velocity Constraints
The differential models seen so far were obtained from wheels that roll along a planar surface. Many generalizations are possible by considering other ways in which bodies can contact each other. In robotics, many interesting differential models arise in the context of manipulation. This section briefly covers some other examples of velocity constraints on the C-space. Once again, dynamics is neglected for now. Such models are sometimes classified as quasi-static because even though motions occur, some aspects of the model treat the bodies as if they were static. Such models are often realistic when moving at slow enough speeds.
- Pushing a box
Imagine using a differential drive robot to push a box around on the floor, as shown in Figure 13.7a. It is assumed that the box is a convex polygon, one edge of which contacts the front of the robot. There are frictional contacts between the box and floor and also between the box and robot. Suppose that the robot is moving slowly enough so that dynamics are insignificant. It is assumed that the box cannot move unless the robot is moving. This prohibits manipulations such as “kicking” the box across the room. The term stable pushing [12, 671, 681] refers to the case in which the robot moves the box as if the box were rigidly attached to the robot.
As the robot pushes the box, the box may slide or rotate, as shown in Figures 13.7b and 13.7c, respectively. These cases are considered illegal because they do
- Stable pushing (b) Illegal sliding (c) Illegal rotation
Figure 13.7: Lynch and Mason showed that pushing a box is very much like driving the simple car: (a) With careful motions, the box will act as if it is attached to the robot. b) If it turns too sharply, however, the box will slide away; this induces limits on the steering angle. c) The box may alternatively rotate from sharp turns [671].
not constitute stable pushing. What motions of the robot are possible? Begin with the configuration transition equation of the differential drive robot, and then determine which constraints need to be placed on U to maintain stable pushing. Suppose that (13.17) is used. It is clear that only forward motion is possible because the robot immediately breaks contact with the box if the robot moves in the opposite direction. Thus, s must be positive (also, to fit the quasi-static model, s should be small enough so that dynamical effects become insignificant). How should the rotation rate ψ be constrained? Constraints on ψ depend on the friction model (e.g., Coulomb), the shape of the box, and the particular edge that is being pushed. Details on these constraints are given in [671, 681]. This leads to an interval [a, b] [ π/2, π/2], in which a < 0 and b > 0, and it is required that ψ [a, b]. This combination of constraints produces a motion model that is similar to the Dubins car. The main difference is that the maximum steering angle in the left and right directions may be different.
∈
⊆ −
To apply this model for planning, it seems that the C-space should be R2 S1 R2 S1 because there are two rigid bodies. The manipulation planning framework of Section 7.3.2 can be applied to obtain a hybrid system and manipulation graph
×
× ×
that expresses the various ways in which the robot can contact the box or fail to contact the box. For example, the robot may be able to push the box along one of several possible edges. If the robot becomes stuck, it can change the pushing edge to move the box in a new direction.
- Flying an airplane
The Dubins car model from Section 13.1.2 can be extended to 3D worlds to provide a simple aircraft flight model that may be reasonable for air traffic analysis. First suppose that the aircraft maintains a fixed altitude and is capable only of yaw rotations. In this case, (13.15) could be used directly by imposing the constraint
that s = 1 (or some suitable positive speed). This is equivalent to the Dubins car, except that s = 0 is prohibited because it would imply that the aircraft can instantaneously stop in the air. This model assumes that the aircraft is small relative to the C-space. A more precise model should take into account pitch and roll rotations, disturbances, and dynamic effects. These would become important, for example, in studying the flight stability of an aircraft design. Such concerns are neglected here.
Now consider an aircraft that can change its altitude, in addition to executing motions like the Dubins car. In this case let = R3 S1, in which the extra R represents the altitude with respect to flying over a flat surface. A configuration is represented as q = (x, y, z, θ). Let uz denote an action that directly causes a change in the altitude: z˙ = uz . The steering action uφ is the same as in the Dubins car model. The configuration transition equation is
C ×
x˙ = cos θ y˙ = sin θ
For a fixed value of u = (uz , uω ) such that uz
z˙ = uz
θ˙ = uω . (13.20) 0 and uω /= 0, a helical path
results. The central axis of the helix is parallel to the z-axis, and projection of the
path down to the xy plane is a circle or circular arc. Maximum absolute values should be set for uz and uω based on the maximum possible altitude and yaw rate changes of the aircraft.
- Rolling a ball
Instead of a wheel, consider rolling a ball in the plane. Place a ball on a table and try rolling it with your palm placed flat on top of it. It should feel like there are two degrees of freedom: rolling forward and rolling side to side. The ball should not be able to spin in place. The directions can be considered as two action variables. The total degrees of freedom of the ball is five, however, because it can achieve any orientation in SO(3) and any (x, y) position in the plane; thus,
2
C = R × SO(3). Given that there are only two action variables, is it possible to
roll the ball into any configuration? It is shown in [632, 491] that this is possible,
even for the more general problem of one sphere rolling on another (the plane is a special case of a sphere with infinite radius). This problem can actually arise in robotic manipulation when a spherical object come into contact (e.g., a robot hand may have fingers with spherical tips); see [103, 676, 725, 729].
The resulting transition equation was shown in [716] (also see [725]) to be
θ˙ = −u2
φ˙ = u1
cos θ
x˙ = −u1ρ sin ψ − u2ρ cos ψ (13.21)
y˙ = −u1ρ cos ψ + u2ρ sin ψ ψ˙ = −u1 tan θ.
In these equations, x and y are the position on the contact point in the plane, and θ and φ are the position of the contact point in the ball frame and are expressed using spherical coordinates. The radius of the ball is ρ. Finally, ψ expresses the orientation of the ball with respect to the contact point.
- Trapped on a surface
It is possible that the constraints cause the configuration to be trapped on a lower dimensional surface. Let C = R2, and consider the system
x˙ = yu
y˙ = −xu, (13.22)
for (x, y) ∈ R2 and u ∈ U = R. What are the integral curves for a constant action u /= 0? From any point (x, y) ∈ R2, the trajectory follows a circle of radius
/ | |
x2 + y2 centered at the origin. The speed along the circle is determined by u , and the direction is determined by the sign of u. Therefore, (13.22) indicates that the configuration is confined to a circle. Other than that, there are no further constraints.
Suppose that the initial configuration is given as (x0, y0). Since the configura- tion is confined to a circle, the C-space could alternatively be defined as = S1.
C
Each point on S1 can be mapped to the circle that has radius r = /x2 + y2
0
0
and center at (0, 0). In this case, there are no differential constraints on the ve-
locities, provided that motions are trapped on the circle. Any velocity in the one-dimensional tangent space at points on the circle is allowed. This model is equivalent to (13.22).
Now consider the possible trajectories that are constrained to traverse a circle,
h(x, y) = x2 + y2 − r2 = 0. (13.23)
This means that for all time t,
h(x(t), y(t)) = x(t)2 + y(t)2 − r2 = 0. (13.24)
To derive a constraint on velocities, take the derivative with respect to time, which yields
dh(x, y)
dt
= 2xx˙ + 2yy˙ = 0. (13.25)
This is an example of a Pfaffian constraint, as given in (13.5). The parametric form of this differential constraint happens to be (13.22). Any velocity vector that is a multiple of (y, x) satisfies (13.25). When expressed as a differential constraint, the radius r does not matter. This is because it is determined from the initial configuration.
−
What just occurred here is a special case of a completely integrable differential model. In general, if the model q˙ = f(q, u) can be expressed as the time derivative of constraints of the form h(q) = 0, then the configuration transition equation is said to be completely integrable. Obtaining an implicit differential model from
constraints of the form hi(q) = 0 is not difficult. Each constraint is differentiated to obtain
dhi(q) = 0. (13.26)
dt
For example, such constraints arise from closed kinematic chains, as in Section 4.4, and the implicit differential model just expresses the condition that velocities must lie in the tangent space to the constraints. It may be difficult, however, to obtain a parametric form of the differential model. Possible velocity vectors can be computed at any particular q, however, by using the linear algebra techniques described in Section 7.4.1.
It is even quite difficult to determine whether a differential model is completely integrable, which means that the configurations are trapped on a lower dimensional surface. For some systems, to be described by (13.41), this will be solved by the Frobenius Theorem in 15.4.2. If such systems are not completely integrable, they are called nonholonomic; otherwise, they are called holonomic. In general, even if a model is theoretically integrable, actually performing the integration is another issue. In most cases, it is difficult or impossible to integrate the model.
Therefore, it is sometimes important to work directly with constraints in dif- ferential form, even if they are integrable. Furthermore, methods for planning under differential constraints can be applied to problems that have constraints of the form h(q) = 0. This, for example, implies that motion planning for closed kinematic chains can be performed by planning algorithms designed to handle differential constraints.