한 대에서 되던 주행은 왜 N대에서 깨지는가 — 멀티로봇 교통 협상 설계

한 대의 가정이 N대에서 무너지는 지점

단일 로봇 내비게이션은 "장애물은 내 결정과 무관하게 움직인다"는 가정 위에 서 있다. 로봇이 두 대가 되는 순간 이 가정이 깨진다. 상대는 나를 보고 반응하는 의사결정자이고, 내 회피가 상대의 입력이 되며 그 결과가 다시 내 입력이 된다. ORCA 논문(van den Berg 외)은 이를 한 문장으로 적었다 — 상대를 단순한 이동 장애물로 취급하면, 상대도 나를 그렇게 취급할 때 진동(oscillation) 이 생길 수 있다.

MAPF 문헌은 이 결합을 그래프 위의 충돌로 정식화한다. Stern 외(SoCS 2019)가 정리한 표준 용어로는 같은 시각 같은 정점을 점유하는 vertex conflict, 같은 간선을 동시에 지나는 edge conflict, 그중 반대 방향으로 자리를 맞바꾸는 swapping conflict, 그리고 following·cycle conflict가 있다. 실무에서 중요한 점은 "어떤 충돌을 금지할지"가 곧 차량 간 안전거리 정책이라는 것이다. 앞차가 비운 칸에 같은 틱에 들어가는 following을 허용하면 처리량이 오르지만, 제동거리가 한 칸보다 긴 차량에서는 그 허용이 곧 추돌이다.

네 가지 실패를 구분하기

현장 티켓은 대개 "로봇이 멈췄어요" 한 줄로 온다. 원인이 넷 중 무엇이냐에 따라 처방이 정반대이므로 먼저 분류해야 한다.

데드락에는 Coffman 외(1971)의 네 조건이 그대로 적용된다. 상호 배제(한 구간에 한 대), 점유 대기(지금 구간을 쥔 채 다음 구간을 요청), 비선점(로봇은 순간이동하지 못하고 예약도 강제로 회수하기 어렵다), 순환 대기. 네 조건이 동시에 성립해야 하므로 설계는 그중 하나를 깨는 일이다. 일방통행은 순환 대기를, "출구까지 확보한 뒤에만 교차로 진입"은 점유 대기를, 대피 포켓으로의 후진 명령은 비선점을 깬다. 라이브락은 데드락 해소 로직이 양쪽에서 동시에, 같은 규칙으로 발동할 때 생기는 2차 실패라는 점도 기억해 둘 만하다.

텔레메트리 창 하나로 세 가지 활성(liveness) 실패를 가르는 최소 로직은 다음과 같다.

def find_cycle(wait_for):            # {robot: 그 자원을 쥐고 있는 상대 robot}
    for start in wait_for:
        seen, r = [], start
        while r in wait_for and r not in seen:
            seen.append(r); r = wait_for[r]
        if r in seen:
            return seen[seen.index(r):]
    return None

def classify(wait_for, moved_m, progress_m, wait_s, median_wait_s):
    """최근 T초: moved_m=주행거리, progress_m=목표까지 남은 거리 감소량"""
    cyc = find_cycle(wait_for)
    if cyc and all(moved_m[r] < 0.05 for r in cyc):
        return "deadlock", cyc                  # 순환 대기 + 전원 정지
    busy = [r for r in moved_m if moved_m[r] > 1.0 and progress_m[r] < 0.1]
    if len(busy) >= 2:
        return "livelock", busy                 # 움직이지만 진척 0
    starved = [r for r in wait_s if wait_s[r] > 5 * median_wait_s]
    return ("starvation", starved) if starved else ("ok", [])

임계값(0.05 m, 5배)은 예시이며 차종과 맵에 맞춰 정해야 한다. 요점은 "정지 여부"가 아니라 "진척 여부"를 계측해야 라이브락과 기아가 보인다는 것이다.

공유 자원: 어디서 부딪히는가

표준과 프레임워크도 이 자원들을 1급 개념으로 다룬다. VDA 5050은 3.0.0(GitHub 릴리스 기준 2026년 3월 공개)에서 zone 개념을 넣었고, 그중 RELEASE 타입은 플릿 제어의 승인을 받아야 들어가는 구역이다. Open-RMF는 레인·정점을 묶어 한 번에 한 로봇만 잠글 수 있게 하는 mutex group 을 제공한다(2023년 12월 릴리스 노트에 등장). 둘 다 "공간을 락으로 다룬다"는 같은 발상이고, 따라서 락의 고전적 문제(순환 대기, 해제 누락)를 그대로 물려받는다. Open-RMF 2024년 6월(Jazzy) 릴리스 노트에 mutex group 수동 해제 기능이 추가된 것은 해제 누락이 실전 문제임을 보여 준다.

로컬 회피끼리 만나면 실패하는 메커니즘

DWA·TEB·MPPI 같은 로컬 플래너는 상대 로봇을 코스트맵의 점유 셀로만 본다. 의도도, 상대 역시 회피 중이라는 사실도 모델에 없다. 같은 소프트웨어를 돌리는 두 로봇이 정면으로 만나면 다음 순서로 무너진다.

1. 동률의 우연: 정면 대면에서는 좌·우 회피의 비용이 거의 같다. 어느 쪽을 고를지는 센서 잡음, 코스트맵 격자, 전역 경로의 미세한 치우침이 정하므로, 두 로봇이 통로의 같은 쪽을 고르는 일이 무시할 수 없는 빈도로 생긴다.
2. 재관측: 같은 쪽을 골랐다면 다음 주기에도 충돌 경로다. 같은 비용함수와 같은 제어 주기로 둘 다 반대쪽으로 수정하고, 이를 반복한다. 진동이 시작된다.
3. 통로 폭 부족: 비킬 횡방향 여유가 없으면 둘 다 정지한다. 이어서 복구 동작(후진·제자리 회전)이 동시에 발동하고, 동시에 재진입한다. 데드락이 라이브락으로 바뀔 뿐이다.

RVO/ORCA는 회피 책임을 양쪽이 나눠 지게 해 1~2단계의 진동을 없앴고, 수천 대 규모 시뮬레이션에서 수 밀리초 만에 전원의 속도를 계산했다고 보고한다. 그러나 논문이 명시한 가정은 홀로노믹 로봇, 완전한 센싱, 모두가 같은 프로토콜 사용이며, 밀집 상황에서는 선형계획이 비가용(infeasible)이 되어 "가장 안전한" 속도로 물러난다. 보장되는 것은 국소적 무충돌이지 진척이 아니다. 사람 군중 속 주행에서 Trautman·Krause(IROS 2010)가 이름 붙인 freezing robot problem — 환경 복잡도가 일정 수준을 넘으면 플래너가 모든 전진 경로를 위험하다고 판단해 멈추는 현상 — 도 같은 뿌리다.

결론은 분명하다. 로컬 회피는 (잘해야) 안전성을 주고, 활성은 주지 못한다. 좁은 통로의 정면 대면은 "누가 물러날지"라는 이산적 순서 결정이며, 연속 속도 공간을 탐색하는 플래너의 시야 밖에 있다.

중앙집중 ↔ 분산 스펙트럼과 양 끝의 실패

중앙 쪽 끝(학술 결과). Yu(2015)는 평면 그래프에서도 흔히 쓰는 시간·거리 목적함수 네 가지의 최적 다중 로봇 경로계획이 NP-complete임을 보였다. 그래서 실용 해법은 최적성을 포기한다. RHCR(Li 외, AAAI 2021)은 시간 창 안의 충돌만 해소하는 방식으로 시뮬레이션 창고에서 1,000대(빈 셀의 38.9%) 까지 풀었다. 다만 창 밖 충돌을 의도적으로 무시하므로, 창이 짧을수록 막다른 대면을 늦게 발견한다. 더 근본적인 문제는 MAPF의 이산 시간·완전 실행 가정이다. 2026년 2월 공개된 LSMART 논문은 기존 MAPF 연구가 단순화된 기구학과 완전한 실행·통신을 가정한다는 점을 출발점으로 삼아, 언제 계획할지·어떻게 계획할지·플래너가 실패하면 어떻게 복구할지를 FMS 설계 변수로 다룬다. 한 대가 3초 늦으면 시각에 묶인 계획 전체가 무효가 되므로, Hönig 외(RA-L 2019)의 Action Dependency Graph처럼 "시각"이 아니라 "통과 순서"만 강제하는 실행 계층이 필요하다.

중앙 쪽 끝(현장). VDA 5050 3.0.0은 범위 절에서 교통 관리 로직(라우팅·우선순위·혼잡 처리·데드락 해소의 전략과 알고리즘)을 다루지 않는다고 명시하면서도, 플릿 제어의 최소 기능 목록에는 "블로키지(데드락)의 검출과 해소"를 넣었다. 표준은 인터페이스만 주고 알고리즘은 구현자 몫이라는 뜻이다. 그 인터페이스의 핵심이 base/horizon 이다. 해제된 구간(base)까지만 주행하고, base의 마지막 노드(decision point)에서 연장이 없으면 정지한다. 또 MQTT가 비동기이고 무선 전송이 신뢰할 수 없으므로 한번 내보낸 base는 바꿀 수 없고, 플릿 제어는 이미 실행된 것으로 가정해야 한다. base를 길게 주면 흐름이 매끄럽지만 회수할 수 없는 락이 늘어나고(비선점), 짧게 주면 매 노드에서 멈칫한다. 이것이 현장 튜닝의 1번 트레이드오프다.

분산 쪽 끝. PIBT(Okumura 외)는 분산형 우선순위 상속으로 전원이 유한 시간 안에 목적지에 도달함을 보장하지만, 조건이 붙는다. 인접한 모든 노드 쌍이 단순 사이클에 속하는 그래프(예: biconnected)여야 한다. 막다른 통로와 단일 차로가 있는 실제 공장 맵은 이 조건을 어긴다. Open-RMF 문서도 협상에 참여하지 못하는 read-only 플릿은 공유 공간에 하나만 허용된다고 적는다. 둘 이상이면 데드락 회피가 거의 불가능해지기 때문이다. 2026년 8월 Open Robotics Discourse에는 밀집·협폭 산업 환경에서 반복되는 정면 충돌, 통로 앞 과도한 대기, 경로 결정의 진동을 보고하는 글이 올라왔다. 9월 메인테이너 답변은 결정론적 모션 모델이 혼잡 지연을 과소평가한다는 한계를 인정하고 일방통행 레인과 동적 레인 폐쇄를 권했다. 최신 협상 프레임워크의 권장 처방이 결국 고전적 AGV 교통 규칙이라는 점이 이 글 전체의 복선이다.

설계 전에 답해야 할 질문

• 맵에 비킬 수 없는 구간(단일 차로, 막다른 길, 도킹 접근로)이 몇 개이고, 각각의 대피 포켓은 어디인가?
• 네 가지 실패를 각각 다른 지표로 계측하는가? "정지 시간" 하나로는 라이브락과 기아가 보이지 않는다.
• 회수할 수 없는 락(해제된 base, 잠긴 mutex)의 최대 길이와 최대 보유 시간은 얼마인가?
• 복구 동작에 비대칭(우선순위·ID·난수 지연)이 들어 있는가? 대칭 복구는 라이브락 생성기다.
• 로컬 회피가 다른 로봇을 만났을 때 양보가 아니라 상위 계층에 보고하도록 되어 있는가?

이후 섹션 지도

뒤따르는 섹션은 위 스펙트럼을 왼쪽에서 오른쪽으로 걷는다. 먼저 MAPF 알고리즘(CBS·우선순위 계획·PIBT/LaCAM 계열)의 핵심 아이디어와 확장 한계를 보고, 이어 예약·구간 블로킹 같은 현장 교통 규칙, VDA 5050의 base/horizon과 zone으로 그 규칙을 구현하는 법, Open-RMF의 스케줄·협상·mutex group, 마지막으로 데드락 검출·복구와 시뮬레이션 검증을 다룬다. 이 섹션의 분류표와 Coffman 네 조건은 각 기법이 무엇을 막고 무엇을 남기는지 판정하는 공통 잣대로 계속 쓰인다.

정식화 — MAPF 가 가정하는 세계

MAPF(Multi-Agent Path Finding)는 그래프 G=(V,E) 위에서 로봇 n대가 이산 시간 스텝마다 "이웃 정점으로 이동" 또는 "대기"를 고르며, 서로 충돌하지 않는 경로 집합을 찾는 문제다. VDA 5050 의 node/edge 토폴로지나 Open-RMF 의 내비게이션 그래프가 곧 이 G 다. Stern 등(2019, Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks)이 용어를 통일했고, 실무자가 챙길 것은 셋이다.

