기술 요약: Edge to Edge: 다중 로봇 시스템을 위한 흐름 기반 스케줄링 플래너

문제 정의

본 논문은 수많은 로봇이 장애물이 많은 환경에서 한쪽(출발지)에서 반대쪽(도착지)으로 통과하도록 조정하는 과제를 다룹니다. 전통적인 다중 로봇 경로 계획은 주로 점 대 점(point-to-point) 내비게이션이나 정적인 다중 에이전트 경로 탐색(MAPF)에 집중하지만, 이러한 방식은 로봇 밀도가 높을 때 혼잡, 교착 상태(deadlock), 비효적인 통과 시간 문제를 빈번하게 일으킵니다. 기존의 프런트엔드 플래너들은 단순한 점 대 점 연결이나 그리드 기반 MAPF 알고리즘(A* 또는 CBS 변형 등)에 의존하는 경우가 많으며, 이는 로봇 간의 상호작용을 무시하거나 동적이고 실시간 실행에 부적합한 경직된 경로를 생성합니다. 또한, 많은 흐름 기반 최적화 방법은 계산 집약적이며 오프라인 사용을 위해 설계되어, 실시간으로 개별 로봇을 위한 실행 가능한 궤적을 생성하는 능력이 부족합니다.

핵심 목표는 로봇들이 혼잡한 공간을 집단적으로 흘러가야 하는 시나리오에서 경로 길이, 우회, 대기 시간을 균형 있게 조절하여 **메이크스팬(makespan, 마지막 로봇이 목적지에 도달하는 시간)**을 최소화하는 것입니다.

방법론

저자들은 기존의 백엔드 충돌 회피 알고리즘(특히 ORCA)과 호환 가능한 프런트엔드 모듈로서 **흐름 기반 스케줄링 플래너(Flow-Inspired Scheduling Planner)**를 제안합니다. 이 프레임워크는 세 가지 주요 단계로 구성됩니다.

1. 네트워크 구축

그리드 맵과 흐름 네트워크 사이의 간극을 메우기 위해, 저자들은 환경을 두 가지 상보적인 표현 방식으로 분해합니다.

• 인접 네트워크(Adjacency Network): Boustrophedon 셀 분해(Boustrophedon Cellular Decomposition)를 사용하여 맵을 셀로 나눕니다. 셀 사이의 경계는 "Pos(위치)"를 샘플링하는 데 사용되며, 이들은 "노드(Nodes)"로 그룹화됩니다. 엣지는 인접한 셀 사이의 노드들을 연결하여, 잠재적인 이동 경로를 나타내는 그래프 $G=\{V, L\}$를 형성합니다.
• 혼잡도 맵(Congestion Map): 환경을 용량을 추정하기 위해 균일한 하위 영역으로 추가 분할합니다. 각 영역의 용량은 해당 영역의 면적과 로봇의 안전 반경을 기반으로 계산되며, 과대 산정을 방지하기 위해 리던던시 계수(redundancy factor)를 고려합니다. 이러한 분리는 용량 중복 계산 없이 공유된 공간 제약을 정밀하게 모델링할 수 있게 합니다.

2. 플래너 구성 요소

플래너는 세 가지 순차적 모듈을 실시간으로 실행합니다.

• 경로 집합 탐색(Path Set Search): 가능한 모든 경로를 열거하는 대신(계산적으로 불가능하므로), 알고리즘은 유망한 후보 경로의 부분 집합을 식별합니다. 로봇의 현재 위치와 목표 지점 근처의 경계 노드를 식선별한 후, 디이크스트라(Dijkstra) 알고리즘을 사용하여 이러한 특정 진입 및 출구 지점들을 연결하는 경로를 찾습니다. 이 "시작-출구, 입구-목적지" 전략은 결정 품질을 유지하면서 탐색 공간을 줄여줍니다.
• 경로 노드 선택(Path Node Selection): 시스템은 경로 선택을 혼합 정수 프로그래밍(MIP) 문제로 정식화합니다. 후보 경로를 다음 두 가지 비용을 기준으로 평가합니다.
  • 대기 비용($f_{Que}$): 혼잡도 맵에 대한 경로의 초기 세그먼트를 분석하여 미래의 혼잡을 예측합니다. 로봇 수가 용량을 초과하는 지역으로 이어지는 경로에 페널티를 부여하며, 과부하를 강력하게 억제하기 위해 제곱 오버로드 항을 사용합니다.
  • 주행 비용($f_{run}$): 과도한 경로 길이에 페널티를 부여합니다.
    최적화 도구는 이 두 비용의 합을 최소화하는 로봇들을 위한 경로 집합을 선택하여, 우회와 대기 시간 사이의 균형을 효과적으로 맞춥니다.
