{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T00:10:15Z","timestamp":1775175015897,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T00:00:00Z","timestamp":1647388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T00:00:00Z","timestamp":1647388800000},"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":["Intel Serv Robotics"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This research introduces a new path planning method for rescue robots in a dynamic and partially known area when the robots are performing tasks in a large area. The path planning of the rescue robots that move in the dynamic area is introduced to solve the issue of unnecessary areas, which are the disadvantages of the existing D*-based algorithms. This paper proposes a method to eliminate unnecessary expanded nodes of the dynamic and partially known environment by segmenting a map with an auto-clustering algorithm, which is able to achieve a faster execution time than conventional algorithms. Furthermore, to show the effectiveness of the proposed algorithms, an expected value of re-planned nodes in the dynamic and partially known area is introduced using a probability-based approach.<\/jats:p>","DOI":"10.1007\/s11370-022-00416-8","type":"journal-article","created":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T11:03:45Z","timestamp":1647428625000},"page":"289-306","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Auto-splitting D* lite path planning for large disaster area"],"prefix":"10.1007","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1362-8441","authenticated-orcid":false,"given":"Shin-nyeong","family":"Heo","sequence":"first","affiliation":[]},{"given":"Jiaheng","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Yu-chi","family":"Liao","sequence":"additional","affiliation":[]},{"given":"Hee-hyol","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,16]]},"reference":[{"key":"416_CR1","unstructured":"Stentz A (1993) Optimal and efficient path planning for unknown and dynamic environments. Tech. rep., CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST"},{"key":"416_CR2","first-page":"476","volume":"15","author":"S Koenig","year":"2002","unstructured":"Koenig S, Likhachev M (2002) D$$^{\\wedge }$$* lite. Aaai\/iaai 15:476\u2013483","journal-title":"Aaai\/iaai"},{"issue":"2","key":"416_CR3","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/rob.20109","volume":"23","author":"D Ferguson","year":"2006","unstructured":"Ferguson D, Stentz A (2006) Using interpolation to improve path planning: the field d* algorithm. J Field Robot 23(2):79\u2013101","journal-title":"J Field Robot"},{"issue":"1","key":"416_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10846-019-01112-z","volume":"99","author":"X Zhong","year":"2020","unstructured":"Zhong X, Tian J, Hu H, Peng X (2020) Hybrid path planning based on safe a* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment. J Intell Robot Syst 99(1):65\u201377","journal-title":"J Intell Robot Syst"},{"issue":"14","key":"416_CR5","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1016\/j.artint.2009.06.004","volume":"173","author":"R Ebendt","year":"2009","unstructured":"Ebendt R, Drechsler R (2009) Weighted a* search-unifying view and application. Artif Intell 173(14):1310\u20131342","journal-title":"Artif Intell"},{"key":"416_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jtbi.2013.11.022","volume":"344","author":"X Liu","year":"2014","unstructured":"Liu X, Deng R, Wang J, Wang X (2014) Costar: a d-star lite-based dynamic search algorithm for codon optimization. J Theor Biol 344:19\u201330","journal-title":"J Theor Biol"},{"key":"416_CR7","unstructured":"Wilt CM, Ruml W (2012) When does weighted a* fail?. In: SOCS, pp 137\u2013144"},{"key":"416_CR8","doi-asserted-by":"crossref","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\u20131001, IEEE","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"416_CR9","doi-asserted-by":"crossref","unstructured":"Karaman S, Walter MR, Perez A, Frazzoli E, Teller S (2011) Anytime motion planning using the rrt. In: 2011 IEEE international conference on robotics and automation, pp 1478\u20131483, IEEE","DOI":"10.1109\/ICRA.2011.5980479"},{"issue":"10","key":"416_CR10","first-page":"20","volume":"16","author":"I Noreen","year":"2016","unstructured":"Noreen I, Khan A, Habib Z (2016) A comparison of rrt, rrt* and rrt*-smart path planning algorithms. Int J Comput Sci Netw Secur (IJCSNS) 16(10):20","journal-title":"Int J Comput Sci Netw Secur (IJCSNS)"},{"issue":"4","key":"416_CR11","doi-asserted-by":"publisher","first-page":"1748","DOI":"10.1109\/TASE.2020.2976560","volume":"17","author":"J Wang","year":"2020","unstructured":"Wang J, Chi W, Li C, Wang C, Meng MQ-H (2020) Neural rrt*: learning-based optimal path planning. IEEE Trans Autom Sci Eng 17(4):1748\u20131758","journal-title":"IEEE Trans Autom Sci Eng"},{"issue":"1","key":"416_CR12","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/70.127236","volume":"8","author":"YK Hwang","year":"1992","unstructured":"Hwang YK, Ahuja N et al (1992) A potential field approach to path planning. IEEE Trans Robot Autom 8(1):23\u201332","journal-title":"IEEE Trans Robot Autom"},{"issue":"2","key":"416_CR13","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1109\/21.148426","volume":"22","author":"J Barraquand","year":"1992","unstructured":"Barraquand J, Langlois B, Latombe J-C (1992) Numerical potential field techniques for robot path planning. IEEE Trans Syst Man Cybern 22(2):224\u2013241","journal-title":"IEEE Trans Syst Man Cybern"},{"issue":"6","key":"416_CR14","doi-asserted-by":"publisher","first-page":"1407","DOI":"10.1080\/00207721.2014.929191","volume":"47","author":"Y-B Chen","year":"2016","unstructured":"Chen Y-B, Luo G-C, Mei Y-S, Yu J-Q, Su X-L (2016) Uav path planning using artificial potential field method updated by optimal control theory. Int J Syst Sci 47(6):1407\u20131420","journal-title":"Int J Syst Sci"},{"issue":"2","key":"416_CR15","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10846-013-9901-z","volume":"77","author":"B Zhang","year":"2015","unstructured":"Zhang B, Mao Z, Liu W, Liu J (2015) Geometric reinforcement learning for path planning of uavs. J Intell Robot Syst 77(2):391\u2013409","journal-title":"J Intell Robot Syst"},{"key":"416_CR16","doi-asserted-by":"publisher","first-page":"221743","DOI":"10.1109\/ACCESS.2020.3043333","volume":"8","author":"AA Ravankar","year":"2020","unstructured":"Ravankar AA, Ravankar A, Emaru T, Kobayashi Y (2020) Hpprm: Hybrid potential based probabilistic roadmap algorithm for improved dynamic path planning of mobile robots. IEEE Access 8:221743\u2013221766","journal-title":"IEEE Access"},{"key":"416_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.autcon.2017.04.013","volume":"81","author":"MD Phung","year":"2017","unstructured":"Phung MD, Quach CH, Dinh TH, Ha Q (2017) Enhanced discrete particle swarm optimization path planning for uav vision-based surface inspection. Autom Constr 81:25\u201333","journal-title":"Autom Constr"},{"key":"416_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2020.106312","volume":"92","author":"P Das","year":"2020","unstructured":"Das P, Jena PK (2020) Multi-robot path planning using improved particle swarm optimization algorithm through novel evolutionary operators. Appl Soft Comput 92:106312","journal-title":"Appl Soft Comput"},{"key":"416_CR19","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.comcom.2020.11.012","volume":"166","author":"Z Wang","year":"2021","unstructured":"Wang Z, Li G, Ren J (2021) Dynamic path planning for unmanned surface vehicle in complex offshore areas based on hybrid algorithm. Comput Commun 166:49\u201356","journal-title":"Comput Commun"},{"key":"416_CR20","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.neucom.2019.06.099","volume":"365","author":"Y Peng","year":"2019","unstructured":"Peng Y, Li S-W, Hu Z-Z (2019) A self-learning dynamic path planning method for evacuation in large public buildings based on neural networks. Neurocomputing 365:71\u201385","journal-title":"Neurocomputing"},{"key":"416_CR21","unstructured":"Yonetani R, Taniai T, Barekatain M, Nishimura M, Kanezaki A (2021) Path planning using neural a* search. In: International conference on machine learning, pp 12029\u201312039, PMLR"},{"key":"416_CR22","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.procs.2018.01.054","volume":"123","author":"AI Panov","year":"2018","unstructured":"Panov AI, Yakovlev KS, Suvorov R (2018) Grid path planning with deep reinforcement learning: preliminary results. Procedia Comput Sci 123:347\u2013353","journal-title":"Procedia Comput Sci"},{"key":"416_CR23","doi-asserted-by":"publisher","first-page":"12800","DOI":"10.1109\/ACCESS.2018.2797070","volume":"6","author":"D Drake","year":"2018","unstructured":"Drake D, Koziol S, Chabot E (2018) Mobile robot path planning with a moving goal. IEEE Access 6:12800\u201312814","journal-title":"IEEE Access"},{"issue":"4","key":"416_CR24","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s11370-012-0120-4","volume":"5","author":"P-Y Cheng","year":"2012","unstructured":"Cheng P-Y, Chen P-J (2012) Navigation of mobile robot by using d++ algorithm. Intel Serv Robot 5(4):229\u2013243","journal-title":"Intel Serv Robot"},{"key":"416_CR25","unstructured":"Van Den\u00a0Berg J, Ferguson D, Kuffner J (2006) Anytime path planning and replanning in dynamic environments. In: Proceedings 2006 IEEE international conference on robotics and automation, 2006. ICRA 2006., pp 2366\u20132371, IEEE"},{"key":"416_CR26","doi-asserted-by":"crossref","unstructured":"Przybylski M, Putz B (2017) D* extra lite: a dynamic a* with search-tree cutting and frontier-gap repairing. Int J Appl Math Comput Sci, 27","DOI":"10.1515\/amcs-2017-0020"},{"key":"416_CR27","unstructured":"Bholowalia P, Kumar A (2014) Ebk-means: a clustering technique based on elbow method and k-means in wsn. Int J Comput Appl, 105(9)"},{"issue":"06","key":"416_CR28","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1142\/S0218195908002787","volume":"18","author":"G Frahling","year":"2008","unstructured":"Frahling G, Sohler C (2008) A fast k-means implementation using coresets. Int J Comput Geom Appl 18(06):605\u2013625","journal-title":"Int J Comput Geom Appl"},{"issue":"2","key":"416_CR29","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1109\/TRO.2016.2524018","volume":"32","author":"O Arslan","year":"2016","unstructured":"Arslan O, Guralnik DP, Koditschek DE (2016) Coordinated robot navigation via hierarchical clustering. IEEE Trans Rob 32(2):352\u2013371","journal-title":"IEEE Trans Rob"},{"issue":"2","key":"416_CR30","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.chemolab.2007.01.005","volume":"87","author":"J Almeida","year":"2007","unstructured":"Almeida J, Barbosa L, Pais A, Formosinho S (2007) Improving hierarchical cluster analysis: a new method with outlier detection and automatic clustering. Chemom Intell Lab Syst 87(2):208\u2013217","journal-title":"Chemom Intell Lab Syst"},{"issue":"3","key":"416_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3068335","volume":"42","author":"E Schubert","year":"2017","unstructured":"Schubert E, Sander J, Ester M, Kriegel HP, Xu X (2017) Dbscan revisited, revisited: why and how you should (still) use dbscan. ACM Trans Database Syst (TODS) 42(3):1\u201321","journal-title":"ACM Trans Database Syst (TODS)"},{"issue":"2","key":"416_CR32","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1023\/A:1009783824328","volume":"1","author":"T Zhang","year":"1997","unstructured":"Zhang T, Ramakrishnan R, Livny M (1997) Birch: a new data clustering algorithm and its applications. Data Min Knowl Disc 1(2):141\u2013182","journal-title":"Data Min Knowl Disc"},{"key":"416_CR33","unstructured":"Telgarsky M, Vattani A (2010) Hartigan\u2019s method: k-means clustering without Voronoi. In: Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp 820\u2013827, JMLR Workshop and Conference Proceedings, 2010"},{"issue":"1","key":"416_CR34","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1080\/19479832.2015.1053995","volume":"7","author":"J Senthilnath","year":"2016","unstructured":"Senthilnath J, Kumar D, Benediktsson J, Zhang X (2016) A novel hierarchical clustering technique based on splitting and merging. Int J Image Data Fusion 7(1):19\u201341","journal-title":"Int J Image Data Fusion"},{"issue":"6","key":"416_CR35","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1109\/TPAMI.2013.190","volume":"36","author":"S Anand","year":"2013","unstructured":"Anand S, Mittal S, Tuzel O, Meer P (2013) Semi-supervised kernel mean shift clustering. IEEE Trans Pattern Anal Mach Intell 36(6):1201\u20131215","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"416_CR36","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.protcy.2012.05.061","volume":"4","author":"D Reddy","year":"2012","unstructured":"Reddy D, Jana PK, Member IS (2012) Initialization for k-means clustering using voronoi diagram. Procedia Technol 4:395\u2013400","journal-title":"Procedia Technol"},{"key":"416_CR37","doi-asserted-by":"publisher","first-page":"227","DOI":"10.4028\/www.scientific.net\/AMR.951.227","volume":"951","author":"HB Zhou","year":"2014","unstructured":"Zhou HB, Gao JT (2014) Automatic method for determining cluster number based on silhouette coefficient. Adv Mater Res 951:227\u2013230","journal-title":"Adv Mater Res"},{"issue":"6","key":"416_CR38","first-page":"90","volume":"1","author":"TM Kodinariya","year":"2013","unstructured":"Kodinariya TM, Makwana PR (2013) Review on determining number of cluster in k-means clustering. Int J 1(6):90\u201395","journal-title":"Int J"},{"issue":"2","key":"416_CR39","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1111\/1467-9868.00293","volume":"63","author":"R Tibshirani","year":"2001","unstructured":"Tibshirani R, Walther G, Hastie T (2001) Estimating the number of clusters in a data set via the gap statistic. J R Stat Soc Ser B (Stat Methodol) 63(2):411\u2013423","journal-title":"J R Stat Soc Ser B (Stat Methodol)"},{"issue":"3","key":"416_CR40","first-page":"156","volume":"36","author":"M Erwig","year":"2000","unstructured":"Erwig M (2000) The graph Voronoi diagram with applications. Netw Int J 36(3):156\u2013163","journal-title":"Netw Int J"},{"issue":"3","key":"416_CR41","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s10846-017-0748-6","volume":"91","author":"A Niewola","year":"2018","unstructured":"Niewola A, Podsedkowski L (2018) L* algorithm-a linear computational complexity graph searching algorithm for path planning. J Intell Robot Syst 91(3):425\u2013444","journal-title":"J Intell Robot Syst"},{"key":"416_CR42","doi-asserted-by":"crossref","unstructured":"Beamer S, Asanovic K, Patterson D (2012) Direction-optimizing breadth-first search. In: SC\u201912: Proceedings of the international conference on high performance computing, networking, storage and analysis, pp 1\u201310, IEEE","DOI":"10.1109\/SC.2012.50"},{"issue":"1","key":"416_CR43","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW et al (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271","journal-title":"Numer Math"},{"issue":"1","key":"416_CR44","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s00357-001-0004-3","volume":"18","author":"A Chaturvedi","year":"2001","unstructured":"Chaturvedi A, Green PE, Caroll JD (2001) K-modes clustering. J Classif 18(1):35\u201355","journal-title":"J Classif"},{"key":"416_CR45","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1016\/j.procs.2016.02.095","volume":"78","author":"P Arora","year":"2016","unstructured":"Arora P, Varshney S et al (2016) Analysis of k-means and k-medoids algorithm for big data. Procedia Comput Sci 78:507\u2013512","journal-title":"Procedia Comput Sci"},{"key":"416_CR46","doi-asserted-by":"crossref","unstructured":"Comaniciu D, Meer P (1999) Mean shift analysis and applications. In: Proceedings of the seventh IEEE international conference on computer vision, vol 2, pp 1197\u20131203, IEEE","DOI":"10.1109\/ICCV.1999.790416"},{"key":"416_CR47","unstructured":"Kaufman L, Rousseeuw PJ (2009) Finding groups in data: an introduction to cluster analysis, vol 44. Wiley"}],"container-title":["Intelligent Service Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11370-022-00416-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11370-022-00416-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11370-022-00416-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T11:01:30Z","timestamp":1726830090000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11370-022-00416-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,16]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["416"],"URL":"https:\/\/doi.org\/10.1007\/s11370-022-00416-8","relation":{},"ISSN":["1861-2776","1861-2784"],"issn-type":[{"value":"1861-2776","type":"print"},{"value":"1861-2784","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,16]]},"assertion":[{"value":"6 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Heo declares that he has no conflict of interest. Chen declares that he has no conflict of interest. Liao declares that she has no conflict of interest. Lee declares that he has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}