다중에이전트 경로탐색(MAPF) 기반의 실내배송로봇 군집제어 구현

1. 서 론

AGV (Automated Guided Vehicle) 로봇은 발전소, 물류/유통센터, 공항 터미널 등 시설에서 많이 활용되고 있다^[1]. 물류분야에서 보면 2006년 Kiva Systems(현재 Amazon Robotics)가 처음 도입했던 RMFS (Robotic Mobile Fulfillment System)는 피킹을 위해 작업자가 선반으로 이동하는 과정에서 소요되던 시간의 50% 이상을 AGV 로봇의 이동으로 대체하여 물류 주문 처리량(throughput)을 크게 향상시켰다^[2,3]. AGV로봇은 장애물이 없는 정해진 공간 환경에서 반복/지속적인 작업을 수행하는데 매우 효과적이기 때문에, 이로부터 실제 작업 효율의 향상을 기대할 수 있다. 최근 물류센터에서는 AMR 로봇 도입에 적극적인 추세에 있는데^[4], 이는 AGV 로봇을 도입할 때와 마찬가지로 생산성과 효율성의 향상에 더불어서 로봇 활용에 대한 확장성과 범용성을 함께 갖추기 위함이다. AMR 로봇은 자신의 위치와 주변 환경 변화를 인식할 수 있기 때문에, 물류센터 내의 작업장과 선반과 같은 공간 배치를 변경하지 않고 손쉽게 도입 및 운영이 가능하다. 또한, 로봇을 안전 기준에 부합된 속도 이내로만 운영한다면, 작업자와 협업하는 형태로도 활용할 수 있다. AMR 로봇과 작업자가 협업하는 형태의 물류센터 피킹 작업은 RMFS와 마찬가지로 작업자 대신 AMR 로봇이 선반이나 포장 위치로 이동하고, 작업자는 로봇의 적재공간에 물건을 놓거나 꺼내기만 하는 방식이다. 작업 과정에서 AMR 로봇들은 할당된 업무에 따라 각각의 목적지로 잦은 빈도로 이동해야 한다. 여기서 로봇들을 목적지로 이동하는 중간에 충돌이나 교착을 회피할 수 있도록 사전에 경로를 계획하고, 계획된 경로를 토대로 로봇들을 움직이는 방법을 찾는 것, 즉 MAPF (Multi-Agent Path Finding) 문제의 해결이 필요하다. MAPF 문제를 해결하는 방식에 관해서는 기존에 다양한 연구가 이루어지고 있다^[5,6].

이론 상 MAPF 문제의 해결 방식으로 충돌 없는 경로를 찾을 수 있지만, 시뮬레이션이 아닌 실제 로봇을 운영해보면 여전히 찾아진 경로대로 로봇이 이동하지 않는다는 불일치가 존재한다^[7,8]. 해당 불일치는 실제 로봇의 움직임과 공간 정보를 현실적인 시간 내에 정확하게 맞출 수 없어 발생된다. 이에 처음 계산된 경로 결과를 끝까지 따라가는 것보다는 오류가 예측되는 시점에 로봇들의 경로를 새롭게 탐색하고 해당 결과를 로봇이 따라가도록 해주는 편이 장시간 잦은 빈도로 다수 로봇을 운영하는데 유리하다.

[7]과 [8]에서는 로봇의 움직임에 대한 불일치를 해소하고자 동역학적인 모델을 일부 도입하여 MAPF 문제를 풀고, 이를 RMFS 운영에 활용하는 방법을 소개하였다. 그러나 해당 해법을 통해 얻어진 로봇들의 이동계획은 연산시간의 제약이 존재하고, 여전히 교착(deadlock) 발생 가능성이 있다. 해당 연구에서는 이런 경우가 발생되었을 때, 로봇의 현재 위치를 임의의 가까운 주변으로 이동하여 회피하는 방법을 제안하였다. 이를 토대로 알고리즘 동작상의 교착 상황을 해결 가능하지만, 해당 이동으로 실제 로봇의 위치와 더욱 차이를 발생시킬 수 있다는 문제가 있다. 이런 차이 때문에 실제 로봇의 이동 경로 계획의 수행 측면에서는 더욱 부정확한 결과를 초래할 수 있고, 추가적인 고려 없이 실제 물류센터 환경에 바로 적용하기에 무리가 있다. [8]에서는 이동 경로 계획의 수행 측면에서 MAPF를 통해 얻어진 경로대로 움직이지 않는 로봇의 문제점을 지적하고, 로봇의 동역학적인 정보와 기존 점유된 공간의 정보를 비교하는 간단한 후 처리 프레임워크를 소개하였다. 하지만 해당 프레임워크는 일관된 형태로 정리되지 않아, 실제 물류환경 적용에 모호함이 있다.