• 충돌 정의: 정점 충돌(같은 시각 같은 셀)과 맞교환(swap) 충돌이 기본이고, 앞차가 비운 셀에 같은 틱에 들어가는 뒤따르기(following)를 허용할지는 변형마다 다르다. 실제 AMR 은 앞차가 빠지는 순간 그 자리를 채울 수 없으므로 following 금지가 현실에 가깝다.
• 목적 함수: makespan(마지막 도착 시각)과 flowtime/sum-of-costs(도착 시각 합). Yu & LaValle(AAAI 2013)은 makespan·총 도착시간·총 이동거리 최적화가 각각 NP-hard 이고 동시에 최적화할 수도 없음을 보였다. "최적 교통 제어"는 대수가 늘면 원리적으로 불가능하다는 뜻이다.
• 벤치마크: MovingAI MAPF 벤치마크는 맵마다 random 25개·even 25개 시나리오를 제공한다. 아래 수치 대부분이 이 맵(warehouse-20-40-10-2-2 등)에서 나왔다.

다섯 갈래의 핵심 아이디어

CBS — 충돌이 난 곳에만 제약을 건다

Sharon 등(2015)의 Conflict-Based Search 는 로봇들을 하나의 "결합 에이전트"로 묶지 않는다. 상위 레벨은 충돌 트리(CT)를 탐색하고, 하위 레벨은 한 대씩 제약을 지키는 최단 경로를 다시 찾는다.

CBS(instance):
  root.paths = 각 로봇의 개별 최단경로;  OPEN = {root}
  while OPEN:
    N = OPEN 에서 비용(sum-of-costs) 최소 노드
    c = N.paths 의 첫 충돌 (a_i, a_j, v, t)
    if c 없음: return N.paths             # 최적해
    for a in (a_i, a_j):                  # 이진 분기
      child = N + 제약 "a 는 시각 t 에 v 금지"
      child.paths[a] = 시공간 A*(a, child 의 제약)   # 한 대만 재계획
      OPEN.add(child)

최적이지만 CT 노드 수가 충돌 수에 지수적으로 는다. 좁은 통로에서 두 대가 마주 보면 "t 에 금지 → t+1 에 또 충돌"이 반복되며 트리가 폭발한다. 확장 한계의 실측치는 EECBS 논문(Li 등, AAAI 2021)에 있다 — 같은 맵에서 최신 최적 알고리즘은 최대 200대 수준이다.

ECBS·EECBS — 최적성을 w 배만큼 내주고 속도를 산다

ECBS 는 상·하위 레벨 모두에 focal search 를 써서 "최적 비용의 w 배 이내" 해를 보장한다. EECBS는 여기에 온라인 비용 추정과 CBS 개선 기법(bypass, 대칭 추론, WDG 휴리스틱)을 얹어 1분 안에 최대 1,000대, 최적 대비 2% 이내가 증명된 해를 찾았다고 보고한다.

우선순위 계획과 PBS — 현장 예약 방식의 이론적 정체

우선순위 계획(prioritized planning)은 로봇에 순서를 매기고, 뒤 로봇이 앞 로봇의 경로를 움직이는 장애물로 보고 계획한다. 예약 테이블 기반 AGV 교통 제어가 사실상 이것이다. Ma 등(AAAI 2019)이 한계를 정리했다.

• 어떤 우선순위를 주어도 일반적으로 불완전하다(Theorem 1). 풀 수 있는 문제를 "해 없음"으로 돌려줄 수 있다.
• 단 well-formed 인스턴스(각 로봇의 출발·목표 셀이 남의 경로를 막지 않는 배치)에서는 어떤 전순서로도 완전하다(Theorem 3).

PBS(Priority-Based Search)는 순서를 미리 고정하지 않고, 충돌이 난 두 로봇에 대해서만 "i≺j / j≺i" 로 분기하는 우선순위 트리를 깊이 우선 탐색한다. 100대 이상에서도 준최적이고, well-formed 인스턴스 600대를 1분 안에 풀었다. 완전성·최적성 보장은 없다.

PIBT·LaCAM — 구성(configuration) 단위로 한 스텝씩

PIBT는 매 스텝 우선순위 상속과 백트래킹으로 "다음 한 칸"만 정한다. 인접한 모든 정점 쌍이 단순 사이클에 속하는 그래프(예: biconnected)에서는 모든 로봇이 유한 시간 안에 목적지에 닿는다는 보장이 있다. 뒤집으면 막다른 통로가 있는 맵에서는 보장이 없다.

LaCAM(Okumura, AAAI 2023)은 전 로봇의 위치 묶음을 상위 노드로 두고, 후속 구성을 PIBT 로 하나씩 게으르게 생성한다. 완전 알고리즘이면서 warehouse-20-40-10-2-2 에서 10,000대 인스턴스를 전부, 최대 30초에 풀었다(제한 1,000초). 같은 논문이 약점도 밝힌다. 통로 폭 2 인 이 맵은 전부 풀었지만, 폭 1 인 warehouse-20-40-10-2-1 에서는 자주 실패했다. 좁은 통로가 이 글의 주제인 이유다. 후속 LaCAM* 는 시간을 주면 최적해로 수렴하고, Engineering LaCAM* (AAMAS 2024)는 1,000대 초기해를 수 초에 얻는다.

코드로 보는 예약 테이블과 k-robust

아래는 시공간 A* + 예약 테이블로 만든 우선순위 계획이다. 실행해 확인한 결과를 주석으로 남겼다.

import heapq

def st_astar(grid, s, g, vres, eres, parked, k, t_max=64):
    """시공간 A*: 상태=(셀, t). vres/eres 는 상위 우선순위 로봇의 예약."""
    h = lambda c: abs(c[0] - g[0]) + abs(c[1] - g[1])
    last = max([t for (c, t) in vres if c == g], default=-1)  # 목표 셀의 마지막 예약
    pq, seen = [(h(s), 0, s, (s,))], set()
    while pq:
        _, t, c, path = heapq.heappop(pq)
        if c == g and t > last:
            return list(path)
        if (c, t) in seen or t >= t_max:
            continue
        seen.add((c, t))
        for dr, dc in ((0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)):  # 대기 포함
            n = (c[0] + dr, c[1] + dc)
            if grid[n[0]][n[1]] == "#":
                continue
            if (n, t + 1) in vres or (n, c, t + 1) in eres:         # 정점 충돌 / 맞교환
                continue
            if n in parked and t + 1 >= parked[n] - k:              # 도착 후 영구 점유
                continue
            heapq.heappush(pq, (t + 1 + h(n), t + 1, n, path + (n,)))
    return None

def prioritized(grid, tasks, k=0):
    vres, eres, parked, out = set(), set(), {}, {}
    for name, s, g in tasks:                   # 리스트 순서가 곧 우선순위
        p = st_astar(grid, s, g, vres, eres, parked, k)
        if p is None:
            return None                        # 불완전성: 순서만 바꿔도 풀릴 수 있다
        for t, c in enumerate(p):
            for d in range(-k, k + 1):         # k-robust: 앞뒤 k 스텝까지 셀을 잡아둔다
                vres.add((c, t + d))
            if t:
                eres.add((p[t - 1], c, t))
        parked[p[-1]] = len(p) - 1
        out[name] = p
    return out

GRID = ["#######",
        "#.....#",
        "####.##",   # (2,4) 가 유일한 대피 포켓
        "#######"]
A, B = ("A", (1, 1), (1, 5)), ("B", (1, 5), (1, 1))
# prioritized(GRID, [A, B], k=0) -> A 4스텝, B 7스텝 (B 가 포켓으로 피함)
# prioritized(GRID, [A, B], k=1) -> A 4스텝, B 8스텝 (강건성의 값 = +1 스텝)
# prioritized(GRID, [B, A], k=0) -> None  (포켓이 A 에게 너무 멀다)

같은 맵, 같은 두 대인데 순서만 바꾸면 해가 사라진다. "대피 포켓에 가까운 쪽이 양보한다"는 현장 규칙은 PBS 가 탐색으로 찾는 우선순위를 사람이 미리 적어 둔 것이다. k=1 은 로봇 한 대가 한 스텝 늦어도 계획이 깨지지 않게 하는 대가로 B 의 경로를 7→8 스텝으로 늘린다.

Lifelong MAPF — 창고는 끝나지 않는다

창고에서는 도착 즉시 새 목표가 떨어진다. RHCR(Rolling-Horizon Collision Resolution; Li 등, AAAI 2021)는 이를 창 길이 w 안의 충돌만 해소하고 h 스텝마다 재계획하는 Windowed MAPF 의 연쇄로 바꾼다. 논문의 실측은 다음과 같다.

• 시뮬레이션 창고에서 1,000대(빈 셀의 38.9%) 까지 확장.
• 작은 w 는 대부분 처리량을 w=∞ 대비 1% 미만만 바꾸면서 실행 시간을 최대 6배 줄였다. PBS 는 w=∞ 에서 700대까지만, w=5 에서는 1,000대 이상 풀었다.
• 대신 w 가 너무 작으면 데드락이 생긴다. 회피 장치를 넣어도 RHCR 은 불완전하며, 저자들은 "처리량과 완전성은 경쟁한다"고 적고 처리량을 택했다.
• 분류 센터 맵(37×77 격자)은 행·열을 두 줄씩 번갈아 손으로 정한 일방통행 방향 그래프로 실험했다. 맞교환 충돌 자체를 없애 솔버를 가볍게 하려는 선택이다. 학술 솔버도 교통 규칙 위에서 더 잘 돈다.

의사결정 기준으로 옮기면 이렇다. 재계획 주기 h 는 "통신 지연 + 계획 시간"보다 길게, w 는 h 이상이면서 맵에서 가장 긴 단일 통로를 빠져나갈 시간보다 길게 잡는다. w 가 통로보다 짧으면 두 대가 서로 안 보이는 채로 양끝에서 진입한다.

League of Robot Runners — 공개 대회가 보여 준 것

Amazon Robotics 가 후원하는 lifelong MAPF 대회다.

• 2023년: 로봇은 전진·90° 회전·대기만 가능하고 계획 시간은 스텝당 1초. 맵은 819~54,320 정점, 최대 10,000대, Random 맵은 819 정점에 800대(밀도 97.7%). Overall Best·Fast Mover 트랙 1위(Line Honours 2위) 팀의 해법 논문에 따르면 뼈대는 PIBT 초기해 → 창 단위 MAPF-LNS anytime 개선 → 멀티코어 병렬화였고, 혼잡 완화를 위해 간선 가중치를 조정한 guidance graph 를 쓰고 병목(막다른 곳·좁은 통로)의 일부 로봇을 아예 세워 두었다.
• 2024년(2024-11-01~2025-02-16): 경로 계획·작업 스케줄링·통합 3개 트랙으로 분리.
• 2026년(AAMAS 2026 공동 개최, 2026-03-18 스타트킷 공개~07-22 종료, 결과 발표 예정일 08-07): 실행 지연이 문제 모델에 들어왔다. 로봇이 계획한 이동을 제때 못 할 수 있고, 실행 정책만 겨루는 Execution 트랙이 신설됐다. 2026-09-19 현재 수상팀 명단은 공식 페이지에서 직접 확인하지 못해 적지 않는다. Virtual Expo 는 2026-11-03 로 공지돼 있다.

스텝당 1초 제약에서 이긴 것은 최적 탐색이 아니라 빠른 규칙 기반 초기해 + 남는 시간의 개선 + 교통 유도였다. 그리고 대회 자체가 3년 만에 "계획"에서 "실행 강건성"으로 중심을 옮겼다.

격자와 실제 로봇 사이의 간극

MAPF 는 단위 시간·동일 속도·즉시 정지·회전 비용 0·완벽한 동기 실행을 가정한다. 하나도 현장에서 성립하지 않는다. 메우는 방법은 세 층이다.

1. 후처리 — MAPF-POST(Hönig 등, ICAPS 2016): 이산 계획을 Simple Temporal Network 로 옮겨 다항 시간에 실행 스케줄을 만든다. 비홀로노믹 로봇의 최대 병진·회전 속도를 반영하고 로봇 간 안전 거리를 보장하며, 여유(slack)로 실행 오차를 흡수해 재계획을 줄인다.
2. 계획 단계의 여유 — k-robust(Atzmon 등, JAIR 2020): 어떤 로봇이 최대 k 스텝 지연돼도 충돌이 없는 계획. 위 코드처럼 예약을 ±k 로 넓히는 것이 가장 단순한 구현이고, 비용은 경로 길이로 나타난다.
3. 실행 프레임워크: Hönig 등(RA-L 2019)은 기존 단발 MAPF 플래너를 그대로 쓰면서 로봇의 예기치 못한 감속과 장애물 출현에도 안전한 실행, 계획과 실행의 중첩을 다룬다. 핵심은 시각이 아니라 "누가 이 셀을 먼저 지나가는가"라는 순서를 지키게 하는 것이다. 순서만 지키면 늦어져도 충돌하지 않는다. 계획 자체에 운동학을 넣는 방향으로는 TP-SIPPwRT(Ma 등, AAAI 2019)가 있고, WinkTPG(2025-08)는 1,000대의 속도 프로파일을 1초 안에 만든다고 보고한다.

도입 전 체크리스트

