Persistent and Robust Execution of MAPF Schedules in Warehouses - 누구나 그럴싸한 계획을 가지고 있지 문제가 발생하기 전까지는!

안녕하세요. 오늘은 MAPF 알고리즘의 안정적인 실행을 위한 방법을 연구한 Prersistent and Robust Execution of MAPF Schedules in Warehouses 논문을 공부해보도록 하겠습니다.

• HÖNIG, Wolfgang, et al. Persistent and robust execution of MAPF schedules in warehouses. IEEE Robotics and Automation Letters, 2019, 4.2: 1125-1131.

 

MAPF 알고리즘을 처음에 공부할 때에는 다음과 같은 궁금증이 항상 따라다녔습니다.

"사람, 지게차와 같은 동적인 장애물 혹은 네트워크 불안정성 때문에 로봇이 계획된 경로대로 움직이지 못하면 어떡하지?"

 

이 질문에 대해서 깔끔한 해결책을 제시해줘서 많은 도움이 되었던 논문입니다 ㅎㅎ

같이 공부해볼까요?

---

1. Introduction

1.1. 기존 연구들의 문제점

많은 MAPF 알고리즘들이 연구되었지만 경로만 짧고, 빠르게 계획할 수 있는 알고리즘들은 물류센터에서 사용될 수 없습니다.

왜일까요? 다음과 같은 현실에 적용 불가능한 가정들이 있기 때문입니다.

1. 로봇이 계획된 경로대로 정확히 움직일 수 있다는 가정
   • 사람, 지게차와 같은 동적인 장애물 혹은 네트워크 불안정성 때문에 서버가 계획한 경로대로 움직이지 못 할 수 있음
2. 로봇들에게 미션 혹은 작업이 계속해서 배정되는 상황을 가정하지 않음
   • MAPF 연구 초기에는 lifelong MAPF가 없었기 때문에 single shot 알고리즘들이 많았습니다.
   • single shot 알고리즘으로 lifelong MAPF 문제를 해결하기 위해서는 all stop과 같은 정책이 추가적으로 필요해집니다.

1.2. 선행 연구들

이를 해결하기 위해 1) 더 오랜 시간 동안 conflict를 허용하지 않거나(k-robust MAPF), 2) 확률에 기반하여 conflict를 계산하는 연구도 있었습니다.

3), 4) 혹은 로봇의 상태를 고려하여 더욱 정확히 경로를 계획하는 연구들도 있었습니다.

1. ATZMON, Dor, et al. Robust multi-agent path finding. In: Proceedings of the International Symposium on Combinatorial Search. 2018. p. 2-9.
2. MA, Hang; KUMAR, TK Satish; KOENIG, Sven. Multi-agent path finding with delay probabilities. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2017.
3. HÖNIG, Wolfgang, et al. Multi-agent path finding with kinematic constraints. In: Proceedings of the International Conference on Automated Planning and Scheduling. 2016. p. 477-485.
4. GREGOIRE, Jean; ČÁP, Michal; FRAZZOLI, Emilio. Locally-optimal multi-robot navigation under delaying disturbances using homotopy constraints. Autonomous Robots, 2018, 42: 895-907.

하지만 위의 연구들 모두 알고리즘 완벽히 충돌을 막을수는 없었습니다.

 

2. 논문에서 제안한 방법

그러면 이 논문은 뭐가 다르길래 충돌을 완벽히 막을 수 있었을까요?

다른 논문들처럼 로봇의 움직임을 정확히 예측하는 대신에 계획된 액션 간의 의존성을 관리하는 방식(Action Dependency Graph, ADG)으로 문제를 풀었습니다.

 

어차피 여러 노이즈 때문에 정확히 경로를 예측하는 것이 어렵다면 계획된대로 동작했는지 확인하면서 다음 명령을 내리는 것이죠.

하지만 이렇게 문제를 풀면 로봇이 자주 멈추게 되지는 않을까요? 조금 더 자세히 알아보겠습니다.