MAPF의 입력으로 주어져야 하는 공간에 대한 그래프는 물류센터의 복잡한 정도와 크기, 경로탐색빈도에 맞게 일반적인 형태로 구성할 수 있어야 한다. 로봇이 활보할 수 있는 자유 공간이 좁은 통로로 구성된 경우 혹은 장애물들로 인해 높은 밀도를 갖는 환경에 대해 격자 형태의 그래프로 공간을 구성하는 것은 경로 계산의 복잡도가 높아져서 높은 빈도의 알고리즘 수행이 어렵다. 이와 반대로 토폴로지 형태의 그래프로 공간을 구성하면, 그래프 내의 탐색 노드 개수가 적어지기 때문에 경로 계산에 필요한 연산량을 줄일 수 있지만, 이동 중간에 재 경로 계획이 필요한 경우 정확한 위치에서 경로 탐색을 하기 어렵게 된다.

본 논문에서는 실제 물류센터에서 다수의 로봇을 운용하기 위한 MAPF 문제를 다루며, 실제환경에서의 부정확한 이동 경로 계획 수행과 동역학적 움직임을 고려한 일반화된 프레임워크를 소개한다. 프레임워크의 적용으로 실제 물류센터에서 다수의 로봇을 충돌이나 교착 없이 장시간 운영할 수 있도록 하는 것을 목표로 하며, 이에 복잡한 물류센터에도 적용할 수 있도록 공간을 그래프로 구성하는 방법을 포함한다.

시뮬레이션을 토대로 확인해 본 결과, 제안하는 방법은 재 경로 계획에 대한 고려하지 않은 방법과 달리, 실제의 물류 공간에 대해 10대의 가상 로봇의 10회 왕복 시험에서 교착 문제가 발생되지 않았다. 제안하는 방법을 실제 물류센터의 AMR 로봇을 활용한 피킹 작업에 적용하였다. 적용 이후, 물류센터 피킹 작업에 대해 AMR 로봇들의 활용 정도를 확인해보았는데, 10대의 로봇이 9일간 평균 일일 피킹 업무의 26%에 해당하는 이동 시간에 활용되고 있음을 확인하였다.

2. 문제 정의

2.1 Multi Agent Path Finding (MAPF)

MAPF는 출발지와 목적지를 갖는 다수의 로봇의 시공간에서의 충돌 없는 경로를 찾는 문제이다. 전통적인 MAPF는 그래프에서의 탐색 형태로 문제를 정의하며, 입출력을 아래 [Table 1]과 같이 표현할 수 있다^[9].

[Table 1]

Classical MAPF problem

이러한 정의를 토대로 MAPF 문제를 해결하는 방법에 관한 연구는 많이 진행되고 있으며, 관련 연구들에 대한 분류와 비교결과는 [9]와 [10]에 잘 설명되어있다. 소개된 방법 중 대표적인 방법으로 로봇들 간의 우선순위를 기준으로 기존에 탐색된 로봇들의 경로를 장애물로 삼아 순서대로 경로를 탐색하는 Priority Planning (PP) 방식^[11-13], 개별 로봇의 경로에서 충돌이 발생되는 로봇들을 그룹으로 합치고 각각의 개별 그룹에 대해 A* 탐색을 수행하는 Independent Detection (ID) 방식^[14], 그리고 로봇들 각각의 경로를 기준으로 중간에 충돌되는 구간을 피할 수 있는 최적해가 도출될 때까지 탐색을 전개하는 Conflict Based Search (CBS) 방식^[15]등이 있다. MAPF 방식에 따른 차이는 있으나 달성하고자 하는 목적 함수에 따라 최적 혹은 준 최적의 경로를 찾을 수 있다. 목적함수로는 대개 모든 로봇의 경로 상 이동거리/시간의 합(sum of costs) 혹은 모든 로봇들 중 최대 소요시간/거리(makespan)를 사용한다.