• [ ] 대기·충전·작업 스테이션이 통로 밖에 있는가(well-formed). 아니면 우선순위·예약 방식의 완전성 보장이 없다.
• [ ] 폭 1 통로마다 대피 포켓이 있는가, 없으면 일방통행인가. PIBT/LaCAM 계열의 약점이 정확히 여기다.
• [ ] 플릿 매니저는 절대 시각이 아니라 셀 통과 순서를 강제하는가. VDA 5050 의 released/horizon 노드 구분이 이 용도에 맞는다.
• [ ] k 를 실측 지연 분포(통신 왕복 + 정지 거리)에서 정했는가.
• [ ] 재계획 창 w 가 가장 긴 단일 통로 통과 시간보다 긴가.

학술 결과와 현장 규칙을 구분해 읽기

위 수치는 모두 격자·동기 실행·완전한 위치 정보를 가정한 시뮬레이션 결과다. "10,000대를 30초에"는 계산 확장성의 증거이지 현장 처리량의 증거가 아니다. 반대로 일방통행·구역 점유(zone blocking)·교차로 선점 같은 AGV 교통 규칙은 최적성 증명은 없지만, 이론이 요구하는 조건(well-formed 배치, 사이클이 있는 그래프)을 레이아웃 단계에서 미리 만족시키는 장치다. 2023년 우승 해법이 guidance graph 와 병목 로봇 정지를 쓴 것, RHCR 실험이 손으로 정한 통행 방향을 쓴 것은 두 세계가 합쳐지고 있다는 신호다. 실무 순서는 규칙으로 그래프를 "풀기 쉬운 형태"로 만든 뒤 솔버를 얹는 것이다.

최적 경로가 아니라 "누가 먼저 쓰느냐"를 푼다

MAPF 논문은 전 로봇의 경로를 한꺼번에 최적화하지만, 돌아가는 AGV/AMR 현장의 교통관리는 대부분 자원 예약이다. 경로는 로봇마다 따로 뽑고, 겹치는 자원(노드·엣지·구역)의 사용권만 중앙에서 직렬화한다. 오픈소스 플릿 제어기 openTCS 6.7.0 의 사용자 가이드는 기본 스케줄러를 "플랜트 모델의 자원(포인트·경로·로케이션)을 상호 배타적으로만 쓰게 하는 단순한 전략"이라고 스스로 규정한다. VDA 5050 도 같은 전제다. 3.0.0(2026-03-19 공개, 2026년 9월 현재 최신)은 플릿 제어의 최소 기능에 "교착 감지·해소"와 "교통 제어"를 넣어 두고, 주문 속 노드·엣지마다 released 불리언을 둔다. 풀린 부분이 base, 안 풀린 부분이 horizon 이고 로봇은 base 까지만 달린다. base 를 얼마나 앞서 풀어 주느냐가 곧 예약이다.

구역 락 — 한 구역에 한 대

현장 실무. 교차로·막다른 길·좁은 통로를 구역으로 묶고 뮤텍스를 건다. 공개된 구현 세 가지가 거의 같은 모양이다.

• openTCS 블록: SINGLE_VEHICLE_ONLY(기본값)와 SAME_DIRECTION_ONLY 두 타입. 할당 요청이 오면 ① 차량이 일시정지가 아닌지 ② 자원이 비었는지 ③ 단독 블록이면 블록 전체로 요청을 확장해 비었는지 ④ 동방향 블록이면 진입 방향이 기존 차량과 같은지 ⑤ 차량 엔벨로프 영역이 겹치지 않는지를 보고, 하나라도 실패하면 큐에 넣는다. 자원이 풀리면 요청 순서대로 다시 검사한다.
• Open-RMF 뮤텍스 그룹: rmf_ros2 PR #310(2023-12-15)로 들어왔다. 레인·정점을 그룹에 넣으면 로봇은 진입 전에 그룹을 잠가야 한다. mutex_group_supervisor 는 claim_time 이 가장 이른 요청자에게 준다(FCFS).
• VDA 5050 3.0.0 RELEASE 구역: 로봇이 state 의 zoneRequests 에 requestType: ACCESS 를 올리고, 플릿 제어가 responses 토픽으로 GRANTED/QUEUED/REJECTED/REVOKED 를 답한다. 주문에 풀린 노드가 구역 안에 있어도 요청은 따로 해야 하고, 응답이 제때 안 오면 들어가면 안 된다. 윤곽 기반 구역이라 적재물 포함 윤곽이 한 점이라도 걸치면 진입, 전부 빠져야 이탈이다.

함정은 여러 구역을 순차로 잡을 때다. A 가 g1 을 쥐고 g2 를, B 가 g2 를 쥐고 g1 을 기다리면 락 자체가 교착을 만든다. Open-RMF 수퍼바이저는 두 요청자가 같은 조합(2개 이상)을 원하면 각자의 claim 시각을 그 요청자의 가장 이른 값으로 정규화해 한쪽이 전부 갖게 한다. VDA 5050 도 RELEASE 구역 여러 개에 걸친 영역은 "전부 승인받은 뒤 진입"을 요구한다. 직접 짠다면 필요한 락을 한 번에 전부(all-or-nothing), 그리고 전역 순번으로 주는 것이 가장 단순하다.

공정성은 공짜가 아니다. openTCS 문서는 기본 전략이 기아를 막지 못한다고 적는다 — 큰 자원 집합을 기다리는 차량은 다른 차량이 부분집합을 계속 가져가면 이론상 영원히 기다리며, 이는 "그래프 토폴로지 문제의 신호"라 기본 구현에선 감수한다는 것이다.

시간창 예약 테이블

학술 계보. Silver 의 Cooperative Pathfinding(AIIDE 2005)이 원형이다. 에이전트를 하나씩 계획하면서 (셀, 시각) 예약 테이블에 경로를 써 넣고, 뒤 에이전트는 그 칸을 장애물로 본다. WHCA* 는 예약을 앞의 w 스텝 창에만 적용해 계산을 주행 시간에 분산한다. 같은 발상의 현대판이 RHCR(Li 외, AAAI 2021)로, 충돌 해소를 유한 시간창 안에서만 하고 그 밖은 무시해 1,000 에이전트(맵 빈 칸의 38.9%) 까지 고품질 해를 냈다고 보고한다. AGV 분야에서는 Kim & Tanchoco(1991)가 노드별 빈 시간창 그래프로 무충돌 최단시간 경로를 구했고, SIPP(Phillips & Likhachev, 2011)는 시각별 칸 대신 "안전 구간" 목록만 들고 있어 테이블을 압축한다.

현장 적용의 한계. 시간창은 로봇이 약속한 시각에 그 자리에 있다는 가정 위에 선다. 사람이 끼어들고 팔레트가 비뚤게 놓인 현장에선 몇 초씩 밀린다. 그래서 실무는 (a) 절대 시각 대신 통과 순서만 고정하거나(같은 자원은 예약 순서대로 통과 — Hönig 외 2019 의 실행 의존성 그래프가 이 방식이다), (b) 시간창에 속도 비례 여유를 두고 어긋나면 그 창만 재계획한다. VDA 5050 의 base 연장은 (a)다. 시각 없이 "여기까지 가도 된다"만 전하고, 로봇은 base 가 짧아지면 newBaseRequest 로 연장을 요청한다.

AIM 에서 빌려올 것

Dresner & Stone 의 AIM(JAIR 31권, 2008)은 교차로를 n×n 예약 타일로 나누고, 차량의 요청(도착 시각·속도)을 관리자가 내부 시뮬레이션해 이미 예약된 타일을 한 번이라도 밟으면 거절, 아니면 그 타일-시각을 예약한다. 자동차용이지만 구역 관리자 설계에 그대로 옮길 결과가 있다.

• 세분도에는 천장이 있다. 계산량은 세분도의 제곱에 비례한다. 한 구성에서 세분도 8 이면 충분했고 9 로 올리자 마주 달리는 차량이 가운데 타일 줄을 다투어 오히려 나빠졌다. 직진만 있는 실험에서 차선 수의 2배를 넘는 세분도는 개선이 미미했고(회전을 넣은 본 실험은 방향당 3차선에 세분도 24), 반대로 6차선에 타일 1개는 교착으로 시뮬레이터 메모리가 넘쳤다. → 서로 만나지 않는 흐름이 같은 예약 단위를 다투지 않을 만큼만 쪼갠다.
• 거절 후 재요청 백오프. 거절 응답에 "이 시각 전 재요청은 무시"를 실어 보낸다. 구현값은 t + min(0.5 s, (tₐ−t)/2). 교차로 앞에 선 차량은 자주, 먼 차량은 드물게 묻게 되어 가까운 쪽이 자연히 우선한다.
• 버퍼는 정적+시간 혼합. 속도에 비례해 진행 방향으로 늘어나는 시간 버퍼에 작은 정적 버퍼(횡오차·저속용)를 더한다. 교차로 경계의 가장자리 타일만 시간 버퍼를 후속 차간 간격만큼 키워, 빠져나간 직후의 추돌을 막으면서 내부의 촘촘한 교차 통과는 유지한다.

빌리면 안 되는 것은 전제다. AIM 의 실험은 제한속도 25 m/s 의 차량이 약속한 궤적을 버퍼로 흡수할 수 있는 오차 안에서 지킨다고 본다. 사람과 섞여 달리는 AMR 은 도착 시각을 그만큼 지키지 못하므로 타일-시각 예약보다 "구역+순서" 예약이 맞는 경우가 많다.

충돌 자체를 없애는 설계 — 일방통행과 차선

가장 싼 교착 해법은 마주 보는 상황이 생기지 않는 그래프다. FAR(Wang & Botea, ICAPS 2008)은 격자의 행·열을 번갈아 일방통행으로 주석해 정면 충돌을 없앤 뒤 각자 A* 를 돌리고, 실행 중엔 k=3 스텝만 예약하며 교착을 "서로 기다리는 순환"으로 검출한다. WHCA* 보다 빠르고 메모리를 덜 쓰며 더 많은 유닛까지 확장됐다는 것이 그 결과다. 이 흐름은 highway(Cohen 외, 2015)를 거쳐 Guidance Graph Optimization(IJCAI 2024)으로 이어진다. 엣지 가중치를 자동 최적화해 벤치마크 맵 8종에서 lifelong MAPF 알고리즘 3종의 처리량을 높였고, 93×91 맵·3,000 에이전트용 가이던스까지 생성했다.

현장 도구도 같은 것을 준다. openTCS 의 SAME_DIRECTION_ONLY 블록, VDA 5050 3.0.0 의 DIRECTED 구역(SOFT/RESTRICTED/STRICT — RESTRICTED 는 장애물 회피는 허용하되 역주행은 금지)과 BIDIRECTED 구역이 그렇다. Open-RMF 메인테이너도 2024년 6월 포럼 답변에서, 뮤텍스 그룹 성능 질문에 C++ 튜닝보다 내비 그래프 튜닝으로 좋은 교통 거동을 얻어 왔다고 답했다.

• 간선은 일방통행 순환 루프로, 양방향은 지선·도킹 구간에만.
• 양방향 단일 통로를 피할 수 없으면 양 끝에 대기 포켓을 두고 통로 전체를 한 락으로.
• 교차로 락은 출구 쪽에 로봇 한 대가 빠져나갈 자리가 있을 때만 준다(박스 정션 규칙). 출구가 막힌 채 진입하면 락이 풀리지 않는다.

예약 단위가 처리량을 정한다

감을 잡는 산수(가정값이지 측정치가 아니다): 통로 12 m, 로봇 1 m, 1.0 m/s, 승인 왕복 1 s. 통로 전체가 락 하나면 점유 시간이 (12+1)/1.0+1 = 14 s 라 상한은 3600/14 ≈ 257대/시다. 3 m 구간 넷으로 쪼개 동방향 추종을 허용하면 차두 간격 4 m = 4 s 로 한 방향 900대/시까지 오르지만, 방향을 바꿀 때마다 통로를 비우는 13 s 를 잃는다. 쪼갤수록 락 연산과 순환 대기 경로가 늘어나므로, 병목 구역의 점유 시간부터 재고 가장 느린 구역만 쪼개는 순서가 맞다.

예약 누수 — 죽은 로봇이 락을 쥐고 있을 때

락 보유자가 배터리 방전·프로세스 크래시·Wi-Fi 음영에 빠지면 구역은 영영 잠긴다. 분산 시스템의 답은 리스(Gray & Cheriton, SOSP 1989)다. 기한부로 주고 갱신이 끊기면 회수한다.

• Open-RMF: 수퍼바이저가 2초마다 점검해 10초간 갱신 없는 claim 을 지우고 다음 요청자를 고른다. 10초는 소스에 하드코딩이고 "설정 가능하게" TODO 가 붙어 있다(2026-09 main 기준). 플릿 어댑터 쪽에도 가드가 있어, 태스크 없이 10초 넘게 유휴인 로봇이 쥔 뮤텍스는 "태스크가 잘못 끝났을 것"이라며 강제 해제한다.
• VDA 5050 3.0.0: 응답에 leaseExpiry 를 실을 수 있고 같은 응답을 다시 보내 연장한다. 만료되면 로봇은 requestStatus 를 EXPIRED 로 바꾸고 진입하지 않는다. 이미 안이라면 구역 정의의 releaseLossBehavior — STOP(기본, RELEASE_LOST CRITICAL 오류)/CONTINUE/EVACUATE — 를 따른다. 연결 단절은 MQTT last will 의 CONNECTION_BROKEN 으로 알 수 있고, state 는 이벤트 시 또는 최소 30초마다 발행된다.

