{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T05:49:54Z","timestamp":1780465794444,"version":"3.54.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["2023JBMC017"],"award-info":[{"award-number":["2023JBMC017"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["6230070656"],"award-info":[{"award-number":["6230070656"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Comput Intell Syst"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Evolutionary algorithms, such as particle swarm optimization (PSO), are widely applied to UAV path planning problems. However, the fixed particle length of PSO, which may not be suitable for the scenario, will compromise the search efficiency. This paper proposes the RGG-PSO+ method, which adapts to scenarios by dynamically adjusting the number of waypoints. Random geometric graphs (RGG) and the divide-and-conquer paradigm are involved in improving the proposed method. Comparative analyses with established heuristic methods demonstrate RGG-PSO+\u2019s superior performance in complex environments, particularly in terms of convergence speed and path length. The implementation of RGG significantly improves the <jats:italic>F<\/jats:italic>-Measure, indicating a shift from exploration to exploitation of PSO\u2019s iterations, and the implementation of the divide-and-conquer paradigm is evident in the improved mean and variance of normalized path lengths.<\/jats:p>","DOI":"10.1007\/s44196-024-00511-x","type":"journal-article","created":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T13:01:42Z","timestamp":1716296502000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["RGG-PSO+: Random Geometric Graphs Based Particle Swarm Optimization Method for UAV Path Planning"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2222-3232","authenticated-orcid":false,"given":"Yang","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaomin","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiao-Yi","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiannan","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaohan","family":"Yu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,5,21]]},"reference":[{"key":"511_CR1","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.: Homotopy based optimal configuration space reduction for anytime robotic motion planning. Chin. J. Aeronaut. 34, 364\u2013379 (2021)","journal-title":"Chin. J. Aeronaut."},{"key":"511_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.knosys.2018.05.033","volume":"158","author":"Y Zhao","year":"2018","unstructured":"Zhao, Y., Zheng, Z., Liu, Y.: Survey on computational-intelligence-based uav path planning. Knowl.-Based Syst. 158, 54\u201364 (2018)","journal-title":"Knowl.-Based Syst."},{"key":"511_CR3","doi-asserted-by":"crossref","unstructured":"Reif, J.H.: Complexity of the mover\u2019s problem and generalizations. In: 20th Annual Symposium on Foundations of Computer Science (SFCS), pp.\u00a0421\u2013427, IEEE Computer Society, (1979)","DOI":"10.1109\/SFCS.1979.10"},{"key":"511_CR4","doi-asserted-by":"publisher","first-page":"59196","DOI":"10.1109\/ACCESS.2021.3070054","volume":"9","author":"G Tang","year":"2021","unstructured":"Tang, G., Tang, C., Claramunt, C., Hu, X., Zhou, P.: Geometric a-star algorithm: an improved a-star algorithm for agv path planning in a port environment. IEEE Access 9, 59196\u201359210 (2021)","journal-title":"IEEE Access"},{"issue":"5","key":"511_CR5","doi-asserted-by":"publisher","first-page":"172988142096226","DOI":"10.1177\/1729881420962263","volume":"17","author":"S Erke","year":"2020","unstructured":"Erke, S., Bin, D., Yiming, N., Qi, Z., Liang, X., Dawei, Z.: An improved a-star based path planning algorithm for autonomous land vehicles. Int. J. Adv. Robot. Syst. 17(5), 1729881420962263 (2020)","journal-title":"Int. J. Adv. Robot. Syst."},{"issue":"5","key":"511_CR6","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1177\/0278364909359210","volume":"29","author":"D Dolgov","year":"2010","unstructured":"Dolgov, D., Thrun, S., Montemerlo, M., Diebel, J.: Path planning for autonomous vehicles in unknown semi-structured environments. Int. J. Robot. Syst. 29(5), 485\u2013501 (2010)","journal-title":"Int. J. Robot. Syst."},{"key":"511_CR7","doi-asserted-by":"crossref","unstructured":"Xie, Z., Cheng, L., Li, X., Chen, X.: A directed jump point search with improved preprocess for path planning. In: 2023 IEEE 18th Conference on Industrial Electronics and Applications (ICIEA), pp.\u00a01333\u20131338, IEEE, (2023)","DOI":"10.1109\/ICIEA58696.2023.10241935"},{"key":"511_CR8","unstructured":"Sturtevant, N.R., Rabin, S.: Canonical orderings on grids. In: International Joint Conference on Artificial Intelligence (IJCAI), pp.\u00a0683\u2013689, AAAI, (2016)"},{"issue":"10","key":"511_CR9","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1177\/0278364918802957","volume":"37","author":"K Solovey","year":"2018","unstructured":"Solovey, K., Salzman, O., Halperin, D.: New perspective on sampling-based motion planning via random geometric graphs. Int. J. Robot. Syst. 37(10), 1117\u20131133 (2018)","journal-title":"Int. J. Robot. Syst."},{"issue":"7","key":"511_CR10","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1177\/0278364911406761","volume":"30","author":"S Karaman","year":"2011","unstructured":"Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. (IJRR) 30(7), 846\u2013894 (2011)","journal-title":"Int. J. Robot. Res. (IJRR)"},{"key":"511_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2021.107796","volume":"112","author":"YV Pehlivanoglu","year":"2021","unstructured":"Pehlivanoglu, Y.V., Pehlivanoglu, P.: An enhanced genetic algorithm for path planning of autonomous uav in target coverage problems. Appl. Soft Comput. 112, 107796 (2021)","journal-title":"Appl. Soft Comput."},{"key":"511_CR12","doi-asserted-by":"crossref","unstructured":"Arantes, M.d.S., Arantes, J.d.S., Toledo, C.F.M., Williams, B.C.: A hybrid multi-population genetic algorithm for uav path planning. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, pp.\u00a0853\u2013860, (2016)","DOI":"10.1145\/2908812.2908919"},{"issue":"8","key":"511_CR13","doi-asserted-by":"publisher","first-page":"8290","DOI":"10.1109\/TITS.2023.3258482","volume":"24","author":"J Zheng","year":"2023","unstructured":"Zheng, J., Ding, M., Sun, L., Liu, H.: Distributed stochastic algorithm based on enhanced genetic algorithm for path planning of multi-uav cooperative area search. IEEE Trans. Intell. Transport. Syst. 24(8), 8290\u20138303 (2023)","journal-title":"IEEE Trans. Intell. Transport. Syst."},{"key":"511_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2023.106672","volume":"125","author":"M Zhang","year":"2023","unstructured":"Zhang, M., Han, Y., Chen, S., Liu, M., He, Z., Pan, N.: A multi-strategy improved differential evolution algorithm for uav 3d trajectory planning in complex mountainous environments. Eng. Appl. Artif. Intell. 125, 106672 (2023)","journal-title":"Eng. Appl. Artif. Intell."},{"issue":"5","key":"511_CR15","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1007\/s42405-023-00578-4","volume":"24","author":"X Zhang","year":"2023","unstructured":"Zhang, X., Zhang, X., Miao, Y.: Cooperative global path planning for multiple unmanned aerial vehicles based on improved fireworks algorithm using differential evolution operation. Int. J. Aeronaut. Sp. Sci. 24(5), 1346\u20131362 (2023)","journal-title":"Int. J. Aeronaut. Sp. Sci."},{"issue":"20","key":"511_CR16","doi-asserted-by":"publisher","first-page":"17734","DOI":"10.1109\/JIOT.2023.3277850","volume":"10","author":"J Li","year":"2023","unstructured":"Li, J., Xiong, Y., She, J.: Uav path planning for target coverage task in dynamic environment. IEEE Internet of Things J. 10(20), 17734\u201317745 (2023)","journal-title":"IEEE Internet of Things J."},{"key":"511_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2023.105942","volume":"121","author":"C Huang","year":"2023","unstructured":"Huang, C., Zhou, X., Ran, X., Wang, J., Chen, H., Deng, W.: Adaptive cylinder vector particle swarm optimization with differential evolution for UAV path planning. Eng. Appl. Artif. Intell. 121, 105942 (2023)","journal-title":"Eng. Appl. Artif. Intell."},{"issue":"5","key":"511_CR18","doi-asserted-by":"publisher","first-page":"172988142093615","DOI":"10.1177\/1729881420936154","volume":"17","author":"B Tang","year":"2020","unstructured":"Tang, B., Xiang, K., Pang, M., Zhanxia, Z.: Multi-robot path planning using an improved self-adaptive particle swarm optimization. Int. J. Adv. Robot. Syst. 17(5), 1729881420936154 (2020)","journal-title":"Int. J. Adv. Robot. Syst."},{"key":"511_CR19","doi-asserted-by":"crossref","unstructured":"Hoang, V., Phung, M.D., Dinh, T.H., Ha, Q.P.: Angle-encoded swarm optimization for uav formation path planning. In: 2018 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.\u00a05239\u20135244, IEEE, (2018)","DOI":"10.1109\/IROS.2018.8593930"},{"issue":"10","key":"511_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.heliyon.2021.e08247","volume":"7","author":"RM Maina","year":"2021","unstructured":"Maina, R.M., Lang\u2019at, P.K., Kihato, P.K.: Collaborative beamforming in wireless sensor networks using a novel particle swarm optimization algorithm variant. Heliyon 7(10), e08247 (2021)","journal-title":"Heliyon"},{"key":"511_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2021.107376","volume":"107","author":"MD Phung","year":"2021","unstructured":"Phung, M.D., Ha, Q.P.: Safety-enhanced uav path planning with spherical vector-based particle swarm optimization. Appl. Soft Comput. 107, 107376 (2021)","journal-title":"Appl. Soft Comput."},{"key":"511_CR22","volume":"2015","author":"Y Zhang","year":"2015","unstructured":"Zhang, Y., Wang, S., Ji, G., et al.: A comprehensive survey on particle swarm optimization algorithm and its applications. Math. Probl. Eng. 2015, 931256 (2015)","journal-title":"Math. Probl. Eng."},{"key":"511_CR23","doi-asserted-by":"crossref","unstructured":"Khandelwal, M.K., Sharma, N.: A survey on particle swarm optimization algorithm. In: International Conference on Communication and Computational Technologies, pp.\u00a0591\u2013602, Springer, (2023)","DOI":"10.1007\/978-981-99-3485-0_47"},{"issue":"2","key":"511_CR24","doi-asserted-by":"publisher","first-page":"1085","DOI":"10.1109\/TCYB.2019.2925015","volume":"51","author":"W Liu","year":"2021","unstructured":"Liu, W., Wang, Z., Yuan, Y., Zeng, N., Hone, K., Liu, X.: A novel sigmoid-function-based adaptive weighted particle swarm optimizer. IEEE Trans. Cybern. 51(2), 1085\u20131093 (2021)","journal-title":"IEEE Trans. Cybern."},{"key":"511_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2020.106960","volume":"100","author":"B Song","year":"2021","unstructured":"Song, B., Wang, Z., Zou, L.: An improved pso algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve. Appl. Soft Comput. 100, 106960 (2021)","journal-title":"Appl. Soft Comput."},{"issue":"2","key":"511_CR26","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1109\/TSMCA.2011.2159586","volume":"42","author":"Y Fu","year":"2012","unstructured":"Fu, Y., Ding, M., Zhou, C.: Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planning for uav. IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 42(2), 511\u2013526 (2012)","journal-title":"IEEE Trans. Syst. Man Cybern. Part A Syst. Humans"},{"issue":"6","key":"511_CR27","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1109\/TSMC.2013.2248146","volume":"43","author":"Y Fu","year":"2013","unstructured":"Fu, Y., Ding, M., Zhou, C., Hu, H.: Route planning for unmanned aerial vehicle (uav) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization. IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 43(6), 1451\u20131465 (2013)","journal-title":"IEEE Trans. Syst. Man Cybern. Part A Syst. Humans"},{"key":"511_CR28","volume":"2013","author":"Y Zhang","year":"2013","unstructured":"Zhang, Y., Wu, L., Wang, S., et al.: Ucav path planning by fitness-scaling adaptive chaotic particle swarm optimization. Math. Probl. Eng. 2013, 705238 (2013)","journal-title":"Math. Probl. Eng."},{"key":"511_CR29","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2021.104418","volume":"105","author":"B Liang","year":"2021","unstructured":"Liang, B., Zhao, Y., Li, Y.: A hybrid particle swarm optimization with crisscross learning strategy. Eng. Appl. Artif. Intell. 105, 104418 (2021)","journal-title":"Eng. Appl. Artif. Intell."},{"key":"511_CR30","doi-asserted-by":"publisher","DOI":"10.1016\/j.apor.2021.102658","volume":"111","author":"J Zhong","year":"2021","unstructured":"Zhong, J., Li, B., Li, S., Yang, F., Li, P., Cui, Y.: Particle swarm optimization with orientation angle-based grouping for practical unmanned surface vehicle path planning. Appl. Ocean Res. 111, 102658 (2021)","journal-title":"Appl. Ocean Res."},{"key":"511_CR31","doi-asserted-by":"crossref","unstructured":"Penrose, M.: Random Geometric Graphs. Oxford University Press, 05 (2003)","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"511_CR32","doi-asserted-by":"crossref","unstructured":"Bohlin, R., Kavraki, L.: Path planning using lazy prm, vol.\u00a01 of Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), pp.\u00a0521\u2013528, IEEE, (2000)","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"511_CR33","doi-asserted-by":"crossref","unstructured":"Mandalika, A., Choudhury, S., Salzman, O., Srinivasa, S.: Generalized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles, vol.\u00a029 of Proceedings of the International Conference on Automated Planning and Scheduling, pp.\u00a0745\u2013753, (2019)","DOI":"10.1609\/icaps.v29i1.3543"},{"issue":"1","key":"511_CR34","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1016\/j.cja.2020.09.036","volume":"34","author":"L Yang","year":"2021","unstructured":"Yang, L., Zheng, Z., Fangyun, Q.: Homotopy based optimal configuration space reduction for anytime robotic motion planning. Chin. J. Aeronaut. 34(1), 364\u2013379 (2021)","journal-title":"Chin. J. Aeronaut."},{"key":"511_CR35","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1146\/annurev-control-061920-093753","volume":"4","author":"JD Gammell","year":"2021","unstructured":"Gammell, J.D., Strub, M.P.: Asymptotically optimal sampling-based motion planning methods. Annu. Rev. Control Robot. Auton. Syst. 4, 295\u2013318 (2021)","journal-title":"Annu. Rev. Control Robot. Auton. Syst."},{"issue":"7","key":"511_CR36","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.: Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions. Int. J. Robot. Res. (IJRR) 34(7), 883\u2013921 (2015)","journal-title":"Int. J. Robot. Res. (IJRR)"},{"issue":"5","key":"511_CR37","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1177\/0278364919890396","volume":"39","author":"JD Gammell","year":"2020","unstructured":"Gammell, J.D., Barfoot, T.D., Srinivasa, S.S.: Batch informed trees (BIT*): informed asymptotically optimal anytime search. Int. J. Robot. Res. (IJRR) 39(5), 543\u2013567 (2020)","journal-title":"Int. J. Robot. Res. (IJRR)"},{"key":"511_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning Algorithms","author":"SM LaValle","year":"2006","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press (2006)"},{"issue":"3","key":"511_CR39","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1137\/16M1100101","volume":"10","author":"C Sakaridis","year":"2017","unstructured":"Sakaridis, C., Drakopoulos, K., Maragos, P.: Theoretical analysis of active contours on graphs. SIAM J. Imag. Sci. 10(3), 1475\u20131510 (2017)","journal-title":"SIAM J. Imag. Sci."},{"issue":"1","key":"511_CR40","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1109\/TII.2012.2198665","volume":"9","author":"V Roberge","year":"2013","unstructured":"Roberge, V., Tarbouchi, M., Labonte, G.: Comparison of parallel genetic algorithm and particle swarm optimization for real-time uav path planning. IEEE Trans. Ind. Inf. 9(1), 132\u2013141 (2013)","journal-title":"IEEE Trans. Ind. Inf."},{"key":"511_CR41","doi-asserted-by":"crossref","unstructured":"Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11, 341\u2013359 (1997)","DOI":"10.1023\/A:1008202821328"}],"container-title":["International Journal of Computational Intelligence Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44196-024-00511-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s44196-024-00511-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44196-024-00511-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T13:04:46Z","timestamp":1716296686000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s44196-024-00511-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,21]]},"references-count":41,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["511"],"URL":"https:\/\/doi.org\/10.1007\/s44196-024-00511-x","relation":{},"ISSN":["1875-6883"],"issn-type":[{"value":"1875-6883","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,21]]},"assertion":[{"value":"18 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 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 no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"127"}}