IEEE Robotics & Automation Magazine - June 2011 - 109
*
steps 1 and 2 or steps 1-3 in one shot; see the "Differential
Constraints" section. The eventual need for feedback in Step 4
motivates the direct computation of a feedback plan, which is
covered in the "Feedback Motion Planning" section.
Another issue with the framework in Figure 1, which is
perhaps more subtle, is that this fixed decomposition of the
overall problem of getting a robot to navigate has artificially
inflated the information requirements. The framework
requires that powerful sensors, combined with strong prior
knowledge, must be providing accurate state estimates at all
times, including the robot configuration, velocity components,
and obstacle models. This unfortunately overlooks a tremendous opportunity to reduce the overall system complexity by
sensing just enough information to complete the task. In this
case, a plan is p : I ! U instead of p : X ! U, in which I
is a specific information space that can be derived from sensor
measurements and from which a complete reconstruction of
the state x(t) 2 X is either impossible or undesirable. The
"Sensing Uncertainty" section introduces sensing, filtering,
and planning from this perspective: The state cannot be fully
estimated, but tasks are nevertheless achieved.
Differential Constraints
In this section, it may help to imagine that the C-space C is
Rn to avoid the manifold technicalities from Part I. In the
models and methods of Part I, it was assumed that a path
can be easily determined between any two configurations
in the absence of obstacles. For example, vertices in the
trapezoidal decomposition approach are connected by a
straight line segment in the collision-free region, Cfree . This
section complicates the problem by introducing differential constraints, which restrict the allowable velocities at
each point in Cfree . These are local constraints in contrast
to the global constraints that arise due to obstacles.
Differential constraints naturally arise from the kinematics and dynamics of robots. Rather than treating them as an
afterthought, this section discusses how to directly model
and incorporate them into the planning process. In this
way, a path is produced that already satisfies the constraints.
Modeling the Constraints
_ y_ ) denote a
For simplicity, suppose C ¼ R2 . Let q_ ¼ (x,
velocity vector in which x_ ¼ dx=dt and y_ ¼ dy=dt. Starting
from any point in R2 , say (0, 0), consider what paths can
possibly
R t be produced by integrating the velocity:
_
~q(t) ¼ 0 q(s)ds.
Here, q_ is interpreted as a function of
time. If no constraints are imposed on q_ (other than requirements for integrability), then the trajectory ~q is virtually
unrestricted. If, however, we require x_ > 0, then the only
trajectories for which x monotonically increases are allowed.
If we further constrain it so that 0 < x_ 1, then the rate at
which x increases is bounded. If time was measured in seconds and R2 in meters, then ~q must cause travel in the x
direction with a rate of no more than 1 m/s.
More generally, we want to express a set of allowable
_ y_ ) for every q ¼ (x, y) 2 R2 . Rather
velocity vectors q_ ¼ (x,
than write a set-valued function with domain R2 , a more
compact, convenient method is to define a function f that
yields q_ as a function of q and a new parameter u:
q_ ¼ f (q, u):
(1)
This results in a velocity-valued function called the
configuration-transition equation, which indicates the
required velocity vector, given q and u. The parameter u is
called an action (or input) and is chosen from a predetermined action space U. Since f is a function of two variables,
there are two convenient interpretations by holding each
variable fixed: 1) if q is held fixed, then each u 2 U produces
a possible velocity q_ at q; in other words, u parameterizes
the set of possible velocities; 2) if u is fixed, then f specifies a
velocity at every q; this results in a vector field over C.
For a common example of the configuration-transition
equation, Figure 2 shows a carlike robot that has the Cspace of a rigid body in the plane: C ¼ R2 3 S1 . The configuration vector is q ¼ (x, y, h). Imagine that the car drives
around slowly (so that dynamics are ignored) in an infinite
parking lot. Let / be the steering angle of the front tires, as
shown in Figure 2. If driven forward, the car will roll along
a circle of radius q. Note that it is impossible to move the
center of the rear axle laterally because the rear wheels
would skid instead of roll. This induces the constraint
y_ =x_ ¼ tan h. This constraint, along with another due to the
steering angle, can be converted into the following form
(see [12, section 13.1.2.1]):
x_ ¼ us cos h
y_ ¼ us sin h
us
h_ ¼ tan u/ ,
L
(2)
Complete Geometric Model of the World
Compute a Collision-Free Path
t : [0, 1] S Cfree
Step 1
Smooth t to Satisfy Differential Constraints
σ : [0, 1] S Cfree
Step 2
Design a Trajectory That Follows σ
~
q : [0, t ] S Cfree
Step 3
~
Design a Feedback Controller to Track q
π:XSU
Step 4
Execute π on the Robot
Figure 1. The long road to using a computed collision-free path.
Note that complete, perfect knowledge of the robot and obstacles
enters in, and sensors are utilized only during the final execution.
JUNE 2011
*
IEEE ROBOTICS & AUTOMATION MAGAZINE
*
109
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2011
IEEE Robotics & Automation Magazine - June 2011 - Cover1
IEEE Robotics & Automation Magazine - June 2011 - Cover2
IEEE Robotics & Automation Magazine - June 2011 - 1
IEEE Robotics & Automation Magazine - June 2011 - 2
IEEE Robotics & Automation Magazine - June 2011 - 3
IEEE Robotics & Automation Magazine - June 2011 - 4
IEEE Robotics & Automation Magazine - June 2011 - 5
IEEE Robotics & Automation Magazine - June 2011 - 6
IEEE Robotics & Automation Magazine - June 2011 - 7
IEEE Robotics & Automation Magazine - June 2011 - 8
IEEE Robotics & Automation Magazine - June 2011 - 9
IEEE Robotics & Automation Magazine - June 2011 - 10
IEEE Robotics & Automation Magazine - June 2011 - 11
IEEE Robotics & Automation Magazine - June 2011 - 12
IEEE Robotics & Automation Magazine - June 2011 - 13
IEEE Robotics & Automation Magazine - June 2011 - 14
IEEE Robotics & Automation Magazine - June 2011 - 15
IEEE Robotics & Automation Magazine - June 2011 - 16
IEEE Robotics & Automation Magazine - June 2011 - 17
IEEE Robotics & Automation Magazine - June 2011 - 18
IEEE Robotics & Automation Magazine - June 2011 - 19
IEEE Robotics & Automation Magazine - June 2011 - 20
IEEE Robotics & Automation Magazine - June 2011 - 21
IEEE Robotics & Automation Magazine - June 2011 - 22
IEEE Robotics & Automation Magazine - June 2011 - 23
IEEE Robotics & Automation Magazine - June 2011 - 24
IEEE Robotics & Automation Magazine - June 2011 - 25
IEEE Robotics & Automation Magazine - June 2011 - 26
IEEE Robotics & Automation Magazine - June 2011 - 27
IEEE Robotics & Automation Magazine - June 2011 - 28
IEEE Robotics & Automation Magazine - June 2011 - 29
IEEE Robotics & Automation Magazine - June 2011 - 30
IEEE Robotics & Automation Magazine - June 2011 - 31
IEEE Robotics & Automation Magazine - June 2011 - 32
IEEE Robotics & Automation Magazine - June 2011 - 33
IEEE Robotics & Automation Magazine - June 2011 - 34
IEEE Robotics & Automation Magazine - June 2011 - 35
IEEE Robotics & Automation Magazine - June 2011 - 36
IEEE Robotics & Automation Magazine - June 2011 - 37
IEEE Robotics & Automation Magazine - June 2011 - 38
IEEE Robotics & Automation Magazine - June 2011 - 39
IEEE Robotics & Automation Magazine - June 2011 - 40
IEEE Robotics & Automation Magazine - June 2011 - 41
IEEE Robotics & Automation Magazine - June 2011 - 42
IEEE Robotics & Automation Magazine - June 2011 - 43
IEEE Robotics & Automation Magazine - June 2011 - 44
IEEE Robotics & Automation Magazine - June 2011 - 45
IEEE Robotics & Automation Magazine - June 2011 - 46
IEEE Robotics & Automation Magazine - June 2011 - 47
IEEE Robotics & Automation Magazine - June 2011 - 48
IEEE Robotics & Automation Magazine - June 2011 - 49
IEEE Robotics & Automation Magazine - June 2011 - 50
IEEE Robotics & Automation Magazine - June 2011 - 51
IEEE Robotics & Automation Magazine - June 2011 - 52
IEEE Robotics & Automation Magazine - June 2011 - 53
IEEE Robotics & Automation Magazine - June 2011 - 54
IEEE Robotics & Automation Magazine - June 2011 - 55
IEEE Robotics & Automation Magazine - June 2011 - 56
IEEE Robotics & Automation Magazine - June 2011 - 57
IEEE Robotics & Automation Magazine - June 2011 - 58
IEEE Robotics & Automation Magazine - June 2011 - 59
IEEE Robotics & Automation Magazine - June 2011 - 60
IEEE Robotics & Automation Magazine - June 2011 - 61
IEEE Robotics & Automation Magazine - June 2011 - 62
IEEE Robotics & Automation Magazine - June 2011 - 63
IEEE Robotics & Automation Magazine - June 2011 - 64
IEEE Robotics & Automation Magazine - June 2011 - 65
IEEE Robotics & Automation Magazine - June 2011 - 66
IEEE Robotics & Automation Magazine - June 2011 - 67
IEEE Robotics & Automation Magazine - June 2011 - 68
IEEE Robotics & Automation Magazine - June 2011 - 69
IEEE Robotics & Automation Magazine - June 2011 - 70
IEEE Robotics & Automation Magazine - June 2011 - 71
IEEE Robotics & Automation Magazine - June 2011 - 72
IEEE Robotics & Automation Magazine - June 2011 - 73
IEEE Robotics & Automation Magazine - June 2011 - 74
IEEE Robotics & Automation Magazine - June 2011 - 75
IEEE Robotics & Automation Magazine - June 2011 - 76
IEEE Robotics & Automation Magazine - June 2011 - 77
IEEE Robotics & Automation Magazine - June 2011 - 78
IEEE Robotics & Automation Magazine - June 2011 - 79
IEEE Robotics & Automation Magazine - June 2011 - 80
IEEE Robotics & Automation Magazine - June 2011 - 81
IEEE Robotics & Automation Magazine - June 2011 - 82
IEEE Robotics & Automation Magazine - June 2011 - 83
IEEE Robotics & Automation Magazine - June 2011 - 84
IEEE Robotics & Automation Magazine - June 2011 - 85
IEEE Robotics & Automation Magazine - June 2011 - 86
IEEE Robotics & Automation Magazine - June 2011 - 87
IEEE Robotics & Automation Magazine - June 2011 - 88
IEEE Robotics & Automation Magazine - June 2011 - 89
IEEE Robotics & Automation Magazine - June 2011 - 90
IEEE Robotics & Automation Magazine - June 2011 - 91
IEEE Robotics & Automation Magazine - June 2011 - 92
IEEE Robotics & Automation Magazine - June 2011 - 93
IEEE Robotics & Automation Magazine - June 2011 - 94
IEEE Robotics & Automation Magazine - June 2011 - 95
IEEE Robotics & Automation Magazine - June 2011 - 96
IEEE Robotics & Automation Magazine - June 2011 - 97
IEEE Robotics & Automation Magazine - June 2011 - 98
IEEE Robotics & Automation Magazine - June 2011 - 99
IEEE Robotics & Automation Magazine - June 2011 - 100
IEEE Robotics & Automation Magazine - June 2011 - 101
IEEE Robotics & Automation Magazine - June 2011 - 102
IEEE Robotics & Automation Magazine - June 2011 - 103
IEEE Robotics & Automation Magazine - June 2011 - 104
IEEE Robotics & Automation Magazine - June 2011 - 105
IEEE Robotics & Automation Magazine - June 2011 - 106
IEEE Robotics & Automation Magazine - June 2011 - 107
IEEE Robotics & Automation Magazine - June 2011 - 108
IEEE Robotics & Automation Magazine - June 2011 - 109
IEEE Robotics & Automation Magazine - June 2011 - 110
IEEE Robotics & Automation Magazine - June 2011 - 111
IEEE Robotics & Automation Magazine - June 2011 - 112
IEEE Robotics & Automation Magazine - June 2011 - 113
IEEE Robotics & Automation Magazine - June 2011 - 114
IEEE Robotics & Automation Magazine - June 2011 - 115
IEEE Robotics & Automation Magazine - June 2011 - 116
IEEE Robotics & Automation Magazine - June 2011 - 117
IEEE Robotics & Automation Magazine - June 2011 - 118
IEEE Robotics & Automation Magazine - June 2011 - 119
IEEE Robotics & Automation Magazine - June 2011 - 120
IEEE Robotics & Automation Magazine - June 2011 - 121
IEEE Robotics & Automation Magazine - June 2011 - 122
IEEE Robotics & Automation Magazine - June 2011 - 123
IEEE Robotics & Automation Magazine - June 2011 - 124
IEEE Robotics & Automation Magazine - June 2011 - 125
IEEE Robotics & Automation Magazine - June 2011 - 126
IEEE Robotics & Automation Magazine - June 2011 - 127
IEEE Robotics & Automation Magazine - June 2011 - 128
IEEE Robotics & Automation Magazine - June 2011 - Cover3
IEEE Robotics & Automation Magazine - June 2011 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2010
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2010
https://www.nxtbookmedia.com