📝 Publications

Homotopy-aware Multi-agent Navigation via Distributed Model Predictive Control

Abstract: Multi-agent trajectory planning requires ensuring both safety and efficiency, yet deadlocks remain a significant challenge, especially in obstacle-dense environments. Such deadlocks frequently occur when multiple agents attempt to traverse the same long and narrow corridor simultaneously. To address this, we propose a novel distributed trajectory planning framework that bridges the gap between global path and local trajectory cooperation. At the global level, a homotopy-aware optimal path planning algorithm is proposed, which fully leverages the topological structure of the environment. A reference path is chosen from distinct homotopy classes by considering both its spatial and temporal properties, leading to improved coordination among agents globally. At the local level, a model predictive control-based trajectory optimization method is used to generate dynamically feasible and collision-free trajectories. Additionally, an online replanning strategy ensures its adaptability to dynamic environments. Simulations and experiments validate the effectiveness of our approach in mitigating deadlocks. Ablation studies demonstrate that by incorporating time-aware homotopic properties into the underlying global paths, our method can significantly reduce deadlocks and improve the average success rate from 4%-13% to over 90% in randomly generated dense scenarios.

Haoze Dong, Meng Guo, Chengyi He, Zhongkui Li

Asynchronous Spatial-Temporal Allocation for Trajectory Planning of Heterogeneous Multi-Agent Systems

Abstract: To plan the trajectories of a large-scale heterogeneous swarm, sequentially or synchronously distributed methods usually become intractable due to the lack of global clock synchronization. To this end, we provide a novel asynchronous spatial-temporal allocation method. Specifically, between a pair of agents, the allocation is proposed to determine their corresponding derivable time-stamped space and can be updated in an asynchronous way, by inserting a waiting duration between two consecutive replanning steps. It is theoretically shown that the inter-agent collision is avoided and the allocation ensures timely updates. Comprehensive simulations and comparisons with state-of-the-art baselines validate the effectiveness of the proposed method and illustrate its improvement in completion time and moving distance. Finally, hardware experiments are carried out, where 8 heterogeneous unmanned ground vehicles with onboard computation navigate in cluttered scenarios with high agility.

Yuda Chen, Haoze Dong, Zhongkui Li

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

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

Deadlock Resolution of Distributed Trajectory Planning in Obstacle Space (Chinese)

董豪泽, 陈昱达, 刘丹, 李忠奎

Haoze Dong, Yuda Chen, Dan Liu, Zhongkui Li

The conference version received the Best Paper Award at CCSICC 2023 🏆