Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-26T17:39:32.690Z Has data issue: false hasContentIssue false
  • English
  • Français

Robust Motion Planning in Dynamic Environments Based on Sampled-Data Hamilton–Jacobi Reachability

Published online by Cambridge University Press:  14 February 2020

Sébastien Kleff Open the ORCID record for Sébastien Kleff [Opens in a new window]  and
Ning Li
Sébastien Kleff
Affiliation:
Department of Automation, Shanghai Jiao Tong University, Shanghai, 200240, China. E-mail: [email protected] Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai, 200240, China
Ning Li*
Affiliation:
Department of Automation, Shanghai Jiao Tong University, Shanghai, 200240, China. E-mail: [email protected] Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai, 200240, China
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

We propose a novel formal approach to robust motion planning (MP) in dynamic environments based on reachability analysis. While traditional MP methods usually fail to provide formal robust safety and performance guarantees, our approach provably ensures safe task achievement in time-varying and adversarial environments under parametric uncertainty. We leverage recent results on Hamilton–Jacobi (HJ) reachability and differential games in order to compute offline guaranteed motion plans that are compatible with the sampled-data (SD) paradigm. Also, we synthesize online provably robust safety-preserving and target-reaching feedback controls. Unlike earlier applications of reachability analysis to MP, our methodology handles arbitrary time-varying constraints, adversarial agents such as pursuing obstacles or evading targets, and takes into account the robot’s configuration. Furthermore, we use HJ projections in order to reduce significantly the computational burden without trading off safety guarantees. The validity of this approach is demonstrated through the case study of a robot arm subject to measurement errors, which is tasked with safely reaching a goal in a known time-varying workspace while avoiding capture by an unpredictable pursuer. Finally, the performance of the approach and research perspectives are discussed.

Keywords