Action Dependency Graph(ADG)

ADG는 계획된 경로 간의 의존성을 파악할 수 있는 그래프입니다.

간단한 예시를 통해서 ADG를 어떻게 생성하는지 보여드리고, pseudo code를 알려드리겠습니다.

예시 1

예시 1 과 같은 상황에서 로봇 1은 노드 5로 로봇 2는 노드 6으로 로봇 3은 노드 7로 가야 하기 위한 경로로 다음과 같은 경로가 계획될 수 있습니다..

	시간 0	시간 1	시간 2	시간 3	시간 4	시간 5	시간 6
로봇 1	노드 1	노드 4	노드 5	노드 5	노드 5	노드 5	노드 5
로봇 2	노드 2	노드 2	노드 2	노드 4	노드 6	노드 6	노드 6
로봇 3	노드 3	노드 3	노드 3	노드 3	노드 3	노드 4	노드 7

 

로봇 1이 노드 5에 도착하기 전까지는 로봇 2가 노드 4로 갈 수 없고, 로봇 2가 노드 6에 도착하기 전까지는 로봇 3이 노드 4로 갈 수 없습니다.

이를 ADG로 나타내면 다음과 같습니다.

예시 1의 ADG

이를 조금 더 pseudo code로 작성하면 다음과 같습니다.

def create_adg(planned_path_for_all_robots) -> Graph:
    adg = Graph()
    for robot_id, planned_path in planned_path_for_all_robots.items():
        prev_node = planned_path[0]
        adg.add_node(key=f"{robot_id}:::{prev_node.id}", node=prev_node)
        for i in range(1, len(planned_path)):
            node = planned_path[i]
            adg.add_node(key=f"{robot_id}:::{node.id}", node=node)
            adg.add_edge(start_node=prev_node, end_node=node)
            prev_node = node

    for robot1_id, planned_path1 in planned_path_for_all_robots.items():
        for robot2_id, planned_path2 in planned_path_for_all_robots.items():
            if robot1_id == robot2_id:
                break

            for robot1_node in planned_path1:
                for robot2_node in planned_path2:
                    if robot1_node.start == robot2_node.end and robot1_node.time <= robot2_node.time:
                        adg.add_edge(start_node=robot1_node, end_node=robot2_node)

    return adg

 

이제 끝일까요?

이 연구는 Lifelong MAPF 문제를 해결하기 위해 단순히 MAPF 알고리즘을 안전하게 실행하는 것에만 집중하지 않았습니다.

경로를 계획하기 위해서 로봇을 정지시켜야 하는 비효율적인 상황을 없애기 위해서 계획된 경로의 실행과 재계획을 동시에 고려하는 방안을 제안합니다.

 

Lifelong Planning을 위한 Commit Cut

방식은 단순합니다.

로봇들에게 미리 보낼 명령을 계산한 다음에 ADG를 이용해서 로봇들의 이동을 위해서 보내야 할 명령을 계산합니다.

• 로봇들에게 미리 보낼 명령을 계산하는 방식은 도메인마다 다르기 때문에 논문에서는 예시를 위해 현재 노드에서 2 노드를 이동하는 방식으로 계산했습니다.

ADG를 이용해서 의존성이 해결될 때까지 액션을 탐색하는 것인데 pseudo code는 다음과 같습니다.

def create_commit_cut(adg) -> dict:
    desired_destination = compute_desired_destination(adg)
    reversed_adg = copy.deepcopy(adg)
    for edge in reversed_adg.edges:
        edge.reverse()
    reachable = {}
    queue = list(desired_destination)

    while not queue.empty():
        node = queue.pop(0)
        try:
            reachable[node.key].append(node)
        except:
            reachable[node.key] = [node]
        for edge in reversed_adg.get_adjacent_edges(node):
            queue.append(edge.end_node)
    return reachable