MAPF 문제를 해결하는 기존 솔루션들은 한 차례에 대한 결과를 내주는데 그치고 있어, 실제 물류센터와 같은 곳의 로봇 운영과 차이가 있다. 실제 물류센터 환경 같이 중앙통제 시스템으로 동일장소에서 장시간 운용을 하면서, 중간중간 시점을 가리지 않고 새로운 작업이 할당될 수 있는 형태는 Online (Lifelong) MAPF 문제의 해결을 통해서 다뤄지고 있다^[16]. Online (Lifelong) MAPF 문제를 해결하는 연구들은 다음과 같다. [17]에서는 Online MAPF 문제의 정의와 그 구분에 대해서 설명하였고, 기존 ID방식^[14]을 Online MAPF에 응용한 방법을 제안하였다. [18]에서는 정해진 시간 구간을 두고 해당 구간에 포함되는 로봇들의 경로만을 탐색하도록 하여 경로탐색에 소요되는 시간을 효과적으로 줄이는 방법을 소개하였다. 마지막으로 [19]에서는 경로 탐색을 수행하는 로봇의 수를 시간이 지남에 따라 다르게 하는 방식으로 Online MAPF 문제를 해결하는 방법을 제안하였다.

본 논문에서는 [17]에서의 정의에 입각하여, 물류센터내의 군집제어 문제를 임의의 위치에서 로봇이 시작할 수 있고, 목적지에 도착한 후 해당 목적지에 머물러 있는 형태의 문제로 정의한다. 이는 실제 물류센터의 피킹 작업에서 임의의 시점에 새로운 로봇들의 경로가 요청되고, 목적지에 위치한 로봇은 작업을 위해 해당 장소에 머물러 있는 경우가 존재하기 때문이다. 해당 문제에서는 기존 이동하고 있는 로봇의 피해가는 경로가 존재하지 않는 임의의 시점에 새로운 로봇이 추가되고 경로가 요청되므로, 완전성이 보장되지 않고 새로운 로봇과 기존 이동중인 로봇간에 교착이나 충돌 상황이 재현될 수 있다. 이런 경우, 이동중인 로봇들을 포함하는 적절한 재 경로 계획이 같이 필요하게 된다.

3. 제안하는 방법

3.1 일반화된 Online MAPF 프레임워크

실제 물류센터 운영환경과 같은 Online MAPF의 경우 로봇들이 경로로 이동하는 중간에도 새로운 작업이 할당되고 수행되어야 한다는 조건이 추가된다. 새로 할당된 작업을 수행하는 시점에는 다른 로봇들로부터 경로가 방해되어서 문제가 될 수 있으므로, 그러한 로봇들을 잘 선별하여 같이 경로계획에 포함해야 한다. 또한 새로운 작업의 할당은 무작위로 발생되므로 경로계획수행은 이벤트 기반으로 동작되어야 한다.

[Fig. 1]은 이런 일련의 과정을 잘 수행할 수 있도록 구성한 프레임워크이다.

[Fig. 1]

The generalized online MAPF Framework

새로운 경로계획을 하는 메인 루프는 (1)로봇 간 충돌 예측, (2)특정 로봇의 현재 목적지 도착, (3)새로운 로봇 목적지의 추가 그리고 (4)경로탐색 시간 초과 중 하나의 이벤트로 시작된다.

3.1.1 현재 목적지 결정

이벤트가 발생되면 현재 시스템 상에 등록된 모든 로봇들의 주행 상태와 최종목적지를 보고 이번 경로계획에서 목표로 해야 하는 현재 목적지를 결정한다. 목적지 선정에서 다수의 로봇이 동일한 목적지(POI)를 선택한 경우, 상대적으로 경로이동에 소요되는 시간이 더 긴 로봇의 목적지를 변경한다. 여기서 변경되는 목적지는 경유지(Way Point, WP)들로 목적지와의 거리 순으로 정렬되어 있다. 경유지에 대기하던 로봇은 순서 상 앞에 있는 다른 경유지나 목적지가 빈 공간이 되면 경로계획에서 목적지를 해당 위치로 순서대로 변경하게 된다.

3.1.2 AGENT, OBSTACLE 분류

