IEEE Robotics & Automation Magazine - September 2011 - 57
abstraction refinement technique is used. The refinement
procedure is based on incremental sampling of the system
trajectories. In contrast to single-layered [24] and hierarchical
approaches [20]-[22], [25], [30], the framework proposed in
[27] is a multilayered synergistic framework that can be used
for planning and safety falsification of hybrid and robotic systems with LTL specifications.
The approaches proposed in [24], [27]-[29], [52]-[54],
and [56]-[59] trade strong completeness guarantees for scalability and efficiency. This means that while such approaches
can deal with complexities arising because of model nonlinearities and geometric constraints, they may fail to find a solution
in finite time (even if one exists). A class of sampling-based
algorithms have also been recently proposed that provide
stronger completeness guarantees for safety analysis [55], [60].
This article presents a summary of the work in [28] and
[29]. The approach described in this article is motivated by
the following question (Figure 2): "Given the state-of-theart model-checking techniques and sampling-based motion
planning algorithms, how can the two be combined for solving motion planning problems involving complex goals and
robots with complex dynamics?"
The focus is on solving problem instances involving nonlinear robot models with finite geometry, complex workspace
environments, and high-level temporal goals. In this article,
recent research efforts toward solving such problems efficiently using a multilayered synergistic framework [27], [58],
[59] are discussed. An important focus of the current work is
on addressing the scalability issues, both in terms of the complexity of the robot model and high-level specifications.
Multilayered Synergistic Planning
The work on multilayered synergistic planning is an instantiation of the recently proposed planning paradigm [27],
[58], [59]. The paradigm has been used previously for safety
analysis of hybrid systems with reachability specifications
[58] and conventional motion planning involving complex
mobile robot models and environments [59]. The framework
is inspired by previous works [61], [62] that introduced a
discrete search component for solving planning problems.
The framework introduces a discrete component to the
search procedure by synergistically utilizing the discrete
structure present in the problem. The framework consists of the following steps: 1) construction of a discrete
abstraction for the system, 2) high-level planning for the
abstraction using the specifications and exploration
information from a low-level planner, and 3) low-level
sampling-based planning using the physical model and
the suggested high-level plans. Note that there is a twoway exchange of information between the high-level and
low-level planning layers in steps 2) and 3). This kind of
synergy helps to systematically convey information
regarding the physics of the problem from the low-level
layer to the high-level layer. The constraints arising due
to temporal goals are systematically conveyed to the lowlevel layer from the high-level layer using synergy.
The construction of the discrete abstraction and two-way
synergistic interaction between the layers are critical issues
that affect the overall performance of the approach. It has
been experimentally shown in [27] and [28] that, in the
absence of synergy, the overall approach does not scale. As
part of an ongoing research, Bhatia et al. [28], [29] have been
investigating the issue of construction of discrete abstraction
while trying to answer the following question: "How should
the discrete abstraction be constructed and explored in the
high-level search layer such that the overall performance of
the approach improves?" While the idea of breaking the
planning problem into multiple layers is not new, the proposed approach differs from the related approaches [22],
[24], [25], [61]-[63] in that there is a two-way, synergistic
interaction between the different layers of planning.
Basic Framework
The instantiation of the multilayered synergistic framework used for motion planning is shown in Figure 3, and a
short description is given. For more details, the reader is
referred to [28] and [29].
Framework for System and Specifications
The robot is modeled as a dynamical system driven by
exogenous inputs and is denoted by H. The model can be
either continuous or hybrid. In all cases, the robot is
assumed to have a finite geometry. The state space of the
system is denoted by S. Let P ΒΌ fp0 , p1 , p2 , . . . , pN g denote the set of Boolean atomic propositions. Each proposition denotes a region of interest in the workspace for the
robot. Every such region is referred to as a propositional
set. p0 denotes the free region of workspace where no other
propositions are true. The planning problems considered
in the work have a finite horizon. A particular class of LTL
formulas called cosafe LTL formulas can be used to describe the finite-horizon specifications of the system [64].
The cosafe LTL formulas are formulas where any good
trace satisfying the formula has a finite good prefix. A finite
good prefix for a formula is a prefix where all its trace
extensions satisfy the formula [64]. The cosafety formulas
are like the guarantee formulas introduced in [65]. The
temporal goals considered in the work are expressed as
syntactically cosafe LTL formulas using atomic propositions. Syntactically, the cosafe LTL formulas are LTL
High-Level
Description
Low-Level
Description
High-Level
Task
Physical
Robot Model
Formal Logic
Sampling-Based
Algorithms
Figure 2. Combining logic with sampling-based algorithms.
SEPTEMBER 2011
*
IEEE ROBOTICS & AUTOMATION MAGAZINE
*
57
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