Robust motion planningReachability analysisSampled-data systemReach-avoid gameHamilton–Jacobi–Isaacs Equation
Type
Articles
Information
Robotica , Volume 38 , Issue 12 , December 2020 , pp. 2151 - 2172
Copyright
Copyright © Cambridge University Press 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Matveev, A. S., Savkin, A. V., Hoy, M. and Wang, C., Safe Robot Navigation Among Moving and Steady Obstacle (Butterworth-Heinemann, Elsevier, Oxford, UK, 2015). ISBN: 978-0-12-803730-0Google Scholar
Lozano-Pérez, T., Mason, M. T. and Taylor, R. H., “Automatic synthesis of fine-motion strategies for robots,” Int. J. Robot. Res. 3(1), 3–24 (1984).CrossRefGoogle Scholar
Latombe, J. C., “Motion Planning with Uncertainty: On the Preimage Backchaining Approach,” In: The Robotics Review (MIT Press, Cambridge, MA, 1989) pp. 55–69.Google Scholar
Isaacs, R., Differential Games. A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization (John Wiley and Sons, New York, 1965).Google Scholar
Mitchell, I. M., “Comparing Forward and Backward Reachability as Tools for Safety Analysis,” In: Hybrid Systems: Computation and Control (Springer, Berlin, Heidelberg, 2007) pp. 428–443.Google Scholar
Tomlin, J., Lygeros, J. and Sastry, S. S., “Controller Synthesis for Hybrid Systems the Hamilton–Jacobi Approach,” Proceedings of the AAAI Spring Symposium, Stanford (1999).Google Scholar
Kaynama, S., “Scalable Techniques for the Computation of Viable and Reachable Sets,” Ph.D. Dissertation (The University Of British Columbia, 2012).Google Scholar
Maidens, J. N., Kaynama, S., Mitchell, I. M., Oishi, M. M. and Dumont, G. A., “Lagrangian methods for approximating the viability kernel in high-dimensional systems,” Automatica 49(7), 2017–2029 (2013).CrossRefGoogle Scholar
Le Guernic, C. and Girard, A., “Reachability analysis of linear systems using support functions,” Nonlinear Anal. Hybrid Syst. 4(2), 250–262 (2010).CrossRefGoogle Scholar
Maler, O., “Computing reachable sets: an introduction,” pp. 1–8 (2008). Available: https://pdfs.semanticscholar.org/2999/49aef669b547a36c091b768cade091d35532.pdf. Google Scholar
Mitchell, I., Bayen, A. and Tomlin, C., “A time-dependent Hamiliton–Jacobi formulation of reachable sets for continuous dynamic games,” IEEE Trans. Autom. Control 50(7), 947–957 (2005).Google Scholar
Margellos, K. and Lygeros, J., “Hamilton–Jacobi formulation for reach-avoid differential games,” IEEE Trans. Autom. Control 56(8), 1849–1861 (2011).CrossRefGoogle Scholar
Bokanowski, O. and Zidani, H., “Minimal Time Problems with Moving Targets and Obstacles,” IFAC Proceedings Volumes (IFAC-PapersOnline), vol. 18, PART 1 (Elsevier, 2011) pp. 2589–2593.CrossRefGoogle Scholar
Bokanowski, O., France, P. C. and Desilles, A., “HJB Approach for Motion Planning and Reachability Analysis,” Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools, vol. 1 (2011) pp. 28–36.Google Scholar
Fisac, J. F., Chen, M., Tomlin, C. J. and Sastry, S. S., “Reach-Avoid Problems with Time-Varying Dynamics, Targets and Constraints,” Proceedings of the 18th International Conference on Hybrid Systems Computation and Control - HSCC’15 (2015) pp. 11–20.Google Scholar
Ding, J. and Tomlin, C. J., “Robust Reach-Avoid Controller Synthesis for Switched Nonlinear Systems,” 49th IEEE Conference on Decision and Control (CDC) (2010).CrossRefGoogle Scholar
Mitchell, I. M., Chen, M. and Oishi, M., “Ensuring Safety of Nonlinear Sampled Data Systems Through Reachability,” IFAC Proceedings Volumes (IFAC-PapersOnline) (2012) pp. 108–114.Google Scholar
Kleff, S. and Li, N., “A Sampled-Data Hamilton-Jacobi Reachability Approach to Safe and Robust Motion Planning,” Proceedings of the 30th Chinese Control and Decision Conference (2018 CCDC) (2018) pp. 3386–3392.Google Scholar
Huang, H., Ding, J., Zhang, W. and Tomlin, C. J., “Automation-assisted capture-the-flag: A differential game approach,” IEEE Trans. Control Syst. Technol. 23(3), 1014–1028 (2015).Google Scholar
Dabadie, C., Kaynama, S. and Tomlin, C. J., “A Practical Reachability-Based Collision Avoidance Algorithm for Sampled-Data Systems: Application to Ground Robots,” IEEE International Conference on Intelligent Robots and Systems (2014) pp. 4161–4168.Google Scholar
Mitchell, I. M., Kaynama, S., Chen, M., and Oishi, M., “Safety preserving control synthesis for sampled data systems,” Nonlinear Anal. Hybrid Syst. Special Issue related to IFAC Conference on Analysis and Design of Hybrid Systems (ADHS 12), 10, 1–174 (2013).Google Scholar
Ding, J., Gillula, J., Huang, H., Vitus, M. P., Zhang, W. and Tomlin, C. J., “Toward Reachability-Based Controller Design for Hybrid Systems in Robotics,” International Symposium on Artificial Intelligence, Robotics and Automation in Space (2011) pp. 1–9.Google Scholar
Mayne, D. Q., “Model predictive control: Recent developments and future promise,” Automatica 50(12), 2967–2986 (2014).CrossRefGoogle Scholar
Majumdar, A., “Funnel libraries for real-time robust feedback motion planning,” Int. J. Robot. Res. 36(8), 947–982 (2017).CrossRefGoogle Scholar
D. Nesic and R. Postoyan, “Nonlinear sampled-data systems,” In: Encyclopedia of Systems and Control (J. Bailleul and T. Samad, eds.) (Springer-Verlag, Berlin, Germany, 2014). Available: https://hal.archives-ouvertes.fr/hal-01104990.CrossRefGoogle Scholar
Bansal, S., Chen, M., Herbert, S. and Tomlin, C. J., “Hamilton-Jacobi Reachability: A Brief Overview and Recent Advances,” 56th Conference on Decision and Control (CDC) (IEEE, 2017).Google Scholar
Chen, M., “High Dimensional Reachability Analysis Addressing the Curse of Dimensionality in Formal Verification,” Ph.D. Dissertation (Electrical Engineering and Computer Sciences, University of California at Berkeley, 2017).Google Scholar
Chen, M., Herbert, S. L., Vashishtha, M., Bansal, S. and Tomlin, C. J., “Decomposition of reachable sets and tubes for a class of nonlinear systems,” IEEE Trans. Autom. Control 63(11), 3675–3688 (2018).CrossRefGoogle Scholar
Fisac, J. F. and Sastry, S. S., “The Pursuit-Evasion-Defense Differential Game in Dynamic Constrained Environments,” 2015 IEEE 54th Annual Conference on Decision and Control (CDC) (2015) pp. 4549–4556.Google Scholar
Zhou, Z., Ding, J., Huang, H., Takei, R. and Tomlin, C., “Efficient path planning algorithms in reach-avoid problems,” Automatica 89, 1–446 (2018).Google Scholar
Chow, Y. T., Darbon, J., Osher, S. and Yin, W., “Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems,” J. Sci. Comput. 73(2–3), 617–643 (2017).CrossRefGoogle Scholar
Bokanowski, O., Garcke, J., Griebel, M. and Klompmaker, I., “An adaptive sparse grid semi-lagrangian scheme for first order Hamilton-Jacobi bellman equations,” J. Sci. Comput. 55(3), 575–605 (2013).CrossRefGoogle Scholar
Kang, W. and Wilcox, L., “A causality free computational method for HJB equations with application to rigid body satellites,” AIAA Guidance, Navigation, and Control Conference (2015) pp. 1–10.Google Scholar
Mitchell, I. M. and Tomlin, C. J., “Overapproximating reachable sets by Hamilton-Jacobi projections,” J. Sci. Comput. 19(1–3), 323–346 (2003).CrossRefGoogle Scholar
Mitchell, I. M., A Toolbox of Level Set Methods Version 1.1 Beta (2005). Available: https://www.cs.ubc.ca/~mitchell/ToolboxLS/index.html. Google Scholar
Ko, N. Y., Leet, B. H. and Ko, M. S., “An approach to robot motion planning for time-varying obstacle avoidance using the view-time concept,” Robotica 11(4), 315–327 (1993).CrossRefGoogle Scholar
Abdel-Malek, K., Yang, J., Blackmore, D. and Joy, K. I., “Swept volumes: Foundation, perspectives, and applications,” Int. J. Shape Model. 12(1), 87–127 (2006).CrossRefGoogle Scholar
Liu, C. and Tomizuka, M., “Designing the Robot Behavior for Safe Human–Robot Interactions,” In: Trends in Control and Decision-Making for Human-Robot Collaboration Systems (W. Yue, ed.) (Springer International Publishing, Cham, 2017) pp. 241–270.CrossRefGoogle Scholar
Gleason, J., Vinod, A. P. and Oishi, M. M. K., “Underapproximation of Reach-Avoid Sets for Discrete-Time Stochastic Systems via Lagrangian Methods,” IEEE 56th Annual Conference on Decision and Control (CDC) (2017) pp. 4283–4290.Google Scholar
Akametalu, A., Kaynama, S., Fisac, J., Zeilinger, M. N., Gillula, J. H. and Tomlin, C. J., “Reachability-Based Safe Learning with Gaussian Processes,” Proceedings of the IEEE Conference on Decision and Control (CDC), 02 (2015) pp. 1424–1431.Google Scholar
Gillula, J. H. and Tomlin, C. J., “Reducing conservativeness in safety guarantees by learning disturbances online: Iterated guaranteed safe online learning,” In: RSS (MIT Press, Cambridge, 2012) pp. 81–88.Google Scholar
Mitchell, I., Bayen, A. M. and Tomlin, C. J., “Validating a Hamilton–Jacobi Approximation to Hybrid System Reachable Sets,” In: Hybrid Systems: Computation and Control (M. D. Di Benedetto and A. Sangiovanni-Vincentelli, eds.), vol. 2034 (Springer Verlag, Berlin, Heidelberg, 2001) pp. 418–432.Google Scholar