시스템에서는 각 로봇의 출발지와 목적지를 기반으로 새 경로를 생성해야 하는 로봇(AGENT)과 정지 상태를 포함하여 기존 경로의 유지가 필요한 로봇(OBSTACLE)으로 나누게 된다. 목적지가 이전에 비해 바뀐 로봇은 AGENT가 되고 목적지에 이미 도착하여 정지해 있거나 이미 경로를 받고 주행 중인 로봇은 OBSTACLE이 된다.

3.1.3 AGENT 우선순위 결정

우선순위 기반의 MAPF는 AGENT의 우선순위에 따라 경로가 다르게 생성되기 때문에 AGENT의 우선순위를 정해주는 일은 전체 시스템의 효율성을 위해서 매우 중요하다. AGENT의 우선순위는 로봇들을 운용하는 환경에 따라 다른 정책을 적용한다. 검증에 사용한 물류센터 환경은 좁고 긴 공간이었기 때문에 막다른 골목에서 빠져 나오는 AGENT에 최우선 순위를 부여하는 방식을 택하였다. 그 외의 AGENT는 현재 목적지까지 거리가 가까운 순으로 우선순위가 정해진다.

3.1.4 우선순위 기반 MAPF 실행

우선순위 기반의 MAPF는, 격자 기반 그래프로 구성된 맵에서 자기보다 우선순위가 높은 AGENT의 경로를 피하는 조건 하에 최단 경로를 구하는 과정을 반복하여 이루어진다. 만약 우선순위가 낮은 AGENT의 경로가 생성되지 않으면, (1) 모든 AGENT의 경로가 생성되거나 (2) 가능한 조합이 모두 시도될 때까지 동적으로 우선순위를 조정하여 MAPF 를 시도한다.

3.1.5 경로 분석 및 plan 생성

OBSTACLE과 충돌하지 않는 조건으로 AGENT의 경로를 생성하고 나면 경로 내에 특정 노드에서 대기하거나 유턴을 하는 등 특별한 부분이 있는지를 분석하여 각 로봇에 전달될 전역 경로 계획(global path plan, 이하 plan)을 만든다. 전송하는 plan은 로봇이 처리할 수 있는 데이터에 맞추어 가공해준다. 예를 들어, 검증에 사용된 로봇의 경우 plan 중간에 대기시간을 처리할 수 없어, 경로 상에 제자리에서 대기하는 노드를 포함하고 있으면 해당 노드까지만 plan을 만들고 다음 이벤트에서 나머지 경로 이동이 수행되도록 하였다. 마지막으로 전송할 필요가 없는 너무 짧은 전역 경로는 전송되는 plan에서 제외한다. 로봇에게 plan을 최종 전송하고 나면 로봇은 주행을 시작 또는 변경하게 된다.

3.1.6 plan 전송

군집제어 시스템은 ROS2 기반으로 구현되어 있기 때문에 같은 ROS2 기반의 주행로봇으로는 ROS2 메시지 형태로 간단히 전송할 수 있다. 만약 ROS2 기반의 로봇이 아니라면 그 로봇이 전송 받을 수 있는 형태로의 메시지 변환 모듈을 추가하면 된다. [Fig. 2]는 ROS2기반 시스템의 컴포넌트와 각 컴포넌트간에 전달되는 메시지들의 구성을 보여주고 있다.

[Fig. 2]

ROS2 based online MAPF system components and messages between components

위의 과정은 다음 이벤트가 발생되었을 때 재 시작되며, 일련의 과정을 통해 로봇들은 최종목적지까지 충돌이나 교착 없이 각각의 목적지에 도착할 수 있게 된다.

3.2 한 줄 격자 형태의 그래프 구성

