IEEE Robotics & Automation Magazine - September 2011 - 62

and [29] indicate that the best performance is obtained
when geometry-using abstractions are used in combination with the lazy high-level search. In fact, for the coverage formula with seven temporal operators, the resulting
value is ten times close to the speedup value. For further
details, the readers are referred to [29].
The proposed ideas can also be used directly for safety
analysis of hybrid and robotic system involving LTL specifications. In fact, the first instantiation of the framework in [27]
has been used for safety falsification of hybrid systems with
LTL specifications. Falsification studies the following problem:
"Can a feasible trajectory for the system be constructed such
that the trajectory violates a given safety condition?" Such a
trajectory is called a counterexample trajectory. The safety
conditions assert that nothing wrong happens to the system.
Falsification is often the focus of model checking in industrial
applications [74]. Experience with industrial formal verification has shown that the ability to exhibit counterexample trajectories is often the most useful part of formal verification,
since it provides designers with scenarios that they did not
consider possible [75].
An instantiation of the multilayered synergistic framework
has been used for reachability-based falsification problems
involving hybrid systems with a large number of discrete
modes (up to 1 million) and nonlinear dynamics in each
discrete mode in [58]. The approach significantly outperforms
single-layered approaches (by orders of magnitude).
The work on reachability-based falsification for hybrid
systems in [58] has inspired an instantiation of the multilayered synergistic planning paradigm for solving traditional motion planning problems in [59]. The approach
treats the motion planning problem as a search problem in
a hybrid space (consisting of both continuous and discrete
components) instead of a purely continuous space. The
continuous search is conducted in the state space of the
system. The discrete search is conducted over an abstraction formed by decomposing the workspace of the robot
using the geometry of the environment. The approach is
shown to outperform the existing single-layered samplingbased planners by up to two orders of magnitude.

variance in performance results. As part of our ongoing
research, we are investigating this issue. There are several
possible directions for future research. First, the specifications in [28] and [29] are described over the workspace of
the robot. Extensions of the proposed ideas to problem
instances involving specifications in the state space of the
robotic system should be investigated. Second, as part of
our current work, we have advocated the use of geometrybased abstractions. Further significant improvements in
performance could be obtained by taking into account the
dynamics of the system. It may be possible to improve the
performance of the approach even further by using predesigned controllers in the low-level search layer. A third
direction of research is on extending the framework to
motion planning with optimal cost trajectories. Extension
of the framework to a broader class of hybrid and robotic
systems with a larger number of discrete modes also
remains an area for future research.
Acknowledgments
We thank Y. Lustig and E. Plaku for many useful comments
and suggestions. The research leading to this work was supported in part by NSF CCF 1018798, NSF IIS 0713623, NSF
DUE 0920721, U.S. ARL W911NF-09-1-0383, NSF EIA0216467, and a partnership among Rice University, Sun
Microsystems, and Sigma Solutions.
References
[1] H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E.
Kavraki, and S. Thrun, Principles of Robot Motion: Theory, Algorithms,
and Implementations. Cambridge MA: MIT Press, 2005.
[2] S. M. LaValle, Planning Algorithms, 1st ed. Cambridge, U.K.:
Cambridge Univ. Press, 2006.
[3] R. E. Fikes and N. J. Nilsson, "STRIPS: A new approach to the application of theorem proving to problem solving," Artif. Intell., vol. 2, no. 3-4,
pp. 189-208, 1971.
[4] M. Gelfond and V. Lifschitz, "Action languages," Electron. Trans. AI,
vol. 2, no. 3-4, pp. 193-210, 1998.
[5] D. McDermott and the AIPS-98 Planning Competition. (1998).
PDDL-The planning domain definition language. [Online]. Available:
www.cs.yale.edu/homes/dvm

Discussion
In this article, an approach for solving motion planning problems involving mobile robots with nonlinear hybrid dynamics and finite geometry, obstacles in the workspace, and highlevel temporal goals has been described. The approach uses
an instantiation of the multilayered synergistic framework
proposed in [27] while addressing two key issues: the construction of the discrete abstraction and its efficient exploration in the high-level search layer. On the basis of the
experimental results, the use of geometry for the construction
of the discrete abstraction is advocated [28], [29]. For the best
performance, it is also recommended to explore such abstractions using efficient high-level search techniques.
As we discussed in the "Experiments" section, an
important area of concern in our current work is the high
62

IEEE ROBOTICS & AUTOMATION MAGAZINE

SEPTEMBER 2011

[6] M. Ghallab, D. Nau, and P. Traverso, Automated Planning: Theory
and Practice. San Mateo, CA: Morgan Kaufmann, 2004.
[7] K. Hauser and J.-C. Latombe, "Integrating task and PRM motion
planning," in Proc. Int. Conf. Automated Planning and Scheduling, Workshop on Bridging the Gap Between Task and Motion Planning, 2009.
[8] L. P. Kaelbling and T. Lozano-Perez, "Hierarchical task and motion
planning in the now," in Proc. IEEE Int. Conf. Robotics and Automation,
Workshop on Mobile Manipulation, 2010, pp. 1470-1477.
[9] E. Plaku and G. D. Hager, "Sampling-based motion and symbolic
action planning with geometric and differential constraints," in Proc. IEEE Int.
Conf. Robotics and Automation, Anchorage, AK, 2010, pp. 5002-5008.
[10] J. Wolfe, B. Marthi, and S. J. Russell, "Combined task and motion
planning for mobile manipulation," in Proc. Int. Conf. Automated Planning and Scheduling, R. I. Brafman, H. Geffner, J. Hoffmann, and H. A.
Kautz, Eds., Toronto, ON: AAAI, 2010, pp. 254-258.

http://www.cs.yale.edu/homes/dvm

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