3. 실험

논문에서는 ECBS-TA와 ADG를 연동하여 ADG가 1) 실제로 경로를 안정적으로 실행하고, 재계획도 잘 실행할 수 있는지 그리고 2) 작업 효율이 얼마나 좋은지를 station utilization이라는 지표를 이용해서 측정했습니다.

• HÖNIG, Wolfgang, et al. Conflict-based search with optimal task assignment. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018.

실험은 1) 시뮬레이션 환경, 2) Mixed Reality 실험 2가지로 진행되었습니다.

 

1)의 시뮬레이션 환경은 아래의 그림과 같이 HARMONIES를 이용했습니다. 그림에는 선반 32개, 로봇 12대, 하차지 2개라고 나와있지만 실제 시뮬레이션 환경은 선반 600개, 로봇 50대, 하차지 8개인 환경입니다.

HÖNIG, Wolfgang, et al. Persistent and robust execution of MAPF schedules in warehouses. IEEE Robotics and Automation Letters, 2019, 4.2: 1125-1131. Fig 1

2) Mixed Reality 같은 경우에는 실제 로봇과 가제보 시뮬레이터를 이용해서 진행되었습니다.

• 실제 로봇의 노이즈가 발생하더라도 안정적으로 경로를 실행하는지 파악하기 위함

 

실험 결과는 다음과 같습니다.

 

persistence

• 1), 2) 두 실험 모두 로봇들이 충돌하지 않았습니다. ADG는 계획된 경로를 안정적으로 실행할 수 있었습니다.

Lifelong MAPF - 딜레이 없는 경로 재계획

• 로봇에게 남은 action이 10개보다 작아지면, 큐잉되어 있는 작업을 다시 할당하여 경로를 재계획하는 것으로 실험을 진행했습니다.
• 아래의 그래프는 로봇에게 전달된 명령들이 0이 되기 전에 경로 재계획에 성공하는 것을 보여줍니다.
• ADG를 사용하여 경로를 실행 중에 재계획하는 것에 성공하여 lifelong MAPF 문제를 딜레이 없이 해결할 수 있었습니다.

HÖNIG, Wolfgang, et al. Persistent and robust execution of MAPF schedules in warehouses. IEEE Robotics and Automation Letters, 2019, 4.2: 1125-1131. Fig 4

작업 성능

• 로봇들에게 한번에 하나씩 명령을 전달하고, 모든 명령이 완료되기까지 기다린 후에 다음 명령을 보내는 baseline과 비교하여 실험을 진행했습니다.
• ADG를 사용한 경우, baseline의 경우보다 2.5배 이상의 작업 성능을 보여줬습니다.

HÖNIG, Wolfgang, et al. Persistent and robust execution of MAPF schedules in warehouses. IEEE Robotics and Automation Letters, 2019, 4.2: 1125-1131. Fig 5

4. 리뷰

계획과 실행을 동시에 진행할 수 있는 점

Lifelong MAPF 문제를 해결하기 위해서는 로봇이 주어진 action을 모두 수행하기 전에 경로를 계획할 수 있어야 합니다.

ADG는 경로를 재계획 할 때, 명령을 미리 전달해두고 경로를 계획함으로써 이 문제를 해결했습니다.

 

미리 전달해둘 명령의 개수에 대한 제한이 없기 때문에 환경 별로 적절한 명령 수, 조건을 정할 수 있어서 다양한 환경에 적용할 수 있다는 장점이 있습니다. 또한, 실행 부분에 대한 프레임워크이므로 추가적인 개발 없이 다른 연구들과 같이 테스트/적용할 수 있습니다.

 

이런 프레임워크들은 잘 공부해둬서 적재적소의 순간에 응용할 수 있어야 할 것 같습니다.

Mixed Reality 실험

로봇의 실제 노이즈를 실험하면서 실제 다중 로봇 관제를 테스트 할 수 있는 아주 경제적인 방법이라고 생각합니다.