물류센터에서 장시간 다수의 로봇을 운영하기 위해서는 공간을 그래프로 구성하는 방식이 중요함을 앞서 언급한 바 있다. 만약 물류센터가 초대규모로 공간이 확보되어 있는 경우에는, [8]에서 제안한 바와 같이 토폴로지와 격자 형태를 혼합하여 사용하는 방식을 선택할 수 있지만, 실제 물류센터에 여유 공간이 많지 않은 좁은 통로만으로 이루어져있는 경우에는 이를 적용하기 어렵다. 이런 물류센터를 대응하기 위해, 좁은 통로구간에 대해 장애물을 제외하고 모두 격자 형태로 구성하면 [Fig. 3(a)]와 같이 경로 탐색결과로 실제 반경을 갖는 로봇이 따라가기 어려운 경로를 도출해내는 경우가 생기고 그로 인해 충돌이나 교착 가능성이 높아진다. 그리고 앞서 언급한대로 노드와 간선의 수가 많아짐으로 인해서 연산량에도 부하가 생긴다. 좁은 통로를 모두 토폴로지 형태의 그래프로 구성하는 방법에도 문제가 있다. 토폴로지 형태의 그래프를 구성하면 노드 갯수가 줄어들어 경로계산에 대한 연산량을 줄일 수 있지만, 실제 로봇이 계산된 경로를 따라 정확한 시점과 위치로 이동하지 않음으로 인해서 경로이동 중간 잦은 재 경로계획이 필요한 상황에 효과적으로 대처하기 어렵다.

[Fig. 3]

(a) A MAPF result on a grid map. The si and ti represent start position and goal for i-th robot. We can see the sharp corner in result path of robot#3 marked with dotted circle. (b) A MAPF result on a one-line grid map. Result paths of the same start position and goal as [Fig. 3(a)]. In above results, the robot#1 will wait for a while on zone between J10&J11, and the robot#3 will wait for a while on zone between J05&06 to prevent conflict or deadlock

이에 좁은 통로를 갖는 물류센터 환경의 경우에 대해, 그래프를 격자 형태로 구성하되, 공간 전체가 아닌 한 줄로만 구성하는 방법을 사용하였다. 한 줄 격자 형태로 그래프를 구성하면 경로계산에 대한 연산량은 줄이면서 경로 중간에서 재 경로 계획이 필요한 상황에도 잘 대처할 수 있다. 로봇의 크기나 통로의 크기에 맞게 한 줄로 격자를 구성하면 양쪽에서 로봇이 마주 오는 경우에 대해 회피하는 경로를 찾을 수 없는 문제가 있는데, 이는 현장 상황에 맞게 중간에 T자 형태로 피해줄 수 있는 공간을 추가해주어 해결하였다. 제안하는 형태로 공간을 구성하면 경로 탐색 결과로 T자 형태로 피해줄 수 있는 공간에서 로봇이 대기하면서 양보하는 결과가 나오며, 이런 형태로 충돌이나 교착없이 다른 로봇이 한 줄로 구성된 통로로 이동해갈 수 있다. [Fig. 3(b)]는 [Fig. 3(a)]와 같은 경로 탐색 문제에 대해 한 줄 격자로 공간을 구성했을 때, 도출된 경로를 보여준다.

한 줄 격자 그래프 구성 방법은 운영 로봇 댓수가 늘어나면 실제 로봇들 사이에 양보하는 경로가 많이 나오게 되어, 로봇 각각의 시간 당 작업 처리량은 약간 감소된다. 그러나 특정 장소로 로봇이 이동한 이후, 작업을 위해 긴 시간 동안 대기해야 하는 물류센터의 운영환경에서 도출된 경로까지 이동하는 시간이 약간 늘어나는 것은 큰 문제가 되지 않고, 양보하는 경로가 많은 만큼 충돌이나 교착 문제 발생 가능성이 줄어들어 동일 장소에 대해서 장시간 안정적으로 로봇 운영이 가능하다.

4. 실험 및 적용 사례

4.1 환경

제안하는 방법을 실제 물류센터에서 사람과 로봇이 협업하는 RMFS형태의 피킹 환경에 적용하였다. 해당 물류센터의 피킹 장소는 매우 좁고 긴 중앙통로에 양쪽으로 랙이 일렬로 늘어서 있는 공간으로 구성되어 있고, 로봇에는 피킹에 사용되는 박스 운송을 위해 별도 기구물을 설치한 상태였다. [Fig. 4] 왼쪽 그림과 같이 뒤에 달린 별도 기구물로 인해 회전을 같이 하면 로봇은 더 큰 반경을 갖게 되고, [Fig. 4] 오른쪽 그림과 같이 좁은 중앙통로에 다른 적재물이나 계단이 있는 경우 로봇 2대가 마주보는 상태로 통과할 수 없다.

[Fig. 4]

(Left) A robot model (top-down view). (Right) An example of two robots passing each other in a narrow aisle. For straight navigation, minimum 1.5 m width along the path of a robot required (25 cm margin for each side) and for passing each other robot in face to face, at least 2.75 m width required

