IEEE Robotics & Automation Magazine - September 2011 - 56

problems [3]-[29]. Much of the earlier work has focused
on discrete planning within the AI community [3]-[6].
The system is typically modeled as a graph and is called a
transition system. Nodes represent states and edges represent transitions between states and are labeled by
actions that enable these transitions. The goal specification is described using formalisms such as Stanford
Research Institute Problem Solver [3] and action languages [4], [5]. Among others, the approaches proposed in
[7]-[11] try to combine motion planning with task planning. Reference [12] is one of the earlier attempts to formalize the concept of motion of robots using ideas from the
control theory. This has been followed by the notion of
motion description languages [13], [14], [19] and maneuver
automaton [15], [19].
A class of complex goals impose temporal constraints
on the trajectories for a given system. Such goal specifications are referred as temporal goals in this article. The goal
specification described in Figure 1 is an example of such
goals. A variety of model-checking inspired approaches
have been proposed for solving planning problems involving mobile robots and temporal goals [17]-[30]. These
approaches differ from some of the earlier works [16] in
that the planning problem is considered for mobile robots
with dynamics. The proposed approaches are inspired by
state-of-the-art techniques used for model-checking
computer programs by the formal methods community
[31], [32]. The temporal goals are described using a formal
framework, e.g., linear temporal logic (LTL) [33], computation tree logic [34], and l-calculus [35]. While the idea of
extending the discrete system semantics to continuous and
hybrid systems has been investigated [36], [37], most of
the approaches implement instantiations of the following
two-layer architecture. At the discrete level, a discrete plan
is constructed using a discrete abstract model of the robot
and formal specifications. Model-checking techniques are
used to construct such a plan. The constructed plan is then

p1

p2

p3

Obstacles
Regions of Interest
(Propositions)

Figure 1. An example of planning with complex goals. The sets
shown in blue correspond to the regions of interest. The sets
shown in black are obstacles. The goal specification is "In future,
visit the region where p1 is true, and then visit a region where p2
or p3 is true." The robot shown in the figure is based on a Mars
Rover image. (Photo courtesy of NASA/JPL-Caltech.)

56

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

SEPTEMBER 2011

used by the continuous layer to construct a physically feasible trajectory for the robot.
The specification language, the discrete abstraction of the
robot model, and the planning framework depend on the
particular problem being solved and the kind of guarantees
required. One of the earliest works that used temporal logic
as the specification language for the synthesis of controller
programs for robotic and manufacturing tasks is [17]. Reference [18] investigates the problem of automatic controller
synthesis for a team of mobile robots with high-level objectives described using LTL. The LTL has also been used to
solve multirobot motion planning problems in [22] and
[23]. The issue of construction of a suitable discrete abstraction has been studied independently and extensively in the
formal methods, robotics, hybrid systems, and control
theory communities [19], [37]-[51]. Ideally, one would like
to construct discrete abstractions that are equivalent to the
exact model in terms of observed behaviors, i.e., bisimilar
[41]. However, such abstractions are known to exist only for
very simple robot models where the dynamics are essentially
linear [41]. For most models of interest, the exact equivalence is typically relaxed to an approximate one [46]-[51].
Furthermore, it is not clear if the geometric constraints arising because of robot geometry and obstacles can be incorporated within such notions. An approach that uses local
controllers for motion planning with temporal goals has also
been proposed in [20] and [21].
Inspired by the success of sampling-based algorithms
in solving conventional motion planning problems [1],
[2], a complementary set of techniques have been proposed for the past few years that use sampling-based
algorithms for safety analysis and motion planning of
hybrid and robotic systems [24], [27]-[29], [52]-[59].
An important feature of sampling-based approaches is
that the required controllers for feasible trajectories are
automatically constructed as a result of the exploration
process. Hence, the approaches typically do not require
the existence of a particular class of controllers.
The earliest work on using sampling-based algorithms for
safety falsification [52] has been followed by more recent
works that try to improve the scalability of such algorithms
[57], [58]. Reference [53] has considered traditional motion
planning problems but with hybrid robot dynamics. Extensions of a class of sampling-based algorithms for planning
and control and verification of hybrid and robotic systems,
and solving planning problems in discrete spaces have been
proposed in [54]. The approach proposed in [56] combines
sampling-based algorithms with sensitivity analysis for
verification of high-dimensional nonlinear systems. The
approaches proposed in [24] and [27]-[29] use samplingbased algorithms within sophisticated frameworks for
planning problems involving complex specifications. The
approach proposed in [24] can be used to solve motion planning problems involving l-calculus specifications. An important contribution of this approach is that instead of relying
on a fixed abstraction of the system, a sampling-based



Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2011