여기에 소프트웨어 락에는 없는 물리 문제가 둘 붙는다.

1. 만료 ≠ 비었음. 죽은 로봇은 그 자리에 있다. 타임아웃으로 락을 자동 해제하면 다음 로봇의 안전은 다른 층(트래픽 스케줄, 로봇의 장애물 정지)에 기대게 된다. 락이 유일한 방어선이라면 만료된 구역은 해제가 아니라 격리하고, 보유자가 구역 밖에 있음을 확인했거나 운영자가 확인했을 때만 푼다. 단일 통로·교차로는 멈추는 것 자체가 봉쇄이므로 CONTINUE/EVACUATE, 사람·문·엘리베이터와 엮인 구역은 STOP 이 맞다.
2. 좀비 보유자. Kleppmann 의 분산 락 글(2016)이 든 예처럼, 프로세스가 리스 기간보다 길게 멈췄다 깨어나면 자기가 아직 보유자라고 믿는다. 부여마다 단조 증가하는 펜싱 토큰을 발급하고 하트비트·주행 명령에 토큰을 실어 낡은 토큰을 거절한다.

TTL 기준: 하트비트 주기의 3~5배(패킷 한두 개 유실로 만료되지 않게), 로봇은 서버보다 먼저 만료로 간주(시계 오차만큼 짧게), 갱신 실패 시 구역 경계 앞에서 설 수 있는 제동 거리 지점을 진입 결정점으로 둔다. 대기열도 샌다 — 죽은 대기자가 줄 맨 앞을 막지 않도록 대기 항목에도 TTL 을 건다. rmf_ros2 이슈 #375(2024-07 보고, 2026-09 현재 열림)는 한 로봇이 구역 안에서 액션을 수행하는 동안 다른 로봇이 같은 뮤텍스를 얻어 교착에 빠졌다는 보고다. 원인은 이슈에서 확정되지 않았지만, 주행이 아닌 상태(액션·충전·수동 조작)에서도 보유가 유지되는지는 누수 테스트의 첫 항목으로 둘 만하다.

짧은 구현 예

전부-아니면-전무 요청, 전역 순번 FCFS, 리스+하트비트, 펜싱 토큰, 만료 시 격리를 담은 최소 구현이다(Python 3.10+).

import itertools, time
from dataclasses import dataclass

@dataclass
class Zone:
    holder: str | None = None
    token: int = 0             # 펜싱 토큰: 부여마다 단조 증가
    expires: float = 0.0
    quarantined: bool = False  # 리스는 끝났지만 비었다는 증거가 없다

class ZoneLocks:
    def __init__(self, ttl=6.0, clock=time.monotonic):
        self.zones, self.waiting = {}, {}   # waiting: robot -> [순번, 구역집합, 마지막 폴링]
        self.ttl, self.clock = ttl, clock
        self._seq, self._tok = itertools.count(1), itertools.count(1)

    def _sweep(self, now):
        for z in self.zones.values():       # 만료 = 해제가 아니라 격리
            if z.holder and z.expires < now:
                z.quarantined = True
        for r in [r for r, w in self.waiting.items() if w[2] + self.ttl < now]:
            del self.waiting[r]             # 죽은 대기자 제거

    def request(self, robot, names):        # 토큰이면 GRANTED, None 이면 QUEUED
        now = self.clock(); self._sweep(now)
        w = self.waiting.setdefault(robot, [next(self._seq), frozenset(names), now])
        w[2] = now
        older = [o[1] for o in self.waiting.values() if o[0] < w[0]]
        for n in w[1]:
            z = self.zones.setdefault(n, Zone())
            if z.quarantined or z.holder not in (None, robot) or any(n in o for o in older):
                return None
        del self.waiting[robot]
        tok = next(self._tok)
        for n in w[1]:
            z = self.zones[n]; z.holder, z.token, z.expires = robot, tok, now + self.ttl
        return tok

    def heartbeat(self, robot, tok):        # False 면 로봇은 상실 동작(STOP/EVACUATE)으로
        now = self.clock(); self._sweep(now)
        held = [z for z in self.zones.values() if z.holder == robot and z.token == tok]
        if not held or any(z.quarantined for z in held):
            return False
        for z in held:
            z.expires = now + self.ttl
        return True

    def release(self, robot, tok, names):   # 윤곽 전체가 구역을 벗어난 뒤에만 호출
        for n in names:
            z = self.zones[n]
            if z.holder == robot and z.token == tok and not z.quarantined:
                z.holder = None

    def clear(self, name):                  # 위치 재확인 또는 운영자 확인 후에만
        self.zones[name] = Zone()

older 검사 때문에 먼저 온 요청이 원하는 구역은 나중 요청이 새치기하지 못한다. 기아와 순환 대기는 사라지지만 뒤 로봇이 빈 구역 앞에서 기다리는 비용을 낸다. 처리량이 급하면 이 검사를 일정 시간 이상 기다린 요청에만 적용해 완화한다. 운영에 올릴 때는 상태를 영속화하고(재시작 후 보유자 복원), 구역별 대기 시간 분포와 격리 횟수를 지표로 남긴다.

데드락은 버그가 아니라 자원 할당의 구조적 귀결이다

Coffman·Elphick·Shoshani 가 1971년 ACM Computing Surveys 3(2) "System Deadlocks" 에서 정리한 4조건은 로봇 교통에 그대로 대입된다. 다만 OS 와 결정적으로 다른 점이 하나 있다. 프로세스는 자원을 0개 쥔 채 기다릴 수 있지만, 로봇은 자기가 서 있는 셀을 절대 놓을 수 없다. 그래서 네 조건 중 둘은 물리 법칙이고, 설계로 건드릴 수 있는 것은 나머지 둘뿐이다.

비선점은 프로토콜에 명문화돼 있다. VDA 5050 3.0.0(2026-03-19 릴리스) 은 경로를 이미 해제된 base 와 아직 해제되지 않은 horizon 으로 나누고, MQTT 가 비동기이고 무선이 불안정하므로 base 는 변경할 수 없으며 플릿 컨트롤은 base 가 이미 실행됐다고 가정해야 한다고 적는다. 주문 취소 절차도 같은 이유로 "신뢰할 수 없다"고 못 박는다. 같은 문서는 범위에서 교통 관리 로직(라우팅·우선순위·데드락 해소 알고리즘)을 명시적으로 제외하면서도, 플릿 컨트롤의 최소 기능 목록에는 "blockage(데드락)의 탐지와 해소"를 넣어 두었다. 요컨대 표준은 인터페이스만 주고, 데드락은 전적으로 당신의 컨트롤러 몫이다.

탐지 — wait-for graph 와 그 사각지대

노드는 로봇, 간선 i→j 는 "i 가 요청한 자원을 j 가 쥐고 있다"이다.

• 복잡도: 로봇이 한 번에 다음 자원 하나만 기다리면 out-degree ≤ 1 인 함수형 그래프라 포인터를 따라가는 것만으로 O(N) 에 끝난다. 풋프린트가 커서 여러 셀을 동시에 요청하면 일반 그래프가 되므로 DFS/SCC 로 O(V+E).
• 사이클 = 데드락은 용량 1 자원에서만 필요충분이다. 2대가 들어가는 버퍼 존은 사이클이 보여도 빠져나갈 수 있으니 그래프 축약으로 확인해야 한다.
• 타임아웃 탐지는 오탐의 원천이다. 적재 작업 대기와 교통 대기를 구분하지 못한다. 로봇 상태에 대기 사유(자원 id)를 싣고 그래프로 판정하라.
• 사각지대 — 안전하지 않은 상태(unsafe state): 단일차선 복도에 양끝에서 동시에 들어간 두 로봇은, 가운데서 마주칠 때까지 wait-for 간선이 하나도 없다. 사이클이 잡히는 순간에는 이미 후진 말고는 답이 없다. 탐지는 복구의 방아쇠일 뿐 회피를 대신하지 못한다.

계획 단계의 탐지도 있다(학술). Hönig 외(IEEE RA-L 2019)의 Action Dependency Graph 는 MAPF 계획을 행동 간 선후관계 그래프로 바꾸는데(구성 O(R²T²), R=로봇 수, T=최장 계획 길이), 2×2 격자에서 4대가 동시에 회전하는 계획처럼 정밀한 동기 실행 없이는 안전하게 실행할 수 없는 계획이 ADG 의 사이클로 드러난다. 이 논문은 50대·선반 600개·스테이션 8개 시뮬레이션에서 평균 15초 걸리는 재계획을 실행과 겹치게 돌리면서 충돌 0건을, 실로봇 6대를 섞은 12대 혼합현실 실험에서도 충돌 0건을 보고했다. 실무 번역: 플래너가 낸 계획을 수락하기 전에 선후관계 그래프의 무사이클을 검사하라.

현장(OR) 쪽에서는 Lehmann·Grunow·Günther(OR Spectrum 28, 2006)가 자동화 컨테이너 터미널에서 AGV 가 항상 크레인이라는 2차 자원을 필요로 하고 인터페이스에 버퍼가 없어 데드락 피해가 크다는 점을 짚고, 탐지법 2가지(터미널의 행렬 표현, 자원 요청 직접 추적)와 해소 절차 3가지(작업 순서 변경 또는 대체 자원 재할당)를 제시했다. 교통 자원만이 아니라 도킹·리프트·충전기까지 같은 그래프에 넣어야 한다는 뜻이다.

회피 — 세 계열

1) 자원 전역 순서(순환 대기 제거). 모든 자원에 전순서를 주고 오름차순으로만 획득한다. 경로가 획득 순서를 정하는 교통에는 그대로 못 쓰고, 두 형태로 변형된다. (a) 일방통행화 — VDA 5050 3.0 의 DIRECTED/BIDIRECTED 존. 단, 링 전체가 차면 일방통행도 멈추므로 n칸 링에는 n−1대까지만 넣는 용량 규칙이 짝으로 필요하다. (b) 복수 존 일괄 잠금 — VDA 5050 3.0 은 둘 이상의 RELEASE 존이 덮는 영역에 들어가려면 필요한 존 전부의 승인을 받은 뒤 진입하라고 규정한다. 점유 대기 제거를 프로토콜로 표현한 것이다.

2) 사이클 진입 전 예약. 단일차선 복도·교차로 박스를 원자 자원으로 묶고, 출구 너머 대피 가능한 셀까지 확보한 뒤에만 진입시킨다("don't block the box"). VDA 5050 에서는 base 의 마지막 노드(decision point)를 임계 구간 한가운데 두지 않는 것으로 구현된다. Open-RMF 의 mutex group(2023-12-29 sync 릴리스에 포함)은 lane·vertex 묶음을 한 번에 한 로봇만 잠그게 하는 같은 계열의 장치다.

3) banker 류 안전 상태 검사. 허가 후 상태에서 "누군가는 남은 경로를 끝까지 갈 수 있고, 그 반납으로 다음 로봇이 풀리는" 순서가 존재하는지 본다. 충분조건이라 안전한 상태도 일부 거절하지만(처리량 손실), 다항 시간이다. 아래 구현은 검사 1회 O(N²·L), 틱당 후보마다 돌리면 O(N³·L) — N=50, L=10 이면 틱당 10⁶ 규모 집합 연산이다(필자 계산). 로봇은 완주해도 사라지지 않는다는 점을 모델에 넣어야 한다. 목적지가 남의 경로 위에 있으면 영구 봉쇄다. Hönig 외가 완전성·활성(liveness) 보장의 전제로 든 well-formed infrastructure(정차 지점이 다른 로봇의 이동을 막지 않는다)가 바로 이 조건이다.

학술 보장의 적용 범위를 맵 설계 기준으로 읽어라. PIBT(Okumura 외, IJCAI 2019/AIJ 2022)는 "인접한 모든 노드 쌍이 단순 사이클에 속하는 그래프(예: biconnected)"에서 에이전트 수와 무관하게 전원의 유한 시간 내 도달을 증명했고, 타임스텝당 O(|A|·(Δ(G)+F+log|A|)) 이다. 뒤집으면 막다른 통로와 트리형 단일차선에는 보장이 없다 — 그 구간은 2)의 구간 예약으로 덮어야 한다. Open-RMF 는 스케줄 DB 로 예방하고 충돌 예고 시 협상으로 해소하는데, 공식 문서는 경로만 보고하는 Read Only 플릿이 한 공유 공간에 둘 이상이면 데드락 회피가 "거의 불가능"하다고 경고한다. traffic light 모드는 moderator 가 기본 조건 충족 시 영구 데드락이 없음을 보장한다고 하지만, 도입 PR 자체가 full control 플릿과 섞을 때 드문 데드락을 known issue 로 적어 두었다. 보장은 제어 수준이 균질할 때만 성립한다.

복구 — 비용이 싼 순서로

