[1]HU Ke,SUN Hongfei.Trajectory planning for multi-drone in unknow mixed dynamic environments[J].CAAI Transactions on Intelligent Systems,2025,20(2):445-456.[doi:10.11992/tis.202401035]
Copy

Trajectory planning for multi-drone in unknow mixed dynamic environments

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 20 Number of periods: 2025 2 Page number: 445-456 Column: 学术论文—智能系统 Public date: 2025-03-05
Title:
Trajectory planning for multi-drone in unknow mixed dynamic environments
Author(s):
HU Ke;  SUN Hongfei
School of Aerospace Engineering, Xiamen University, Xiamen 361102, China
Keywords:
autonomous agents; real-time systems; motion planning; online searching; collision avoidance; optimization; gradient methods; decentralized control
CLC:
TP27
DOI:
10.11992/tis.202401035
Abstract:
The realization of fast online replanning for multi-drone in an unknown mixed dynamic environment poses a significant challenge. This paper proposes a decentralized kinodynamic planning scheme to rapidly replan dynamically feasible trajectories for autonomous drones in mixed dynamic environments with static and dynamic obstacles. Firstly, we introduce an improved kinodynamic path search method that addresses the limitations of dealing with dynamic obstacles and low search efficiency. This is achieved by incorporating the optimal reciprocal collision avoidance algorithm, resulting in a safe reference path. Then, an initial trajectory is fitted according to the reference path and optimized using a gradient-based optimization method. To enhance optimization efficiency, a gradient construction method is proposed, adapting kinodynamic planning schemes. This method efficiently utilizes known information to rapidly construct obstacle avoidance gradients, enabling trajectory optimization to be completed within a few milliseconds. Finally, the feasibility and efficiency of the proposed approach were validated through comparison with other planning schemes.
References:
[1] PARK J, KIM J, JANG I, et al. Efficient multi-agent trajectory planning with feasibility guarantee using relative Bernstein polynomial[C]//2020 IEEE International Conference on Robotics and Automation. Paris: IEEE, 2020: 434-440.
[2] MELLINGER D, KUSHLEYEV A, KUMAR V. Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams[C]//2012 IEEE International Conference on Robotics and Automation. Saint Paul: IEEE, 2012: 477-483.
[3] H?NIG W, PREISS J A, SATISH KUMAR T K, et al. Trajectory planning for quadrotor swarms[J]. IEEE transactions on robotics, 2018, 34(4): 856-869.
[4] 李樾, 韩维, 陈清阳, 等. 基于改进的速度障碍法的有人/无人机协同系统三维实时避障方法[J]. 西北工业大学学报, 2020, 38(2): 309-318.
LI Yue, HAN Wei, CHEN Qingyang, et al. Real-time obstacle avoidance for manned/unmanned aircraft cooperative system based on improved velocity obstacle method[J]. Journal of northwestern polytechnical university, 2020, 38(2): 309-318.
[5] 张钟元, 戴炜, 李光昱, 等. 基于改进人工势场和一致性协议的协同避障算法[J]. 计算机应用, 2023, 43(8): 2644-2650.
ZHANG Zhongyuan, DAI Wei, LI Guangyu, et al. Cooperative obstacle avoidance algorithm based on improved artificial potential field and consensus protocol[J]. Journal of computer applications, 2023, 43(8): 2644-2650.
[6] 罗瑞宁, 黄树彩, 赵岩, 等. 子拦截弹拦截无人机集群防碰撞制导律[J]. 航空兵器, 2023, 30(1): 51-58.
LUO Ruining, HUANG Shucai, ZHAO Yan, et al. Collision avoidance guidance law for sub-interceptors intercepting UAV cluster[J]. Aero weaponry, 2023, 30(1): 51-58.
[7] TORDESILLAS J, HOW J P. MADER: trajectory planner in multiagent and dynamic environments[J]. IEEE transactions on robotics, 2022, 38(1): 463-476.
[8] FIORINI P, SHILLER Z. Motion planning in dynamic environments using velocity obstacles[J]. The international journal of robotics research, 1998, 17(7): 760-772.
[9] VAN DEN BERG J, GUY S J, LIN Ming, et al. Reciprocal n-body collision avoidance[M]//Robotics Research. Berlin: Springer Berlin Heidelberg, 2011: 3-19.
[10] ARUL S H, MANOCHA D. DCAD: decentralized collision avoidance with dynamics constraints for agile quadrotor swarms[J]. IEEE robotics and automation letters, 2020, 5(2): 1191-1198.
[11] ALONSO-MORA J, MONTIJANO E, SCHWAGER M, et al. Distributed multi-robot formation control among obstacles: a geometric and optimization approach with consensus[C]//2016 IEEE International Conference on Robotics and Automation. Stockholm: IEEE, 2016: 5356-5363.
[12] YU Zhang, YANG Jingzhao, CHEN Shaofei, et al. Decentralized cooperative trajectory planning for multiple UAVs in dynamic and uncertain environments[C]//2015 IEEE Seventh International Conference on Intelligent Computing and Information Systems. Cairo: IEEE, 2015: 377-382.
[13] ZHOU Xin, WANG Zhepei, WEN Xiangyong, et al. Decentralized spatial-temporal trajectory planning for multicopter swarms[EB/OL]. (2021-06-23) [2024-01-23]. https://arxiv.org/abs/2106.12481v2.
[14] HOU Jialiang, ZHOU Xin, GAN Zhongxue, et al. Enhanced decentralized autonomous aerial robot teams with group planning[J]. IEEE robotics and automation letters, 2022, 7(4): 9240-9247.
[15] XU Gang, KANG Xiao, YANG Helei, et al. Distributed multi-vehicle task assignment and motion planning in dense environments[J]. IEEE transactions on automation science and engineering, 2024, 21(4): 7027-7039.
[16] LU Liangliang, DAI Jiyang, YING Jin. Distributed multi-UAV cooperation for path planning by an NTVPSO-ADE algorithm[C]//2022 41st Chinese Control Conference. Hefei: IEEE, 2022: 5973-5978.
[17] LIU Sikang, WATTERSON M, MOHTA K, et al. Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-D complex environments[J]. IEEE robotics and automation letters, 2017, 2(3): 1688-1695.
[18] CHEN Jing, LIU Tianbo, SHEN Shaojie. Online generation of collision-free trajectories for quadrotor flight in unknown cluttered environments[C]//2016 IEEE International Conference on Robotics and Automation. Stockholm: IEEE, 2016: 1476-1483.
[19] 张浩杰, 张玉东, 梁荣敏, 等. 改进A* 算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45(2): 513-520.
ZHANG Haojie, ZHANG Yudong, LIANG Rongmin, et al. Energy-efficient path planning method for robots based on improved A* algorithm[J]. Systems engineering and electronics, 2023, 45(2): 513-520.
[20] 徐彬, 孙恒飞, 唐寿星, 等. 基于改进运动原语生成的陆空两栖机器人Kinodynamic A*算法[J]. 北京理工大学学报, 2024, 44(2): 189-199.
XU Bin, SUN Hengfei, TANG Shouxing, et al. Kinodynamic A* algorithm of hybrid aerial-ground robot based on improved motion primitive generation[J]. Transactions of Beijing Institute of Technology, 2024, 44(2): 189-199.
[21] LIN Jiahui, ZHOU Tong, ZHU Delong, et al. Search-based online trajectory planning for car-like robots in highly dynamic environments[C]//2021 IEEE International Conference on Robotics and Automation. Xi’an: IEEE, 2021: 8151-8157.
[22] YAN Jingyu, MA Jianjun. Search-based trajectory planning with motion primitives for quadrotors using pruning A* algorithm[C]//2022 37th Youth Academic Annual Conference of Chinese Association of Automation. Beijing: IEEE, 2022: 996-1000.
[23] PEDROSA M V A, SCHNEIDER T, FLA?KAMP K. Graph-based motion planning with primitives in a continuous state space search[C]//2021 6th International Conference on Mechanical Engineering and Robotics Research. Krakow: IEEE, 2021: 30-39.
[24] ADABALA B, AJANOVI? Z. A multi-heuristic search-based motion planning for automated parking[C]//2023 XXIX International Conference on Information, Communication and Automation Technologies. Sarajevo: IEEE, 2023: 1-8.
[25] ZHOU Boyu, GAO Fei, WANG Luqi, et al. Robust and efficient quadrotor trajectory generation for fast autonomous flight[J]. IEEE robotics and automation letters, 2019, 4(4): 3529-3536.
[26] LIU Sikang, ATANASOV N, MOHTA K, et al. Search-based motion planning for quadrotors using linear quadratic minimum time control[C]//2017 IEEE/RSJ International Conference on Intelligent Robots and Systems. New York: ACM, 2017: 2872-2879.
[27] DING Wenchao, GAO Wenliang, WANG Kaixuan, et al. An efficient B-spline-based kinodynamic replanning framework for quadrotors[J]. IEEE transactions on robotics, 2019, 35(6): 1287-1306.
[28] LAU B, SPRUNK C, BURGARD W. Improved updating of Euclidean distance maps and Voronoi diagrams[C]//2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. Taipei: IEEE, 2010: 281-286.
[29] OLEYNIKOVA H, TAYLOR Z, FEHR M, et al. Voxblox: incremental 3D euclidean signed distance fields for on-board MAV planning[C]//2017 IEEE/RSJ International Conference on Intelligent Robots and Systems. Vancouver: IEEE, 2017: 1366-1373.
[30] ZHOU Xin, WANG Zhepei, YE Hongkai, et al. EGO-planner: an ESDF-free gradient-based local planner for quadrotors[J]. IEEE robotics and automation letters, 2021, 6(2): 478-485.
[31] WANG Yingjian, JI Jialin, WANG Qianhao, et al. Autonomous flights in dynamic environments with onboard vision[C]//2021 IEEE/RSJ International Conference on Intelligent Robots and Systems. Prague: IEEE, 2021: 1966-1973.
[32] MELLINGER D, KUMAR V. Minimum snap trajectory generation and control for quadrotors[C]//2011 IEEE International Conference on Robotics and Automation. Shanghai: IEEE, 2011: 2520-2525.
[33] VERRIEST E I, LEWIS F L. On the linear quadratic minimum-time problem[J]. IEEE transactions on automatic control, 1991, 36(7): 859-863.
[34] GAO Fei, LIN Yi, SHEN Shaojie. Gradient-based online safe trajectory generation for quadrotor flight in complex environments[C]//2017 IEEE/RSJ International Conference on Intelligent Robots and Systems. Vancouver: IEEE, 2017: 3681-3688.
[35] OLEYNIKOVA H, BURRI M, TAYLOR Z, et al. Continuous-time trajectory optimization for online UAV replanning[C]//2016 IEEE/RSJ International Conference on Intelligent Robots and Systems. Daejeon: IEEE, 2016: 5332-5339.
[36] LIU Sikang, MOHTA Kartik, ATANASOV Nikolay, et al. Towards search-based motion planning for micro aerial vehicles[EB/OL]. (2018-10-07) [2024-01-23]. https://arxiv.org/pdf/1810.03071.pdf.
[37] WANG Zhepei, ZHOU Xin, XU Chao, et al. Geometrically constrained trajectory optimization for multicopters[J]. IEEE transactions on robotics, 2022, 38(5): 3259-3278.
[38] ZHOU Xin, WEN Xiangyong, WANG Zhepei, et al. Swarm of micro flying robots in the wild[J]. Science robotics, 2022, 7(66): eabm5954.
Similar References:

Memo

-

Last Update: 2025-03-05

Copyright © CAAI Transactions on Intelligent Systems