Abstract

• 기존 ORCA(https://velog.io/@jk01019/Reciprocal-Collision-Avoidance-RCA)는 계산적으로 효율적이며 많은 수의 에이전트에 대해 잘 확장
  • 그러나, 좁은 통로나 제한된 공간을 통한 내비게이션과 같은 많은 시나리오에서, 에이전트들의 이기적인 행동으로 인해 교착 상태가 발생할 수 있으며, 결과적으로 이들은 목표를 달성할 수 없습니다.
• 이를 해결하기 위해, 교착 상태에 빠진 것으로 보이는 에이전트들의 하위 그룹을 조정하는, 지역적으로 제한된 다중 에이전트 경로 찾기(MAPF) 솔버의 적용을 제안
  • (후자를 감지하기 위해 간단하면서도 효율적인 ad-hoc 루틴을 제안).
  • 'ad-hoc 네트워크'는 중앙 관리 장치 없이 각기 다른 기기들이 서로 직접 통신을 하는 네트워크 형태
    • 서로, 현재 위치와 원하는 목표에 대한 정보를 교환
• 우리는 현대 MAPF 솔버들이 일반적으로 요구하는, 그리드 기반 MAPF 사례를 구축하는 방법을 제시
• 우리는 실험에서 이들 중 두 가지, 즉 PUSH AND ROTATE(https://velog.io/@jk01019/PUSH-AND-ROTATE) 및 CONFLICT BASED SEARCH (ECBS)(https://velog.io/@jk01019/CONFLICT-BASED-SEARCH-ECBS)의 경계가 있는 부최적 버전을 평가하고, 그들의 내비게이션 파이프라인에 포함시킴으로써 성공률이 크게 증가

Introduction

중앙집중식 접근법

• 중앙집중식 접근법은 모든 에이전트와 환경에 대한 정보를 가지고 있으며, 에이전트와 통신할 수 있는 (중앙) 컨트롤러가 존재한다고 가정
• 컨트롤러는 충돌 없는 공동 계획을 만들고 에이전트가 이를 실행하게 합니다.
• 이러한 접근법의 주요 장점 중 하나는 강력한 이론적 보장입니다.

비중앙집중식 접근법

• 좁은 공간을 통한 내비게이션과 같은 특정 시나리오에서는 이러한 메커니즘이 실패할 가능성이 높습니다.(그림 1-a)

• 이 논문에서는 지역 중심의 다중 에이전트 경로 찾기(MAPF) 솔버를 포함하는 것이, 이 문제를 완화하고 임무 완료 가능성을 높이는 방법을 연구합니다.
• 
• 그림 1-b,c,d를 보십시오.
• 이 솔버들이 적용되기 위해 먼저 간단하면서도 효과적인 교착 상태 탐지 메커니즘을 설계합니다.
• 교착 상태에 처하면, 지역적으로 조정된 분산 다중 에이전트 시스템이 형성됩니다.
  • 즉, 교착 상태에 빠진 에이전트는 현재 위치와 원하는 목표에 대한 정보를 교환하므로 각 에이전트는 동일한 (지역) 세계 모델을 형성하고 운영
• 다음으로, 공유된 세계 모델과 일치하고 현대 그래프 기반 MAPF 솔버의 입력으로 사용되는 그리드 기반 MAPF 사례를 만드는 방법을 제안
  • 구체적으로, MAPF를 해결하기 위해 PUSH AND ROTATE [2]와 Conflict Based Search (ECBS)의 경계가 있는 부최적 버전 [3]의 조합을 사용할 것을 제안
  • MAPF 솔루션이 얻어지면 모든 에이전트는 모두가 MAPF 목표에 도달할 때까지 이를 따릅니다. 이렇게 되면 개별 경로를 따르도록 전환

• 이 작업은 [4]에 제시된 예비 연구를 바탕으로 합니다. 논문의 주요 새로운 기여 4가지
  • 도메인에 독립적인, 쉽게 구현할 수 있는 교착 상태 탐지 메커니즘을 제시
  • 교착 상태를 해결하기 위해 MAPF 사례를 형성하는 새로운 접근법을 제시
    • 이러한 루틴을 철저히 설명하고 알고리즘의 완전한 의사 코드를 제시
  • MAPF를 해결할 때 서로 보완하는 MAPF 솔버의 조합을 사용
    • PUSH AND ROTATE / CONFLICT BASED SEARCH (ECBS)

Related Work

다중 에이전트 경로 찾기

• 모든 에이전트에 대한 중앙집중식 컨트롤러가 존재한다는 본질적인 가정은, MAPF 연구에서 지배적입니다.
• 현재 MAPF를 최적으로 해결하기 위해 널리 사용되는 Conflict-Based Search (CBS) [7]는, MAPF 문제를 최적으로 해결하는 열쇠입니다.
• CBS의 성능을 향상시키는 여러 가지 개선 사항이 있습니다 [8], [9].
• 그러나 여전히 좁은 시간 제약 하에서 많은 수의 에이전트에 대한 최적 해결책을 얻는 것은 문제
  • 이 문제를 완화하는 한 가지 방법은 예를 들어 ECBS [3]가 제공할 수 있는 경계가 있는 부최적 해결책을 찾는 것
  • 또 다른 방법은 돌 이동 솔버에서 아이디어를 적용하는 알고리즘을 사용하는 것입니다 [10], [2].
  • 이러한 알고리즘은 매우 빠르고 많은 수의 에이전트에 잘 확장됩니다.
  • 그러나 종종 그들의 해결책 비용이 높습니다.
• 우선 순위가 있는 계획자는 두 접근법의 이점을 누립니다.
  • 그들은 종종 실제로 최적에 가까운 해결책을 찾고 눈에 띄게 빠르고 확장 가능합니다.
• 그러나 일부 특별한 경우를 제외하고는 그들은 완전하지 않습니다 [11].

분산 충돌 회피

• 충돌 회피를 위한 다양한 알고리즘이 존재하며, 주로 이동 제약, 관측/통신 제한 등과 관련된 기본 가정에서 다릅니다.
• 현재 가장 일반적인 접근법은 속도 장애물(VO) 개념에 기반을 둔 것입니다.
• 속도 장애물은 원래 [12]에서 설명되었으며, [13]에서는 상호 속도 장애물(RVO) 구축을 기반으로 한 상호 충돌 회피 방법이 제시되었습니다.
• 그 후, 속도 기반 방법은 지속적으로 수정되었으며,
• 다양한 수정 중에서도 가장 발전된 것은 RVO와 달리, 특정 온건한 가정 하에서 충돌의 부재를 보장할 수 있는 ORCA 기반 알고리즘입니다 [1].
• ORCA를 기반으로 하는 여러 알고리즘이 있으며, 이는 위치 정확도와 운동 제약 [16], [17], [18]을 고려
• 또 다른 충돌 회피 접근법은 보로노이 셀 [19], [20] 구축을 기반으로 합니다.
  • 이러한 방법들은 이차 프로그래밍을 포함하므로 일반적으로 ORCA(선형 프로그래밍에 의존)보다 느리지만, 고차 동력학을 고려할 수 있으며 이웃 에이전트의 속도를 알 필요가 없습니다.
• 마지막으로, 기계 학습은 충돌 회피 정책을 생성하는 데 사용될 수 있습니다 [21], [22]."