Concurrent-Allocation Task Execution for Multi-Robot Path-Crossing-Minimal Navigation in Obstacle Environments
Binbin Hu, Weijia Yao, Zhou Yanxin, Henglai Wei, Chen Lv
AI summary
Problem
Existing multi-robot path-crossing-minimal navigation methods rely on distance-based goal assignment, which becomes computationally intractable or infeasible when obstacles block direct paths, leading to detours, conflicts, and high processing loads.
Approach
The authors encode robot allocation, convergence, and obstacle avoidance into integer and control barrier function constraints within an online optimization framework that simultaneously minimizes allocation costs and slack variables to implicitly reduce path crossings without explicit path planning.
Key results
- Guarantees solution feasibility and asymptotic convergence in obstacle environments
- Reduces computational burden by concurrently computing optimal allocation and control inputs
- Outperforms state-of-the-art baselines in feasibility and efficiency across 2D/3D simulations and multi-AMR experiments
- Effectively handles dynamic obstacles, evades deadlocks, and navigates narrow gaps
Why it matters
Enables reliable and efficient multi-robot coordination in cluttered, real-world settings like warehouses and search operations, advancing scalable autonomous fleet navigation.
Abstract
Reducing undesirable path crossings among tra- jectories of different robots is vital in multi-robot navigation missions, which not only reduces detours and conflict scenarios, but also enhances navigation efficiency and boosts productiv- ity. Despite recent progress in multi-robot path-crossing-minimal (MPCM) navigation, the majority of approaches depend on the minimal squared-distance reassignment of suitable desired points to robots directly. However, if obstacles occupy the passing space, calculating the actual robot-point distances becomes complex or intractable, which may render the MPCM navigation in obstacle environments inefficient or even infeasible. In this paper, the concurrent-allocation task execution (CATE) algorithm is presented to address this problem (i.e., MPCM navigation in obstacle environments). First, the path-crossing- related elements in terms of (i) robot allocation, (ii) desired-point convergence, and (iii) collision and obstacle avoidance are en- coded into integer and control barrier function (CBF) constraints. Then, the proposed constraints are used in an online constrained optimization framework, which implicitly yet effectively mini- mizes the possible path crossings and trajectory length in obstacle environments by minimizing the desired point allocation cost and slack variables in CBF constraints simultaneously. In this way, the MPCM navigation in obstacle environments can be achieved with flexible spatial orderings. Note that the feasibility of solutions and the asymptotic convergence property of the proposed CATE algorithm in obstacle environments are both guaranteed, and the calculation burden is also reduced by concurrently calculating the optimal allocation and the control input directly without the path planning process. Finally, extensive simulations and experiments are conducted to validate that the CATE algorithm (i) outperforms the existing state-of-the-art baselines in terms of feasibility and efficiency in obstacle environments, (ii) is effective in environments with dynamic obstacles and is adaptable for per- forming various navigation tasks in 2D and 3D, (iii) demonstrates its efficacy and practicality by 2D experiments with a multi-AMR onboard navigation system, and (iv) provides a possible solution to evade deadlocks and pass through a narrow gap. This work was supported in part by the Agency for Science, Technology and Research (A*STAR), Singapore, through the MTC Individual Research under Grant M22K2c0079; in part by the CoE Dean’s Interdisciplinary Grant, Nanyang Technological University; and in part by the Ministry of Education (MOE), Singapore, through Tier 2 under Grant MOE-T2EP50222- 0002. The work of Yao was supported in part by the National Natural Science Foundation of China under Grant 62573182, and in part by the State Key Laboratory of Digital-Intelligent Modeling and Simulation. The work of Wei was supported by the Key R&D Program of Shandong Province, China, under Grant 2023CXGC010111 (Corresponding author: Chen Lv). Bin-Bin Hu, Yanxin Zhou, and Chen Lv are with the School of Mechanical and Aerospace Engineering, Nanyang Technological University, Singapore, 637460 (e-mails: {binbin.hu, yanxin.zhou, lyuchen}@ntu.edu.sg). Weijia Yao is with the School of Robotics, Hunan University, Hunan 410082, P.R. China. (e-mail: wjyao@hnu.edu.cn). Henglai Wei is School of Transportation Science and Engineering, Beihang University, Beijing, China, 100191, P.R. China. (e-mail: wei- henglai@gmail.com).