1. 재계획: 사이클 중 한 대만. 전원이 동시에 재계획하면 같은 우회로로 몰려 라이브락이 된다.
2. 양보 포켓 이동: 가장 가까운 대피 셀로. 포켓 경로도 예약 대상이다.
3. 후진: 비선점을 "자발적 반납"으로 우회한다. 기종·적재 상태가 후진을 허용하는지 먼저 확인.
4. 우선순위 승격: 희생자는 (되돌림 비용, robot_id) 최소로 고른다.
5. 사람 호출: 시한 내 미해결 시.

VDA 5050 제약상 복구 명령은 base 회수가 아니라 포켓으로 가는 새 order update 여야 하고, 취소는 상태 메시지로 확인될 때까지 실행된 것으로 간주한다. 3.0 에서 선점에 가장 가까운 수단은 RELEASE 존 승인의 leaseExpiry/REVOKED 와 존 정의의 releaseLossBehavior 다.

라이브락·기아·결정론적 타이브레이크

라이브락(Ashcroft, 1975)은 상태는 계속 바뀌는데 아무도 전진하지 못하는 경우다. 반응형 회피가 대표적이어서, Liu 외(Robotica 44(4), 2026)는 로봇이 대칭으로 배치되면 ORCA 가 합리적인 회피 속도를 내지 못해 멈춘다고 보고한다. 처방은 대칭을 깨는 것이다.

• 에이징: PIBT 의 규칙이 모범이다. 목표에 도달하지 못한 에이전트의 우선순위를 매 스텝 올리고, 도달하면 에이전트마다 서로 다른 ε∈[0,1) 로 초기화해 우선순위가 항상 유일하게 한다. 고정 우선순위는 기아를, 동률은 라이브락을 만든다.
• 전순서 키: (−에이징된 우선순위, 요청 논리시각, robot_id). 벽시계 비교·난수·dict 순회 순서·부동소수 동률은 금지다. 이중화된 컨트롤러가 같은 결론을 내고 포스트모템을 리플레이하려면 필수다.
• 히스테리시스: 양보 결정은 일정 시간 유지해 핑퐁을 막는다.

검증 가능한 규칙으로 만들기

규칙을 시계·난수·I/O 없는 순수 함수 decide(state) → grants 로 두고 불변식을 테스트로 고정한다. (I1) 상호배제 (I2) 허가 후 wait-for graph 무사이클 (I3) 허가 후에도 안전 상태 (I4) 입력 순열 불변 (I5) 에이징에 의한 유한 대기.

from dataclasses import dataclass, replace

@dataclass(frozen=True)
class Req:
    robot: str          # 정규화된 id — 최후의 타이브레이크
    holds: frozenset    # 지금 점유한 임계 자원
    wants: tuple        # 남은 경로의 임계 자원 시퀀스
    prio: int = 0
    waited: int = 0     # 대기 틱(에이징)
    seq: int = 0        # 요청 논리시각(벽시계 금지)

def order_key(r, alpha=1, cap=1000):
    return (-(r.prio + min(alpha * r.waited, cap)), r.seq, r.robot)

def find_cycle(reqs):                      # out-degree<=1 → O(N)
    owner = {res: r.robot for r in reqs for res in r.holds}
    nxt = {r.robot: owner.get(r.wants[0]) for r in reqs
           if r.wants and owner.get(r.wants[0]) != r.robot}
    done = set()
    for start in sorted(nxt):
        path, pos, cur = [], {}, start
        while cur is not None and cur not in done and cur not in pos:
            pos[cur] = len(path); path.append(cur); cur = nxt.get(cur)
        if cur in pos:
            return path[pos[cur]:]
        done.update(path)
    return None

def is_safe(reqs):                         # banker 류 충분조건
    held = {r.robot: set(r.holds) for r in reqs}
    todo = sorted(reqs, key=order_key)
    while todo:
        for r in todo:
            blocked = set().union(*(held[o] for o in held if o != r.robot))
            if not blocked & set(r.wants):
                if r.wants:                # 완주해도 마지막 자원은 계속 쥔다
                    held[r.robot] = {r.wants[-1]}
                todo.remove(r)
                break
        else:
            return False
    return True

def decide(reqs, check=True):
    state, grants = {r.robot: r for r in reqs}, []
    for r in sorted(reqs, key=order_key):
        if not r.wants:
            continue
        res = r.wants[0]
        if any(res in o.holds for o in state.values() if o.robot != r.robot):
            continue
        trial = dict(state)
        trial[r.robot] = replace(r, holds=r.holds | {res},
                                 wants=r.wants[1:] or (res,))
        if not check or is_safe(list(trial.values())):
            state = trial
            grants.append((r.robot, res))
    return grants

이 코드를 3칸 단일차선 복도의 양끝 진입 시나리오에 돌리면 check=False 에서는 find_cycle 이 ['amr-01', 'amr-02'] 를 잡고, check=True 에서는 한 대가 입구에서 기다렸다가 둘 다 완주한다. 무작위 300개 시나리오(로봇 2~4대, 8칸)의 모든 입력 순열에서 decide 결과가 같았고, 안전 상태에서 출발한 허가 결과는 전부 안전·무사이클이었다(2026-09-19 실행).

체크리스트

• 가드를 끈 변이(check=False)에서 테스트가 실제로 실패하는지 확인했는가 — 실패하지 않는 가드 테스트는 장식이다.
• 소형 맵(로봇 3~4대, 셀 10개 안팎)은 전수 상태 탐색으로, 그 이상은 속성 기반 테스트와 현장 로그 리플레이로 나눴는가.
• 도킹·리프트·충전기·문이 교통 자원과 같은 wait-for graph 에 들어 있는가.
• decision point 가 임계 구간 밖(포켓·다차선)에만 놓이는가.
• 제어 수준이 다른 플릿이 섞이는 구역에 별도의 구간 잠금이 있는가.

표준은 교통 규칙이 아니라, 교통 규칙을 꽂을 자리다

먼저 기대치를 맞추자. VDA 5050 3.0.0 본문 2장(Scope)은 다루지 않는 항목으로 "Traffic Management Logic — routing, prioritization, congestion handling, or deadlock resolution" 을 명시한다. 안전 요구사항과 사이버보안도 범위 밖이다. 같은 문서 5.3절은 "데드락 탐지·해소"와 "버퍼 경로·대기 위치"를 플릿 컨트롤의 기능으로 적어 둔다. 즉 표준은 누가 먼저 가는지를 정하지 않는다. 그 결정을 로봇에게 전달하는 훅(hook) 만 정한다. 이 절은 그 훅이 정확히 무엇이고, 어디서 끊기는지를 본다(2026년 9월 기준).

VDA 5050 — order / state / instantActions

전송은 MQTT(최소 3.1.1) + JSON, 권장 토픽은 vda5050/v3/{manufacturer}/{serialNumber}/order 형태다. order·state·instantActions는 QoS 0, connection만 QoS 1(last will)이다. 교통 제어에 쓰이는 필수 토픽은 셋이다.

base / horizon 의 규칙

• 노드·엣지마다 released 불리언이 있다. released 집합이 base, 나머지가 horizon, base의 마지막 노드가 decision point 다. base가 늘어나지 않으면 로봇은 decision point에서 반드시 정지한다.
• 엣지는 양 끝 노드가 모두 released일 때만 released가 될 수 있고, unreleased 엣지 뒤에는 released가 올 수 없다.
• base는 바꿀 수 없다. 스펙은 MQTT가 비동기이고 무선이 불안정하므로 "플릿 컨트롤은 base가 이미 실행됐다고 가정해야 한다"고 쓴다. cancelOrder 도 같은 이유로 "unreliable"로 취급된다. 바꿀 수 있는 것은 horizon뿐이다.
• 갱신은 같은 orderId에 orderUpdateId를 올리고, 첫 노드를 이전 base의 마지막 노드(stitching node)로 맞춰 보낸다.
• state는 이벤트 발생 시 + 최소 30초마다 발행된다. 로봇은 base가 바닥나 감속이 필요해지면 newBaseRequest=true로 알린다.

교차로 제어는 이 위에 얹힌다. 공식 저장소 Discussion #110에서 메인테이너는 "VDA 5050 is not a recommendation for implementing traffic management, but rather a communication standard"라고 답했고, 방법으로는 교차로 앞 노드까지만 release 하고 비면 다음 구간을 푸는 방식을, 순서 규칙(우측 우선·선착순)은 "마스터 컨트롤 구현 몫"이라고 정리했다.

핵심 로직: 자원 단위 release 게이트

base가 비가역이라는 점 때문에 실무 규칙 하나가 강제된다. decision point를 교차로·좁은 통로 안에 두지 않는다. 자원을 통째로 잡을 수 있을 때만 그 너머의 빈 노드까지 한 번에 푼다.

def extend_base(route, k, robot, locks, lookahead=4):
    """route[j] = (node_id, resource_id | None), k = 현재 decision point 인덱스.
    반환 m: route[k..m] 을 released=True 로 내보내도 되는 마지막 인덱스."""
    m, j, taken = k, k, []
    while j + 1 < len(route):
        res = route[j + 1][1]
        if res is not None:
            if locks.get(res, robot) != robot:
                break                          # 남이 점유 중 → 자원 앞에서 끊는다
            if res not in locks:
                locks[res] = robot
                taken.append(res)
        j += 1
        if res is None or j == len(route) - 1:  # 자원 '안'은 decision point 가 될 수 없다
            m = j
            if m - k >= lookahead:
                break
    for r in taken:                            # 끝까지 통과시키지 못한 자원은 즉시 반납
        if all(route[x][1] != r for x in range(k, m + 1)):
            del locks[r]
    return m

잠금 해제는 state.lastNodeSequenceId가 자원의 마지막 노드를 지난 것을 확인한 뒤에만 한다(QoS 0이므로 "보냈다"는 근거가 못 된다). 튜닝 변수는 lookahead 하나로 수렴한다. 짧으면 decision point마다 감속·정지가 생기고, 길면 되돌릴 수 없는 허가가 쌓여 재경로 여지가 사라진다. 그리고 이 게이트는 상호배제만 보장한다. 두 로봇이 서로의 다음 자원을 기다리는 순환 대기는 그대로 남으며, 그 해소는 표준 밖이다.

버전 변화 (2026년 9월 기준)

3.0.0이 교통 제어에 더한 훅은 세 가지다.

• Zone: BLOCKED, RELEASE, COORDINATED_REPLANNING, LINE_GUIDED, SPEED_LIMIT, ACTION, PRIORITY/PENALTY, DIRECTED/BIDIRECTED. 이 중 RELEASE는 표준화된 뮤텍스 + 임대(lease) 다. 로봇이 state.zoneRequests에 ACCESS 요청을 올리면 플릿 컨트롤이 responses 토픽으로 GRANTED/QUEUED/REJECTED/REVOKED를 돌려주고, leaseExpiry로 유효 시각을 건다. 응답이 제때 안 오면 진입 금지이고, 구역 안에서 허가를 잃으면 zone 정의의 releaseLossBehavior(STOP/CONTINUE/EVACUATE)를 따른다. COORDINATED_REPLANNING에서는 로봇이 후보 궤적을 NURBS로 여러 개 제안하고 플릿 컨트롤이 승인한다.
• 경로 공유: 자유 주행 로봇은 plannedPath(NURBS, 최소한 현재 base를 덮어야 함)와 intermediatePath(웨이포인트별 ETA가 붙은 폴리라인)를 매 state에 실어야 한다. 시공간 충돌 검사를 할 입력이 처음으로 표준에 들어왔다.
• corridor 승인: releaseRequired=true면 로봇은 edgeRequests로 승인을 받은 뒤에만 궤적을 벗어날 수 있다.

주의점도 있다. 3.0은 파라미터 이름을 대거 바꾼 breaking 릴리스이고(타임스탬프도 1/100 s → 1/1000 s), 토픽의 majorVersion이 v3로 갈린다. zone은 선택 기능이라 로봇이 factsheet의 supportedZones에 적은 타입만 믿을 수 있다.

Open-RMF — 스케줄, 협상, 자원 중재

VDA 5050이 "마스터 1개 ↔ 로봇 N대"의 선이라면, Open-RMF는 벤더별 플릿 매니저 여러 개를 묶는 층이다. 공식 문서는 설계 이유를 이렇게 적는다. 벤더는 컴퓨팅 자원 공유를 책임 문제로 꺼리므로 교통 관리가 여러 머신에 분산된 채 동작해야 한다.

