MAPF 알고리즘들에서 사용되는 지표 - 만들었으면 얼마나 좋은지 봐야겠죠?

안녕하세요. 오늘은 MAPF 알고리즘들에서 널리 사용되는 지표들에 대해서 알아보려고 합니다.

 

알고리즘을 고안하는 것만큼이나 중요하는 것이 바로 성능을 측정하는 것입니다.

알고리즘을 평가할 때 사용되는 지표는 일반적으로 실행 시간과 메모리 사용량입니다.

 

하지만 MAPF 알고리즘들은 NP-hard 문제를 풀기 때문에 실행 시간을 O 표기법으로 표현하는 것이 큰 의미가 없습니다.

그러면 그 많은 연구들은 어떤 지표들을 사용하고 있을까요?

 

---

0.  테스트 환경

테스트 환경을 명시하는 것이 굉장히 중요합니다.

모든 환경에서 최적의 성능을 보여주는 MAPF 알고리즘은 없기 때문인데요.

 

지도가 어떻게 구성되어 있는지, 얼마나 개방되었는지, 통로가 좁은지, 에이전트 수 등

다양한 요소가 알고리즘의 성능에 영향을 줄 수 있습니다.

 

고안한 알고리즘의 강점과 약점을 정확히 분석하기 위해서는 위와 같은 요소들을 고려하면서 테스트 해야 합니다.

 

1.  알고리즘 실행 시간 

MAPF 알고리즘의 경우 실시간성이 매우 중요할 때가 많기 때문에 실행 시간이 굉장히 중요합니다.

주어진 문제 환경에서 에이전트 수에 따른 실행 시간을 측정하는 것이 일반적입니다.

2. 성공률

"최적해를 계산하는데 무슨 성공률?" 이렇게 생각하실 수도 있습니다.

 

decoupled 알고리즘들의 경우 대체로 최적성과 완전성을 보장하지 않습니다.

coupled 알고리즘들도 실행 시간을 줄이기 위해 sub-optimal 해를 구하는 경우가 많고, 이마저도 실행 시간이 일정 이상 커지면 실패했다고 판단합니다.

 

3. 모든 미션을 해결하는데 걸리는 시간

Makespan이라고도 하는데 모든 에이전트가 미션을 해결하기까지 걸린 시간입니다. 

 

4. 미션을 해결하는데 걸린 시간의 총합

Sum of Costs라고도 하는데 모든 미션을 해결하는데 걸린 평균 시간이라고 보셔도 됩니다.

 

3번 Makespan과 비슷하다고 생각할 수 있는데 다음 경우를 생각해봅시다.

 

에이전트가 10개 있을 때, 하나의 에이전트가 미션을 해결하기까지 100초 걸리고 다른 에이전트들은 모두 10초가 걸립니다.

이 상황에서 Makespan은 100초, Sum of Costs는 190초(평균 19초)가 됩니다.

Sum of Costs만 보면 괜찮은 알고리즘이지만 Makespan을 같이 보면 어느 한 미션이 유독 오래 걸리는 것을 알 수 있습니다.

만약 모든 미션의 우선 순위가 동일하다면 문제가 될 수 있겠죠.

 

따라서 Makespanrhk Sum of Costs는 상호보완적인 지표라고 할 수 있습니다.

5. cycle conflict 발생 횟수(decoupled 알고리즘의 경우)

아시다시피 decoupled 알고리즘은 conflict free를 보장하지 않습니다.그래서 미션을 해결하는 중에 cycle conflict가 발생할 수 있는데요.

 

계획된 경로의 품질을 측정하는 지표로 cycle conflict 발생 횟수를 사용했습니다.

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

 

6. 최단 경로 길이 대비 실제 이동 경로의 길이(fuel efficiency)

다음과 같은 문제가 있을 때, 충돌이 없는 최단 경로가 계획된다면 두 에이전트 중 하나는 윗 부분에서 기다리게 될 것입니다.

예시 문제

이 때, 윗부분에서 다른 에이전트가 지나가는 것을 가만히 기다릴 수도 있고, 

차분히 기다리는 중!

윗 부분에서 왔다갔다 하면서 기다릴 수도 있습니다.

오두방정 떨며 기다리는 중!

위의 두가지 경우 중에서 어떤 것이 효율적으로 보일까요?

상황에 따라 다르겠지만 일반적으로는 가만히 기다리는 것이 더 효율적으로 보이겠죠?

fuel efficiency 라고도 하는 이 지표는 경로 계획 관점에서는 부가적인 지표지만 사용자 관점에서 보면 상당히 중요한 지표라고 생각됩니다.

---

소개드린 지표들은 어떠셨나요?

 

저는 처음에 MAPF 알고리즘의 성능을 측정할 때 고민만 엄청하다가 연구들을 찾아보면서 다들 비슷하구나 라는 것을 깨달았습니다 ㅋㅋㅋ

 

이외에도 좋은 지표들이 있다면 공유 부탁드립니다 :)