障碍物空间下分布式轨迹规划的死锁破解
收稿日期: 2023-10-26
修回日期: 2023-10-30
录用日期: 2023-11-22
网络出版日期: 2023-12-13
基金资助
国家自然科学基金(U2241214)
基于优化的分布式轨迹规划方法因具有较强的可解释性和可扩展性而备受关注，但由于缺少中心节点和全局优先级，容易诱发集群运动陷入死锁，即若干机器人互相阻隔而无法到达终点的情形。现有的障碍物空间下死锁解决方案大多是启发式的，缺乏理论支撑。为此，本文针对可行域为半空间交集这一基础情形，通过构建多机器人轨迹规划的模型预测控制 （MPC）问题，得到了死锁发生的必要条件，并指出该条件可以理解为机器人所受来自自身目标的吸引力、来自其他机器人的斥力和来自障碍物约束面的斥力三者的受力平衡。在此基础上，提出了一种死锁破解策略，并证明其在一定条件下可避免发生稳定的死锁现象。最后，通过密集空间下的随机对比仿真验证了算法的有效性。
董豪泽 , 陈昱达 , 刘丹 , 李忠奎 . 障碍物空间下分布式轨迹规划的死锁破解[J]. 航空学报, 2023 , 44(S2) : 729771 -729771 . DOI: 10.7527/S1000-6893.2023.29771
| 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. |
/
| 〈 |
|
〉 |
CJA