IEEE Robotics & Automation Magazine - September 2011 - 60

and obstacles.) The geometry of the workspace is used by
triangulating it. We call such an abstraction geometry
using. The workspace is given as a planar straight line
graph (PSLG) to a mesh-generation package (we have
used the triangle package [71]). A PSLG is made of vertices and segments. The Segments are edges whose endpoints are vertices in the PSLG and whose presence in
any mesh generated from the PSLG is enforced. Holes
correspond to the regions that cannot be triangulated. To
ensure that the resulting decomposition is proposition
preserving, the sets describing propositions are given as
segments, and the obstacles are given as holes. Based on
previous experience in solving conventional motion planning problems [59], the workspace is triangulated using
conforming Delaunay triangulation. One such decomposition is shown in Figure 5.
The dual graph of the triangulation is used to construct
transition relations between abstract states. It must be
remarked here that the idea of using a triangulation-based
decomposition of the workspace has been used before [25],
[45]. However, the abstractions used in [25] and [45] need
to satisfy the bisimilarity property [72], while in our work,
this is not required.
The use of geometry for constructing the discrete
abstractions results in abstractions that are larger in size.
As an example, for the problem instance shown in Figure 5
the geometry-ignoring abstraction has eight states,
whereas the triangulation-based decomposition shown in
Figure 5 results in an abstraction with 618 states. To effectively utilize such abstractions in the high-level layer, it is
also important to conduct the high-level search efficiently.
The high-level search technique proposed in [27] (referred
to as reinitialized-search technique) always starts the
search from initial states of the automaton (say z0 ) and
abstraction (say d0 ). This can be expensive for the cases
when the size of search space (A/ 3 M) is large. To reduce
the time spent on high-level search, a lazy-search
technique has been proposed in [29] that starts the search
Regions
of Interest

Obstacles

Decomposition
Using Triangulation

(a)

(b)

Figure 5. (a) Workspace with seven propositions. The sets
shown in blue are labeled with propositions. (b) Triangulationbased decomposition of the workspace. The triangulation-based
decomposition was done using conforming Delaunay
triangulation, resulting in 618 elements in the decomposition.
Also see the "Construction and Exploration of Discrete
Abstraction" section and [28].

IEEE ROBOTICS & AUTOMATION MAGAZINE

SEPTEMBER 2011

from (z0 , d0 ) only when other candidate high-level states
that have been used previously do not look promising.
Instead of reinitializing the search from (z0 , d0 ) every time,
a new high-level plan is being constructed, the lazy
search initializes the search from the previously explored
high-level states. This effectively means that portions of
previously explored plans are reused.
Experiments
The proposed ideas have been tested for solving motion
planning problems involving nonlinear robot models,
complex environments with obstacles, and a variety of LTL
specifications.
Second-order models of a car, a unicycle, and a differential drive have been used as robot models in the experiments. These models are rich enough to capture the key
aspects of the dynamics and have been extensively used for
benchmarking planning algorithms for mobile robots. The
readers are referred to [28] and [29] for more details.
To evaluate the effect of specifications on performance,
three different types of LTL formulas have been considered
in the experiments. The first type is the class of coverage
op
, and nop 2 ½1; 7 is the number of temporal
formulas /ncov
operators in the formula. The coverage formulas deal with
visiting a given set of regions in the workspace without
imposing any constraints on the order of visits. The formula
/ ¼ Fp1 ^ Fp2 is a coverage formula with two temporal
operators. The second type is the class of sequencing formuop
. The sequencing formulas deal with visiting a given
las /nseq
set of regions in the workspace in a given order. The formula
/ ¼ F(p1 ^ F(p2 )) is a sequencing formula with two
temporal operators. The third type is the class of strict
n
sequencing formulas /stopseq . The strict sequencing formulas
deal with visiting a given set of regions in the workspace in a
given order. The formula / ¼ F ðp1 ^ ð(p0 _ p1 )Up2 ÞÞ is a
strict sequencing formula with two temporal operators.
Note that U denotes the strict until operator in the strict
sequencing formula. For constructing the automaton, we
have used the tool scheck [73]. The coverage formulas typically result in the largest automaton and the sequencing formulas in the smallest automaton. As an example, /7cov
results in an automaton with 128 states and 2,186 transitions, /7seq results in an automaton with eight states and 35
transitions, and /7st seq results in an automaton with 29 states
and 569 transitions.
A comparison of performance obtained by using and
ignoring geometry in the construction of the abstraction is
shown in Figure 6. The results indicate that the performance of the approach is affected by not only the length of
the formula but also the type of temporal operators in the
op
)
formula. Problems involving coverage formulas (/ncov
with about six to seven temporal operators take the longest
time to solve.
Although the discrete abstraction can be constructed by
ignoring the geometry of the specifications, there is a
significant improvement in performance if the abstraction

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