IEEE Robotics & Automation Magazine - September 2011 - Cover1
IEEE Robotics & Automation Magazine - September 2011 - Cover2
IEEE Robotics & Automation Magazine - September 2011 - 1
IEEE Robotics & Automation Magazine - September 2011 - 2
IEEE Robotics & Automation Magazine - September 2011 - 3
IEEE Robotics & Automation Magazine - September 2011 - 4
IEEE Robotics & Automation Magazine - September 2011 - 5
IEEE Robotics & Automation Magazine - September 2011 - 6
IEEE Robotics & Automation Magazine - September 2011 - 7
IEEE Robotics & Automation Magazine - September 2011 - 8
IEEE Robotics & Automation Magazine - September 2011 - 9
IEEE Robotics & Automation Magazine - September 2011 - 10
IEEE Robotics & Automation Magazine - September 2011 - 11
IEEE Robotics & Automation Magazine - September 2011 - 12
IEEE Robotics & Automation Magazine - September 2011 - 13
IEEE Robotics & Automation Magazine - September 2011 - 14
IEEE Robotics & Automation Magazine - September 2011 - 15
IEEE Robotics & Automation Magazine - September 2011 - 16
IEEE Robotics & Automation Magazine - September 2011 - 17
IEEE Robotics & Automation Magazine - September 2011 - 18
IEEE Robotics & Automation Magazine - September 2011 - 19
IEEE Robotics & Automation Magazine - September 2011 - 20
IEEE Robotics & Automation Magazine - September 2011 - 21
IEEE Robotics & Automation Magazine - September 2011 - 22
IEEE Robotics & Automation Magazine - September 2011 - 23
IEEE Robotics & Automation Magazine - September 2011 - 24
IEEE Robotics & Automation Magazine - September 2011 - 25
IEEE Robotics & Automation Magazine - September 2011 - 26
IEEE Robotics & Automation Magazine - September 2011 - 27
IEEE Robotics & Automation Magazine - September 2011 - 28
IEEE Robotics & Automation Magazine - September 2011 - 29
IEEE Robotics & Automation Magazine - September 2011 - 30
IEEE Robotics & Automation Magazine - September 2011 - 31
IEEE Robotics & Automation Magazine - September 2011 - 32
IEEE Robotics & Automation Magazine - September 2011 - 33
IEEE Robotics & Automation Magazine - September 2011 - 34
IEEE Robotics & Automation Magazine - September 2011 - 35
IEEE Robotics & Automation Magazine - September 2011 - 36
IEEE Robotics & Automation Magazine - September 2011 - 37
IEEE Robotics & Automation Magazine - September 2011 - 38
IEEE Robotics & Automation Magazine - September 2011 - 39
IEEE Robotics & Automation Magazine - September 2011 - 40
IEEE Robotics & Automation Magazine - September 2011 - 41
IEEE Robotics & Automation Magazine - September 2011 - 42
IEEE Robotics & Automation Magazine - September 2011 - 43
IEEE Robotics & Automation Magazine - September 2011 - 44
IEEE Robotics & Automation Magazine - September 2011 - 45
IEEE Robotics & Automation Magazine - September 2011 - 46
IEEE Robotics & Automation Magazine - September 2011 - 47
IEEE Robotics & Automation Magazine - September 2011 - 48
IEEE Robotics & Automation Magazine - September 2011 - 49
IEEE Robotics & Automation Magazine - September 2011 - 50
IEEE Robotics & Automation Magazine - September 2011 - 51
IEEE Robotics & Automation Magazine - September 2011 - 52
IEEE Robotics & Automation Magazine - September 2011 - 53
IEEE Robotics & Automation Magazine - September 2011 - 54
IEEE Robotics & Automation Magazine - September 2011 - 55
IEEE Robotics & Automation Magazine - September 2011 - 56
IEEE Robotics & Automation Magazine - September 2011 - 57
IEEE Robotics & Automation Magazine - September 2011 - 58
IEEE Robotics & Automation Magazine - September 2011 - 59
IEEE Robotics & Automation Magazine - September 2011 - 60
IEEE Robotics & Automation Magazine - September 2011 - 61
IEEE Robotics & Automation Magazine - September 2011 - 62
IEEE Robotics & Automation Magazine - September 2011 - 63
IEEE Robotics & Automation Magazine - September 2011 - 64
IEEE Robotics & Automation Magazine - September 2011 - 65
IEEE Robotics & Automation Magazine - September 2011 - 66
IEEE Robotics & Automation Magazine - September 2011 - 67
IEEE Robotics & Automation Magazine - September 2011 - 68
IEEE Robotics & Automation Magazine - September 2011 - 69
IEEE Robotics & Automation Magazine - September 2011 - 70
IEEE Robotics & Automation Magazine - September 2011 - 71
IEEE Robotics & Automation Magazine - September 2011 - 72
IEEE Robotics & Automation Magazine - September 2011 - 73
IEEE Robotics & Automation Magazine - September 2011 - 74
IEEE Robotics & Automation Magazine - September 2011 - 75
IEEE Robotics & Automation Magazine - September 2011 - 76
IEEE Robotics & Automation Magazine - September 2011 - 77
IEEE Robotics & Automation Magazine - September 2011 - 78
IEEE Robotics & Automation Magazine - September 2011 - 79
IEEE Robotics & Automation Magazine - September 2011 - 80
IEEE Robotics & Automation Magazine - September 2011 - 81
IEEE Robotics & Automation Magazine - September 2011 - 82
IEEE Robotics & Automation Magazine - September 2011 - 83
IEEE Robotics & Automation Magazine - September 2011 - 84
IEEE Robotics & Automation Magazine - September 2011 - 85
IEEE Robotics & Automation Magazine - September 2011 - 86
IEEE Robotics & Automation Magazine - September 2011 - 87
IEEE Robotics & Automation Magazine - September 2011 - 88
IEEE Robotics & Automation Magazine - September 2011 - 89
IEEE Robotics & Automation Magazine - September 2011 - 90
IEEE Robotics & Automation Magazine - September 2011 - 91
IEEE Robotics & Automation Magazine - September 2011 - 92
IEEE Robotics & Automation Magazine - September 2011 - 93
IEEE Robotics & Automation Magazine - September 2011 - 94
IEEE Robotics & Automation Magazine - September 2011 - 95
IEEE Robotics & Automation Magazine - September 2011 - 96
IEEE Robotics & Automation Magazine - September 2011 - 97
IEEE Robotics & Automation Magazine - September 2011 - 98
IEEE Robotics & Automation Magazine - September 2011 - 99
IEEE Robotics & Automation Magazine - September 2011 - 100
IEEE Robotics & Automation Magazine - September 2011 - 101
IEEE Robotics & Automation Magazine - September 2011 - 102
IEEE Robotics & Automation Magazine - September 2011 - 103
IEEE Robotics & Automation Magazine - September 2011 - 104
IEEE Robotics & Automation Magazine - September 2011 - 105
IEEE Robotics & Automation Magazine - September 2011 - 106
IEEE Robotics & Automation Magazine - September 2011 - 107
IEEE Robotics & Automation Magazine - September 2011 - 108
IEEE Robotics & Automation Magazine - September 2011 - 109
IEEE Robotics & Automation Magazine - September 2011 - 110
IEEE Robotics & Automation Magazine - September 2011 - 111
IEEE Robotics & Automation Magazine - September 2011 - 112
IEEE Robotics & Automation Magazine - September 2011 - 113
IEEE Robotics & Automation Magazine - September 2011 - 114
IEEE Robotics & Automation Magazine - September 2011 - 115
IEEE Robotics & Automation Magazine - September 2011 - 116
IEEE Robotics & Automation Magazine - September 2011 - 117
IEEE Robotics & Automation Magazine - September 2011 - 118
IEEE Robotics & Automation Magazine - September 2011 - 119
IEEE Robotics & Automation Magazine - September 2011 - 120
IEEE Robotics & Automation Magazine - September 2011 - 121
IEEE Robotics & Automation Magazine - September 2011 - 122
IEEE Robotics & Automation Magazine - September 2011 - 123
IEEE Robotics & Automation Magazine - September 2011 - 124
IEEE Robotics & Automation Magazine - September 2011 - 125
IEEE Robotics & Automation Magazine - September 2011 - 126
IEEE Robotics & Automation Magazine - September 2011 - 127
IEEE Robotics & Automation Magazine - September 2011 - 128
IEEE Robotics & Automation Magazine - September 2011 - 129
IEEE Robotics & Automation Magazine - September 2011 - 130
IEEE Robotics & Automation Magazine - September 2011 - 131
IEEE Robotics & Automation Magazine - September 2011 - 132
IEEE Robotics & Automation Magazine - September 2011 - 133
IEEE Robotics & Automation Magazine - September 2011 - 134
IEEE Robotics & Automation Magazine - September 2011 - 135
IEEE Robotics & Automation Magazine - September 2011 - 136
IEEE Robotics & Automation Magazine - September 2011 - Cover3
IEEE Robotics & Automation Magazine - September 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