• 위치 할당(Position Allocation): 노드 시퀀스가 선택되면, 플래너는 각 노드에 구체적인 "Pos" 좌표를 할당합니다. 휴리스틱 그리디(greedy) 알고리즘이 사용됩니다. 첫 번째 노드의 경우, 클러스터링을 방지하기 위해 유클리드 거리와 현재 위치 점유도를 균형 있게 고려합니다. 이후의 노드들에 대해서는 매끄러운 전환을 보장하기 위해 이전 위치에서 가장 가까운 가용 위치를 선택합니다.

3. 실행

생성된 이산 경로는 궤적을 실행하면서 안전을 보장하는 백엔드 컨트롤러(ORCA 사용)로 전달됩니다. 플래너는 동적인 변화에 적응하기 위해 주기적으로(예: 시뮬레이션에서 2초마다) 실행됩니다.

주요 기여

1. 흐름 기반 스케줄링: 환경을 흐름 기반 네트워크 구조로 분해하여, 혼잡도 수준에 따라 로봇을 경로에 실시간으로 할당할 수 있는 새로운 프런트엔드 플래너를 제공합니다.
2. 실시간 효율성: 이 방법은 광범위한 네트워크 추상화를 활용하고 전수 조사를 피함으로써, 대규모 시스템(최대 500대의 로봇)에서도 온라인 동작을 지원하는 높은 계산 효율성을 달로합니다.
3. 혼잡 인지 최적화: 플래너는 지역 용량을 명시적으로 모델링하고 미래의 혼잡을 예측하여, 전체 메이크스팬을 최소화하기 위해 우회와 대기 시간 사이의 균형을 맞춥니다.
4. 검증: 다양한 맵 유형(숲, 미로, 장애물, 복도)과 로봇 밀도(10~500대)에 걸친 광범위한 시뮬레이션을 통해 프레임워크를 검증하였으며, 10대의 드론을 이용한 실제 비행 테스트를 수행했습니다.

실험 결과

• 소규모 규모(10–100 로봇): 제안된 "Flow" 방식은 메이크스팬 측면에서 A*, ECBS, P-SIPP, TVMA를 포함한 베이스라인들을 일관되게 능가했습니다. 특히 로봇 밀도가 높아질수록 강점을 보였으며, 최고의 MAPF 베이스라인들과 비교했을 때 메이크스팬을 약 5~9% 감소시켰습니다.
• 대규모 규모(100–500 로봇): 대규모 시나리오에서 Flow 방식은 최신 MAPF 알고리즘(CBSH2-RTC, LNS2) 및 혼잡 인지 방식(CMPP)을 크게 앞질렀습니다. 베이스라인 대비 4~15%의 메이크스팬 개선을 달성했습니다. 주목할 점은, LNS2는 혼잡을 줄였지만 종종 과도한 우회를 초래한 반면, Flow 방식은 혼잡 회피와 경로 길이 사이의 균형을 더 잘 맞추었다는 것입니다.
• 계산 시간: Flow 플래너는 우수한 확장성을 보여주었습니다. 500대의 로봇에 대해 평균 계획 시간은 1초 미만(약 0.9초)이었으나, 오프라인 MAPF 방식들은 훨씬 더 오랜 시간이 걸리거나 확장에 실패했습니다.
• 실제 테스트: 장애물이 많은 제한된 환경에서 10대의 DJI Tello 드론을 이용한 비행 테스트를 통해 방법의 실용적 타당성을 확인했습니다. 시스템은 충돌이나 교착 상태 없이 모든 드론을 한쪽에서 다른 쪽으로 성공적으로 유도했습니다.
• 밀도 분석: Flow 알고리즘은 다른 방법들에 비해 낮은 피크 로봇 밀도와 더 적은 "대기 상태" 로봇 수를 유지하여, 가용 공간을 더 효율적으로 활용함을 보여주었습니다.

의의 및 주장

본 논문은 복잡한 환경에서 방향성 있는 다중 로봇 통과(edge-to-edge)에 특화된 실시간 흐름 기반 스케줄링 플래너를 제공한다고 주장합니다. 이 연구의 의의는 창고 물류 및 도시 배송에서 흔히 발생하지만 표준적인 점 대 점 플래너에서는 간과되기 쉬운, 집단적 이동(edge-to-edge)을 위한 조정 문제를 해결했다는 데 있습니다.

저자들은 이 방법이 백엔드 충돌 회피를 대체하는 것이 아니라 오히려 프런트엔드 계획 단계를 강화하는 것임을 강조합니다. 네트워크 흐름 원리를 활용하여 선제적으로 혼잡을 관리함으로써, 시스템은 더 매끄럽고 빠른 집단적 통과를 달성합니다. 논문은 현재의 접근 방식이 단방향 흐름(출발지에서 도착지)에 최적화되어 있으며, 이를 전방향 또는 다방향 흐름으로 확장하는 것이 향후 연구 과제임을 겸허히 밝히고 있습니다.