Safe Interval RRT* for Scalable Multi-Robot Path Planning in Continuous Space
연속 공간에서 확장 가능한 다중 로봇 경로 계획을 위한 안전 간격 RRT*
- 주제어 (키워드) Multi-Robot Path Planning , Multi-Robot Motion Planning
- 발행기관 서강대학교 일반대학원
- 지도교수 남창주
- 발행년도 2025
- 학위수여년월 2025. 2
- 학위명 석사
- 학과 및 전공 일반대학원 전자공학과
- 실제 URI http://www.dcollection.net/handler/sogang/000000079439
- UCI I804:11029-000000079439
- 본문언어 영어
- 저작권 서강대학교 논문은 저작권 보호를 받습니다.
초록 (요약문)
In this thesis, we consider the problem of Multi-Robot Path Planning (MRPP) in continuous space. The difficulty of the problem arises from the extremely large search space caused by the combinatorial nature of the problem and the continuous state space. We propose a two-level approach where the low level is a sampling-based planner Safe Interval RRT* (SI-RRT*) that finds a collision-free trajectory for individual robots. The high level can use any method that can resolve inter-robot conflicts where we employ two representative methods that are Prioritized Planning (SI-CPP) and Conflict Based Search (SI-CCBS). Experimental results show that SI-RRT∗ can quickly find a high-quality solution with a few samples. SI-CPP exhibits improved scalability while SI-CCBS produces higher-quality solutions compared to the state-of-the- art planners for continuous space.
more초록 (요약문)
본 논문에서는 연속 공간에서의 다중 로봇 경로 계획(Multi-Robot Path Planning, MRPP) 문제를 다루고자 한다. 이 문제는 조합적 특성과 연속적인 상태 공간으로 인해 탐색 공간이 매우 커지는 어려움이 있다. 이를 해결하기 위해 두 단계 접근법을 제안한다. 하위 단계에서는 개별 로봇의 충돌 없는 경로를 찾기 위해 샘플링 기반 계획 기법인 Safe Interval RRT* (SI-RRT*)를 사용한다. 상위 단계에서는 로봇 간 충돌을 해결할 수 있는 모든 방법을 적용할 수 있으며, 본 연구에서는 우선순위 기반 계획(SI-CPP)과 충돌 기반 탐색(SI-CCBS)이라는 두 가지 대표적인 방법을 사용한다. 실험 결과, SI-RRT* 는 소수의 샘플만으로도 빠르게 높은 품질의 솔루션을 찾을 수 있음을 보인다. SI-CPP 는 확장성이 향상된 결과를 보이며, SI-CCBS 는 연속 공간에서 기존 최신 계획 기법에 비해 더 높은 품질의 솔루션을 제공한다.
more목차
1 Introduction 1
2 Related works 4
3 Background 6
3.1 Rapidly-Exploring Random Trees 6
3.2 Prioritized Planning 7
3.3 Conflict-Based Search 8
4 Problem Definition 10
5 Proposed Method 13
5.1 Single-Robot Planner: Safe Interval RRT* 13
5.1.1 Functions for tree expansion 13
5.1.2 Functions for tree optimization 14
5.1.3 SI-RRT* 18
5.1.4 Analysis of SI-RRT* 19
5.1.5 An extension for kinodynamic constraints of robots 21
5.2 Conflict resolution for multiple robots 22
5.2.1 Safe Interval Continuous-space PP (SI-CPP) 22
5.2.2 Safe Interval Continuous-space CBS (SI-CCBS) 23
6 Experiments 25
6.1 Single-robot path planning 26
6.2 Multi-robot path planning 27
6.3 Dynamic simulation 30
7 Conclusion 37
Bibliography 38
