A Decentralized Approach for Preventing Deadlocks in Multi-Robot Control for Mobile Navigation
- 발행기관 서강대학교 일반대학원
- 지도교수 Changjoo Nam
- 발행년도 2026
- 학위수여년월 2026. 2
- 학위명 석사
- 학과 및 전공 일반대학원 인공지능학과협동과정
- 실제URI http://www.dcollection.net/handler/sogang/000000082362
- UCI I804:11029-000000082362
- 본문언어 영어
- 저작권 논문은 저작권에 의해 보호받습니다.
초록(요약문)
본 연구에서는 안전성과 교착 상태 방지를 모두 보장하는 분산형 다중 로봇 내비게이션을 위한 하이브리드 접근법을 제안한다. 표준 제어 공식을 기반으로, 임시 ``회전교차로''(원형 참조 경로)를 형성하여 경량 교착 상태 방지 메커니즘을 추가한다. 각 로봇은 지역적 peer-to-peer 통신과 기본 충돌 회피를 위한 제어기에만 의존하며, 교착 상태를 회피하기 위해 필요시 회전교차로가 생성되거나 참여한다. 회전교차로의 로봇들은 탈출 조건이 충족될 때까지 한 방향으로 이동하여 목표 지향 운동으로 복귀할 수 있다. 명시적인 교착 상태 해결 방법이 없는 기존의 분산형 방법들과 달리, 본 연구의 회전교차로 기법은 안전 제약 조건을 유지하면서 시스템 전체의 진행을 보장한다. 광범위한 시뮬레이션과 물리 로봇 실험을 통해 본 방법이 특히 밀집되거나 고밀도 시나리오에서 다른 분산형 제어 접근법의 성공률 및 도착률을 일관되게 능가하거나 동등함을 보여준다.
more초록(요약문)
We propose a hybrid approach for decentralized multi-robot navigation that ensures both safety and deadlock prevention. Building on a standard control formulation, we add a lightweight deadlock prevention mechanism by forming temporary ``roundabouts'' (circular reference paths). Each robot relies only on local, peer-to-peer communication and a controller for base collision avoidance; a roundabout is generated or joined on demand to avert deadlocks. Robots in the roundabout travel in one direction until an escape condition is met, allowing them to return to goal-oriented motion. Unlike classical decentralized methods that lack explicit deadlock resolution, our roundabout maneuver ensures system-wide forward progress while preserving safety constraints. Extensive simulations and physical robot experiments show that our method consistently outperforms or matches the success and arrival rates of other decentralized control approaches, particularly in cluttered or high-density scenarios, all with minimal centralized coordination.
more목차
1 Introduction 1
2 Related Work 4
2.1 Centralized Planning and Control 4
2.2 Decentralized Control 5
2.3 Learning-based Approaches 5
2.4 Deadlock Resolution Methods 6
3 Background 7
3.1 Control Lyapunov Functions 7
3.2 Control Barrier Functions 9
3.3 QP-based Control Formulation 10
3.4 Limitations of QP-based Control 12
4 Problem Definition 13
4.1 System Model and Formulation 13
4.2 Assumptions 14
5 Proposed Method 15
5.1 Merry-Go-Round for Deadlock Prevention 15
5.1.1 Deadlock Prediction 18
5.1.2 Roundabout Creation and Adjustment 20
5.1.3 Joining Roundabout 21
5.1.4 Escape Condition 23
5.2 Time Complexity Analysis 23
6 Experiments 25
6.1 Setup for Algorithm Tests 25
6.2 Results 27
6.3 Physical Robot Experiment 30
7 Conclusion 34
