RHCR 란

MAPF 문제를 해결하기 위해 사용하는 알고리즘이다.
다수의 에이전트가 충돌하지 않고 목표 지점까지 이동하는 경로를 계획하는 문제를 풀기 위한 방법론을 나타내는 것이다.
특히 대규모 창고나 물류센터에서 여러 로봇이 효율적으로 작업할 때 중요한 알고리즘이다.

실행해보기

https://github.com/Jiaoyang-Li/RHCR

위의 링크에 들어가면 알고리즘이 아주 잘 구현되어 있다.. 앞으로 다른 것들을 하기 위해 위 코드를 먼저 돌려보았다.

우선 위 레포를 클론받은 후 아래대로 진행하면 된다.
❗️MacOS 기준이다.

1. Boost 라이브러리 설치

brew install boost // masOS 기준

2. 코드 다운로드 및 컴파일

cmake . // 컴파일
make

3. 코드 실행

./lifelong -m maps/sorting_map.grid -k 800 --scenario=SORTING --simulation_window=5 --planning_window=10 --solver=PBS --seed=0
// .lifelong 이라는 실행 파일을 사용하여 시물레이션 실행
// RHCR with PBS 를 sorting center 맵에서 800명의 에이전트와 함께 실행

./lifelong -m maps/kiva.map -k 100 --scenario=KIVA --simulation_window=1 --solver=ECBS --suboptimal_bound=1.5 --dummy_path=1 --seed=0
// ECBS 알고리즘을 Kiva 맵에서 w=1.5로 실행

위에서 궁금할 만한 변수??들을 정리해보았다.

• m: 맵 파일을 지정. 예를 들어, maps/sorting_map.grid는 정렬 센터를 나타내는 맵 파일.
• k: 에이전트의 수를 의미. 예시에서는 800명 또는 100명의 에이전트를 사용.
• -scenario: 시뮬레이션 시나리오 지정. SORTING은 정렬 센터 시나리오, KIVA는 창고 시나리오
• -simulation_window: 재계획 주기 h를 지정. 즉, 몇 초마다 경로를 다시 계산할지 결정.
• -planning_window: 계획 창 w를 지정. 이는 경로 계획을 몇 초 동안 수행할지 결정하는 값.
• -solver: MAPF 문제를 푸는 알고리즘을 지정. 여기서는 PBS, ECBS와 같은 알고리즘을 사용할 수 있음.
• -suboptimal_bound: ECBS 알고리즘에서 사용하는 서브옵티멀 바운드. 값이 클수록 성능은 빠르지만 경로가 최적에서 멀어짐.
• -seed: 난수 생성 시 사용되는 시드 값. 시뮬레이션의 일관성을 유지하는 데 사용됨.

실행 결과

RHCR의 알고리즘으로 또 2가지가 있다.

1️⃣ PBS

우선순위를 기반으로 충돌을 해결하는 알고리즘이다.
우선순위가 낮은 에이전트는 우선순위가 높은 에이전트의 경로를 피해야 하므로 최적 경로를 보장하기 어렵다.

에이전트 수가 적거나 우선순위 기반으로 경로를 설정할 때 사용하기가 적합하다.

./lifelong -m maps/sorting_map.grid -k 800 --scenario=SORTING --simulation_window=5 --planning_window=10 --solver=PBS --seed=0

위와 같은 명령어로 PBS를 실행할 수 있다.

사진과 같이 출력된다!

• 여기서는 "PBS"가 출력되고 있으며, 각 타임스텝마다 성공적으로 처리된 작업의 수가 기록된다.
• ex. Timestep 45에서 115개의 작업이 완료, 이후 Timestep 50에서는 130개의 작업이 완료되었음을 나타낸다.

2️⃣ ECBS

이는 PBS와 달리 서브옵티멀 경로를 허용하여 빠른 충돌을 해결하는 것이다 ! 즉, 경로 품질을 다소 희생하면서도 CBS보다는 빠르게 충돌을 해결할 수 있는 것이다.

충돌이 발생할 때마다 경로를 조정하여 충돌 없는 경로를 탐색하게 된다.

에이전트 수가 많고, 어느 정도 경로 품질을 희생하면서도 속도를 높이고 싶을 때 적합한 방법이다.

./lifelong -m maps/kiva.map -k 100 --scenario=KIVA --simulation_window=1 --solver=ECBS --suboptimal_bound=1.5 --dummy_path=1 --seed=0

위와 같은 명령어로 ECBS를 실행할 수 있다.

사진과 같이 출력된다!

• 각 타임스텝마다 "ECBS"가 출력되고, 성공한 작업의 수와 경과 시간이 기록된다.
• ex. Timestep 529에서 3개의 작업이 완료, 그 이후로 매번 1~6개의 작업이 완료되었음을 나타낸다.

  Timestep 529
  ECBS:Succeed,0.017838,0,0,3258,5890,270,265,46,0,1073741823
  3 tasks has been finished

→ 더 빠른 처리를 목표로 하므로 PBS보다 타임스텝이 훨 빠르다 !!!

---

오늘은 이렇게 RHCR을 돌려보고 두 가지 방법의 차이점에 대해 탐구해보았다. 다음에는 무얼 할까나 ~