• Traffic schedule: 시설 내 모든 로봇의 의도된 궤적을 담는 중앙 DB. 충돌의 정의는 한 로봇의 footprint_radius가 다른 로봇의 vicinity_radius에 들어가도록 예정된 경우다.
• 예방: 각 플릿 어댑터가 스케줄을 보고 시간 확장 A*(rmf_traffic의 Planner)로 남의 궤적을 피해 계획한다. 문서상 이 플래너는 그리드를 따르는 AGV형 로봇용이다.
• 협상: 그래도 충돌이 잡히면 conflict notice가 나가고, 참가자들이 "누구를 수용(accommodate)한 제안인가"로 키가 붙는 테이블 트리에 일정을 제출한다. 수용 불가면 대안(rollout)을 붙여 reject, 풀 수 없으면 forfeit 한다. 승자는 통합자가 배치하는 제3자 심판(Evaluator)이 고른다. 기본 구현 QuickestFinishEvaluator는 전체 지연 합 최소이며 우선순위 가중이 없다. 우선순위가 필요하면 Evaluator를 교체한다. 테이블 키가 참가자의 순서열이므로 동시 참가자가 늘면 탐색해야 할 테이블이 순열 규모로 불어나는 구조다(헤더 정의에서 도출한 해석이며, 공식 벤치마크 수치는 확인하지 못했다).
• 자원 중재: 문은 /door_states·/door_requests·/adapter_door_requests, 엘리베이터는 같은 패턴의 lift_* 토픽을 쓰고, 그 사이의 door/lift supervisor가 로봇 작업을 방해할 요청을 걸러 낸다. 2024-01 릴리스는 lane·vertex에 거는 mutex group(한 번에 한 로봇만 잠금)을 넣었고, 엘리베이터 사용 중인 로봇은 협상에 불참(stubborn)해 남들이 비키게 했다. 2024-08 Jazzy 릴리스 노트는 mutex group 등으로 좁은 공간의 데드락이 줄었다고 적는다.

플릿 어댑터는 통제 수준으로 나뉜다. Full Control(경로까지 RMF가 지시), Traffic Light(일시정지/재개만), Read Only(상태만 수신), No Interface(호환 불가). 문서의 단서가 중요하다. 공유 공간에 Read Only 플릿은 최대 하나이며, 둘 이상이면 데드락 회피가 "거의 불가능"하다고 명시한다.

차세대 설계(2025-06 제안, 2026-04 로드맵)는 Dispatching / Reservation / Planning / Execution 4계층으로 쪼개고 VDA 5050·MassRobotics·Nav2 정합을 목표로 든다. 로드맵에서 Traffic Negotiation은 6단계 중 마지막이며 일정은 확약하지 않는다.

MassRobotics AMR Interop

가장 얇은 표준이다. v1.0(2021-05-17 공개)은 WebSocket(RFC 6455) + JSON 위에 identityReport와 statusReport 두 메시지만 정의한다. statusReport 필수 필드는 uuid·timestamp·operationalState·location이고, 선택 필드 path는 향후 약 10초, 최대 10점, destinations도 최대 10개다. 상태는 변경 시 전송하되 1초에 한 번을 넘지 않는다(최소 주기 조항은 원문이 "sixty (30) seconds"로 표기가 어긋나 있다). 스키마에 명령 메시지가 없다. 즉 조율이 아니라 인지(awareness) 계층이다. 임무 통신을 다루는 2.0은 2022년에 예고됐지만, 2026년 9월 기준 공개 저장소의 릴리스는 1.0뿐이다.

이기종 플릿에서 해결되는 것과 남는 것

공개 실증 규모도 참고할 만하다. VDA 5050 상호운용 시연인 AGV Mesh-Up에서 하나의 마스터가 동시에 제어한 로봇은 2021년 6대, 2022년 7대, 2023년 9대였다(SYNAOS 발표). 표준 호환은 입증됐지만, 대규모 혼잡에서의 교통 성능을 말해 주는 수치는 아니다.

의사결정 기준

1. 단일 마스터를 강제할 수 있는가? 가능하면 VDA 5050으로 전 로봇을 붙이고, 교통 로직은 마스터에 구현한다. 가장 단순하고 예약 알고리즘을 그대로 쓸 수 있다.
2. 벤더가 자기 플릿 매니저를 고집하는가? 플릿 간 계층(Open-RMF식 스케줄 + mutex/zone)이 필요하다. 최소한 pause/resume(Traffic Light) 권한은 계약으로 확보한다.
3. 위치만 주는 플릿인가? Read Only 하나까지만 허용하고, 나머지는 물리적으로 구역을 분리한다.

RFP·인수 시험 체크리스트: ① 지원 VDA 5050 메이저 버전과 supportedZones ② newBaseRequest 발행 여부와 minimumStateInterval ③ decision point 정지 시 감속 프로파일(lookahead 산정 근거) ④ cancelOrder·startPause 후 실제 정지 거리 ⑤ 연결 끊김 시 "마지막 released 노드까지 주행" 동작 확인 ⑥ RELEASE zone의 leaseExpiry 만료 시 거동.

"중앙이 없다"의 세 가지 수준

분산 협상은 한 덩어리가 아니다. 로봇이 무엇을 알고 결정하는가에 따라 보장이 완전히 달라지므로, 설계 전에 어느 수준을 말하는지부터 고정한다.

핵심은 안전(safety)과 진행(liveness)을 따로 세는 것이다. L0는 안전만 주고, 진행은 L1 이상에서만 설계할 수 있다. 아래에서 "학술"은 논문에서 증명·시뮬레이션된 결과, "현장"은 AGV 교통 규칙 실무를 뜻한다.

RVO/ORCA — 통신 없는 상호 회피와 그 천장

학술. ORCA(van den Berg 외, ISRR 2011)는 각 에이전트가 쌍별 충돌 회피 책임을 절반씩 진다고 가정하고, 이웃마다 속도 공간의 반평면 제약을 만든 뒤 선호 속도에 가장 가까운 속도를 저차원 선형계획으로 고른다. 통신이 필요 없고, 저자들은 밀집 시나리오에서 수천 에이전트의 회피 동작을 수 밀리초에 계산한다고 보고한다. 계산량은 문제가 아니다. 문제는 세 군데서 난다.

• 대칭. 마주 본 두 로봇이 같은 규칙으로 같은 양만큼 피하면 속도 0의 평형에 갇힌다. Robotica 44권 4호(2026)의 Liu 외 논문은 로봇이 대칭으로 배치될 때 ORCA가 합리적인 회피 속도를 못 내 멈춘다고 정리했고, Grover·Liu·Sycara(IJRR)는 CBF 기반 반응 제어에서 데드락이 로봇에 걸리는 "힘의 평형"이며 안전 집합의 경계 위에 있음을 보였다. 데드락은 버그가 아니라 안전을 지키려다 생기는 평형점이다.
• 좁은 통로. 두 대가 교행할 수 없는 폭에서는 제약을 모두 만족하면서 전진하는 속도가 존재하지 않는다. 비홀로노믹 제약을 유효 반경 확대로 흡수하는 변형(ORCA-DD 계열)은 여기서 더 불리하다.
• 이기성. Dergachev·Yakovlev(CASE 2021)는 좁은 통로·밀폐 공간의 데드락 원인을 에이전트의 이기적 행동으로 짚고, 데드락에 빠진 소그룹만 국소 MAPF(Push and Rotate, ECBS)로 풀게 해 일부 시나리오의 성공률을 15%에서 99%로 올렸다.

의사결정 기준. 두 대가 교행할 수 없는 구간은 회피 문제가 아니라 상호배제 문제다. 그 구간은 ORCA 영역에서 빼 예약 자원(zone)으로 선언하고, ORCA는 교행 가능한 개활 구간의 마지막 방어선으로만 쓴다. 속도 0이 N초 이어지고 상대도 정지해 있으면 데드락으로 판정해 L1/L2로 올린다.

우선권 규칙 — 현장이 실제로 쓰는 것

현장. AGV 교통 규칙은 대부분 아래 다섯 가지의 조합이다.

규칙을 나열하는 것보다 중요한 건 전순서(total order) 로 만드는 일이다. 같은 입력을 받은 모든 로봇이 같은 승자를 계산해야 하고, 마지막 키는 반드시 전역 유일 ID여야 한다. VanMiddlesworth·Dresner·Stone(AAMAS 2008)의 V2V 교차로 프로토콜이 정확히 이 구조다 — 정지선에 선 차량의 Claim이 주행 중인 차량의 Claim을 지배하고, 그 안에서 ① 둘 다 주행 중이면 이탈 시각이 이른 쪽, ② 둘 다 정지해 있으면 오른쪽, ③ 그다음은 직진, ④ 그래도 안 갈리면(오른쪽 순환 포함) 가장 낮은 차량번호. 이를 AMR용으로 옮기면 다음과 같다.

from dataclasses import dataclass

@dataclass(frozen=True)
class Claim:
    robot_id: str    # 전역 유일 — 최후의 타이브레이커
    zone: str        # 교차로·통로 자원 id
    t_in: float      # 진입 예정 시각
    t_out: float     # 이탈 보장 시각
    stopped: bool    # 정지선에 실제로 서 있는가
    loaded: bool     # 화물 적재 여부
    rx_time: float = 0.0   # 수신 시각(수신 측 단조시계)

def conflicts(a, b):
    return a.zone == b.zone and a.t_in < b.t_out and b.t_in < a.t_out

def rank(c):
    # 작을수록 우선. 같은 입력이면 모든 로봇이 같은 전순서를 계산해야 한다.
    return (not c.stopped, not c.loaded, c.t_in, c.robot_id)

def may_enter(mine, heard, now, first_tx, zone_clear, ttl=1.0, t_p=0.4):
    if now - first_tx < t_p:                # 최소 T_p 동안 알린 뒤에만 진입
        return False, "announcing"
    for c in heard:
        if not conflicts(mine, c):
            continue
        if now - c.rx_time > ttl:           # 소식이 끊긴 상대
            if not zone_clear():            # = 안에 멈춰 있을 수 있는 상대
                return False, "hold+escalate"
            continue
        if rank(c) < rank(mine):
            return False, "yield:" + c.robot_id
    return True, "go"

완전히 대칭인 두 Claim(같은 시각·같은 상태)을 넣어도 한 대만 go가 나오는 것이 이 코드의 요점이다. t_p=0.4는 위 논문의 구현값(최소 0.4초 방송 후 진입)을 그대로 옮긴 것이고, ttl은 아래 지연 예산으로 정한다.

토큰·경매·합의 — L2 기법 비교

실무 해석: TP·PIBT의 증명은 맵 조건에 걸려 있다. 맵에 막다른 통로나 대기 위치가 남의 경로를 끊는 지점이 있으면 보장이 사라진다 — 알고리즘을 고르기 전에 그래프부터 검사한다. 2025년(AAAI)의 MAPF-GPT처럼 통신·휴리스틱 없이 모방학습만으로 분산 행동을 내는 계열도 나왔지만, 증명된 진행 보장은 없으므로 2026년 9월 현재로선 L0 대체재이지 L2 대체재가 아니다.

통신이 끊기거나 늦을 때의 기본 동작

1. 침묵은 양보가 아니다. 갱신이 끊긴 상대는 "안에 멈춰 있을 수 있는 상대"다. 위 코드처럼 TTL 초과 시 구간이 비었음을 자기 센서로 확인하지 못하면 대기하고 감독에 올린다.
2. 이미 받은 허가가 어디서 끝나는지 설계한다. VDA 5050 3.0.0(GitHub 릴리스 2026-03-18)은 로봇이 브로커와 끊기면 "주문 정보를 유지하고 마지막 released 노드까지 수행"한다고 규정한다. 즉 base는 통신 없이 끝까지 가도 안전한 만큼만 풀어야 한다. base가 교차로 안에서 끝나면 단절 시 로봇이 교차로 한가운데 선다 — 교차로 앞 또는 완전히 빠져나간 뒤에서 끊는다. 같은 규격의 newBaseRequest는 base 끝이 가까운데 새 base가 없으면 로봇이 감속한다는 신호다.
3. 연결 감시와 협상 채널을 섞지 않는다. 같은 규격에서 state는 "이벤트 발생 시 또는 최소 30초마다"이고, connection 토픽(Last Will CONNECTION_BROKEN)은 로봇 건강 확인용으로 쓰지 말라고 명시한다. 30초 주기는 교차로 협상에 쓸 수 없다. 협상용 하트비트는 따로 둔다.
4. 여러 구역은 전부 허가받고 들어간다. 3.0.0의 RELEASE 구역은 로봇이 state의 zoneRequests(ACCESS)로 요청하고 responses 토픽으로 허가받으며, 겹친 구역은 모두 승인된 뒤 진입한다 — 부분 점유 후 대기(hold-and-wait)를 끊는 규칙이다.
5. 지연 예산을 숫자로 적는다. 계산 예시: 1.5 m/s, 감속 1.0 m/s²면 제동거리 v²/2a ≈ 1.1 m. 하트비트 100 ms·TTL 1 s라면 상대가 사라졌음을 알 때까지 최대 1.5 m를 더 간다. 정지선은 구간 경계에서 최소 (TTL 전진거리 + 제동거리) 앞에 둔다.

위 V2V 논문은 메시지를 반복 방송하므로 손실이 지연을 늘릴 뿐 안전을 해치지 않는다고 설계했지만, 통신 장애 내성 시험은 향후 과제로 남겼다. 프로토콜 계층의 안전은 가정이지 증명이 아니다 — 최종 방어선은 통신과 무관한 온보드 센서 정지여야 한다.

차량 V2X 교차로 연구에서 빌려올 것

