{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T21:32:49Z","timestamp":1774992769847,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,7,20]],"date-time":"2024-07-20T00:00:00Z","timestamp":1721433600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,20]],"date-time":"2024-07-20T00:00:00Z","timestamp":1721433600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Intell. Syst."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the field of autonomous mobile robots, sampling-based motion planning methods have demonstrated their efficiency in complex environments. Although the Rapidly-exploring Random Tree (RRT) algorithm and its variants have achieved significant success in known static environment, it is still challenging in achieving optimal motion planning in unknown dynamic environments. To address this issue, this paper proposes a novel motion planning algorithm Bi-HS-RRT<jats:inline-formula><jats:alternatives><jats:tex-math>$$^\\text {X}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mmultiscripts>\n                    <mml:mrow\/>\n                    <mml:mrow\/>\n                    <mml:mtext>X<\/mml:mtext>\n                  <\/mml:mmultiscripts>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which facilitates asymptotically optimal real-time planning in continuously changing unknown environments. The algorithm swiftly determines an initial feasible path by employing the bidirectional search. When dynamic obstacles render the planned path infeasible, the bidirectional search is reactivated promptly to reconstruct the search tree in a local area, thereby significantly reducing the search planning time. Additionally, this paper adopts a hybrid heuristic sampling strategy to optimize the planned path quality and search efficiency. The convergence of the proposed algorithm is accelerated by merging local biased sampling with nominal path and global heuristic sampling in hyper-ellipsoid region. To verify the effectiveness and efficiency of the proposed algorithm in unknown dynamic environments, numerous comparative experiments with existing algorithms were conducted. The experimental results indicate that the proposed planning algorithm has significant advantages in planned path length and planning time.<\/jats:p>","DOI":"10.1007\/s40747-024-01557-2","type":"journal-article","created":{"date-parts":[[2024,7,20]],"date-time":"2024-07-20T19:01:22Z","timestamp":1721502082000},"page":"7497-7512","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Bi-HS-RRT$$^\\text {X}$$: an efficient sampling-based motion planning algorithm for unknown dynamic environments"],"prefix":"10.1007","volume":"10","author":[{"given":"Longjie","family":"Liao","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7159-8666","authenticated-orcid":false,"given":"Qimin","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Xinyi","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Xu","family":"Li","sequence":"additional","affiliation":[]},{"given":"Xixiang","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,20]]},"reference":[{"issue":"11","key":"1557_CR1","doi-asserted-by":"publisher","first-page":"6682","DOI":"10.1109\/TSMC.2021.3088776","volume":"52","author":"RG Ribeiro","year":"2022","unstructured":"Ribeiro RG, Cota LP, Euz\u00e9bio TAM, Ram\u00edrez JA, Guimar\u00e3es FG (2022) Unmanned-aerial-vehicle routing problem with mobile charging stations for assisting search and rescue missions in postdisaster scenarios. IEEE Trans Syst Man Cybern Syst 52(11):6682\u20136696. https:\/\/doi.org\/10.1109\/TSMC.2021.3088776","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"issue":"11","key":"1557_CR2","doi-asserted-by":"publisher","first-page":"13161","DOI":"10.1109\/TITS.2022.3193679","volume":"24","author":"N Yin","year":"2023","unstructured":"Yin N (2023) Multiobjective optimization for vehicle routing optimization problem in low-carbon intelligent transportation. IEEE Trans Intell Transp Syst 24(11):13161\u201313170. https:\/\/doi.org\/10.1109\/TITS.2022.3193679","journal-title":"IEEE Trans Intell Transp Syst"},{"issue":"1","key":"1557_CR3","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1109\/TMECH.2021.3068259","volume":"27","author":"X Zhao","year":"2022","unstructured":"Zhao X, Tao B, Ding H (2022) Multimobile robot cluster system for robot machining of large-scale workpieces. IEEE\/ASME Trans Mechatron 27(1):561\u2013571. https:\/\/doi.org\/10.1109\/TMECH.2021.3068259","journal-title":"IEEE\/ASME Trans Mechatron"},{"issue":"2","key":"1557_CR4","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100\u2013107. https:\/\/doi.org\/10.1109\/TSSC.1968.300136","journal-title":"IEEE Trans Syst Sci Cybern"},{"key":"1557_CR5","doi-asserted-by":"publisher","unstructured":"Stentz A (1994) Optimal and efficient path planning for partially-known environments. In: Proceedings of the 1994 IEEE international conference on robotics and automation, pp 3310\u201333174 . https:\/\/doi.org\/10.1109\/ROBOT.1994.351061","DOI":"10.1109\/ROBOT.1994.351061"},{"key":"1557_CR6","doi-asserted-by":"publisher","unstructured":"Khatib O (1985) Real-time obstacle avoidance for manipulators and mobile robots. In: Proceedings. 1985 IEEE international conference on robotics and automation, vol 2, pp 500\u2013505. https:\/\/doi.org\/10.1109\/ROBOT.1985.1087247","DOI":"10.1109\/ROBOT.1985.1087247"},{"issue":"2","key":"1557_CR7","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1109\/TIV.2021.3123341","volume":"7","author":"H Li","year":"2022","unstructured":"Li H, Liu W, Yang C, Wang W, Qie T, Xiang C (2022) An optimization-based path planning approach for autonomous vehicles using the dynefwa-artificial potential field. IEEE Trans Intell Veh 7(2):263\u2013272. https:\/\/doi.org\/10.1109\/TIV.2021.3123341","journal-title":"IEEE Trans Intell Veh"},{"key":"1557_CR8","unstructured":"LaValle SM (1998) Rapidly-exploring random trees: a new tool for path planning. The annual research report"},{"key":"1557_CR9","doi-asserted-by":"publisher","unstructured":"Kuffner JJ, LaValle SM (2000) Rrt-connect: an efficient approach to single-query path planning. In: Proceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings (Cat. No.00CH37065), vol 2, pp 995\u201310012. https:\/\/doi.org\/10.1109\/ROBOT.2000.844730","DOI":"10.1109\/ROBOT.2000.844730"},{"issue":"7","key":"1557_CR10","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1177\/0278364911406761","volume":"30","author":"S Karaman","year":"2011","unstructured":"Karaman S, Frazzoli E (2011) Sampling-based algorithms for optimal motion planning. Int J Robot Res 30(7):846\u2013894. https:\/\/doi.org\/10.1177\/0278364911406761","journal-title":"Int J Robot Res"},{"key":"1557_CR11","doi-asserted-by":"publisher","unstructured":"Gammell JD, Srinivasa SS, Barfoot TD (2014) Informed rrt*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. In 2014 IEEE\/RSJ international conference on intelligent robots and systems, pp 2997\u20133004. https:\/\/doi.org\/10.1109\/IROS.2014.6942976","DOI":"10.1109\/IROS.2014.6942976"},{"key":"1557_CR12","doi-asserted-by":"publisher","unstructured":"Bruce J, Veloso M (2002) Real-time randomized path planning for robot navigation. In: IEEE\/RSJ international conference on intelligent robots and systems, vol 3, pp 2383\u201323883 . https:\/\/doi.org\/10.1109\/IRDS.2002.1041624","DOI":"10.1109\/IRDS.2002.1041624"},{"issue":"7","key":"1557_CR13","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1177\/0278364915594679","volume":"35","author":"M Otte","year":"2016","unstructured":"Otte M, Frazzoli E (2016) Rrtx: asymptotically optimal single-query sampling-based motion planning with quick replanning. Int J Robot Res 35(7):797\u2013822. https:\/\/doi.org\/10.1177\/0278364915594679","journal-title":"Int J Robot Res"},{"key":"1557_CR14","doi-asserted-by":"publisher","unstructured":"Ferguson D, Kalra N, Stentz A (2006) Replanning with rrts. In: Proceedings 2006 IEEE international conference on robotics and automation, 2006. ICRA 2006, 1243\u20131248. https:\/\/doi.org\/10.1109\/ROBOT.2006.1641879","DOI":"10.1109\/ROBOT.2006.1641879"},{"key":"1557_CR15","doi-asserted-by":"publisher","unstructured":"Zucker M, Kuffner J, Branicky M (2007) Multipartite rrts for rapid replanning in dynamic environments. In: Proceedings 2007 IEEE international conference on robotics and automation, pp 1603\u20131609. https:\/\/doi.org\/10.1109\/ROBOT.2007.363553","DOI":"10.1109\/ROBOT.2007.363553"},{"key":"1557_CR16","doi-asserted-by":"publisher","unstructured":"Kuwata Y, Teo J, Karaman S, Fiore G, Frazzoli E, How J (2008) Motion planning in complex environments using closed-loop prediction. https:\/\/doi.org\/10.2514\/6.2008-7166","DOI":"10.2514\/6.2008-7166"},{"key":"1557_CR17","unstructured":"Fulgenzi C, Spalanzani A, Laugier C, Tay C (2010) Risk based motion planning and navigation in uncertain dynamic environment. Research report (October). https:\/\/inria.hal.science\/inria-00526601"},{"key":"1557_CR18","doi-asserted-by":"publisher","unstructured":"Naderi K, Rajam\u00e4ki J, H\u00e4m\u00e4l\u00e4inen P (2015) Rt-rrt*: a real-time path planning algorithm based on rrt*, pp 113\u2013118 . https:\/\/doi.org\/10.1145\/2822013.2822036","DOI":"10.1145\/2822013.2822036"},{"issue":"3","key":"1557_CR19","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1109\/TIV.2022.3152740","volume":"7","author":"H Ma","year":"2022","unstructured":"Ma H, Meng F, Ye C, Wang J, Meng MQ-H (2022) Bi-risk-rrt based efficient motion planning for autonomous ground vehicles. IEEE Trans Intell Veh 7(3):722\u2013733. https:\/\/doi.org\/10.1109\/TIV.2022.3152740","journal-title":"IEEE Trans Intell Veh"},{"issue":"1","key":"1557_CR20","doi-asserted-by":"publisher","first-page":"1282","DOI":"10.1109\/TIV.2023.3307283","volume":"9","author":"Y Zhang","year":"2024","unstructured":"Zhang Y, Wang H, Yin M, Wang J, Hua C (2024) Bi-am-rrt*: a fast and efficient sampling-based motion planning algorithm in dynamic environments. IEEE Trans Intell Veh 9(1):1282\u20131293. https:\/\/doi.org\/10.1109\/TIV.2023.3307283","journal-title":"IEEE Trans Intell Veh"},{"key":"1557_CR21","doi-asserted-by":"publisher","unstructured":"Arslan O, Tsiotras P (2013) Use of relaxation methods in sampling-based algorithms for optimal motion planning. In: 2013 IEEE international conference on robotics and automation, pp 2421\u20132428. https:\/\/doi.org\/10.1109\/ICRA.2013.6630906","DOI":"10.1109\/ICRA.2013.6630906"},{"key":"1557_CR22","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.eswa.2019.01.032","volume":"123","author":"I-B Jeong","year":"2019","unstructured":"Jeong I-B, Lee S-J, Kim J-H (2019) Quick-rrt*: triangular inequality-based implementation of rrt* with improved initial solution and convergence rate. Expert Syst Appl 123:82\u201390. https:\/\/doi.org\/10.1016\/j.eswa.2019.01.032","journal-title":"Expert Syst Appl"},{"key":"1557_CR23","doi-asserted-by":"publisher","unstructured":"Islam F, Nasir J, Malik U, Ayaz Y, Hasan O (2012) Rrt*-smart: Rapid convergence implementation of rrt* towards optimal solution. In: 2012 IEEE international conference on mechatronics and automation, pp 1651\u20131656. https:\/\/doi.org\/10.1109\/ICMA.2012.6284384","DOI":"10.1109\/ICMA.2012.6284384"},{"key":"1557_CR24","doi-asserted-by":"crossref","unstructured":"Faroni M, Pedrocchi N, Beschi M (2024) Adaptive hybrid local-global sampling for fast informed sampling-based optimal path planning","DOI":"10.1007\/s10514-024-10157-5"},{"key":"1557_CR25","doi-asserted-by":"publisher","unstructured":"Enevoldsen TT, Galeazzi R (2022) Informed sampling-based collision avoidance with least deviation from the nominal path. In: 2022 IEEE\/RSJ international conference on intelligent robots and systems (IROS), pp 8094\u20138100. https:\/\/doi.org\/10.1109\/IROS47612.2022.9982202","DOI":"10.1109\/IROS47612.2022.9982202"},{"key":"1557_CR26","unstructured":"Arslan O, Tsiotras P (2012) The role of vertex consistency in sampling-based algorithms for optimal motion planning. arXiv:1204.6453"},{"key":"1557_CR27","doi-asserted-by":"publisher","unstructured":"Solovey K, Janson L, Schmerling E, Frazzoli E, Pavone M (2020) Revisiting the asymptotic optimality of rrt. In: 2020 IEEE international conference on robotics and automation (ICRA), pp 2189\u20132195. https:\/\/doi.org\/10.1109\/ICRA40945.2020.9196553","DOI":"10.1109\/ICRA40945.2020.9196553"},{"issue":"6","key":"1557_CR28","doi-asserted-by":"publisher","first-page":"3636","DOI":"10.1109\/TRO.2022.3181947","volume":"38","author":"S Nayak","year":"2022","unstructured":"Nayak S, Otte MW (2022) Bidirectional sampling-based motion planning without two-point boundary value solution. IEEE Trans Robot 38(6):3636\u20133654. https:\/\/doi.org\/10.1109\/TRO.2022.3181947","journal-title":"IEEE Trans Robot"},{"key":"1557_CR29","doi-asserted-by":"publisher","unstructured":"Nguyen V, Martinelli A, Tomatis N, Siegwart R (2005) A comparison of line extraction algorithms using 2d laser rangefinder for indoor mobile robotics. In: 2005 IEEE\/RSJ international conference on intelligent robots and systems, pp 1929\u20131934. https:\/\/doi.org\/10.1109\/IROS.2005.1545234","DOI":"10.1109\/IROS.2005.1545234"},{"issue":"4","key":"1557_CR30","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1109\/TRO.2018.2830331","volume":"34","author":"JD Gammell","year":"2018","unstructured":"Gammell JD, Barfoot TD, Srinivasa SS (2018) Informed sampling for asymptotically optimal path planning. IEEE Trans Robot 34(4):966\u2013984. https:\/\/doi.org\/10.1109\/TRO.2018.2830331","journal-title":"IEEE Trans Robot"},{"key":"1557_CR31","doi-asserted-by":"publisher","unstructured":"Klemm S, Oberl\u00e4nder J, Hermann A, Roennau A, Schamm T, Zollner J.M, Dillmann R(2015) Rrt*-connect: faster, asymptotically optimal motion planning. In: 2015 IEEE international conference on robotics and biomimetics (ROBIO), pp 1670\u20131677. https:\/\/doi.org\/10.1109\/ROBIO.2015.7419012","DOI":"10.1109\/ROBIO.2015.7419012"},{"issue":"7","key":"1557_CR32","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1177\/0278364915577958","volume":"34","author":"L Janson","year":"2015","unstructured":"Janson L, Schmerling E, Clark A, Pavone M (2015) Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions. Int J Robot Res 34(7):883\u2013921. https:\/\/doi.org\/10.1177\/0278364915577958","journal-title":"Int J Robot Res"}],"container-title":["Complex &amp; Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-024-01557-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-024-01557-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-024-01557-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T22:07:35Z","timestamp":1729116455000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-024-01557-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,20]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["1557"],"URL":"https:\/\/doi.org\/10.1007\/s40747-024-01557-2","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"value":"2199-4536","type":"print"},{"value":"2198-6053","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,20]]},"assertion":[{"value":"17 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}