물류센터 공간은 한 줄 격자 그래프로 구성하였다. 좁은 통로를 포함하는 물류센터 전체 지도를 한 줄 격자 형태의 그래프로 구성하고, 이후 양방향 교차가 가능하도록 T자 형태로 피해줄 수 있는 공간을 추가해 주었고, T자 공간의 끝부분은 최종목적지(POI)들로 지정하였다. [Fig. 5]는 좁은 통로의 물류센터공간의 일부를 격자 그래프와 한 줄 격자 형태 그래프로 구성한 예시이다.

[Fig. 5]

(a) An occupancy grid map image of a warehouse. (b) A grid map extracted from the selected region in [Fig. 5(a)]. (c) A one-line grid map extracted from the selected region in the same region

4.2 AMR로봇을 활용한 물류센터 피킹

AMR 로봇을 활용한 물류 센터에서 진행되는 피킹 작업은 아래와 같이 진행된다. 먼저 하역장소 근처에서 (1)피킹할 물건들을 POI 위치에 따라 분류하고 (2)관리자가 로봇별로 POI 선정하여, (3)선정된 근처 POI 로 로봇을 보낸다. 이 후 POI 에서는 (4)대기하던 작업자가 기구물에 설치된 박스에 물건을 담고, (5)피킹한 물건을 전부 담고 나면 다시 하역장소로 되돌려 보낸다. 이후 관리자는 빈 박스로 바꾸어 동일 작업을 반복한다. 아래 [Fig. 6]과 [Fig. 7]은 실제 로봇을 활용한 피킹 작업이 이루어지는 공간을 보여주고 있다.

[Fig. 6]

A typical example of an unloading station in a warehouse

[Fig. 7]

A typical example of picking stations in a warehouse

4.3 교착 발생 여부에 대한 시뮬레이션

제안하는 방법이 적용되었을 때의 효과를 확인해보고자, 물류센터와 동일한 공간 구성과 로봇 움직임을 모사한 가상의 로봇들로 시뮬레이션을 수행하였다. 시뮬레이션은 10대의 가상 로봇 각각에게 순서 없이 목적지까지 10회 왕복(20회 이동)하도록 구성하고, 이를 3번 반복하였다. 로봇들의 시작위치는 물류센터 공간의 하역장소이며, 목적지는 가장 멀리 떨어져있는 피킹 장소로 선정하였다. 하역장소에서는 로봇들이 한 줄로 대기하여, 앞선 로봇이 출발해야 그 다음 로봇이 출발할 수 있다. 또한, 현재 구성은 중간 구간에 2대의 로봇이 다른 방향으로 동시에 지나갈 수 없는 좁은 통로가 포함되어 있어, 한 로봇이 양보를 하지 않으면 교착이 발생될 가능성이 있다.

로봇이 POI에 도착한 경우를 기록하고, 시뮬레이션을 시작한 일정시간 이후에 로봇들의 상태를 확인하면, 로봇들 간 교착이 생겼는지 여부와 시점을 확인할 수 있다. 제안한 프레임워크의 방식처럼 가까운 미래 시점 충돌이 예측되거나 혹은 우선순위 기반 MAPF에서 새로 목적지가 추가된 로봇으로 인해 경로가 나오지 않는 상황에 대해 재 경로 계획의 처리를 하지 않은 경우, 3회 반복시험에서 모두 15회 이동 이전에 가상 로봇들 간에 교착상태가 발생됨을 확인할 수 있었다. 시뮬레이션 공간이 좁은 중앙통로이기 때문에 특정 구간에서 한 번 교착이 발생되면, 다른 로봇들도 지나갈 수 없어 엉키는 현상이 나타나게 된다. [Fig. 8]은 시뮬레이션에서 교착이 발생된 상황의 예를 보여주고 있다. 좁은 통로에서 D16과 D17사이 대기구간에 있는 로봇 그리고 바로 아래 있는 로봇은 오른쪽으로 경로가 나와서 이동하고자 하는데, 나머지 로봇들의 경로가 왼쪽으로 나와있는 상태로 교착이 발생되었다.

[Fig. 8]

An example of deadlock

