{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:03:23Z","timestamp":1777716203585,"version":"3.51.4"},"reference-count":56,"publisher":"SAGE Publications","issue":"8","license":[{"start":{"date-parts":[[2025,2,27]],"date-time":"2025-02-27T00:00:00Z","timestamp":1740614400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100002553","name":"Seoul National University of Science and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002553","id-type":"DOI","asserted-by":"publisher"}]}],"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>Decentralized multi-agent trajectory planning (MATP) can enhance the efficiency of multi-robot systems thanks to high scalability and short computation time. However, it may lead to deadlock or livelock in obstacle-rich environments. To tackle this challenge, this paper presents a decentralized MATP algorithm for a quadrotor swarm that ensures convergence to a goal in maze-like environments. The proposed method guides the agents to their goal using the waypoints generated by a grid-based multi-agent path planning (MAPF) algorithm. Additionally, we introduce subgoal optimization to prevent deadlock while the agents follow the waypoints. The proposed algorithm guarantees that the agents converge to their goal if there is no dynamic obstacle and the agents are connected through a fully connected network. Moreover, it ensures deadlock-free even when the agent has a limited communication range. For dynamic obstacle avoidance, we revise the grid-based MAPF to prioritize collision avoidance when the agents encounter dynamic obstacles in a narrow corridor. In simulation, the proposed algorithm achieves a 100% success rate in static environments and shows a higher success rate and shorter flight time compared to most state-of-the-art baseline algorithms in dynamic environments. We validate the safety and robustness of the proposed work through the experiment with 10 quadrotors and one pedestrian in a maze-like environment.<\/jats:p>","DOI":"10.1177\/02783649241312352","type":"journal-article","created":{"date-parts":[[2025,2,27]],"date-time":"2025-02-27T12:32:21Z","timestamp":1740659541000},"page":"1336-1359","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":3,"title":["Decentralized trajectory planning for quadrotor swarm in cluttered environments with goal convergence guarantee"],"prefix":"10.1177","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4930-5628","authenticated-orcid":false,"given":"Jungwon","family":"Park","sequence":"first","affiliation":[{"name":"Department of Mechanical System Design Enginnering, Seoul National University of Science and Technology (SEOULTECH), Seoul, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunwoo","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Aerospace Engineering, Seoul National University, Seoul, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inkyu","family":"Jang","sequence":"additional","affiliation":[{"name":"Department of Aerospace Engineering, Seoul National University, Seoul, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H. Jin","family":"Kim","sequence":"additional","affiliation":[{"name":"Department of Aerospace Engineering, Seoul National University, Seoul, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2025,2,27]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"crossref","unstructured":"Abdullhak M Vardy A (2021) Deadlock prediction and recovery for distributed collision avoidance with buffered voronoi cells. In: 2021 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) Prague Czech Republic 27 September 2021\u201301 October 2021 429\u2013436.","DOI":"10.1109\/IROS51168.2021.9636609"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-017-9665-6"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.2967281"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1609\/socs.v5i1.18315"},{"key":"e_1_3_3_6_1","article-title":"Rule-based lloyd algorithm for multi-robot motion planning and control with safety and convergence guarantees","author":"Boldrer M","year":"2023","unstructured":"Boldrer M, Serra-Gomez A, Lyons L, et al. (2023) Rule-based lloyd algorithm for multi-robot motion planning and control with safety and convergence guarantees. arXiv preprint arXiv:2310.19511.","journal-title":"arXiv preprint arXiv:2310.19511"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2018.2828380"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2020.3000748"},{"key":"e_1_3_3_10_1","unstructured":"Chen Y Guo M Li Z (2022) Recursive feasibility and deadlock resolution in mpc-based multi-robot trajectory generation. ArXiv Preprint arXiv:2202.06071."},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2023.3248377"},{"key":"e_1_3_3_12_1","doi-asserted-by":"crossref","unstructured":"Dergachev S Yakovlev K (2021) Distributed multi-agent navigation based on reciprocal collision avoidance and locally confined multi-agent path finding. In: 2021 IEEE 17th International Conference on Automation Science and Engineering (CASE) Lyon France 23\u201327 August 2021 1489\u20131494.","DOI":"10.1109\/CASE49439.2021.9551564"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-012-9275-2"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2012.03.001"},{"key":"e_1_3_3_15_1","volume-title":"Real-time Trajectory Generation for Constrained Nonlinear Dynamical Systems Using Non-uniform Rational B-spline basis Functions","author":"Flores ME","year":"2008","unstructured":"Flores ME (2008) Real-time Trajectory Generation for Constrained Nonlinear Dynamical Systems Using Non-uniform Rational B-spline basis Functions. PhD Thesis. California Institute of Technology, Pasadena, CA."},{"key":"e_1_3_3_16_1","volume-title":"Automated Maze Generation and Human Interaction","author":"Foltin M","year":"2011","unstructured":"Foltin M (2011) Automated Maze Generation and Human Interaction. Brno: Masaryk University Faculty of Informatics."},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/56.2083"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588795"},{"key":"e_1_3_3_19_1","first-page":"294","volume-title":"International Workshop on the Algorithmic Foundations of Robotics","author":"Grover JS","year":"2020","unstructured":"Grover JS, Liu C, Sycara K (2020) Deadlock analysis and resolution for multi-robot systems. In: LaValle SM, Lin M, Ojala T, Shell D, Yu J (eds). International Workshop on the Algorithmic Foundations of Robotics. Berlin: Springer, 294\u2013312."},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2018.2853613"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-012-9321-0"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3191037"},{"key":"e_1_3_3_23_1","article-title":"IBM ILOG CPLEX 12.7 User\u2019s Manual (IBM ILOG CPLEX Division, Incline Village, NV).","author":"IBM","year":"2017","unstructured":"IBM (2017) IBM ILOG CPLEX 12.7 User\u2019s Manual (IBM ILOG CPLEX Division, Incline Village, NV). IBM CPLEX Studio. Available at: https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio.","journal-title":"IBM CPLEX Studio"},{"key":"e_1_3_3_24_1","doi-asserted-by":"crossref","unstructured":"Jager M Nebel B (2001) Decentralized collision avoidance deadlock detection and deadlock resolution for multiple mobile robots. In: IEEE\/RSJ international conference on intelligent robots and systems Maui HI USA 29 October 2001\u201303 November 2001 1213\u20131219.","DOI":"10.1109\/IROS.2001.977148"},{"key":"e_1_3_3_25_1","doi-asserted-by":"crossref","unstructured":"Jang I Park J Kim HJ (2023) Safe and distributed multi-agent motion planning under minimum speed constraints. In: 2023 IEEE International Conference on Robotics and Automation (ICRA) London UK 29 May 2023\u201302 June 2023 7677\u20137683.","DOI":"10.1109\/ICRA48891.2023.10160280"},{"key":"e_1_3_3_26_1","unstructured":"Liu S Mohta K Atanasov N et al. (2018) Towards search-based motion planning for micro aerial vehicles. ArXiv Preprint arXiv:1810.03071."},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.2964159"},{"key":"e_1_3_3_29_1","doi-asserted-by":"crossref","unstructured":"Mellinger D Kumar V (2011) Minimum snap trajectory generation and control for quadrotors. In: 2011 IEEE International Conference on Robotics and Automation (ICRA) Shanghai China 09\u201313 May 2011 2520\u20132525.","DOI":"10.1109\/ICRA.2011.5980409"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.softx.2018.10.002"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","unstructured":"Okumura K Tamura Y D\u00e9fago X (2021) Iterative refinement for real-time multi-robot path planning. In: 2021 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) Prague Czech Republic 27 September 2021\u201301 October 2021 9690\u20139697. DOI: 10.1109\/IROS51168.2021.9636071.","DOI":"10.1109\/IROS51168.2021.9636071"},{"key":"e_1_3_3_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103752"},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCA.2012.2221457"},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.3047786"},{"key":"e_1_3_3_35_1","doi-asserted-by":"crossref","unstructured":"Park J Kim J Jang I et al. (2020) Efficient multi-agent trajectory planning with feasibility guarantee using relative bernstein polynomial. In: 2020 IEEE International Conference on Robotics and Automation (ICRA) Paris France 31 May 2020\u201331 August 2020 434\u2013440.","DOI":"10.1109\/ICRA40945.2020.9197162"},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3152702"},{"key":"e_1_3_3_37_1","doi-asserted-by":"crossref","unstructured":"Park J Jang I Kim HJ (2023a) Decentralized deadlock-free trajectory planning for quadrotor swarm in obstacle-rich environments. In: 2023 IEEE International Conference on Robotics and Automation (ICRA) London UK 29 May 2023\u201302 June 2023 1428\u20131434.","DOI":"10.1109\/ICRA48891.2023.10160847"},{"key":"e_1_3_3_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2023.3279903"},{"key":"e_1_3_3_39_1","doi-asserted-by":"crossref","unstructured":"Preiss JA Honig W Sukhatme GS et al. (2017) Crazyswarm: a large nano-quadcopter swarm. In: International Conference on Robotics and Automation (ICRA) Singapore 29 May 2017\u201303 June 2017 3299\u20133304.","DOI":"10.1109\/ICRA.2017.7989376"},{"key":"e_1_3_3_40_1","doi-asserted-by":"crossref","unstructured":"Rahmani A Kosuge K Tsukamaki T et al. (2008) Multiple uav deconfliction via navigation functions. In: AIAA Guidance Navigation and Control Conference and Exhibit 6626.","DOI":"10.2514\/6.2008-6626"},{"key":"e_1_3_3_41_1","doi-asserted-by":"crossref","unstructured":"Richards A How J (2004) Decentralized model predictive control of cooperating UAVs. In: 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No. 04CH37601) Nassau Bahamas 14\u201317 December 2004 4286\u20134291.","DOI":"10.1109\/CDC.2004.1429425"},{"key":"e_1_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2020.2994122"},{"key":"e_1_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-023-10104-w"},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42256-021-00341-y"},{"key":"e_1_3_3_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2021.3133802"},{"key":"e_1_3_3_46_1","doi-asserted-by":"publisher","DOI":"10.1142\/S2301385018500115"},{"key":"e_1_3_3_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2021.3080235"},{"key":"e_1_3_3_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3196777"},{"key":"e_1_3_3_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19457-3_1"},{"key":"e_1_3_3_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2017.2659727"},{"key":"e_1_3_3_51_1","doi-asserted-by":"crossref","unstructured":"Zhang S So O Garg K et al. (2024) Gcbf+: a neural graph control barrier function framework for distributed safe multi-agent control. ArXiv Preprint arXiv:2401.14554.","DOI":"10.1109\/TRO.2025.3530348"},{"key":"e_1_3_3_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2656241"},{"key":"e_1_3_3_53_1","doi-asserted-by":"crossref","unstructured":"Zhou X Zhu J Zhou H et al. (2021) EGO-swarm: a fully autonomous and decentralized quadrotor swarm system in cluttered environments. In: 2021 IEEE International Conference on Robotics and Automation (ICRA) Xi\u2019an China 30 May 2021\u201305 June 2021 4101\u20134107.","DOI":"10.1109\/ICRA48506.2021.9561902"},{"key":"e_1_3_3_54_1","doi-asserted-by":"publisher","DOI":"10.1126\/scirobotics.abm5954"},{"key":"e_1_3_3_55_1","doi-asserted-by":"crossref","unstructured":"Zhu H Alonso-Mora J (2019a) B-UAVC: buffered uncertainty-aware voronoi cells for probabilistic multi-robot collision avoidance. In: 2019 International Symposium on Multi-Robot and Multi-Agent Systems (MRS) New Brunswick NJ USA 22\u201323 August 2019 162\u2013168.","DOI":"10.1109\/MRS.2019.8901092"},{"key":"e_1_3_3_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2893494"},{"key":"e_1_3_3_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-021-10029-2"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241312352","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649241312352","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241312352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:39Z","timestamp":1777457859000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649241312352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,27]]},"references-count":56,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.1177\/02783649241312352"],"URL":"https:\/\/doi.org\/10.1177\/02783649241312352","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,27]]}}}