• 대화 없는 2메시지(Claim/Cancel). 애드혹 망에서는 요청-응답을 믿을 수 없다. 최신 Claim 하나만 보면 되도록 상태 전체를 매번 싣는다.
• 단조 증가 message_id. 재방송과 새 Claim을 구분해 stale 판별을 가능하게 한다.
• lurk distance. 너무 일찍 Claim하면 남의 Claim에 지배당할 예약만 쌓인다. 논문은 차량 기준 75 m(통신 150 m·지연 20 ms 미만 가정)를 썼다. AMR에는 속도 비례로 환산한다.
• 정지 플래그와 "안에 있는 Claim은 지배당하지 않는다".
• 관리형/비관리형 분할. 같은 논문에서 V2V 방식은 0.3대/초 미만이면 대부분 감속 없이 통과했고(4-way stop 기본 지연 약 3초, 신호등 약 18초), stop은 0.35대/초, V2V는 약 0.7대/초에서 한계였으며 그 이상은 관리형을 권했다. 중앙 예약(Dresner·Stone, AAMAS 2004)은 시뮬레이션의 지연 지표에서 신호등보다 200~300배 나은 성능을 보고했다. 바쁜 교차로는 중앙 예약, 한산한 교차로는 로컬 규칙이 결론이다.
• 서명. 위조 Claim은 곧 통행권 탈취다.

수치는 차량·시뮬레이션 결과다. 비율과 구조만 가져오고 임계값은 자기 현장에서 다시 잰다.

하이브리드 — 중앙 감독 + 엣지 자율

공개 시스템은 이미 하이브리드다. Open-RMF는 의도 궤적을 모으는 중앙 스케줄 DB가 충돌을 감지하면, 플릿 어댑터끼리 선호 경로를 제안·수정하는 협상을 벌이고 통합 사업자가 배치한 제3자 judge가 채택안을 고른다. 제어 수준은 Full Control / Traffic Light(일시정지·재개만) / Read Only / No Interface로 나뉘며, 문서는 공유 공간당 Read Only 플릿을 최대 1개로 제한하고 No Interface는 데드락을 부른다고 경고한다.

원칙은 하나다. 허가를 좁히는 명령은 즉시, 넓히는 명령은 갱신으로만. 중앙이 죽어도 엣지는 안전하고, 중앙은 엣지가 못 푸는 진행 문제만 푼다.

도입 체크리스트

• [ ] 교행 불가 구간을 전부 zone으로 선언했는가(ORCA 영역에서 제외)
• [ ] 우선권 키가 전순서이고 마지막 키가 전역 유일 ID인가
• [ ] 완전 대칭 입력에서 한 대만 진입하는지 테스트했는가
• [ ] TTL 초과 상대를 "점유 중"으로 취급하는가
• [ ] base/lease 종점이 교차로·통로 안에 놓이지 않는가
• [ ] 겹친 구역을 일괄 획득하는가
• [ ] 화물 우선·경매에 에이징 또는 system bid가 있는가
• [ ] 맵이 선택한 알고리즘의 전제(biconnected, well-formed)를 만족하는가
• [ ] 협상 하트비트가 30초 state와 분리돼 있는가

협상 계층이 약속하는 것, 약속하지 않는 것

교통 협상(예약·우선권·데드락 해소)이 푸는 문제는 처리량과 생존성(liveness) 이다. "두 대가 부딪히지 않는다"는 그 계층의 산출물이 아니라, 그 아래 계층이 이미 보장하고 있어야 하는 전제다. 이 구분은 설계 취향이 아니라 표준 문서에 적힌 범위 선언이다.

• VDA 5050 3.0.0(GitHub 릴리스 2026-03-18)은 다루지 않는 주제를 명시한다. 이 문서는 기능·운영·시스템 안전 요구사항을 정의하지 않으며 "안전 표준으로 간주하거나 적용해서는 안 된다". 라우팅·우선순위·혼잡 처리·데드락 해소 같은 교통 관리 로직도, 사이버보안 수단도 범위 밖이다. 상태 메시지의 safetyState(activeEmergencyStop, fieldViolation)는 안전 기능의 결과를 보고할 뿐 구현하지 않는다.
• Open-RMF 문서는 트래픽 스케줄을 "의도된 궤적의 중앙 데이터베이스"로, 그 역할을 의도 간 충돌의 식별과 통지로 정의한다. FAQ는 예기치 못한 장애물이나 예측 오류 때문에 "충돌을 완벽히 예방하는 것이 항상 가능하지는 않다"고 적는다.

설계 리뷰에서 쓸 리트머스 시험은 하나다. 플릿 매니저와 브로커를 전부 꺼도 아무도 다치지 않는가. "아니오"라면 안전 기능이 무선 위의 일반 소프트웨어에 올라가 있다는 뜻이고, 그 구조는 어떤 협상 알고리즘으로도 구제되지 않는다.

안전 표준은 책임을 차량에 둔다

ISO 3691-4(무인 산업용 트럭, 2020년 초판 → 현행 2023년판)는 EN 1525를 대체한 C형 표준이다. 벨기에 Sirris의 정리에 따르면 EN ISO 3691-4는 2024년 5월 기계류 지침 2006/42/EC의 조화 표준이 됐다. TÜV Rheinland 백서(2020년판 기준)에서 확인되는 골격은 다음과 같다.

• 4.11절 Table 1이 27개 안전 기능과 각각의 최소 요구 성능수준(PLr, ISO 13849-1)을 나열한다. 인원 감지와 제동 제어는 PLr d, 주차 제동은 PLr b다.
• EN 1525가 "정지시킬 신호를 생성한다"였던 요구는 "정지한 사람과 트럭·화물의 단단한 부분이 접촉하기 전에 정지한다"로 바뀌었다. 감지기만이 아니라 제동까지 포함한 체인 전체가 평가 대상이다.
• 부속서 A는 구역을 operating / operating hazard / restricted / confined 로 나눈다. 백서가 발췌한 Table A.1에서 양측·진행 방향 이격이 500 mm를 넘고 인원 감지가 활성이면 정격 속도가 허용되고, 감지를 뮤트하면 0.3 m/s 와 바닥 표시가 요구된다.
• 표준의 한계도 같은 백서에 적혀 있다. 옆에서 경로로 뛰어드는 사람은 적용 범위 밖이다. 잔여 위험은 통합자와 사용자의 위험성 평가로 넘어간다.

인증을 준비 중이라면 대상 판을 먼저 확인할 것. 2026년 9월 검색 시점에 ISO 카탈로그에는 3691-4의 후속 개정 초안(ISO/DIS)이 올라와 있다.

ANSI/RIA R15.08은 산업용 이동 로봇(IMR)을 A형(부착물 없는 AMR), B형(매니퓰레이터가 아닌 부착물), C형(AMR·AGV + 매니퓰레이터)으로 나눈다. Part 1(2020)은 제조사, Part 2(2023년 10월 9일 발표)는 단일 IMR이나 플릿을 현장에 통합·구성하는 통합자의 요구사항이고, 사용자용 Part 3는 2026년판(R15.08-3-2026)으로 ANSI 목록에 올라 있다. 매니퓰레이터가 없는 AGV는 ANSI/ITSDF B56.5 소관이다.

보호 필드 크기는 물리에서 나온다. SICK의 설명대로 정지 거리는 제동 거리 + 스캐너 응답 시간 동안 간 거리 + 안전 제어기 응답 시간 동안 간 거리이고, 속도가 오르면 필드를 키워야 하므로 엔코더 기반 안전 속도 감시와 필드 전환이 한 묶음이다. 속도·분리 감시도 같은 구조다 — 거리가 줄면 속도를 낮추고 한계에서 보호 정지한다. 입력이 전부 자기 센서라는 점이 핵심이다. 그래서 협상 계층이 보내는 "이 구간 0.5 m/s" 같은 제한은 에티켓이지 안전 기능이 아니다.

협상이 기대는 네 가지 전제

협상 계층은 "모두가 같은 지도 위의 같은 시각을 말하고, 그 말이 제때 위조 없이 도착한다"고 가정한다. 넷 다 현장에서 깨진다.

시계 의존은 설계로 줄일 수 있다. Hönig 외(RA-L 2019)의 Action Dependency Graph는 MAPF 스케줄을 절대 시각이 아니라 "A의 이 동작이 끝나야 B의 저 동작이 시작된다"는 선행 관계로 바꿔 실행한다. 로봇은 위치를 계속 방송하지 않고 동작 완료만 알리면 되고, 동역학 한계가 제각각이어도 충돌 없는 실행이 유지된다. 학술 결과지만 현장 규칙 "앞차가 구간을 비웠다는 통지를 받기 전에는 들어가지 않는다"와 같은 구조다.

전제가 깨질 때의 기본값: 허가는 임대, 침묵은 거절

VDA 5050은 이 원칙을 프로토콜에 박아 두었다. 로봇은 해제(release)된 노드까지만 달린다. 브로커와 끊기면 "마지막 해제 노드까지 주문을 수행"하고, base가 연장되지 않으면 decision point에서 정지한다. 3.0.0의 RELEASE 구역은 허가에 leaseExpiry를 붙이고, 허가가 만료·철회됐을 때의 동작(releaseLossBehavior: STOP / CONTINUE / EVACUATE)을 구역마다 정하게 하며, 미정의 시 기본은 STOP + RELEASE_LOST(CRITICAL) 다. localized=false면 자동 주행을 재개하지 않는다.

여기서 나오는 실무 규칙은 세 가지다.

1. 진입 전에는 보수적으로. 임대 잔여 시간이 교차로를 빠져나갈 때까지를 덮지 못하면 들어가지 않는다.
2. 진입 후에는 비운다. 교차로·방화문·좁은 통로 한가운데의 정지는 그 자체가 위험이자 데드락의 씨앗이다. 그런 구역은 CONTINUE나 EVACUATE로 지정한다. fail-safe는 "어디서든 즉시 정지"가 아니라 "서도 되는 곳에서 정지" 다.
3. 기본값은 HOLD. 검증을 하나라도 통과하지 못한 허가는 없는 허가다.

import hmac, hashlib, json

def canon(o):
    return json.dumps(o, sort_keys=True, separators=(",", ":")).encode()

def gate(msg, st, cfg, key):
    """교차로 진입 허가를 쓸지 판단한다. 하나라도 의심스러우면 HOLD."""
    b = msg["body"]
    mac = hmac.new(key, canon(b), hashlib.sha256).hexdigest()
    if not hmac.compare_digest(mac, msg["mac"]):      return "HOLD", "bad_mac"
    if b["seq"] <= st["last_seq"]:                    return "HOLD", "replay_or_reorder"
    if [b["map_id"], b["map_ver"]] != st["map"]:      return "HOLD", "frame_mismatch"
    if not st["localized"]:                           return "HOLD", "not_localized"
    if st["skew_bound_s"] is None or st["skew_bound_s"] > cfg["max_skew_s"]:
        return "HOLD", "clock_unsynced"
    if st["mono"] - st["last_rx_mono"] > cfg["link_timeout_s"]:
        return "HOLD", "link_stale"              # 경과 시간은 단조 시계로만 잰다
    left = b["lease_expiry_utc"] - st["utc"] - st["skew_bound_s"]
    if left < st["eta_clear_s"] + cfg["margin_s"]:    return "HOLD", "lease_too_short"
    return "PROCEED", "ok"

이 게이트는 안전 기능이 아니다. 통과해도 PL d 체인은 그대로 돌고 있어야 하고, 게이트가 틀려도 결과는 대기 시간이어야 한다. HOLD 사유를 코드로 남기는 이유는 운영 때문이다. lease_too_short가 늘면 임대 길이를, link_stale이 특정 구역에 몰리면 AP 배치를 고친다.

결정론은 디버깅 기능이 아니라 검증 수단이다

협상 로직의 버그는 대개 "그 순간의 메시지 순서"에서만 재현된다. Menard 외(DATE 2020)는 AUTOSAR Adaptive의 브레이크 어시스트 데모를 같은 입력으로 20회 돌려 최저 0.018%, 최고 22.25%, 평균 5.60% 의 오류율을 관측했다. 원인은 알고리즘이 아니라 1칸 버퍼와 주기 콜백 간 위상차, 곧 시작 타이밍이었다. 실행마다 답이 달라지는 시스템은 테스트를 통과해도 통과한 것이 아니다.

def arbitrate(zone, claims, cfg):
    """같은 입력이면 언제 어디서 돌려도 같은 승자. 시계·난수·dict 순서에 기대지 않는다."""
    order = sorted(claims, key=lambda c: (-c["prio"], c["seq"], c["robot"]))
    rec = {"in": hashlib.sha256(canon([zone, order])).hexdigest()[:16],
           "cfg": cfg["version"], "out": order[0]["robot"]}
    return order[0]["robot"], rec

