AMR의 회피 주행을 잘 활용할 수 있는 MAPF 알고리즘이 있을까? #1

안녕하세요. 간절기인데  무탈하신지요?

슬슬 봄이 찾아오고 있는지 온도가 영상 10도보다 높은 날들이 많아져서 무슨 옷을 입을지 애매합니다 ㅋㅋㅋ

 

저는 요즘 스스로 장애물을 피해 움직이는 Autonomous Mobile Robot(AMR)을 잘 활용할 수 있는 MAPF 알고리즘에 대해서 찾아보고 있습니다.

 

MAPF 알고리즘들은 주로 Autonomous Guided Vehicle(AGV)를 대상으로 개발됩니다.

MAPF 알고리즘 관점에서 AMR과 AGV의 차이를 꼽자면 AGV는 알고리즘의 결과값대로 움직이지만 AMR은 그렇지 않다는 것입니다.

• AMR과 AGV의 차이점이 더 궁금하시다면 트위니 블로그를 참고해주세요 :)
• 참고: AMR과 AGV 로봇의 차이점 (feat.쿠팡 소팅봇)

AMR이 스스로 장애물을 피하는 것은 좋지만 MAPF 알고리즘이 예측한대로 움직이지 않는다면 예상치 못한 병목이 발생할 수 있습니다.

 

다수의 로봇을 운용하면서 문제를 직접 겪은 것은 아니지만 미리 준비해야 할 영역이라고 판단되서 조금씩 공부하고 있습니다.

---

1. MAPF 알고리즘으로 AMR을 관제할 때 생기는 문제

위에서 언급한 AMR을 MAPF 알고리즘으로 관제할 때 발생할 수 있는 문제를 조금 더 구체적으로 설명드리겠습니다.

AMR이 스스로 장애물을 피하는 것은 좋지만 MAPF 알고리즘이 예측한대로 움직이지 않는다면 예상치 못한 병목이 발생할 수 있습니다.

 

 

1. 그림1과 같이 로봇1이 노드1, 로봇2가 노드4에 있다고 가정합시다.

그림 1

 

2. 로봇 1은 노드 5로 가야하고, 몇 초 후에 로봇 2는 노드 6으로 가야해서 다음과 같이 경로가 계획되었습니다.

	1초	2초	3초	4초	5초
로봇 1	노드1	노드2	노드2	노드5	노드5
로봇 2	노드4	노드4	노드6	노드6	노드6

 

3. 로봇 1은 계획된 대로 노드2를 거쳐서 노드 5로 움직이는 중에 장애물을 만나게 되었습니다.

 

4. 장애물을 피하다보니 노드6까지 움직이게 되었고, 결국 로봇 2의 주행을 방해하게 되었습니다.

 

 

알고리즘 상으로는 로봇끼리 병목이 발생하지 않아야 했지만 AMR이 장애물을 회피하게 되면서 예상치 못한 병목이 발생하게 되었습니다.

 

이런 병목은 로봇이 많아질수록 더욱 빈번하게 발생하고 전체 관제 효율에 끼치는 악영향 또한 커질 것입니다.

2. AMR의 경로마저 서버에서 계획해버리면 어떨까?

사실 AMR 스스로 장애물을 회피하는 것도 MAPF 알고리즘으로 계획할 수 있습니다.

 

1) 그래프의 노드를 더욱 더 촘촘히 생성하고, 2) 각각의 AMR이 장애물을 회피해야겠다고 판단할 때마다 경로를 계획하면 됩니다.

 

실제로 이 방향으로 접근한 CL-CBS라는 연구가 있었습니다!

• WEN, Licheng; LIU, Yong; LI, Hongliang. CL-MAPF: Multi-agent path finding for car-like robots with kinematic and spatiotemporal constraints. Robotics and Autonomous Systems, 2022, 150: 103997.

하지만 로봇 수가 조금만 많아지더라도 경로 계획에 걸리는 시간이 초 단위로 느려지는 치명적인 단점이 있었습니다.

실행 시간에 대한 결과

 

3. 일단 Decentralized 방식을 공부해보자!

다음 방법으로 생각한 것은 Centralized 방식과 Decentralized 방식을 혼합하는 것이었습니다.

AMR이 장애물을 회피하기 위해 스스로 경로를 계획하는 것을 Decentralized 방식으로 볼 수 있기 때문입니다.

 

하지만 Decentralized 방식을 어떻게 섞어야 할지는 감이 안 잡혀서 일단 관련 논문들을 찾아봤습니다.

그런데 제가 이런 논문을 공부했더라고요…?

• ČÁP, Michal; VOKŘÍNEK, Jiří; KLEINER, Alexander. Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures. In: Proceedings of the international conference on automated planning and scheduling. 2015. p. 324-332.
• Task and Path Planning For Multi Agent Pickup and Delivery 논문에서 well-formed infrastructure 개념을 공부하면서 가볍게 읽어본 논문이었습니다 ㄷㄷ

이 논문이 눈에 띄었던 이유는 trajectory 때문입니다.

짧은 식견이지만, trajectory라는 단어는 주로 로봇의 실제 경로를 계획할 때 사용되는 용어였습니다.

제가 관심 있는 영역과 정확히 일치하는 것이죠!

 

그래서 논문을 호다닥 살펴봤는데... 막상 논문에서 제안된 솔루션은 크게 와닿치 않더라고요.

• token passing 기법으로 로봇 간의 충돌이 발생하지 않는 경로를 계획하자. 정도였습니다.

 

솔루션보다 더 좋았던 것은 introduction에서 decentralized 방식의 다른 연구들이 많이 소개해준 것이었습니다.

• Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation
• Reciprocal n-body Collision Avoidance
• ClearPath: Highly Parallel Collision Avoidance for Multi-Agent Simulation
• Distributed reactive collision avoidance
• Push and Rotate: Cooperative Multi-Agent Path Planning

 

앞으로는 위의 논문들을 하나씩 하나씩 공부하면서 decentralized 방식을 이해하려고 합니다.

흥미로운 내용이 있으면 또 작성해보겠습니다!