{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:03:24Z","timestamp":1777716204005,"version":"3.51.4"},"reference-count":32,"publisher":"SAGE Publications","issue":"8","license":[{"start":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T00:00:00Z","timestamp":1774915200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"},{"start":{"date-parts":[[2025,3,31]],"date-time":"2025-03-31T00:00:00Z","timestamp":1743379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-19-1-0169"],"award-info":[{"award-number":["FA9550-19-1-0169"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-20-1-0238"],"award-info":[{"award-number":["FA9550-20-1-0238"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-23-1-0145"],"award-info":[{"award-number":["FA9550-23-1-0145"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-23-1-0313"],"award-info":[{"award-number":["FA9550-23-1-0313"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-2039054"],"award-info":[{"award-number":["CNS-2039054"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-2111688"],"award-info":[{"award-number":["CNS-2111688"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["FA8651-22-1-0017"],"award-info":[{"award-number":["FA8651-22-1-0017"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["FA8651-23-1-0004"],"award-info":[{"award-number":["FA8651-23-1-0004"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-20-1-0253"],"award-info":[{"award-number":["W911NF-20-1-0253"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DoD","award":["W911NF-23-1-0158"],"award-info":[{"award-number":["W911NF-23-1-0158"]}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>This paper focuses on the motion planning problem for the systems exhibiting both continuous and discrete behaviors, which we refer to as hybrid dynamical systems. First, the motion planning problem for hybrid systems is formulated using the hybrid equation framework, which is general to capture most hybrid systems. Second, a propagation algorithm template is proposed that describes a general framework to solve the motion planning problem for hybrid systems. Third, a rapidly-exploring random trees (RRT) implementation of the proposed algorithm template is designed to solve the motion planning problem for hybrid systems. At each iteration, the proposed algorithm, called HyRRT, randomly picks a state sample and extends the search tree by flow or jump, which is also chosen randomly when both regimes are possible. Through a definition of concatenation of functions defined on hybrid time domains, we show that HyRRT is probabilistically complete, namely, the probability of failing to find a motion plan approaches zero as the number of iterations of the algorithm increases. This property is guaranteed under mild conditions on the data defining the motion plan, which include a relaxation of the usual positive clearance assumption imposed in the literature of classical systems. The motion plan is computed through the solution of two optimization problems, one associated with the flow and the other with the jumps of the system. The proposed algorithm is applied to an actuated bouncing ball system and a walking robot system so as to highlight its generality and computational features.<\/jats:p>","DOI":"10.1177\/02783649241312695","type":"journal-article","created":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:05:42Z","timestamp":1743465942000},"page":"1360-1395","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":2,"title":["Motion planning for hybrid dynamical systems: Framework, algorithm template, and a sampling-based approach"],"prefix":"10.1177","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9504-5591","authenticated-orcid":false,"given":"Nan","family":"Wang","sequence":"first","affiliation":[{"name":"Hybrid Systems Laboratory, Department of Electrical and Computer Engineering, University of California, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6671-5362","authenticated-orcid":false,"given":"Ricardo G.","family":"Sanfelice","sequence":"additional","affiliation":[{"name":"Hybrid Systems Laboratory, Department of Electrical and Computer Engineering, University of California, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2025,3,31]]},"reference":[{"key":"e_1_3_4_2_1","volume-title":"Probability and Measure","author":"Billingsley P","year":"2017","unstructured":"Billingsley P (2017) Probability and Measure. Hoboken, NJ: John Wiley & Sons."},{"key":"e_1_3_4_3_1","unstructured":"Branicky MS Curtiss MM Levine J et al. (2003a) Sampling-based planning and control. In: Proceedings of the 12th Yale workshop on adaptive and learning systems. New Haven CT Citeseer."},{"key":"e_1_3_4_4_1","doi-asserted-by":"crossref","unstructured":"Branicky MS Curtiss MM Levine JA et al. (2003b) Rrts for nonlinear discrete and hybrid planning and control. In: 42nd IEEE international conference on decision and control (IEEE Cat. No. 03CH37475) volume 1 Maui HI 09\u201312 December 2003 657\u2013663. IEEE.","DOI":"10.1109\/CDC.2003.1272639"},{"key":"e_1_3_4_5_1","volume-title":"Sampling-based motion planning with differential constraints","author":"Cheng P","year":"2005","unstructured":"Cheng P (2005) Sampling-based motion planning with differential constraints. University of Illinois at Urbana-Champaign."},{"key":"e_1_3_4_6_1","unstructured":"Fink E Veloso M (1994) Prodigy planning algorithm. Technical Report. Pittsburgh PA: Carnegie-Mellon University Pittsburgh PA Department of Computer Science."},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.4271\/9781468601770"},{"issue":"1","key":"e_1_3_4_8_1","first-page":"14","article-title":"The volume of n-balls","volume":"15","author":"Gipple J","year":"2014","unstructured":"Gipple J (2014) The volume of n-balls. Rose-Hulman Undergraduate Mathematics Journal 15(1): 14.","journal-title":"Rose-Hulman Undergraduate Mathematics Journal"},{"key":"e_1_3_4_9_1","unstructured":"Goldberg K (1994) Completeness in robot motion planning. In: Workshop on algorithmic foundations of robotics College Park MD 419\u2013429."},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.898695"},{"key":"e_1_3_4_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.938385"},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"e_1_3_4_13_1","doi-asserted-by":"crossref","unstructured":"Karaman S Walter MR Perez A et al. (2011) Anytime motion planning using the rrt. In: 2011 IEEE international conference on robotics and automation Shanghai 09\u201313 May 2011 1478\u20131483. IEEE.","DOI":"10.1109\/ICRA.2011.5980479"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8997-2_29"},{"issue":"2","key":"e_1_3_4_15_1","first-page":"10","article-title":"Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation","volume":"4","author":"Kleinbort M","year":"2018","unstructured":"Kleinbort M, Solovey K, Littlefield Z, et al. (2018) Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation. IEEE Robotics and Automation Letters 4(2): 10\u201316.","journal-title":"IEEE Robotics and Automation Letters"},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16595-0_14"},{"key":"e_1_3_4_17_1","article-title":"Rapidly-exploring random trees: a new tool for path planning.","author":"LaValle SM","year":"1998","unstructured":"LaValle SM (1998) Rapidly-exploring random trees: a new tool for path planning. Research Report 9811.","journal-title":"Research Report 9811"},{"key":"e_1_3_4_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"e_1_3_4_19_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"e_1_3_4_20_1","volume-title":"Probability and Random Processes for Electrical Engineering","author":"Leon-Garcia A","year":"1994","unstructured":"Leon-Garcia A (1994) Probability and Random Processes for Electrical Engineering. Chennai: Pearson Education India."},{"key":"e_1_3_4_21_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915614386"},{"key":"e_1_3_4_22_1","unstructured":"Likhachev M Ferguson DI Gordon GJ et al. (2005) Anytime dynamic A*: an anytime replanning algorithm. In: ICAPS Volume 5 262\u2013271."},{"key":"e_1_3_4_23_1","doi-asserted-by":"crossref","unstructured":"Liu S Atanasov N Mohta K et al. (2017) Search-based motion planning for quadrotors using linear quadratic minimum time control. In: 2017 IEEE\/RSJ international conference on intelligent robots and systems (IROS) Vancouver BC 2872\u20132879. IEEE.","DOI":"10.1109\/IROS.2017.8206119"},{"key":"e_1_3_4_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2020.3006716"},{"key":"e_1_3_4_25_1","volume-title":"Vehicle Dynamics and Control","author":"Rajamani R","year":"2011","unstructured":"Rajamani R (2011) Vehicle Dynamics and Control. Berlin: Springer Science & Business Media."},{"key":"e_1_3_4_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0263574719001176"},{"key":"e_1_3_4_27_1","article-title":"Hybrid feedback control","author":"Sanfelice RG","year":"2021","unstructured":"Sanfelice RG (2021) Hybrid feedback control. Princeton University Press.","journal-title":"Princeton University Press."},{"key":"e_1_3_4_28_1","doi-asserted-by":"crossref","unstructured":"Sanfelice R Copp D Nanez P (2013) A toolbox for simulation of hybrid systems in matlab\/simulink: hybrid equations (hyeq) toolbox. In: Proceedings of the 16th international conference on hybrid systems: Computation and control Philadelphia PA 101\u2013106.","DOI":"10.1145\/2461328.2461346"},{"key":"e_1_3_4_29_1","doi-asserted-by":"crossref","unstructured":"Short BE Sanfelice RG (2018) A hybrid predictive control approach to trajectory tracking for a fully actuated biped. In: 2018 annual American control conference (ACC) Milwaukee WI 27\u201329 June 2018 3526\u20133531. IEEE.","DOI":"10.23919\/ACC.2018.8431254"},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915615688"},{"key":"e_1_3_4_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIV.2023.3274536"},{"key":"e_1_3_4_32_1","doi-asserted-by":"crossref","unstructured":"Wu A Sadraddini S Tedrake R (2020) R3t: rapidly-exploring random reachable set tree for optimal kinodynamic planning of nonlinear hybrid systems. In: 2020 IEEE international conference on robotics and automation (ICRA) Paris 31 May 2020\u201331 August 2020 4245\u20134251. IEEE.","DOI":"10.1109\/ICRA40945.2020.9196802"},{"key":"e_1_3_4_33_1","doi-asserted-by":"crossref","unstructured":"Zha J Mueller MW (2021) Exploiting collisions for sampling-based multicopter motion planning. In: 2021 IEEE international conference on robotics and automation (ICRA) Xi\u2019an 7943\u20137949. IEEE.","DOI":"10.1109\/ICRA48506.2021.9561166"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241312695","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649241312695","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241312695","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241312695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:40Z","timestamp":1777457860000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649241312695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,31]]},"references-count":32,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.1177\/02783649241312695"],"URL":"https:\/\/doi.org\/10.1177\/02783649241312695","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,31]]}}}