障碍物空间下分布式轨迹规划的死锁破解

doi:10.7527/S1000-6893.2023.29771

集群智能与协同控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

障碍物空间下分布式轨迹规划的死锁破解

董豪泽¹, 陈昱达¹, 刘丹², 李忠奎¹()

^1.北京大学工学院，北京 100871
^2.中国空间技术研究院通信与导航卫星总体部，北京 100094

收稿日期:2023-10-26 修回日期:2023-10-30 接受日期:2023-11-22 出版日期:2023-12-14 发布日期:2023-12-13
通讯作者: 李忠奎 E-mail:zhongkli@pku.edu.cn
基金资助:
国家自然科学基金(U2241214)

Received:2023-10-26 Revised:2023-10-30 Accepted:2023-11-22 Online:2023-12-14 Published:2023-12-13

摘要/Abstract

摘要：

基于优化的分布式轨迹规划方法因具有较强的可解释性和可扩展性而备受关注，但由于缺少中心节点和全局优先级，容易诱发集群运动陷入死锁，即若干机器人互相阻隔而无法到达终点的情形。现有的障碍物空间下死锁解决方案大多是启发式的，缺乏理论支撑。为此，本文针对可行域为半空间交集这一基础情形，通过构建多机器人轨迹规划的模型预测控制（MPC）问题，得到了死锁发生的必要条件，并指出该条件可以理解为机器人所受来自自身目标的吸引力、来自其他机器人的斥力和来自障碍物约束面的斥力三者的受力平衡。在此基础上，提出了一种死锁破解策略，并证明其在一定条件下可避免发生稳定的死锁现象。最后，通过密集空间下的随机对比仿真验证了算法的有效性。

关键词: 多机器人系统, 分布式轨迹规划, 死锁破解, 模型预测控制, 障碍物空间

中图分类号:

V219

董豪泽, 陈昱达, 刘丹, 李忠奎. 障碍物空间下分布式轨迹规划的死锁破解[J]. 航空学报, 2023, 44(S2): 729771-729771.

图/表 8

图1

图2

图3

图4

图5

表 1

表 2

图A1

参考文献 21

1	徐广通，王祝，曹严，等. 动态优先级解耦的无人机集群轨迹分布式序列凸规划［J］. 航空学报， 2022， 43（2）： 325059.
	XU G T， WANG Z， CAO Y， et al. Dynamic-priority-decoupled UAV swarm trajectory planning using distributed sequential convex programming［J］. Acta Aeronautica et Astronautica Sinica， 2022， 43（2）： 325059 （in Chinese）.
2	王祝，刘莉，龙腾，等. 基于罚函数序列凸规划的多无人机轨迹规划［J］. 航空学报，2016， 37（10）： 3149-3158.
	WANG Z， LIU L， LONG T， et al. Trajectory planning for multi-UAVs using penalty sequential convex pro-gramming ［J］. Acta Aeronautica etAstronautica Sinica， 2016， 37（10）： 3149-3158 （in Chinese）.
3	刘哲，陆浩然，郑伟，等. 多滑翔飞行器时间协同轨迹快速规划［J］. 航空学报， 2021， 42（11）： 310-324.
	LIU Z， LU H R， ZHENG W， et al. Rapid time-coordination trajectory planning method for multi-glide vehicles ［J］. Acta Aeronautica et Astronautica Sinica， 2021，42（11）： 524497 （in Chinese）.
4	王通，黄攀峰，董刚奇. 启发式多无人机协同路网持续监视轨迹规划［J］. 航空学报，2020，41（S1）： 723753.
	WANG T， HUANG P F， DONG G Q. Cooperation path planning of multi-UAV in road-network continuous monitoring［J］. Acta Aeronautica et Astronautica Sinica， 2020， 41（S1）： 723753 （in Chinese）.
