Task and Motion Planning with Deadlock Resolution for Multi-Agent Systems

다국어 초록 (Multilingual Abstract)

This thesis proposes an integrated Task and Motion Planning (TAMP) framework to resolve deadlocks occurring in cluttered environments and ensure efficient mission execution for Multi-Agent Systems (MAS). The autonomy of unmanned systems typically follows a hierarchical structure composed of Mission Planning, Task Planning, Motion Planning, and Control. Existing studies possess limitations by treating each layer inde- pendently, which results in the infeasibility of plans generated at the high level or inefficient operations at the low level. In particular, in MAS en- vironments adopting a decentralized decision-making architecture, local path planning by individual agents frequently induces path entanglement and subsequent deadlocks in environments cluttered with static obstacles, such as narrow passages. To address these issues, this thesis proposes an integrated TAMP framework that connects discrete task planning and continuous motion planning via a closed-loop system. In the continuous space planning phase, a Collision-Aware Adaptive Horizon Model Predictive Control (CA-AH-MPC) is proposed to account for collision risks. The proposed algorithm reduces unnecessary computational costs by dynamically ad- justing the length of the prediction horizon based on predicted collision risks. Simultaneously, to prevent potential safety degradation caused by horizon reduction, safety is enforced by integrating a Control Barrier Function, which guarantees the set invariance of the safety set, as a con- straint. For task planning and TAMP integration, based on the existing TAS- AMP (Approximate Message Passing) algorithm for Task Assignment and Scheduling (TAS), high-level mission reallocation and coordination rules are additionally introduced to resolve deadlocks occurring in obstacle en- vironments. The proposed framework features a structure in which the TAS-AMP-based high-level Task Planner and the CA-AH-MPC-based low-level Motion Planner interact. The performance of CA-AH-MPC was validated through Monte Carlo simulations, and simulations in various ob- stacle map environments confirmed that the integrated TAMP framework effectively resolves deadlocks and successfully completes missions.

목차 (Table of Contents)

• I. Introduction 1
• 1.1 Background 1
• 1.2 Literature review and statement of contributions 3
• 1.2.1 Motion planning 3
• 1.2.2 Task and motion planning 10
• 1.2.3 Contributions 13
• 1.3 Thesis overview 14
• II. Overall framework and problem formulation 16
• 2.1 Overview of TAMP framework 16
• 2.2 Problem formulation 17
• 2.2.1 Task planning 17
• 2.2.2 Motion planning 20
• III. Hierarchical task and motion planning strategy 26
• 3.1 Motion planning in open space 26
• 3.2 Integrated TAMP Strategy in obstacle-rich environments 34
• 3.2.1 Global path planning and tracking 34
• 3.2.2 Deadlock resolution strategy 36
• IV. Simulation results 43
• 4.1 Motion planning in open space 43
• 4.1.1 Analysis of conflict resolution in an example scenario 44
• 4.1.2 Ablation study in a high-density crossing environment 47
• 4.2 Integrated TAMP strategy in obstacle-rich environments 52
• 4.2.1 Motion planning result 53
• 4.2.2 TAMP result 59
• V. Conclusion 65
• Summary (in Korean) 67