[Algorithm][Path Planning] MAPF Search 성능 향상법

순서

I. 성능 향상 법
II. 우선순위 기반 접근(Priority-Based Approaches)

 

---

I. 성능 향상 법

CCBS의 경우 Agent수가 많아지고 맵이 복잡할수록 성능이 지수적으로 떨어질 수 있다.
(Path 충돌이 발생한 경우 다수의 Agent를 다시 동시에 스케줄링 하기 때문)

 

1. 그룹화(Agent Grouping)

Agent들을 초기 위치, 목표 위치, 경로의 유사성 등을 기준들을 통해 그룹으로 나눈다.
각 그룹 내에서 경로를 계획하고 그룹 내 Agent간 충돌을 해결한다.
그룹간의 경로 계획은 병렬적으로 진행하고 그룹간 충돌은 추가로 해결한다.
다양한 그룹화 기준을 통해 유연하게 문제의 크기를 줄여 각 그룹에 대해 독립적으로 해결할 수 있다.

 

2. 분할정복(Divide and Conquer)

Agent를 나눈 그룹화와 비슷하게 분할정복은 Map을 여러 구역으로 나눈다.
여러개로 나눈 Map의 각 구역내에서 독립적으로 경로를 계획한 후 구역 간 경로를 후에 조정하는 방법이다.

 

3. 우선순위 기반 접근(Priority-Based Approaches)

Agent에 우선순위를 부여하고, 우선순위가 높은 Agent의 경로를 계획. 보장해주고 이후 나머지 Agent의 경로를 조정한다.
우선순위를 선정하는 명확한 룰만 있다면 구현은 비교적 간단하다.
: 내가 사용중인 방식.

 

4. 병렬처리 (Parallel Processing)

Agent들을 멀티스레딩, 분산 컴퓨팅을 통한 병렬처리로 동시에 독립적으로 경로를 계산하여, 나중에 충돌을 해결한다.
다만, 오히려 하드웨어 요구사항이나 구현이 복잡할 수 있다.

 

결과적으로 성능 향상을 위한 방법론들의 목적은 Agent가 많아 질 때 점점 커지는 문제상황(충돌)을 작은 단위로 만드는 것이다.

동시에 하던지 맵을 쪼개던지 Agent를 쪼개던지, 확정 경로를 만들던지...

 

---

II. 우선순위 기반 접근(Priority-Based Approaches)

 

현재 나는 MAPF Conflict를 위해서는 TimeTable-Base 방식을 사용하고
이전글:Conflict방식들

성능을 위해서 우선순위 기반 접근법을 사용한다.

이 두 가지가 아주 깔끔하게 매칭된다고 생각하는데,
1. 우선순위 높은 Agent가 경로를 탐색하고 TimeTable에 등록한다.
2. 다음 Agent가 경로를 탐색하되, 앞선 Agent와 TimeTable 충돌이 발생하면 차선책의 경로를 선정한다.
3. 다음 Agent 반복...

위와 같이 이미 경로를 탐색한 Agent들은 건드리지 않는 것이 우선순위 기반 접근의 방식이다.
CBS의 단점인 충돌한 Agent를 모두 분기하여 재탐색하는 성능저하를 우선순위를 통해 막는 것이다.

물론, 경로 최적화를 위해 높은 우선순위의 Agent가 경로 계획을 다시 해야하는 일도 필요할 수 있다.
T자형 길에서 잠시 옆으로 비켜준다던지 등...

하지만 기본 룰 자체를 우선순위로 선택하는 것이다. 효율에 관한건 별도 문제로 푸는걸로 하자...