5	JOSE K， PRATIHAR D. Task allocation and collision-free path planning of centralized multi-robots system for industrial plant inspection using heuristic methods［J］. Robotics and Autonomous Systems， 2016， 80： 34-42.
6	YAN Z， JOUANDEAU N， ALI-CHÉRIF A. Multi-robot heuristic goods transportation［C］∥ 2012 6th IEEE International Conference Intelligent Systems. Piscataway： IEEE Press， 2012： 409-414.
7	YAN Z， JOUANDEAU N， ALI-CHÉRIF A. Sampling-based multi-robot exploration［C］∥ ISR 2010 （41st International Symposium on Robotics） and ROBOTIK 2010 （6th German Conference on Robotics）.Piscataway： IEEE Press， 2010： 1-6.
8	AMATO C， KONIDARIS G， CRUZ G， et al. Planning for decentralized control of multiple robots under uncertainty［C］∥ 2015 IEEE International Conference on Robotics and Automation（ICRA）. Piscataway： IEEE Press， 2015： 1221-1248.
9	AMATO C， KONIDARIS G， OMIDSHAFIEI S， et al. Probabilistic planning for decentralized multi-robot systems［C］∥ 2015 AAAI Fall Symposium. Paol Alto： AAAI： 2015： 10-12.
10	GROVER J， LIU C L， SYCARA K. Why does symmetry cause deadlocks？［J］. FAC-PapersOnLine， 2020， 53（2）： 9746-9753
11	AUGUGLIARO F， SCHOELLIG A P， D’ANDREA R. Generation of collision-free trajectories for a quadrocopter fleet： A sequential convex programming approach［C］∥ 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway： IEEE Press， 2012： 1917-1922
12	PARK J， KIM D， KIM G C， et al. Online distributed trajectory planning for quadrotor swarm with feasibility guarantee using linear safe corridor［J］. IEEE Robotics and Automation Letters， 2022， 7（2）： 4869-4876.
13	WANG L， AMES A D， EGERSTEDT M. Safety barrier certificates for collisions-free multirobot systems［J］. IEEE Transactions on Robotics， 2017， 33（3）： 661-674.
14	PIERSONA， SCHWARTING W， KARAMAN S， et al. Weighted Buffered Voronoi Cells for distributed semi-cooperative behavior［C］∥ IEEE International Conference on Robotics and Automation（ICRA）. Piscataway： IEEE Press， 2020： 5611-5617.
15	ZHOU D J， WANG Z J， BANDYOPADHYAY S， et al. Fast， on-line collision avoidance for dynamic vehicles using Buffered Voronoi Cells［J］. IEEE Robotics and Automation Letters， 2017， 2（2）： 1047-1054.
16	CHEN Y D， GUO M， LI Z K. Deadlock resolution and feasibility Guarantee in MPC-based multi-robot trajectory generation［DB/OL］. arxiv preprint： 2022.06071， 2022.
17	GROVER J， LIU C L， SYCARA K. The before， during， and after of multi-robot deadlock［J］. International Journal of Robotics Research， 2023， 42（6）： 317-336.
18	THRUN S， BURGARD W，FOXD.Probabilistic Robotics［M］. Cambridge： MIT Press， 2006： 503-507.
19	CHEN YD， WANG CH， GUO M， et al. Multi-robot trajectory planning with feasibility guarantee and deadlock resolution： An obstacle-dense environment［J］.IEEE Robotics and Automation Letters， 2023， 8（4）： 2197-2204.
20	DIAMOND S， BOYD S. CVXPY： A Python-embedded modeling language for convex optimization［J］.The Journal of Machine Learning Research，2016， 17（1）： 2909-2913.
21	ANDERSEN ED， ANDERSEN KD. The MOSEK interior point optimizer for linear programming： An implementation of the homogeneous algorithm［M］. Berlin： Springer， 2000： 197-232.

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

参数	单面墙	平行墙d/m			相交墙∂/（°）
参数	单面墙	1.3	1.5	1.7	60	90	135
机器人数量	8	5	7	8	7	10	10
成功数量	100	100	100	100	100	100	100
平均时间/s	6.15	5.74	7.99	6.85	6.49	7.56	7.48

[1]	曹煜琪, 付皓然, 高飞, 吕熙敏. 基于MPCC的鸭翼尾座式垂直起降无人机轨迹跟踪控制算法[J]. 航空学报, 2023, 44(S2): 729950-729950.
[2]	岳承磊, 汪雪川, 岳晓奎, 宋婷. 基于逆强化学习的航天器交会对接方法[J]. 航空学报, 2023, 44(19): 328420-328420.
[3]	文超, 董文瀚, 解武杰, 蔡鸣, 刘日. 基于回访机制的无人机集群分布式协同区域搜索方法[J]. 航空学报, 2023, 44(11): 327561-327561.
[4]	柴源, 罗建军, 王明明. 脉冲推力下多星协同搬运的预测博弈控制[J]. 航空学报, 2022, 43(12): 326112-326112.
[5]	颜黎明, 郭鑫, 赵冬冬. 基于新型权重解析法的永磁电机预测转矩控制[J]. 航空学报, 2022, 43(12): 327785-327785.
[6]	颜黎明, 赵冬冬, 焦宁飞. 基于鲁棒模型的航空交流感应电机预测转矩控制[J]. 航空学报, 2021, 42(9): 324700-324700.
[7]	赵冬冬, 赵国胜, 夏磊, 方淳, 马睿, 皇甫宜耿. 无人机用燃料电池阴极供气系统建模与控制[J]. 航空学报, 2021, 42(7): 324659-324659.
[8]	董凯凯, 罗建军, 马卫华, 高登巍, 谭龙玉. 非合作目标交会的双层MPC全局轨迹规划控制[J]. 航空学报, 2021, 42(11): 524903-524903.
[9]	王子安, 龚正, 陈永亮, 史志伟, 徐锦法. 混合动力复合翼应急迫降在线航迹规划与制导[J]. 航空学报, 2019, 40(10): 323105-323105.
[10]	聂雪媛, 杨国伟. 基于CFD降阶模型的阵风减缓主动控制研究[J]. 航空学报, 2015, 36(4): 1103-1111.
[11]	刘刚, 李传江, 马广富. 应用非线性模型预测控制的绳系卫星Halo轨道保持控制[J]. 航空学报, 2014, 35(9): 2605-2614.
[12]	王超, 张胜修, 郑建飞, 张超. 基于气动特性辨识的飞行器抗饱和自适应控制[J]. 航空学报, 2013, 34(12): 2645-2657.
[13]	王健康, 张海波, 黄向华, 陆波. 基于直升机/涡轴发动机综合仿真平台的发动机非线性模型预测控制[J]. 航空学报, 2012, (3): 402-411.
[14]	彭辉;沈林成;朱华勇. 基于分布式模型预测控制的多UAV协同区域搜索[J]. 航空学报, 2010, 31(3): 593-601.
[15]	姚文荣;孙健国. 涡轴发动机非线性模型预测控制[J]. 航空学报, 2008, 29(4): 776-780.

障碍物空间下分布式轨迹规划的死锁破解

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 21

相关文章 15

编辑推荐

Metrics

本文评价