IEEE Robotics & Automation Magazine - September 2011 - 42

This also highlights another important advantage of
reachability analysis: reachable sets are attractive and
intuitive tools for assisting human operators. Tools are
also being developed for complex situations with teams
of multiple human and robotic agents. A significant part
of this research will involve field experiments using a
smartphone-based capture-the-flag game system currently
being developed.
Finally, another project that is being pursued examines
the use of reachability-based tools for robust machine
learning. While many commonly used machine-learning
algorithms demonstrate excellent performance in robotic
tasks, the convergence guarantees associated with these
algorithms are typically asymptotic in nature; few have
guarantees about their robustness under more realistic
assumptions of limited sample sizes. This is particularly
problematic when it is necessary to run these algorithms
online, for example, in a reinforcement learning scenario
where a robot is simulta* neously learning a model
and must make decisions
The ability to generate
about how to act in that
given model. In such a
safety and attainability
scenario, a spurious sample could cause the robot's
guarantees within model
model to temporarily be
incorrect, causing it to
error for control of complex take an unsafe or even
catastrophic action.
robotic systems is a
This situation may be
avoided by combining
powerful tool.
machine-learning tech* niques with reachabilitystyle tools that make use
of physics-based models and reasonable assumptions
about worst-case errors. By doing so, it is hoped that the
resulting toolset will provide the same level of excellent
performance common to machine-learning algorithms,
while simultaneously providing the kinds of guarantees
about safety that are the essence of the reachability-based
techniques described in this article.
The ability to generate safety and attainability guarantees within model error for control of complex robotic
systems is a powerful tool. Such guarantees could be
used in practice to quickly rule out large parts of the system state space as safe and to focus detailed simulation
and testing on scenarios that operate close to the
boundary of the safe set, leading to shorter design and
testing times. Such methods could increase the number
of scenarios in which robotic and other automation
technology can be used, particularly in safety-critical
areas where unexpected or unpredicted robotic behavior
might result in human injury. By using such formal
methods, designers can have increased confidence that
the robotic systems they create will always function in a
safe, reliable manner.
42

IEEE ROBOTICS & AUTOMATION MAGAZINE

SEPTEMBER 2011

Acknowledgments
The authors thank Prof. Ian Mitchell for his insight into
the computational complexity of level set methods. This
research was supported in part by the "Integrating
Collision Avoidance and Tactical Air Traffic Control
Tools" project administered by NASA under grant
NNA06CN22A, in part by the "Modeling and Optimization of Super-Density Multi-Airport Terminal Area
Systems in the Presence of Uncertainty" project administered by NASA under grant 5710002106, in part by the
"Frameworks and Tools for High Confidence Design of
Adaptive, Distributed Embedded Control Systems" project
administered by the AFOSR under MURI grant FA955006-0312, in part by the NSF ActionWebs project under
grant CNS-0931843, and in part by the ONR SMARTS
project under grant N00014-09-1-1051. Additionally, the
authors thank the NSF and the ASEE for their support via
graduate fellowships.
References
[1] J. P. Laumond, P. E. Jacobs, M. Taix, and R. M. Murray, "A motion
planner for nonholonomic mobile robots," IEEE Trans. Robot. Automat.,
vol. 10, no. 5, pp. 577-593, Oct. 1994.
[2] L. Kavraki, P. Svestka, J.-C. Latombe, and M. Overmars,
"Probabilistic roadmaps for path planning in high-dimensional configuration spaces," IEEE Trans. Robot. Automat., vol. 12, no. 4, pp. 566-580,
Aug. 1996.
[3] E. Rimon and D. Koditschek, "Exact robot navigation using artificial
potential functions," IEEE Trans. Robot. Automat., vol. 8, no. 5, pp. 501-
518, Oct. 1992.
[4] T. Lozano-Perez, "Spatial planning: A configuration space approach,"
IEEE Trans. Comput., vol. C-32, no. 2, pp. 108-120, Feb. 1983.
[5] M. Spong and M. Vidyasagar, "Robust linear compensator design for
nonlinear robotic control," IEEE J. Robot. Automat., vol. 3, no. 4, pp. 345-
351, Aug. 1987.
[6] R. M. Murray, L. Zexiang, and S. S. Sastry, A Mathematical Introduction to Robotic Manipulation, 1st ed. Boca Raton, FL: CRC, 1994.
[7] A. Coates, P. Abbeel, and A. Y. Ng, "Apprenticeship learning for helicopter control," Commun. ACM, vol. 52, no. 7, pp. 97-105, 2009.
[8] E. Asarin, O. Maler, and A. Pnueli, "Reachability analysis of dynamical systems having piecewise-constant derivatives," Theor. Comput. Sci.,
vol. 138, no. 1, pp. 35-65, 1995.
[9] C. Tomlin, J. Lygeros, and S. Sastry, "A game theoretic approach to
controller design for hybrid systems," Proc. IEEE, vol. 88, no. 7, pp. 949-
970, July 2000.
[10] J. Ding, E. Li, H. Huang, and C. J. Tomlin, "Reachability-based
synthesis of feedback policies for motion planning under bounded disturbances," in Proc. IEEE Int. Conf. Robotics and Automation (ICRA),
Shanghai, China, May 2011.
[11] S. Prajna, A. Jadbabaie, and G. Pappas, "A framework for worst-case
and stochastic safety verification using barrier certificates," IEEE Trans.
Automat. Contr., vol. 52, no. 8, pp. 1415-1428, Aug. 2007.
[12] A. Bemporad, F. D. Torrisi, and M. Morari, "Optimization-based
verification and stability characterization of piecewise affine and hybrid
systems," in Proc. Hybrid Systems: Computation and Control, 2000,
pp. 45-58.

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