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

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

물류센터와 같은 곳에서의 로봇 운용은 정형화된 장소에서 장시간 운영을 목표로 한다. 최초 물류공간에 랙과 통로로 이루어진 공간을 그래프로 구성, 그대로 활용해서 전역경로생성(global path planning)을 하고, 작업자나 팔레트와 같은 동적인 장애물이 발견되면 별도의 지역경로생성(local path planning)으로 이를 피하는 형태로 맵을 구성한다. 여기서 전역경로생성에 활용되는 그래프 구성 방식의 선정은 매우 중요한데, 이는 장시간 높은 빈도로 경로계획 운용이 가능해야 하기 때문이다.

그래프를 구성하는 방식은 그 밀도에 따라 토폴로지(topology) 기반 혹은 격자(grid) 기반으로 나눠볼 수 있다. 토폴로지 기반 그래프 구성 방식은 노드(node)과 간선(edge)의 수를 줄일 수 있어 높은 빈도로 연산이 필요한 경우를 대비할 수 있으나, 간선에서 중간에 다시 경로계획을 할 수 없다는 문제가 있다. 격자 기반 그래프 구성 방식은 노드의 밀도가 높아 어느 위치에서도 다시 경로계획을 할 수 있는 반면, 밀도가 높아짐에 따라 연산량이 많아져서 높은 빈도로 연산하기 어렵다.

[8]에서는 물류센터에서 유동이 많은 랙 사이의 통로들을 단 방향의 토폴로지 기반 그래프(highway)로 구성하고 나머지 공간은 격자 기반의 그래프로 구성하는 Kiva systems의 방식을 소개하였다. 해당 방식은 넓은 공간에서는 로봇 움직임에 제약이 없는 반면, 유동이 많은 구간에서 로봇의 움직임을 예측 가능하게 하고, 로봇들 간의 정면충돌을 막아주는 역할을 한다.

실제로 다수의 로봇을 가지고 운용을 해 보면, 그래프 상에서 계산된 경로를 따라 정확한 시점과 위치로 로봇이 잘 따라가지는 않는데, 이는 로봇의 동역학적 특성이나 공간 지각이 전통적인 MAPF계산방식에 완전히 반영되어 있지 않기 때문이다^[8]. 연산량이 많은 MAPF 알고리즘에 다수 로봇에 대한 정확한 동역학적 특성이나 공간지각 정밀도를 모두 반영하는 것은 현실적이지 않고, 따라서 선택적으로 반영하여야 한다.

계산된 경로를 따라 정확한 시점과 위치로 로봇이 이동하지 않는다는 점은 또 다른 문제를 야기하게 된다. 로봇들이 이동하면서 중간에 계산된 결과에서 확인할 수 없었던 충돌이나 교착이 발생될 소지가 생기게 되는데, [7,8]등에서는 후 처리를 통해서 이런 문제점들을 해결하는 방법을 제안하고 있다. 이처럼 미리 예상하기 힘든 상황을 대비해서 처음의 경로 계산 결과를 가지고 로봇을 한 번에 이동하기 보다는, 중간중간 필요할 때마다 여러 번 경로 계획을 수행하는 방법이 필요하다.

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

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

[Fig. 1] 
The generalized online MAPF Framework

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

3.1.6 plan 전송

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

[Fig. 2] 
ROS2 based online MAPF system components and messages between components

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

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

[Fig. 3] 
(a) A MAPF result on a grid map. The s_i and t_i 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)]와 같은 경로 탐색 문제에 대해 한 줄 격자로 공간을 구성했을 때, 도출된 경로를 보여준다.

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

제안하는 방법을 실제 물류센터에서 사람과 로봇이 협업하는 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

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

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

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

[Fig. 8] 
An example of deadlock

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

로봇을 활용한 피킹 작업의 효율을 확인해보고자 실제 물류센터에서 각각의 로봇이 이동하는 거리, 소요되는 시간 그리고 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%가 넘는 수치이다. 측정 데이터를 종합해보면, 물류센터에서 피킹 작업 시 로봇들이 매우 큰 비중으로 활용되고 있음을 알 수 있다.