반면, 제안하는 프레임워크를 사용한 실험에서는 뒤늦게 출발한 로봇이 더 많이 양보를 하면서 하역장소에 대기하느라 10회 모두 왕복하지 못하는 경우가 있었으나, 목적지를 이동하는 동안 교착이 발생되지 않았다. 시뮬레이션 결과의 평균치는 아래 [Table 2]와 같다.

[Table 2]

Average number of POI arrived by each robot per 10 round trips (total 20 trips)

4.4 작업 효율

로봇을 활용한 피킹 작업의 효율을 확인해보고자 실제 물류센터에서 각각의 로봇이 이동하는 거리, 소요되는 시간 그리고 POI 이동 횟수를 확인해보았다. 여기서 사용된 로봇은 2바퀴 차륜형 방식(two-wheels differential drive)으로 구동되며, 최대 각 속도는 38 deg/s 이다. 피킹 작업은 로봇과 사람 작업자가 같은 공간에서 수행하기 때문에, 안전을 고려하여 로봇의 선 속도를 최대 1.1 m/s 수준으로 제한하였다. 아래 [Fig. 9(a)], [Fig. 9(b)] 그리고 [Fig. 9(c)] 는 해당 로봇 10대를 9일동안 하루 7시간 작업에 투입했을 때의 활용 정도를 측정한 결과이다.

[Fig. 9]

(a) Cumulated distance traveled by each robot per day (km). (b) Cumulated number of POI arrivals by each robot per day. (c) Average operation hours of each robot per day (hours)

결과를 보면, 피킹을 위해 일일 누적 평균44.8 km 로봇들의 이동이 이루어졌고, 평균 290번 POI로 이동하였다. 10대의 로봇 모두 작업이 끝날 때까지 이동이 이루어지고 있었으므로, 중간에 교착 상황이 발생되지 않았다. 로봇 각각이 이동에 소요하는 시간은 평균 1.85시간인데, 이는 일일 작업시간의 26%가 넘는 수치이다. 측정 데이터를 종합해보면, 물류센터에서 피킹 작업 시 로봇들이 매우 큰 비중으로 활용되고 있음을 알 수 있다.

5. 결 론

본 논문에서는 복잡하고 다양한 물류센터 공간에서 다수 AMR로봇을 운영하기 위한 방법을 제안하였다. 제안한 방법은 Online MAPF 기반의 일반화된 프레임워크로 로봇의 동역학적 차이가 있거나, 경로 계획과 실행 간의 불일치가 있는 상황에서도 각각의 로봇을 목적지까지 충돌이나 교착 없이 운영할 수 있도록 해 준다. 또한, 물류센터가 로봇을 자유롭게 운영할 만큼 여유공간이 확보되지 않는 상황에서 MAPF에서 활용되는 그래프를 한 줄 격자 형태로 구성하고 회피 공간과, POI 설정을 통해 로봇의 운영이 가능하도록 하였다.

제안한 방법을 기반으로 실제 매우 좁고 긴 공간의 물류센터에서 작업자와 로봇이 협업하는 방식으로 피킹 운영에 적용해보았고, 로봇 10대 운영으로 일일 작업 시간의 25% 이상에 해당하는 부분을 로봇을 활용하여 대체할 수 있음을 확인하였다.

추후 연구방향으로는 현재의 일반화된 프레임워크를 확장하여 사용할 수 있도록 하는 것을 고민하고 있다. 가령, AMR의 특성을 고려하여 동적 장애물을 포함한 Online MAPF 운영 방식에 대한 연구, 혹은 100대 정도의 초대규모 로봇 운영에 대한 연구 등이다.

Acknowledgments

This project was supported by Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korean government (No. 2020-0-00857)

References

