HCA* - HA* 공부했으니 이제 Hirearchical Cooperative A* 공부해야죠!

안녕하세요. 오늘은 Hirearchical Cooperative A*에 대해서 공부하려고 합니다.

• SILVER, David. Cooperative pathfinding. In: Proceedings of the aaai conference on artificial intelligence and interactive digital entertainment. 2005. p. 117-122.

이번에는 논문 내용 그대로 정리하지 않고, 제가 이해한 방식대로 정리해보겠습니다.

이론적인 내용을 정확히 이해하지 못하여 아쉬운 부분이 많지만 더 공부하면서 제 걸로 만들도록 하겠습니다.

---

본 논문에서는 MAPF 문제를 해결할 수 있는 decoupled 알고리즘 4개를 제안합니다.

1. Local Repair A*(LRA*)
2. Cooperative A*(CA*)
3. Hirearchical CA*(HCA*)
4. Windowed HCA*(WHCA*)

LRA는 기존에 있던 알고리즘이고, CA*, HCA*, WHCA*는 논문에서 제시된 알고리즘이며 순서대로 성능이 개선됩니다.

• 읽다보면 성장 스토리가 있어서 재밌습니다!

LRA*

LRA* 알고리즘을 간단하게 설명하면 다음과 같습니다.

1. 각 에이전트들은 다른 에이전트와 인접한 경우를 제외하고는 타 에이전트들을 무시하고 경로를 계획합니다.
2. 에이전트들은 계획된 경로대로 이동하다가, 다른 에이전트와 충돌이 발생하게 될 경우에만 경로를 재계획합니다.

LRA* 알고리즘은 빠르고, 간단하다는 장점이 있지만 복잡한 환경에서 여러 에이전트를 다룰 수 없다는 명확한 한계가 존재합니다.

 

좁은 구간에 여러 에이전트가 몰릴 경우, 무차별적인 경로재계획이 발생하면서

오히려 LRA* 때문에 cyclic conflict 같은 문제가 발생할 수 있습니다.

 

이 문제를 어떻게 해결 했을까요?

CA*

CA* 알고리즘을 간단하게 설명하면 다음과 같습니다.

1. Agents = {A1, A2, ... , An}, reservation table = 시간 t에 대해 좌표가 점유되어 있는지 여부를 관리하는 3차원 
2. A = Agents.pop();
3. 에이전트 A에 대해서 reservation table에서 점유된 좌표들을 피하며 시간-경로를 계획한다.
4. 3에서 계획된 시간-경로를 reservation table에 표시한다.
5. Agents에 에이전트가 남아있으면 2로 돌아간다.

 

참고:

최적의 경로를 미리 계산하여 에이전트들에게 할당하는 decoupled, greedy 알고리즘들은

한 에이전트의 path가 다른 에이전트의 path를 침범하면 문제를 해결할 수 없는 니다.

 

구체적인 예시로 다음 예시가 있습니다.

greedy, decoupled 알고리즘으로 이거 풀기 어렵죠 ㅜ

 

일반적으로 바닐라 CA*(의미있는 heuristic을 사용하지 않은 CA*)라고 하면 맨허튼 거리를 heuristic 함수로 사용합니다.

그러나 복잡한 환경에서  맨허튼 거리를 heuristic 함수로 사용하면 성능이 매우 좋지 않다고 합니다.

 

이 문제를 어떻게 해결했을까요?

HCA*

일반적으로 abstract space에서 heuristic 함수의 성능을 높이는 방법은 2가지가 있습니다.

1. abstract space에서의 최적 경로를 미리 계산해두는 것
2. hierarchical abstraction을 적용하는 것

 

1의 경우에는 사용 가능한 경로가 동적으로 변하는 복잡한 멀티 에이전트 환경에서 적합하지 않습니다.

 

2의 경우에는 1) 좋은 hirearchical abstraction을 사용하고, 2) 각 abstraction에서 계산된 값들을 빠르게 재활용 해야합니다.

1. 각 에이전트에 대해서 다른 에이전트들을 무시하고 abstract space의 최적 경로를 저장하는 2차원 맵을 이용하여 heuristic 함수를 사용합니다. 
2. Reverse Resumable A*(RRA*)를 이용하여 abstraction에서 계산된 값들을 재활용합니다.

-> 사용하기 적합하다!

 

하지만 HCA*도 문제들이 있습니다. 하나가 아닙니다!

1. 미션이 종료된 에이전트들이 다른 에이전트의 경로를 막아버리는 경우 valid solution을 찾을 수 없다.
2. 경로를 계획하는 에이전트의 순서가 valid solution을 찾는 것에 아주 큰 영향을 끼친다.
3. 속도를 향상시키기 위해서 매우 많은 메모리를 사용하게 된다.

이 문제들은 어떻게 해결했을까요?

WHCA*

논문에서는 각 에이전트들이 목적지까지의 경로를 탐색하는 것이 아니라, 주어진 윈도우 사이즈만큼만 경로를 탐색하는 것으로 문제를 해결했습니다.

에이전트들은 경로를 어느 정도 진행했을 때, 다시 윈도우 사이즈만큼만 경로를 탐색합니다.

모든 에이전트가 목적지에 도착할 때까지 경로 탐색이 반복됩니다.

 

처음부터 모든 경로를 계획하는 것이 아니기 때문에 많은 문제가 해결된다는 것이 신기하지 않나요?

윈도우 사이즈를 적절히 설정하는 것으로 서로의 상태를 고려할 수 있게 되는 것 같습니다.

 

그리고 시간이 지날 때마다 에이전트들의 경로를 재탐색하기 때문에 HCA*에서 지적되었던 문제 1, 2도 해결이 됩니다.

모든 경로를 계획하는 것도 아니기 때문에 문제 3도 해결되죠!

결과

당연하게도(?) 실험 결과는 LRA*, CA*, HCA*, WHCA* 순으로 성능이 향상됩니다.

실험 결과를 통해 얻어갈 수 있는 것은 윈도우 사이즈와 WHCA* 성능의 상관 관계, 그리고 지표들이 있었습니다.

 

WHCA*의 경우 윈도우 사이즈가 작으면 LRA*와 비슷한 양상을 보이고, 윈도우 사이즈가 커지면 HCA*와 비슷한 양상을 보이게 됩니다.

 

실험에 따르면 윈도우 사이즈는 적당한 크기인 16일 때 모든 환경에서 가장 강인한 성능을 보여줬다고 합니다.

 

일반적으로 윈도우 사이즈는 주어진 환경에서 가장 길게 발생할 수 있는 교착 상태의 길이 이상이어야 합니다.

예시) RTS 게임에서 적절한 윈도우 사이즈는 그룹에 존재하는 유닛 수만큼입니다.

 

그리고 논문에서 제시한 지표들은 다음과 같습니다.

혹시 경로 계획 알고리즘을 개발하고 있으시다면 다음 지표를 통해서 경로 계획 알고리즘의 실용성, 계획된 경로의 퀄리티를 추정해보세요!

• 미션 성공률(계획된 경로의 길이가 정해진 값보다 크면 실패했다고 판단)
• 에이전트가 미션을 마치기까지 걸린 시간
• cycle conflict 발생 획수
• 경로계획에 소요된 연산 시간