{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T17:07:24Z","timestamp":1772039244639,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T00:00:00Z","timestamp":1687219200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T00:00:00Z","timestamp":1687219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62073266"],"award-info":[{"award-number":["62073266"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004750","name":"Aeronautical Science Foundation of China","doi-asserted-by":"publisher","award":["201905053003"],"award-info":[{"award-number":["201905053003"]}],"id":[{"id":"10.13039\/501100004750","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Intell. Syst."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The real-time path planning of unmanned aerial vehicles (UAVs) in dynamic environments with moving threats is a difficult problem. To solve this problem, this paper proposes a time-based rapidly exploring random tree (time-based RRT*) algorithm, called the hierarchical rapidly exploring random tree algorithm based on potential function lazy planning and low-cost optimization (HPO-RRT*). The HPO-RRT* algorithm can guarantee path homotopy optimality and high planning efficiency. This algorithm uses a hierarchical architecture comprising a UAV perception system, path planner, and path optimizer. After the UAV perception system predicts moving threats and updates world information, the path planner obtains the heuristic path. First, the path planner uses the bias sampling method based on the artificial potential field function proposed in this paper to guide sampling to improve the efficiency and quality of sampling. Then, the tree is efficiently extended by the improved time-based lazy collision checking RRT* algorithm to obtain the heuristic path. Finally, a low-cost path optimizer quickly optimizes the heuristic path directly to optimize the path while avoiding additional calculations. Simulation results show that the proposed algorithm outperforms the three existing advanced algorithms in terms of addressing the real-time path-planning problem of UAVs in a dynamic environment.<\/jats:p>","DOI":"10.1007\/s40747-023-01115-2","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T03:24:21Z","timestamp":1687231461000},"page":"7133-7153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":35,"title":["HPO-RRT*: a sampling-based algorithm for UAV real-time path planning in a dynamic environment"],"prefix":"10.1007","volume":"9","author":[{"given":"Yicong","family":"Guo","sequence":"first","affiliation":[]},{"given":"Xiaoxiong","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Qianlei","family":"Jia","sequence":"additional","affiliation":[]},{"given":"Xuhang","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Weiguo","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"1115_CR1","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.robot.2018.04.007","volume":"106","author":"B Fu","year":"2018","unstructured":"Fu B, Chen L, Zhou Y et al (2018) An improved A* algorithm for the industrial robot path planning with high success rate and short length. Rob Auton Syst 106:26\u201337. https:\/\/doi.org\/10.1016\/j.robot.2018.04.007","journal-title":"Rob Auton Syst"},{"key":"1115_CR2","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.dt.2019.04.011","volume":"15","author":"BK Patle","year":"2019","unstructured":"Patle BK, Babu LG, Pandey A et al (2019) A review: on path planning strategies for navigation of mobile robot. Def Technol 15:582\u2013606","journal-title":"Def Technol"},{"key":"1115_CR3","doi-asserted-by":"publisher","first-page":"1255","DOI":"10.1109\/TITS.2016.2604240","volume":"18","author":"Y Rasekhipour","year":"2017","unstructured":"Rasekhipour Y, Khajepour A, Chen SK, Litkouhi B (2017) A potential field-based model predictive path-planning controller for autonomous road vehicles. IEEE Trans Intell Transp Syst 18:1255\u20131267. https:\/\/doi.org\/10.1109\/TITS.2016.2604240","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"1115_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ast.2015.09.037","author":"P Yao","year":"2015","unstructured":"Yao P, Wang H, Su Z (2015) Real-time path planning of unmanned aerial vehicle for target tracking and obstacle avoidance in complex dynamic environment. Aerosp Sci Technol. https:\/\/doi.org\/10.1016\/j.ast.2015.09.037","journal-title":"Aerosp Sci Technol"},{"key":"1115_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-020-10139-6","author":"S Katoch","year":"2021","unstructured":"Katoch S, Chauhan SS, Kumar V (2021) A review on genetic algorithm: past, present, and future. Multimed Tools Appl. https:\/\/doi.org\/10.1007\/s11042-020-10139-6","journal-title":"Multimed Tools Appl"},{"key":"1115_CR6","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1109\/LRA.2021.3056028","volume":"6","author":"M Thoresen","year":"2021","unstructured":"Thoresen M, Nielsen NH, Mathiassen K, Pettersen KY (2021) Path planning for UGVs based on traversability hybrid A*. IEEE Robot Autom Lett 6:1216\u20131223. https:\/\/doi.org\/10.1109\/LRA.2021.3056028","journal-title":"IEEE Robot Autom Lett"},{"key":"1115_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2020.106499","author":"M Djukanovic","year":"2020","unstructured":"Djukanovic M, Raidl GR, Blum C (2020) Finding longest common subsequences: new anytime A\u2217 search results. Appl Soft Comput J. https:\/\/doi.org\/10.1016\/j.asoc.2020.106499","journal-title":"Appl Soft Comput J"},{"key":"1115_CR8","unstructured":"Meng Z, Huang P, Yan J (2008) Trajectory planning for hypersonic vehicle using improved sparse A* algorithm. In: IEEE\/ASME international conference on advanced intelligent mechatronics, AIM"},{"key":"1115_CR9","doi-asserted-by":"crossref","unstructured":"Majumder S, Prasad MS (2016) Three dimensional D\u2217 algorithm for incremental path planning in uncooperative environment. In: 3rd international conference on signal processing and integrated networks, SPIN 2016. pp 431\u2013435","DOI":"10.1109\/SPIN.2016.7566733"},{"key":"1115_CR10","unstructured":"LaValle SM, Kuffner JJ, Donald B et al (2000) Rapidly-exploring random trees: progress and prospects. Algorithmic Comput Robot New Dir 5:293\u2013308. https:\/\/www.taylorfrancis.com\/books\/9781439864135\/chapters\/10.1201\/9781439864135-43"},{"key":"1115_CR11","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/70.508439","volume":"12","author":"LE Kavraki","year":"1996","unstructured":"Kavraki LE, \u0160vestka P, Latombe JC, Overmars MH (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans Robot Autom 12:566\u2013580. https:\/\/doi.org\/10.1109\/70.508439","journal-title":"IEEE Trans Robot Autom"},{"key":"1115_CR12","doi-asserted-by":"publisher","first-page":"2271","DOI":"10.1007\/s10514-019-09879-8","volume":"43","author":"Y Chen","year":"2019","unstructured":"Chen Y, He Z, Li S (2019) Horizon-based lazy optimal RRT for fast, efficient replanning in dynamic environment. Auton Robots 43:2271\u20132292. https:\/\/doi.org\/10.1007\/s10514-019-09879-8","journal-title":"Auton Robots"},{"key":"1115_CR13","doi-asserted-by":"publisher","first-page":"2033","DOI":"10.1007\/s12541-019-00224-8","volume":"20","author":"H Ryu","year":"2019","unstructured":"Ryu H, Park Y (2019) Improved informed RRT* using gridmap skeletonization for mobile robot path planning. Int J Precis Eng Manuf 20:2033\u20132039. https:\/\/doi.org\/10.1007\/s12541-019-00224-8","journal-title":"Int J Precis Eng Manuf"},{"key":"1115_CR14","doi-asserted-by":"crossref","unstructured":"Webb DJ, Van Den Berg J (2013) Kinodynamic RRT*: asymptotically optimal motion planning for robots with linear dynamics. In: Proceedings\u2014IEEE international conference on robotics and automation. pp 5054\u20135061","DOI":"10.1109\/ICRA.2013.6631299"},{"key":"1115_CR15","doi-asserted-by":"publisher","first-page":"2063","DOI":"10.1109\/TASE.2020.2987397","volume":"17","author":"J Wang","year":"2020","unstructured":"Wang J, Meng MQH, Khatib O (2020) EB-RRT: optimal motion planning for mobile robots. IEEE Trans Autom Sci Eng 17:2063\u20132073. https:\/\/doi.org\/10.1109\/TASE.2020.2987397","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"1115_CR16","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s10514-019-09832-9","volume":"44","author":"R Shome","year":"2020","unstructured":"Shome R, Solovey K, Dobson A et al (2020) dRRT*: scalable and informed asymptotically-optimal multi-robot motion planning. Auton Robots 44:443\u2013467. https:\/\/doi.org\/10.1007\/s10514-019-09832-9","journal-title":"Auton Robots"},{"key":"1115_CR17","doi-asserted-by":"crossref","unstructured":"Chandler B, Goodrich MA (2017) Online RRT\u2217 and online FMT\u2217: rapid replanning with dynamic cost. In: IEEE international conference on intelligent robots and systems. pp 6313\u20136318","DOI":"10.1109\/IROS.2017.8206535"},{"key":"1115_CR18","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 Rob Res 35:797\u2013822. https:\/\/doi.org\/10.1177\/0278364915594679","journal-title":"Int J Rob Res"},{"key":"1115_CR19","doi-asserted-by":"crossref","unstructured":"Petti S, Fraichard T (2005) Safe motion planning in dynamic environments. In: 2005 IEEE\/RSJ international conference on intelligent robots and systems, IROS. pp 2210\u20132215","DOI":"10.1109\/IROS.2005.1545549"},{"key":"1115_CR20","unstructured":"Fulgenzi C, Spalanzani A, Laugier C, Tay C (2010) Risk based 1225 motion planning and navigation in uncertain dynamic environment. Res Rep 1\u201314. https:\/\/hal.inria.fr\/inria-00526601"},{"key":"1115_CR21","doi-asserted-by":"crossref","unstructured":"Chi W, Meng MQH (2017) Risk-RRT\u2217: a robot motion planning algorithm for the human robot coexisting environment. In: 2017 18th international conference on advanced robotics, ICAR 2017. pp 583\u2013588","DOI":"10.1109\/ICAR.2017.8023670"},{"key":"1115_CR22","doi-asserted-by":"crossref","unstructured":"Thomas S, Morales M, Tang X, Amato NM (2007) Biasing samplers to improve motion planning performance. In: Proceedings\u2014IEEE international conference on robotics and automation. pp 1625\u20131630","DOI":"10.1109\/ROBOT.2007.363556"},{"key":"1115_CR23","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:966\u2013984. https:\/\/doi.org\/10.1109\/TRO.2018.2830331","journal-title":"IEEE Trans Robot"},{"key":"1115_CR24","doi-asserted-by":"crossref","unstructured":"Gammell JD, Srinivasa SS, Barfoot TD (2015) Batch Informed Trees (BIT\u2217): sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs. In: Proceedings\u2014IEEE international conference on robotics and automation. pp 3067\u20133074","DOI":"10.1109\/ICRA.2015.7139620"},{"key":"1115_CR25","doi-asserted-by":"publisher","first-page":"278","DOI":"10.4103\/0377-2063.83650","volume":"57","author":"N Gasilov","year":"2011","unstructured":"Gasilov N, Do\u01e7an M, Arici V (2011) Two-stage shortest path algorithm for solving optimal obstacle avoidance problem. IETE J Res 57:278\u2013285. https:\/\/doi.org\/10.4103\/0377-2063.83650","journal-title":"IETE J Res"},{"key":"1115_CR26","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1109\/TRO.2013.2240176","volume":"29","author":"M Otte","year":"2013","unstructured":"Otte M, Correll N (2013) C-FOREST: parallel shortest path planning with superlinear speedup. IEEE Trans Robot 29:798\u2013806. https:\/\/doi.org\/10.1109\/TRO.2013.2240176","journal-title":"IEEE Trans Robot"},{"key":"1115_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/s40747-021-00628-y","author":"J Yi","year":"2022","unstructured":"Yi J, Yuan Q, Sun R, Bai H (2022) Path planning of a manipulator based on an improved P_RRT* algorithm. Complex Intell Syst. https:\/\/doi.org\/10.1007\/s40747-021-00628-y","journal-title":"Complex Intell Syst"},{"key":"1115_CR28","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.1007\/s10514-015-9518-0","volume":"40","author":"AH Qureshi","year":"2016","unstructured":"Qureshi AH, Ayaz Y (2016) Potential functions based sampling heuristic for optimal path planning. Auton Robots 40:1079\u20131093. https:\/\/doi.org\/10.1007\/s10514-015-9518-0","journal-title":"Auton Robots"},{"key":"1115_CR29","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1109\/TCST.2016.2582144","volume":"25","author":"P Pharpatara","year":"2017","unstructured":"Pharpatara P, Herisse B, Bestaoui Y (2017) 3-D trajectory planning of aerial vehicles using RRT\u2217. IEEE Trans Control Syst Technol 25:1116\u20131123. https:\/\/doi.org\/10.1109\/TCST.2016.2582144","journal-title":"IEEE Trans Control Syst Technol"},{"key":"1115_CR30","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.asoc.2014.09.046","volume":"26","author":"X Zhang","year":"2015","unstructured":"Zhang X, Duan H (2015) An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Appl Soft Comput J 26:270\u2013284. https:\/\/doi.org\/10.1016\/j.asoc.2014.09.046","journal-title":"Appl Soft Comput J"},{"key":"1115_CR31","doi-asserted-by":"crossref","unstructured":"Sintov A, Shapiro A (2014) Time-based RRT algorithm for rendezvous planning of two dynamic systems. In: Proceedings\u2014IEEE international conference on robotics and automation. pp 6745\u20136750","DOI":"10.1109\/ICRA.2014.6907855"},{"key":"1115_CR32","doi-asserted-by":"crossref","unstructured":"Karaman S, Frazzoli E (2011) Sampling-based algorithms for optimal motion planning. Int J Robot Res 30(7):846\u2013894. http:\/\/journals.sagepub.com\/doi\/10.1177\/0278364911406761","DOI":"10.1177\/0278364911406761"},{"key":"1115_CR33","doi-asserted-by":"publisher","first-page":"7244","DOI":"10.1109\/TIE.2020.2998740","volume":"68","author":"J Qi","year":"2021","unstructured":"Qi J, Yang H, Sun H (2021) MOD-RRT*: a sampling-based algorithm for robot path planning in dynamic environment. IEEE Trans Ind Electron 68:7244\u20137251. https:\/\/doi.org\/10.1109\/TIE.2020.2998740","journal-title":"IEEE Trans Ind Electron"},{"key":"1115_CR34","doi-asserted-by":"publisher","first-page":"4121","DOI":"10.1109\/TAC.2019.2904239","volume":"64","author":"Y Mo","year":"2019","unstructured":"Mo Y, Dasgupta S, Beal J (2019) Robustness of the adaptive bellman-ford algorithm: global stability and ultimate bounds. IEEE Trans Automat Control 64:4121\u20134136. https:\/\/doi.org\/10.1109\/TAC.2019.2904239","journal-title":"IEEE Trans Automat Control"},{"key":"1115_CR35","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1016\/j.cja.2020.09.036","volume":"34","author":"Y Liu","year":"2021","unstructured":"Liu Y, Zheng Z, Qin F (2021) Homotopy based optimal configuration space reduction for anytime robotic motion planning. Chinese J Aeronaut 34:364\u2013379. https:\/\/doi.org\/10.1016\/j.cja.2020.09.036","journal-title":"Chinese J Aeronaut"},{"key":"1115_CR36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ast.2021.107314","author":"W Jiang","year":"2022","unstructured":"Jiang W, Lyu Y, Li Y et al (2022) UAV path planning and collision avoidance in 3D environments based on POMPD and improved grey wolf optimizer. Aerosp Sci Technol. https:\/\/doi.org\/10.1016\/j.ast.2021.107314","journal-title":"Aerosp Sci Technol"}],"container-title":["Complex &amp; Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-023-01115-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-023-01115-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-023-01115-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T19:03:07Z","timestamp":1698433387000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-023-01115-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,20]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1115"],"URL":"https:\/\/doi.org\/10.1007\/s40747-023-01115-2","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"value":"2199-4536","type":"print"},{"value":"2198-6053","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,20]]},"assertion":[{"value":"24 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2023","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"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Yicong Guo, Xiaoxiong Liu, Qianlei Jia, Xuhang Liu and Weiguo Zhang.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Yicong Guo, Xiaoxiong Liu, Qianlei Jia, Xuhang Liu and Weiguo Zhang.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}