• T. Le-Anh and M. B. M. de Koster, “A review of design and control of automated guided vehicle systems,” European Journal of Operational Research, vol. 171, no. 1, May, 2006. [https://doi.org/10.1016/j.ejor.2005.01.036]
• J. A. Tompkins, J. A. White, Y. A. Bozer, and J. M. A. Tanchoco, Facilities Planning, 4th ed. John Wiley & Sons, Hoboken, NJ and Chichester, 2010. [https://doi.org/10.1080/00207543.2011.563164]
• P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of cooperative, autonomous vehicles in warehouses,” AI magazine, vol. 29, no. 1, 2008. [https://doi.org/10.1609/aimag.v29i1.2082]
• “Autonomous Mobile Robot Market by Type, by Application, and by End-User - Global Opportunity Analysis and Industry Forecast 2022-2030,” Autonomous Mobile Robot Market, Global, April 2022, [Online], https://www.researchandmarkets.com/reports/5529480/autonomous-mobile-robot-market-by-type-by?utm_source=GNOM&utm_medium=PressRelease&utm_code=jb6znx&utm_campaign=1652896+-+Global+Autonomous+Mobile+Robot+Market+(2022+to+2030)+-+Opportunity+Analysis+and+Industry+Forecasts&utm_exec=jamu273prd, .
• M. Merschformann, L. Xie, and D. Erdmann, “Path planning for robotic mobile fulfillment systems,” Artificial Intelligence, 2018. [https://doi.org/10.48550/arXiv.1706.09347]
• M. Merschformann, T. Lamballais, M. B. M. de Koster, and L. Suhl, “Decision rules for robotic mobile fulfillment systems,” Operations Research Perspectives, vol. 6, 2019. [https://doi.org/doi.org/10.1016/j.orp.2019.100128]
• W. Hönig, T. K. Kumar, L. Cohen, H. Ma, H. Xu, N. Ayanian, and S. Koenig, “Multi-agent path finding with kinematic constraints,” Twenty-Sixth International Conference on Automated Planning and Scheduling, vol. 26, 2016. [https://doi.org/10.1609/icaps.v26i1.13796]
• H. Ma, S. Koenig, N. Ayanian, L. Cohen, W. Hönig, T. K. S. Kumar, T. Uras, H. Xu, C. Tovey, and G. Sharon, “Overview: Generalizations of multi-agent path finding to real-world scenarios,” Artificial Intelligence, 2016. [https://doi.org/10.48550/arXiv.1702.05515]
• R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Bartak, “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks,” Artificial Intelligence, 2019. [https://doi.org/10.48550/arXiv.1906.08291]
• A. Felner, R. Stern, S. Shimony, E. Boyarski, M. Goldenberg, G. Sharon, N. Sturtevant, G. Wagner, and P. Surynek, “Search-based optimal solvers for the multiagent pathfinding problem: Summary and challenges,” Tenth Annual Symposium on Combinatorial Search, vol. 8, no. 1, 2017, [Online], https://ojs.aaai.org/index.php/SOCS/article/view/18423, . [https://doi.org/10.1609/socs.v8i1.18423]
• D. Silver, “Cooperative pathfinding,” The 1st Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE-2005), pp. 117-122, 2005. [https://doi.org/10.1609/aiide.v1i1.18726]
• M. Phillips and M. Likhachev, “SIPP: Safe interval path planning for dynamic environments,” 2011 IEEE International Conference on Robotics and Automation (ICRA), Shanghai, China, 2011. [https://doi.org/10.1109/icra.2011.5980306]
• K. Yakovlev and A. Andreychuk, “Any-angle pathfinding for multiple agents based on SIPP algorithm,” Artificial Intelligence, 2017. [https://doi.org/10.48550/arXiv.1703.04159]
• T. S. Standley, “Finding optimal solutions to cooperative pathfinding problems,” AAAI Conference on Artificial Intelligence, 2010. [https://doi.org/doi.org/10.1609/aaai.v24i1.7564]
• G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” Artificial Intelligence, vol. 219, pp. 40-66, February, 2015. [https://doi.org/10.1016/j.artint.2014.11.006]
• H. Ma, J. Li, T. K. Satish Kumar, and S. Koenig, “Life-long multi-agent path finding for online pickup and delivery tasks,” Artificial Intelligence, 2017. [https://doi.org/10.48550/arXiv.1705.10868]
• J. Švancara, M. Vlk, R. Stern, D. Atzmon, and R. Barták, “Online multi-agent pathfinding,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 1, 2019. [https://doi.org/10.1609/aaai.v33i01.33017732]
• J. Li, A. Tinka, S. Kiesel, J. W. Durham, T. K. Satish Kumar, and S. Koenig, “Lifelong multi-agent path finding in large-scale warehouses,” Artificial Intelligence, 2020. [https://doi.org/10.48550/arXiv.2005.07371]
• Q. Wan, C. Gu, S. Sun, M. Chen, H. Huang, and X. Jia, “Lifelong multi-agent path finding in a dynamic environment,” 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), Singapore, 2018. [https://doi.org/10.1109/ICARCV.2018.8581181]