Very Large-scale Multi-Robot Task Allocation in Challenging Environments via Robot Redistribution
- 주제어 (키워드) Multi-Robot System , Multi-Robot Task Allocation
- 발행기관 서강대학교 일반대학원
- 지도교수 남창주
- 발행년도 2024
- 학위수여년월 2024. 8
- 학위명 석사
- 학과 및 전공 일반대학원 전자공학과
- 실제 URI http://www.dcollection.net/handler/sogang/000000078853
- UCI I804:11029-000000078853
- 본문언어 영어
- 저작권 서강대학교 논문은 저작권 보호를 받습니다.
초록 (요약문)
We consider the Multi-Robot Task Allocation (MRTA) problem that aims to optimize an assignment of multiple robots to multiple tasks in challenging environments which are with densely populated obstacles and narrow passages. In such environments, conventional methods optimizing the sum-of-cost are of- ten ineffective because the conflicts between robots or conflicts between obsta- cles and robots incur additional costs (e.g., collision avoidance, waiting). Also, an allocation that does not incorporate the actual robot paths could cause deadlocks, which significantly degrade the collective performance of the robots. We propose a scalable MRTA method that considers the paths of the robots to avoid collisions and deadlocks which result in a fast completion of all tasks (i.e., minimizing the makespan). To incorporate robot paths into task alloca- tion, the proposed method constructs a roadmap using a Generalized Voronoi Diagram. The method partitions the roadmap into several components to know how to redistribute robots to achieve all tasks with less conflicts between the robots. In the redistribution process, robots are transferred to their final desti- nations according to a push-pop mechanism with the first-in first-out principle. From the extensive experiments, we show that our method can handle instances with hundreds of robots in dense clutter while competitors are unable to com- pute a solution within a time limit.
more초록 (요약문)
본 연구는 장애물이 밀집되어 있고 좁은 통로가 존재하는 복잡한 환경에서 여러 로봇을 여러 작업에 할당하는 것을 최적화하는 것을 목표로 하는 다중 로봇 작업 할당 문제를 다룬다. 이러한 환경에서는 로봇 간의 충돌 또는 장애물과 로봇 간의 충돌로 인해 충돌 회피 및 대기등의 추가적인 비용이 발생하기 때문에 로봇 운용 비용의 합계를 최적화하는 기존 방식은 종종 비효율적이다. 또한, 실제 로봇 경로를 반영하지 않은 할당 방법은 교착 상태를 유발하여 로봇의 총체적인 성능을 크게 저하시킬 수 있다. 본 연구는 로봇의 경로를 고려하여 충돌과 교착 상태를 피함으로써 모든 작업을 빠르게 완료할 수 있는 확장성이 높은 다중 로봇 작업 할당 방법을 제안한다. 로 봇 경로를 작업 할당에 통합하기 위해 일반화된 보로노이 다이어그램 (Generalized Voronoi Diagram)을 활용하여 로드맵을 구성한다. 제안하는 방법은 로드맵을 여 러 구역으로 분할하여 로봇 간의 충돌을 줄이면서 모든 작업을 수행하기 위해 로봇을 재분배한다. 재분배 과정에서 로봇은 선입 선출 원칙에 따라 푸시-팝 메커니즘 (push-pop mechanism)에 따라 최종 목적지로 이동한다. 광범위한 실험을 통해 비교 방법들이 제한 시간 내에 결과를 도출하지 못하는 동안 제안하는 방법은 복잡한 환경에서 수백 대의 로봇을 다룰 수 있음을 보여준다.
more목차
1 Introduction 1
2 Related works 5
3 Background 10
3.1 Matching algorithms 10
3.1.1 Integer Linear Programming 11
3.1.2 Hungarian method 11
3.1.3 Greedy method 12
3.2 Generalized Voronoi Diagram 13
3.2.1 Definition and construction of GVD 14
3.2.2 Utilization of GVD in robot navigation 15
4 Problem Description 16
5 Proposed Method 21
5.1 Environment partitioning 22
5.2 Demand and supply analysis 23
5.3 Robot redistribution plan 26
5.4 Conflict-aware task allocation 32
5.5 Analysis 39
6 Experiments 45
6.1 Comparison with the methods resolving conflicts explicitly 49
6.2 Comparisons with the methods without conflict resolution 52
7 Conclusion 59
Bibliography 61
