[1]胡克,孙洪飞.未知混动态环境下多无人机轨迹规划[J].智能系统学报,2025,20(2):445-456.[doi:10.11992/tis.202401035]
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]
点击复制
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]
未知混动态环境下多无人机轨迹规划
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
20
期数:
2025年第2期
页码:
445-456
栏目:
学术论文—智能系统
出版日期:
2025-03-05
- Title:
- Trajectory planning for multi-drone in unknow mixed dynamic environments
- Keywords:
- autonomous agents; real-time systems; motion planning; online searching; collision avoidance; optimization; gradient methods; decentralized control
- 分类号:
- TP27
- 摘要:
- 实现多无人机在野外未知混动态环境下的快速在线重规划具有较大挑战。本文提出一种分布式的动力学规划方案，用于自主无人机集群在具有静态障碍和动态障碍的混动态环境中快速重规划动态可行轨迹。首先，提出一种改进的动力学路径搜索方法，利用最优相互避碰算法弥补动力学路径搜索难以处理动态障碍和搜索效率低下的不足，获取一条安全的参考路径。然后，根据参考路径拟合出一条初始轨迹并通过基于梯度的优化方法进行优化。为提高优化效率，提出了一种适配动力学规划方案的避障梯度构建方法，它充分利用已知信息快速构建避障梯度，使得轨迹优化可以在几毫秒以内完成。最后，通过与其他规划方案相比较，验证了本方案的可行性与快速性。
- 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.
备注/Memo
收稿日期:2024-1-23。
基金项目:航空科学基金项目(20220058068001).
作者简介:胡克，硕士研究生，主要研究方向为多智能体轨迹规划。E-mail：hooke155@163.com;孙洪飞，教授，主要研究方向为无人飞行器智能控制系统设计与实现、高超声速飞行器运动控制。发表学术论文40余篇。 E-mail：sunhf@xmu.edu.cn。
通讯作者:孙洪飞. E-mail：sunhf@xmu.edu.cn
更新日期/Last Update:
2025-03-05