특히 가제보 시뮬레이터와 실제 로봇 간의 속도 차이로 persistence를 확인하기에는 아주 좋았을 것 같습니다.

 

Station Utilization

Station Utilization의 가리키는 바가 무엇인지 고민해보았고, 제가 이해한 내용을 간단히 작성해봤습니다.

 

물류센터에 로봇을 도입하는 이유는 물류센터에서 일어나는 작업을 자동화하기 위함입니다.

매우 큰 규모의 물류센터 같은 경우는 완전 자동화를 꿈꿀수도 있겠지만 중소 규모의 물류센터는 부분 자동화가 한계일 것입니다.

부분 자동화라고 한다면 작업자와 로봇이 함께 물류 작업을 진행하면서 작업자의 효율을 높여주는 것이겠죠.

 

그러면 로봇이 참여함으로써 시간을 절약할 수 있는 부분이 무엇일까요?

바로 피킹된 물건을 패킹 장소까지 옮기는 부분입니다.

• 피킹 작업: 물류센터에 보관되어 있는 물건을 찾아서 주문 수량에 맞춰서 찾는 작업
• 패킹 작업: 피킹이 완료된 물건을 주문자에게 보내기 위해서 포장하는 작업

비교적 까다로운 피킹 작업과 패킹 작업을 작업자가 진행하고, 그 사이의 이동을 로봇에게 맡기는 것이죠.

 

로봇을 도입함으로써 이루고 싶은 목표는 작업자들이 최대한 많이 피킹 작업과 패킹 작업을 하는 것입니다.

즉 작업자의 유휴 시간을 최소화 하는 것인데요. 하지만 작업자 별로 피킹/패킹 작업 시간을 측정하고, 추적하는 것은 어려운 문제입니다.

그래서 문제를 조금 단순화 시켜서 스테이션에서 피킹/패킹 작업이 일어나는 시간을 측정하는 것으로 바꾼 것입니다.

 

선반 이동 - 물류센터 문제 종류

이 논문에서는 로봇이 선반을 한번에 하나만 옮깁니다.

Station Utilizatino 부분에서 언급했듯 규모에 따라서 로봇을 활용하는 방법이 달라질텐데 중소 규모의 물류센터에서 선반을 옮기는 방식으로 피킹/패킹 작업을 진행할 수 있을지 모르겠습니다.

 

첫번째로 동일한 물건에 대해서 주문 수량이 많을 때에 선반을 옮기는 방식이 효율적일텐데 이런 경우가 흔치 않을 수 있습니다.

두번째로 동일한 물건에 대해서 주문 수량이 많더라도 단 건 주문에 대한 수량이 적다면 물건을 주문 별로 분배해야 해서 패킹 작업에 시간이 오래 걸리게 됩니다.

 

그래서 중소 규모의 물류센터에서는 로봇이 여러 개의 피킹 작업을 처리하면서 패킹 작업지로 가게 되지 않을까 싶습니다.

물론! 물류센터마다 그리고 운영 방침마다 달라질 수 있긴 합니다.

 

결국에는 로봇 운용 시나리오를 잘 고민해야 할 것 같습니다.

---

이번 논문은 어떠셨나요?

다른 논문들을 통해서 ADG를 이미 알게 되었지만 이렇게 연구를 직접 보니 또 다른 것 같습니다.

 

현실에서 MAPF 문제를 잘 풀기 위해서는 단순히 경로만 잘 계획하는 것이 아니라 계획된 경로를 잘 실행해야 합니다.

잘 계획하는 것도 여러 방법이 있고, 잘 실행하는 것도 여러 방법이 있는 것 같습니다.

 

모든 상황에 적용될 수 있는 마법 같은 해결책을 찾기 위해 공부하는 것이 아니라 주어진 문제를 해결할 수 있는 기반을 다진다는 생각으로 공부해야 하는 것 같습니다.