Conflict-Based Search for Explainable Multi-Agent Path Finding - Explainable MAPF가 대체 뭘까요!

안녕하세요.  이번에는 Explainable MAPF에 대해서 공부하고자 합니다.

• KOTTINGER, Justin; ALMAGOR, Shaull; LAHIJANIAN, Morteza. Conflict-based search for explainable multi-agent path finding. In: Proceedings of the International Conference on Automated Planning and Scheduling. 2022. p. 692-700.

제가 어떤 이유로 Explainable MAPF를 찾게 되었고, 이 논문을 읽었는지, 그리고 논문에서 어떤 것들을 배웠는지 간단히 정리해 보겠습니다.

---

1. 시작 - 버그 발견, 디버깅이 너무 어려워 ㅜㅠ

MAPF 알고리즘을 실제로 구현해 보면 디버깅이 정말 어렵습니다.

 

알고리즘을 정확히 구현했는지 확인하기 어려운 것은 물론이고,

주어진 문제를 해결하기 위해서 알고리즘을 조금 수정했을 때 버그가 없는지 찾는 것도 어렵고,

버그를 재현하는 것도 정말 까다롭습니다.

 

지속 가능한 관제 시스템을 만들기 위해서는 MAPF 알고리즘의 유지보수와 추가 개발이

필수적이기 때문에 이런 문제를 해결해야만 합니다 ㅜㅠ

 

"MAPF 알고리즘을 우리만 사용하는 것은 아닐 텐데 연구된 내용이 있지 않을까?"라는 생각으로

연구들을 찾기 시작했고 위의 논문을 찾을 수 있었습니다.

 

2. Explainable

논문 내용을 정리하기 전에 Explainable이 왜 중요한지 간단히 설명드리겠습니다.  

 

사물 인식, 사용자 추천과 같은 복잡한 문제들은 "하나의 정답"이 있는 것이 아닙니다.

요구사항에 따라서, 상황에 따라서 필요한 답이 달라집니다.

 

알고리즘을 문제에 알맞게 적절히 튜닝하기 위해서는 "어떻게 오답이 도출되었는지" 아는 것이 중요합니다.

 

하지만 많은 AI 알고리즘들은 "어떻게"를 알기 어려운 블랙박스입니다.

 

그래서 "어떻게" 답이 도출되었는지 설명 가능한 AI 알고리즘이 하나의 연구 분야가 되었고, 이를 Explainable AI(XAI)라고 합니다.

MAPF 알고리즘도 이런 연구가 진행되고 있고, Explainable MAPF라고 하더라고요.

3. 논문 내용

3.1. 솔루션 개요

논문에서는 다음 이미지와 같이 복잡한 경로를 어떻게 하면 사용자가 쉽게 검증할 수 있는지에 대해서 솔루션을 제안하고 있습니다

Figure 10. Conflict-Based Search for Explainable Multi-Agent Path Finding

쉽게 검증할 수 있는 방법으로는 (시간, 각 로봇의 위치)로 표현되는 로봇의 경로를 조금씩 잘라서(segment) 사용자에게 제공합니다.

 

segment들은 서로 경로를 침범하지 않아서 검증하기 쉬우며,

솔루션 자체적으로 segment를 최대한 크게 생성하여서 사용자가 볼 segment 수도 줄어듭니다.

 

예시)

위의 경로를 아래와 같이 2개의 화면으로 나눠서 사용자에게 제공합니다.

Figure 10. Conflict-Based Search for Explainable Multi-Agent Path Finding

3.2. 시스템에 적용하기 아쉬운 점들: 실행 시간, 호환성

하지만 실험 결과를 보니 경로 계획 알고리즘의 실행 시간이 예상보다 너무 길더라고요.

 

저희들은 경로 계획 알고리즘의 실행 시간을 최대 1초로 잡고 있는데

16x16의 작은 환경에서 agent 수가 20개만 되더라도 이를 가뿐히 넘는 것을 확인할 수 있습니다 ㅜㅠ

Figure 16. Conflict-Based Search for Explainable Multi-Agent Path Finding

 

또한, 현재 개발 중인 알고리즘과 호환되지 않을 것으로 예상되어 더 깊게 살펴보지 않았습니다.

 

대신 "계획된 경로를 시각화하여 사용자에게 보여주면 로봇이 정상적으로(?) 움직일 것인지 검증할 수 있다."라는 인사이트를 얻었습니다.

그리고 이를 바탕으로 1) 계획된 경로를 어떻게 저장할지, 2) 저장된 경로를 어떻게 시각화할지 고민하고 있습니다. 

---

Explainable MAPF라는 키워드를 알게 되어 의미있었습니다.

 

저는 연구 결과가 아쉬워서 더 깊게 읽지 않았지만 여러분들에게는 도움이 되었으면 좋겠네요!

 

피드백은 언제나 환영입니다!