{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:56:16Z","timestamp":1747173376608,"version":"3.40.5"},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"12","license":[{"start":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T00:00:00Z","timestamp":1581638400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotica"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>SUMMARY<\/jats:title><jats:p>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\u2013Jacobi (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\u2019s 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.<\/jats:p>","DOI":"10.1017\/s0263574719001905","type":"journal-article","created":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T09:20:50Z","timestamp":1581672050000},"page":"2151-2172","source":"Crossref","is-referenced-by-count":3,"title":["Robust Motion Planning in Dynamic Environments Based on Sampled-Data Hamilton\u2013Jacobi Reachability"],"prefix":"10.1017","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9025-6143","authenticated-orcid":false,"given":"S\u00e9bastien","family":"Kleff","sequence":"first","affiliation":[]},{"given":"Ning","family":"Li","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,2,14]]},"reference":[{"key":"S0263574719001905_ref7","unstructured":"7. Kaynama, S. , \u201cScalable Techniques for the Computation of Viable and Reachable Sets,\u201d Ph.D. Dissertation (The University Of British Columbia, 2012)."},{"key":"S0263574719001905_ref14","unstructured":"14. Bokanowski, O. , France, P. C. and Desilles, A. , \u201cHJB Approach for Motion Planning and Reachability Analysis,\u201d Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools, vol. 1 (2011) pp. 28\u201336."},{"key":"S0263574719001905_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2013.03.020"},{"key":"S0263574719001905_ref22","unstructured":"22. Ding, J. , Gillula, J. , Huang, H. , Vitus, M. P. , Zhang, W. and Tomlin, C. J. , \u201cToward Reachability-Based Controller Design for Hybrid Systems in Robotics,\u201d International Symposium on Artificial Intelligence, Robotics and Automation in Space (2011) pp. 1\u20139."},{"key":"S0263574719001905_ref35","unstructured":"S35. Mitchell, I. M. , A Toolbox of Level Set Methods Version 1.1 Beta (2005). Available: https:\/\/www.cs.ubc.ca\/~mitchell\/ToolboxLS\/index.html."},{"key":"S0263574719001905_ref6","unstructured":"6. Tomlin, J. , Lygeros, J. and Sastry, S. S. , \u201cController Synthesis for Hybrid Systems the Hamilton\u2013Jacobi Approach,\u201d Proceedings of the AAAI Spring Symposium, Stanford (1999)."},{"key":"S0263574719001905_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-012-9648-x"},{"key":"S0263574719001905_ref17","unstructured":"17. Mitchell, I. M. , Chen, M. and Oishi, M. , \u201cEnsuring Safety of Nonlinear Sampled Data Systems Through Reachability,\u201d IFAC Proceedings Volumes (IFAC-PapersOnline) (2012) pp. 108\u2013114."},{"key":"S0263574719001905_ref11","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1109\/TAC.2005.851439","article-title":"A time-dependent Hamiliton\u2013Jacobi formulation of reachable sets for continuous dynamic games","volume":"50","author":"Mitchell","year":"2005","journal-title":"IEEE Trans. Autom. Control"},{"key":"S0263574719001905_ref33","unstructured":"33. Kang, W. and Wilcox, L. , \u201cA causality free computational method for HJB equations with application to rigid body satellites,\u201d AIAA Guidance, Navigation, and Control Conference (2015) pp. 1\u201310."},{"key":"S0263574719001905_ref2","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300101"},{"key":"S0263574719001905_ref37","doi-asserted-by":"publisher","DOI":"10.1142\/S0218654306000858"},{"key":"S0263574719001905_ref15","unstructured":"15. Fisac, J. F. , Chen, M. , Tomlin, C. J. and Sastry, S. S. , \u201cReach-Avoid Problems with Time-Varying Dynamics, Targets and Constraints,\u201d Proceedings of the 18th International Conference on Hybrid Systems Computation and Control - HSCC\u201915 (2015) pp. 11\u201320."},{"key":"S0263574719001905_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2797194"},{"key":"S0263574719001905_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2014.10.128"},{"key":"S0263574719001905_ref41","first-page":"81","volume-title":"Reducing conservativeness in safety guarantees by learning disturbances online: Iterated guaranteed safe online learning,","author":"Gillula","year":"2012"},{"key":"S0263574719001905_ref18","unstructured":"18. Kleff, S. and Li, N. , \u201cA Sampled-Data Hamilton-Jacobi Reachability Approach to Safe and Robust Motion Planning,\u201d Proceedings of the 30th Chinese Control and Decision Conference (2018 CCDC) (2018) pp. 3386\u20133392."},{"key":"S0263574719001905_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-017-0436-5"},{"key":"S0263574719001905_ref39","unstructured":"39. Gleason, J. , Vinod, A. P. and Oishi, M. M. K. , \u201cUnderapproximation of Reach-Avoid Sets for Discrete-Time Stochastic Systems via Lagrangian Methods,\u201d IEEE 56th Annual Conference on Decision and Control (CDC) (2017) pp. 4283\u20134290."},{"key":"S0263574719001905_ref21","unstructured":"21. Mitchell, I. M. , Kaynama, S. , Chen, M. , and Oishi, M. , \u201cSafety preserving control synthesis for sampled data systems,\u201d Nonlinear Anal. Hybrid Syst. Special Issue related to IFAC Conference on Analysis and Design of Hybrid Systems (ADHS 12), 10, 1\u2013174 (2013)."},{"key":"S0263574719001905_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40533-9_11"},{"key":"S0263574719001905_ref13","doi-asserted-by":"publisher","DOI":"10.3182\/20110828-6-IT-1002.02261"},{"key":"S0263574719001905_ref3","unstructured":"3. Latombe, J. C. , \u201cMotion Planning with Uncertainty: On the Preimage Backchaining Approach,\u201d In: The Robotics Review (MIT Press, Cambridge, MA, 1989) pp. 55\u201369."},{"key":"S0263574719001905_ref19","unstructured":"19. Huang, H. , Ding, J. , Zhang, W. and Tomlin, C. J. , \u201cAutomation-assisted capture-the-flag: A differential game approach,\u201d IEEE Trans. Control Syst. Technol. 23(3), 1014\u20131028 (2015)."},{"key":"S0263574719001905_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2010.5717115"},{"key":"S0263574719001905_ref34","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025364227563"},{"key":"S0263574719001905_ref36","doi-asserted-by":"publisher","DOI":"10.1017\/S026357470001657X"},{"key":"S0263574719001905_ref40","unstructured":"40. Akametalu, A. , Kaynama, S. , Fisac, J. , Zeilinger, M. N. , Gillula, J. H. and Tomlin, C. J. , \u201cReachability-Based Safe Learning with Gaussian Processes,\u201d Proceedings of the IEEE Conference on Decision and Control (CDC), 02 (2015) pp. 1424\u20131431."},{"key":"S0263574719001905_ref10","unstructured":"10. Maler, O. , \u201cComputing reachable sets: an introduction,\u201d pp. 1\u20138 (2008). Available: https:\/\/pdfs.semanticscholar.org\/2999\/49aef669b547a36c091b768cade091d35532.pdf."},{"key":"S0263574719001905_ref29","unstructured":"29. Fisac, J. F. and Sastry, S. S. , \u201cThe Pursuit-Evasion-Defense Differential Game in Dynamic Constrained Environments,\u201d 2015 IEEE 54th Annual Conference on Decision and Control (CDC) (2015) pp. 4549\u20134556."},{"volume-title":"Differential Games. A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization","year":"1965","author":"Isaacs","key":"S0263574719001905_ref4"},{"key":"S0263574719001905_ref30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.automatica.2018.08.022","article-title":"Efficient path planning algorithms in reach-avoid problems","volume":"89","author":"Zhou","year":"2018","journal-title":"Automatica"},{"key":"S0263574719001905_ref27","unstructured":"27. Chen, M. , \u201cHigh Dimensional Reachability Analysis Addressing the Curse of Dimensionality in Formal Verification,\u201d Ph.D. Dissertation (Electrical Engineering and Computer Sciences, University of California at Berkeley, 2017)."},{"key":"S0263574719001905_ref24","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917712421"},{"key":"S0263574719001905_ref20","unstructured":"20. Dabadie, C. , Kaynama, S. and Tomlin, C. J. , \u201cA Practical Reachability-Based Collision Avoidance Algorithm for Sampled-Data Systems: Application to Ground Robots,\u201d IEEE International Conference on Intelligent Robots and Systems (2014) pp. 4161\u20134168."},{"volume-title":"Safe Robot Navigation Among Moving and Steady Obstacle","year":"2015","author":"Matveev","key":"S0263574719001905_ref1"},{"key":"S0263574719001905_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5102-9_98-1"},{"key":"S0263574719001905_ref5","first-page":"428","volume-title":"Comparing Forward and Backward Reachability as Tools for Safety Analysis,","author":"Mitchell","year":"2007"},{"key":"S0263574719001905_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2105730"},{"key":"S0263574719001905_ref42","unstructured":"42. Mitchell, I. , Bayen, A. M. and Tomlin, C. J. , \u201cValidating a Hamilton\u2013Jacobi Approximation to Hybrid System Reachable Sets,\u201d In: Hybrid Systems: Computation and Control (M. D. Di Benedetto and A. Sangiovanni-Vincentelli, eds.), vol. 2034 (Springer Verlag, Berlin, Heidelberg, 2001) pp. 418\u2013432."},{"volume-title":"Hamilton-Jacobi Reachability: A Brief Overview and Recent Advances,","year":"2017","author":"Bansal","key":"S0263574719001905_ref26"},{"key":"S0263574719001905_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.nahs.2009.03.002"}],"container-title":["Robotica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0263574719001905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T06:36:56Z","timestamp":1605595016000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0263574719001905\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,14]]},"references-count":42,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["S0263574719001905"],"URL":"https:\/\/doi.org\/10.1017\/s0263574719001905","relation":{},"ISSN":["0263-5747","1469-8668"],"issn-type":[{"type":"print","value":"0263-5747"},{"type":"electronic","value":"1469-8668"}],"subject":[],"published":{"date-parts":[[2020,2,14]]}}}