FAR - Flow Annotation Replanning이 decoupled 에서는 꽤 먹어주는 것 같습니다!

안녕하세요. 오늘은 Flow Annotation Replanning에 대해서 공부하려고 합니다.

• WANG, Ko-Hsin Cindy, et al. Fast and Memory-Efficient Multi-Agent Pathfinding. In: ICAPS. 2008. p. 380-387.

 

MAPF를 해결할 수 있는 방법으로 decoupled 알고리즘은 포기하려고 했는데 생각보다 좋은 결과에

decoupled 알고리즘 공부도 멈추면 안되겠다는 생각을 가졌습니다!

• 공부할 알고리즘 가짓 수 좀 줄여보려고 했는데 쉽지 않네요...ㅋㅋㅋㅋ;;

 

논문 내용 그대로 번역하는 것이 아닌 이해한 내용을 토대로 최대한 정리해보겠습니다!

---

FAR 

Flow Annotation Replanning(FAR)은 다음 3가지 방법으로

에이전트가 많은 환경에서도 HCA*와 비교해 압도적으로 빠른 속도와 보다 높은 성공률을 얻을 수 있었습니다.

1. 길지도 구성
2. k-step reservation table을 이용한 경로 계획
3. node density 기반 데드락 감지

각 방법들을 자세히 살펴보며, FAR 알고리즘을 공부해보죠!

1. 길지도 구성

본 논문에서는 길지도를 구성할 때부터 에이전트들 간의 충돌이 덜 발생하게끔 길지도를 구성합니다.

1) 충돌 자체가 덜 발생하고, 2) 발생하더라도 데드락이 덜 발생하게끔 길지도를 구성하는데요.

 

구체적인 예시를 들어보면 원래는 모든 엣지가 양방향이었던 그래프를

다음 그림과 같이 단방향 엣지로 구성된 그래프로 변환시킵니다.

flow-annotation search graph

이렇게 길지도를 구성하면 흐름 자체가 제한되므로 에이전트들 간의 충돌이 덜 발생하게 되고,

head-on collision 대신 side-on collision이 발생하여 데드락이 덜 발생하게 됩니다.

• head-on collision은 에이전트가 마주보는 방향으로 collision이 발생하는 것이고, side-on collision은 측면 방향으로 collision이 발생하는 것입니다.
• head-on collision의 경우, 경로를 재계획하는 수단 이외의 collision 해소 방법이 없지만 side-on collision은 한 에이전트가 다른 에이전트를 기다리는 것만으로도 collision이 해소될 수 있어서 훨씬 해결하기 쉬운 collision 입니다.

 

단, 단방향 엣지로 전환할 때 원 그래프의 모든 노드 간의 connectivity는 보장되어야 합니다.

• 만약 보장되지 않을 시, 대각선 엣지를 추가하거나 양방향 엣지를 추가하는 것으로 connectivity 조건을 만족시켜줘야 합니다.

2. k-step reservation table을 이용한 경로 계획

1. 길지도 구성에서 충돌을 완화시켰지만 여전히 side-on collision이 발생합니다.

이를 해결하기 위해서 FAR은 k-step reservation table을 이용합니다.

 

reservation table을 이용하여 에이전트들의 모든 경로를 예약하는 다른 알고리즘들과는 다르게,

에이전트들의 경로에서 k개 만큼만 예약합니다.

• 여기서 k는 파라미터로 변경 가능한 값입니다.
• 실험적으로 k=3 일 때, 좋은 성능을 보여줬다고 합니다.

만약 에이전트가 계획된 경로를 k개만큼 예약하는 것에 실패한다면 일정 시간 대기 후에 재시도합니다.

 

그리고 경로를 계획할 때에도 기존 방향을 유지하는 것에 집중합니다.

방향이 바뀌게 되면 아무래도 다른 에이전트와  side-on collision이 발생할 확률이 높아지게 되기 때문이죠...!

• 이전 이동 방향이 세로 방향이라면 다음 경로를 계획할 때, 휴리스틱 함수에서 가로로 연결된 엣지보다 세로로 연결된 엣지를 선택하는 비용을 조금 더 낮게 계산하는 것이죠.

3. node density 기반 데드락 감지

1, 2 방안을 모두 사용하더라도 데드락이 발생할 수 있습니다.

데드락이 발생하면 원인이 되는 에이전트들 중 일부를 골라서 다른 곳으로 이동시켜 데드락을 해소해야 합니다.

 

데드락을 해소하기 위해서는 일단 데드락이 발생했는지 감지해야 합니다. 데드락 감지 방법은 단순합니다.

에이전트가 경로 예약에 실패할 때마다, 데드락이 존재하는지 체크합니다.

 

만약 데드락이 발생했다면, critical unit을 찾아서 예정된 진행 방향의 반대 방향으로 이동시킨 뒤, 데드락이 해소되는 것을 기다립니다.

• 데드락을 해소하기 위해서 이동시켜야 하는 에이전트를 critical unit이라고 합니다.
• 논문에서는 critical unit을 찾기 위한 heuristic한 방법으로 node density를 사용합니다.
• node density는 해당 노드에 있거나 가려고 하는 에이전트의 수를 의미합니다.

한계

통로가 좁은 곳에 에이전트가 몰리는 경우에 대해서는 FAR로 해결하기 어렵다고 논문에서 밝히고 있습니다.

물류센터의 랙 사이 래인과 같은 환경이 위의 환경과 유사하다고 생각됩니다.