• 순수 함수로 격리한다. 결정 = f(스냅숏, 설정 버전). 네트워크·시계·난수는 함수 밖에서 스냅숏으로 굳힌 뒤 넘긴다.
• 전순서 타이브레이크. 마지막 키는 로봇 ID처럼 절대 같아질 수 없는 값이어야 한다. "먼저 도착한 메시지가 이긴다"는 비결정론이다.
• 입력 해시·설정 버전·결과를 결정마다 기록한다. 사고 조사는 로그를 같은 함수에 다시 넣어 같은 답이 나오는지 확인하는 데서 시작한다. 이 리플레이를 CI에 걸어 두면 리팩터링이 결정을 바꿨는지 즉시 드러난다.
• 부동소수 비교를 경계에 두지 않는다. 거리·시간 임계는 mm·ms 정수로 양자화한 뒤 비교한다.

배포 전 체크리스트

• [ ] 플릿 매니저·브로커를 끈 상태의 교차 주행 시험에서 접촉이 없다(안전 계층 단독 시험).
• [ ] 협상 계층의 속도·구역 제한 가운데 안전 근거로 쓰이는 것이 하나도 없다.
• [ ] 맵 정합 오차와 시계 오차 상한이 측정값으로 있고, 구역 여유와 임대 마진이 그 값에서 도출됐다.
• [ ] 허가 메시지마다 순번·만료·맵 버전이 있고, 브로커는 TLS + 클라이언트별 인증 + 토픽 ACL 이다.
• [ ] 구역마다 허가 상실 시 동작(STOP/CONTINUE/EVACUATE)이 지정돼 있고, 정지 지점은 충돌 구역 밖이다.
• [ ] 결정 로그로 같은 결정을 재생하는 테스트가 CI에 있다.

실기로는 데드락률을 잴 수 없다

데드락은 드문 사건이고, 드문 사건의 비율은 표본 수가 정한다. 통계의 rule of three에 따르면 n번 시행에서 한 번도 안 나왔을 때 발생률의 95% 신뢰 상한은 3/n 이다((1−p)^n = 0.05 에서 유도). 교차로 시험을 실기로 30번 돌려 0건이면 말할 수 있는 것은 "10% 이하"뿐이다. "0.1% 이하"를 말하려면 무사고 3,000회가 필요하다. 로봇 두 대와 작업자 한 명으로 채울 수 있는 숫자가 아니다.

그래서 순서가 뒤집힌다. 비율은 시뮬에서 재고, 실기는 시뮬이 현실과 같은 결정을 내리는지 확인하는 데 쓴다. 분산 DB 쪽의 선례가 FoundationDB다. 클러스터 전체를 단일 스레드 프로세스 안에서 결정론적으로 시뮬레이션하고, 네트워크·머신·데이터센터 수준의 고장(연결 단절, 성능 저하, 재부팅, "죽었다 살아난 머신")을 주입하며, 결정론이 "완벽한 반복 재현"을 가능케 한다고 적는다. 로봇 쪽에서는 Open-RMF 의 slotcar 플러그인이 같은 선택을 했다. 로봇마다 내비게이션 스택을 돌리는 부담을 피하려고 웨이포인트 사이를 "레일처럼" 움직이게 했고, 초점이 로봇 주행이 아니라 이기종 플릿의 교통 관리라고 명시한다. 교통 로직 검증에 물리 엔진은 필요 없다.

헤드리스 결정론 시뮬의 최소 구성

규칙은 다섯 개다.

1. 논리 틱. 벽시계·sleep·스레드를 쓰지 않는다. ROS 2 도 use_sim_time 과 /clock으로 시간을 주입 가능한 값으로 다루며, 실시간보다 빠른 실행이 반복 시스템 테스트에 유용하다고 적는다.
2. 난수원은 하나, 시드로 고정. 요청 도착 순서, 실행 지연, 고장 시각이 모두 여기서 나온다.
3. 결정 로직은 실물 그대로. 시뮬 전용 재구현을 두면 시뮬은 다른 프로그램을 검증한다. 운영 코드의 순수 함수 decide 를 그대로 호출한다.
4. 하네스는 정책을 믿지 않는다. 상호배제 같은 불변식은 하네스가 독립적으로 검사한다.
5. 멈춤에 이름을 붙인다. "타임아웃"이 아니라 deadlock:X>Y, blocked_by_dead:X 로 분류해야 지표가 된다.

import hashlib, json, random
from dataclasses import dataclass

@dataclass
class Robot:
    rid: str
    path: list
    i: int = 0
    wait: int = 0        # 연속 대기 틱
    worst: int = 0
    dies_at: int = -1    # 고장 주입: 이 틱부터 멈추고 점유도 풀지 않는다

def run(robots, decide, seed, slip=0.2, max_ticks=400, stall=40):
    rng = random.Random(seed)                      # 난수원은 하나, 시드로 고정
    owner = {r.path[0]: r.rid for r in robots}
    log, idle, blocked, viol = [], 0, {}, 0
    for t in range(max_ticks):                     # 논리 틱 — 벽시계·sleep 없음
        live = [r for r in robots
                if r.i < len(r.path) - 1 and not 0 <= r.dies_at <= t]
        if not live:
            break
        rng.shuffle(live)                          # 요청 도착 순서 교란
        blocked = decide(live, dict(owner))        # 순수 함수 → {rid: 막는 로봇 | None}
        moved = False
        for r in sorted(live, key=lambda r: r.rid):
            go = blocked[r.rid] is None and rng.random() >= slip  # 실행 지연 주입
            if go and r.path[r.i + 1] in owner:    # 하네스가 상호배제를 독립 검사
                viol += 1; go = False
            if go:
                owner.pop(r.path[r.i]); r.i += 1; r.wait = 0; moved = True
                if r.i < len(r.path) - 1:
                    owner[r.path[r.i]] = r.rid     # 종점은 개별 베이라 점유 안 함
            else:
                r.wait += 1; r.worst = max(r.worst, r.wait)
        log.append([t, sorted(blocked.items(), key=str), sorted(owner.items())])
        idle = 0 if moved else idle + 1
        if idle >= stall:
            break
    done = all(r.i == len(r.path) - 1 or r.dies_at >= 0 and r.rid not in blocked.values()
               for r in robots)
    return {"verdict": "ok" if done else classify(robots, blocked), "violations": viol,
            "ticks": t + 1, "worst_wait": max(r.worst for r in robots),
            "digest": hashlib.sha256(json.dumps(log).encode()).hexdigest()[:12]}

def classify(robots, blocked):                     # 멈춘 이유에 이름을 붙인다
    dead = {r.rid for r in robots if r.dies_at >= 0}
    for start in sorted(blocked):
        seen, cur = [], start
        while cur in blocked and cur not in seen:
            seen.append(cur); cur = blocked[cur]
        if cur in seen:
            return "deadlock:" + ">".join(seen[seen.index(cur):])
        if cur in dead:
            return "blocked_by_dead:" + cur
    return "stall"

정책은 decide(요청들, 점유표) → {로봇: 막는 로봇 | None} 하나로 꽂는다. "다음 노드가 비면 허가"하는 naive 정책과 "통로·교차로 전체를 자원 하나로 묶고 로봇 ID 로 타이브레이크"하는 구역 락 정책을 이 하네스에 넣고 시나리오마다 시드 1,000개를 돌린 결과다(이 글을 위해 만든 장난감 실험이며 현장 수치가 아니다).

사망 시나리오의 ok 48런은 지연 탓에 X 가 통로에 들어가기 전에 죽어 Y 가 그냥 지나간 경우다. 세 가지가 보인다. 첫째, naive 정책도 정면 대면을 1,000번 중 8번은 통과한다. 한 번 돌려 초록이면 증거가 아니다. 둘째, 대칭 교차로의 naive 는 전원 완주하면서 매번 같은 노드를 두 대에 허가했다. 완주 여부만 보는 테스트는 위반을 놓친다. 셋째, 지연을 0 으로 두고 도착 순서만 1,000가지로 섞으면 구역 락의 로그 해시는 1종이다. 입력 순열 불변이 해시 하나로 확인된다. 같은 시드의 재실행은 결과와 해시가 일치한다.

필수 회귀 시나리오 네 가지

마지막 줄이 중요하다. 사망 시나리오의 합격은 "락이 풀렸다"가 아니라 "물리적으로 막혔다고 올바르게 판정했다"이다. 탐지 입력도 시험 대상이다. VDA 5050 3.0.0에서 비정상 단절은 브로커가 Last Will 로 connection 토픽에 CONNECTION_BROKEN 을 내고, state 는 이벤트 발생 시 또는 최소 30초마다 나온다. 시뮬은 "연결은 살아 있는데 진행이 없는" 로봇과 "연결이 끊긴" 로봇을 따로 주입해야 한다.

손으로 짠 네 개 위에는 무작위 탐색을 얹는다. Hypothesis 의 stateful testing은 기본 동작(요청·해제·지연·사망)을 조합해 실패하는 동작 시퀀스를 찾고, 매 스텝 뒤 불변식을 검사하며, 실패 시퀀스를 최소 형태로 줄여 붙여 넣을 수 있는 코드로 내준다. 줄어든 시퀀스는 그대로 다섯 번째 회귀 시나리오가 된다.

지표 — 무엇을 세고 어떻게 보고하나

학술 쪽 관행. RHCR(Li 외, AAAI 2021)은 처리량을 "타임스텝당 방문한 목표 위치의 평균 수"로 정의하고 실험마다 5,000 타임스텝을 돌렸다. 33×46 격자·60대·ECBS 에서 창 길이 w=5 는 처리량 1.72·실행 0.07초, w=10 은 2.02·0.17초, 동적 창은 2.10·0.35초였다. 처리량은 항상 계산 시간과 쌍으로 보고된다. one-shot MAPF 의 표준 목적함수인 makespan·sum-of-costs(Stern 외, SoCS 2019)는 미션이 끝없이 들어오는 플릿에는 맞지 않는다. 빌려올 것은 지표보다 고정된 공개 시나리오 집합이라는 관행이다. Moving AI MAPF 벤치마크는 맵 33개에 맵마다 even 25개·random 25개 시나리오 파일을 둔다.

현장 쪽 관행. 자기 시설의 그래프로 시나리오 집합을 고정하고, 정책을 바꿀 때마다 같은 시드 묶음으로 전후를 비교한다. 시드가 다르면 비교가 아니다.

1대 → 2대 → N대 단계적 실기 전개

아래 게이트 숫자는 표준이 아니라 rule of three 에서 역산한 예시다.

2대 단계에서 데드락률을 재려 하지 않는다. 30회 무사고가 말해 주는 상한은 10%다. 이 단계가 답할 질문은 "시뮬이 예측한 승자·대기·정지 위치가 현장에서도 그대로인가" 하나다. 어긋나면 고칠 것은 시뮬의 지연·정지 거리 모델이고, 고친 뒤 0단계를 다시 돈다. 안전 계층 단독 시험은 이 표와 별개로 먼저 통과해 있어야 한다.

관측과 리플레이 로깅

로그의 목적은 열람이 아니라 재실행이다.

• 결정 이벤트: 논리 시각, 입력 스냅숏(또는 해시), 설정·맵 버전, 출력, 막힌 로봇에는 막는 로봇. 멈췄을 때 wait-for 그래프를 로그만으로 복원할 수 있어야 한다.
• 실행 이벤트: 허가 수신, 진입, 이탈, 해제. 허가와 진입 사이의 시간이 시뮬의 slip 분포를 보정하는 자료다.
• 세 가지 리플레이: ① 결정 재생 — 같은 입력, 같은 출력인지. CI 에 건다. ② 사고 재생 — 현장 로그를 시나리오 파일로 변환해 회귀 집합에 추가. ③ what-if — 같은 입력열을 새 정책에 넣어 지표 전후 비교.
• 컨테이너: MCAP은 이종 타임스탬프 데이터를 한 파일에 담고 메시지 스키마를 파일에 내장해 별도 의존성 없이 디코딩된다. 결정 이벤트(JSON/Protobuf)와 로봇 토픽을 한 타임라인에 둘 수 있다.
• 시각화는 로그의 소비자로 둔다. League of Robot Runners 의 Start-Kit 이 시뮬 출력 파일을 별도 도구(PlanViz)로 그리는 구조와 같다. 시각화가 시뮬 안에 있으면 헤드리스 CI 가 깨진다.

도입 체크리스트

• [ ] 교통 결정 코드가 시뮬과 운영에서 같은 바이너리/모듈이다.
• [ ] 시뮬에 벽시계·스레드·시드 없는 난수가 없고, 같은 시드 두 번의 로그 해시가 일치한다.
• [ ] 네 시나리오가 CI 에 있고, 상호배제는 정책이 아니라 하네스가 검사한다.
• [ ] 멈춤이 deadlock/blocked_by_dead/stall 로 분류돼 집계된다.
• [ ] 데드락률을 "0건"이 아니라 "n런 0건, 95% 상한 3/n"으로 보고한다.
• [ ] 처리량은 결정 계산 시간과, 평균 대기는 최악 대기와 함께 보고한다.
• [ ] 정책 변경 PR 에 같은 시드 묶음의 전후 지표가 붙는다.
• [ ] 현장 결정 로그를 decide 에 재생하는 테스트가 있고, 현장 사고는 시나리오 파일로 환류된다.
• [ ] N대 전개는 섀도 → 카나리 → 전체 순이며, 되돌릴 정책 버전이 남아 있다.