STATERA Library · Series 08 · Volume 15 · Chapter 07 · KR
Source: https://github.com/Statera-Library/08_Vol_15_Motion_Planning_and_Navigation/blob/main/Chapter_07_Multi_Robot_Navigation/Chapter_07_Multi_Robot_Navigation_KR.md

Volume 15. Motion Planning and Navigation

Chapter 07. Multi Robot Navigation

07.01. Multi Robot Navigation Architectures Centralized Decentralized

다중 로봇 내비게이션(Multi-Robot Navigation)은 단일 로봇 모션 플래닝(Motion Planning)을 여러 자율 로봇이 공유 환경에서 각각 또는 공동의 목표에 도달하도록 확장한 개념이다. 이 과정에서는 충돌(Collision), 교착 상태(Deadlock), 비효율적인 상호 간섭을 방지해야 한다. 문제는 위치 추정(Localization), 인지(Perception), 경로 계획(Path Planning), 작업 조정(Task Coordination), 통신(Communication), 교통 관리(Traffic Management)를 통합하며, 각 로봇이 지능형 에이전트(Intelligent Agent)이면서 다른 로봇에게는 동적으로 변화하는 장애물이 되기 때문에 복잡도가 빠르게 증가한다.

다중 로봇 내비게이션 아키텍처(Multi-Robot Navigation Architecture)는 내비게이션 의사결정이 어디에서 계산되는지, 정보가 어떻게 교환되는지, 로봇 사이의 충돌과 경로 갈등이 어떻게 해결되는지를 정의한다. 두 가지 기본적인 아키텍처 모델은 중앙집중형 내비게이션(Centralized Navigation)과 분산형 내비게이션(Decentralized Navigation)이다. 실제 시스템에서는 차량군 규모(Fleet Size), 통신 품질, 연산 자원, 안전 요구사항, 운용 환경에 따라 두 방식의 중간 형태인 하이브리드 구조(Hybrid Architecture)를 자주 사용한다.

중앙집중형 아키텍처(Centralized Architecture)에서는 중앙 조정기(Central Coordinator)가 로봇의 상태, 목표, 지도, 계획된 경로, 관련 환경 조건에 대한 정보를 유지한다. 개별 로봇은 자신의 상태를 주기적으로 중앙 조정기에 전송하고, 중앙 조정기는 전체적으로 조정된 경로나 궤적(Trajectory)을 계산한다. 중앙 조정기는 시스템 전체를 관찰할 수 있으므로 각 로봇이 독립적으로 움직임을 최적화하는 대신 로봇 간 상호작용을 명시적으로 고려할 수 있다.

중앙집중형 내비게이션은 전체 로봇군(Fleet)을 결합 계획 문제(Joint Planning Problem)로 표현할 수 있다. 로봇 i의 상태를 x_i, 제어 입력을 u_i라고 하면 플래너(Planner)는 결합 상태 X = [x_1, x_2, ..., x_N]를 고려하고 장애물, 운동학적 제약(Kinematic Constraint), 로봇 간 충돌 제약을 만족하는 움직임을 탐색한다. 이를 통해 이동 거리, 임무 완료 시간, 혼잡도, 에너지 소비량, 전체 로봇군 처리량(Fleet Throughput) 등의 목표를 전역적으로 최적화할 수 있다.

중앙집중형 조정(Centralized Coordination)의 주요 장점은 공유 자원(Shared Resource)을 체계적으로 관리할 수 있다는 것이다. 좁은 복도, 교차로, 엘리베이터, 도킹 스테이션(Docking Station), 충전 구역, 상하차 구역, 제한 통로 등을 사용 일정이 관리되어야 하는 자원으로 모델링할 수 있다. 중앙 조정기는 우선순위를 할당하고 공간 또는 시간 영역을 예약하며 실제 충돌이 발생하기 전에 경로를 변경할 수 있어 구조화된 창고나 공장 환경에 특히 적합하다.

그러나 중앙집중형 계획(Centralized Planning)은 상당한 확장성(Scalability) 문제를 가진다. 로봇 수가 증가하면 결합 구성 공간(Joint Configuration Space)이 급격하게 커지고 가능한 상호작용의 수도 증가한다. 따라서 정확한 다중 에이전트 경로 탐색(Multi-Agent Path Finding)은 대규모 로봇군에서 높은 연산 비용을 요구할 수 있다. 실제 구현에서는 계층적 계획(Hierarchical Planning), 우선순위 기반 계획(Prioritized Planning), 예약 테이블(Reservation Table), 그래프 분할(Graph Decomposition), 롤링 호라이즌 최적화(Rolling-Horizon Optimization), 충돌 주변의 국부 재계획(Local Replanning) 등을 사용하여 복잡도를 줄인다.

통신(Communication) 역시 중요한 의존 요소이다. 중앙 조정기가 유효한 의사결정을 수행하려면 충분히 최신 상태의 로봇 정보를 확보해야 하며, 로봇은 허용 가능한 지연시간(Latency) 내에 갱신된 계획을 받아야 한다. 패킷 손실(Packet Loss), 네트워크 혼잡, 일시적인 연결 단절, 상태 정보 지연이 발생하면 중앙 시스템의 표현과 실제 물리적 상황 사이에 차이가 발생할 수 있다. 따라서 강건한 아키텍처(Robust Architecture)는 타임스탬프(Timestamp), 상태 예측(State Prediction), 통신 상태 감시, 로컬 안전 제어기(Local Safety Controller), 성능 저하 운용 모드(Degraded Operating Mode)를 포함한다.

중앙 서버(Central Server)는 이중화(Redundancy)를 의도적으로 설계하지 않으면 논리적인 단일 장애점(Single Point of Failure)이 될 수 있다. 산업용 구현에서는 복제된 차량군 관리자(Fleet Manager), 장애 전환 서버(Failover Server), 영속적 임무 데이터베이스(Persistent Mission Database), 분산 안전 기능(Distributed Safety Function)을 적용할 수 있다. 특히 충돌 방지는 중앙 컴퓨터에만 의존해서는 안 되며, 각 로봇은 예상하지 못한 장애물이나 통신 장애에 즉각 대응할 수 있도록 로컬 인지(Local Perception)와 비상 동작(Emergency Behavior)을 유지하는 것이 일반적이다.

분산형 아키텍처(Decentralized Architecture)에서는 모든 내비게이션 의사결정을 하나의 전역 조정기가 결정하는 대신 개별 로봇에 분산한다. 각 로봇은 자신의 주변 환경을 추정하고 움직임을 계획하며 인접 로봇을 직접 관찰하거나 전달받은 정보를 이용해 자신의 궤적을 조정한다. 하나의 중앙 권한이 모든 로봇의 움직임을 계산하는 대신 국부 상호작용(Local Interaction), 공유 프로토콜(Shared Protocol), 협상(Negotiation), 분산 최적화(Distributed Optimization)를 통해 조정된 행동이 형성된다.

분산형 내비게이션(Decentralized Navigation)은 연산 작업이 자연스럽게 여러 로봇으로 분산되기 때문에 높은 확장성과 결함 허용성(Fault Tolerance)을 제공한다. 하나의 로봇에 장애가 발생해도 반드시 전체 로봇군이 정지하는 것은 아니며, 기반시설과의 연결이 불가능한 경우에도 로봇이 계속 동작할 수 있다. 이러한 특성은 야외 로봇, 탐사 시스템, 수색 및 구조(Search and Rescue), 농업 기계, 이기종 로봇 팀(Heterogeneous Robot Team)처럼 안정적인 중앙 통신을 항상 보장하기 어려운 환경에서 중요하다.

분산화(Decentralization)의 핵심적인 어려움은 국부적으로 이용 가능한 정보만으로 전체 시스템 차원의 효율적인 행동을 만들어 내는 것이다. 두 로봇이 각각 독립적으로는 최적인 경로를 선택하더라도 두 경로가 서로 양립하지 못할 수 있다. 여러 로봇이 대칭적인 충돌 상황에 진입하거나 반복적으로 서로 양보하면서 진동(Oscillation)을 일으키거나 제한된 통로 주변에서 교착 상태를 형성할 수 있다. 따라서 분산형 시스템에는 우선순위, 통행권(Right-of-Way), 협상, 충돌 해결, 조정 실패 복구에 대한 명확한 규칙이 필요하다.

로컬 충돌 회피(Local Collision Avoidance)는 분산형 상호작용의 한 계층을 제공한다. 로봇은 주변 로봇의 미래 궤적을 예측하고 목표 방향으로 진행하면서 안전한 분리 거리를 유지하는 속도를 선택할 수 있다. 속도 장애물(Velocity Obstacle), 상호 충돌 회피(Reciprocal Collision Avoidance), 모델 예측 제어(Model Predictive Control), 분산 궤적 최적화(Distributed Trajectory Optimization) 기반의 방법을 사용할 수 있다. 그러나 순수한 반응형 회피(Reactive Avoidance)만으로는 좁은 복도, 병목 구간, 장시간의 자원 경합과 같은 구조적 충돌을 항상 해결할 수 없다.

정보 공유(Information Sharing)는 분산 로봇이 달성할 수 있는 조정 수준을 결정한다. 로봇들은 위치 자세(Pose), 속도, 계획된 궤적, 목적지, 우선순위, 의도(Intent), 불확실성(Uncertainty), 예약 영역 등을 교환할 수 있다. 특히 미래의 이동 의도를 공유하면 다른 로봇이 물리적인 충돌이 임박하기 전에 대응할 수 있다. 그러나 안전 시스템은 모든 주변 로봇이 항상 정확하고 적시에 정보를 제공한다고 가정할 수 없으므로 통신 프로토콜은 메시지 손실과 불일치하는 상태 추정에도 대응할 수 있어야 한다.

따라서 중앙집중형 및 분산형 아키텍처는 단순히 서로 다른 계획 알고리즘(Planning Algorithm)을 의미하는 것이 아니라 지식과 의사결정 권한을 서로 다르게 분배하는 구조라고 볼 수 있다. 중앙집중형 방식은 전역 가시성(Global Visibility), 예측 가능한 교통 관리, 로봇군 수준 최적화에 유리하며, 분산형 방식은 자율성(Autonomy), 확장성, 회복탄력성(Resilience), 불완전한 통신 환경에서의 운용에 유리하다. 적절한 방식은 환경이 구조화되고 기반시설이 충분한지, 또는 개방적이고 동적이며 지리적으로 분산되어 있고 통신 제약이 존재하는지에 따라 달라진다.

하이브리드 아키텍처(Hybrid Architecture)는 두 방식을 결합하며 실제 로봇군에서 점점 중요해지고 있다. 차량군 관리자(Fleet Manager)가 임무, 전역 경로(Global Route), 교통 우선순위, 자원 예약을 결정하는 동안 각 로봇은 위치 추정, 단기 궤적 생성(Short-Horizon Trajectory Generation), 장애물 회피, 비상 정지를 독립적으로 수행할 수 있다. 이러한 역할 분담은 중앙 시스템이 모든 제어 결정을 처리하지 않아도 되게 하면서 혼잡과 교착 상태를 줄이는 데 필요한 전역 조정 능력을 유지한다.

계층적 조정(Hierarchical Coordination)은 내비게이션을 여러 공간적·시간적 수준으로 분할하여 하이브리드 개념을 확장한다. 전역 계층(Global Layer)은 목적지와 주요 경로 구간을 할당하고, 지역 조정기(Regional Coordinator)는 교차로나 특정 구역을 관리하며, 개별 로봇은 로컬 궤적(Local Trajectory)을 실행할 수 있다. 대규모 시설에서는 로봇을 그룹이나 운용 영역으로 추가 분할하여 완전한 중앙집중형 차량군 계획보다 조정 복잡도가 더 완만하게 증가하도록 설계할 수 있다.

정적 장애물(Static Obstacle)과 다른 로봇을 구분하는 것은 다중 로봇 내비게이션에서 매우 중요하다. 다른 로봇은 단순한 이동 장애물이 아니라 목표와 계획 능력을 가지고 있으며 자신의 이동 의도를 통신할 수도 있다. 협력 로봇(Cooperative Robot)을 예측 불가능한 동적 객체와 동일하게 처리하면 활용 가능한 정보를 낭비하게 된다. 대신 공유 계획, 예약 정보, 예상 도착 시간, 협상된 우선순위를 활용하면 독립적인 장애물 회피보다 훨씬 효율적으로 움직임을 조정할 수 있다.

시간적 조정(Temporal Coordination)은 기하학적 경로 계획(Geometric Path Planning)만큼 중요하다. 두 로봇이 서로 다른 시간에 동일한 복도를 사용한다면 안전하게 통과할 수 있으므로 내비게이션은 공간만이 아니라 시공간(Space-Time)을 함께 고려해야 한다. 예약 기반 시스템(Reservation-Based System)은 경로 구간, 그래프 노드, 교차로 또는 특정 영역을 시간 구간과 연결한다. 이를 통해 많은 충돌 문제를 스케줄링 문제(Scheduling Problem)로 변환하고 밀집된 로봇군이 제한된 기반시설을 효율적으로 공유하도록 할 수 있다.

교착 상태 관리(Deadlock Management)는 아키텍처 수준에서 고려되어야 한다. 교착 상태는 로봇들이 서로 충돌하지는 않지만 계획된 움직임이 서로를 차단하여 더 이상 진행하지 못하는 상황이다. 대기 관계 그래프(Wait-for Graph), 타임아웃 조건(Timeout Condition), 진행도 지표(Progress Metric), 예약 의존성(Reservation Dependency), 반복적인 재계획 패턴 등을 이용하여 이를 감지할 수 있다. 복구 방법에는 우선순위 재할당, 경로 역행, 일시적인 후퇴, 예약 취소, 로컬 협상으로 해결할 수 없는 경우의 중앙 개입 등이 포함된다.

내비게이션 아키텍처는 조정 안전성(Coordination Safety)과 기능 안전성(Functional Safety)도 구분해야 한다. 협력 계획은 정상 운용 조건에서 충돌을 방지하는 것을 목적으로 하지만 안전 메커니즘(Safety Mechanism)은 위치 추정 오류, 통신 장애, 예상하지 못한 사람의 움직임, 제어기 고장, 잘못된 예측으로부터 시스템을 보호해야 한다. 독립적인 센싱(Independent Sensing), 속도 감독(Speed Supervision), 보호 정지(Protective Stop), 최소 분리 거리 정책, 보수적인 폴백 동작(Conservative Fallback Behavior)은 조정 과정의 가정이 무너졌을 때 추가적인 보호 계층을 제공한다.

이기종 로봇군(Heterogeneous Fleet)은 로봇마다 외형 크기(Footprint), 속도, 회전 반경, 적재 능력(Payload), 센싱 능력, 이동 메커니즘(Locomotion Mechanism)이 다를 수 있기 때문에 아키텍처를 더욱 복잡하게 만든다. 따라서 공유 내비게이션 표현(Shared Navigation Representation)은 단순한 점유 정보 이상을 표현해야 한다. 중앙집중형 시스템은 이기종 제약을 스케줄링에 직접 포함할 수 있으며, 분산형 시스템에서는 로봇들이 서로의 이동 능력과 의도를 해석할 수 있도록 공통 규약(Common Convention)이 필요하다.

시스템 성능은 궁극적으로 개별 로봇과 전체 로봇군 수준에서 모두 평가되어야 한다. 개별 이동 시간만 평가하면 공격적인 최단 경로 선택이 다른 로봇의 혼잡을 증가시키는 현상을 제대로 반영하지 못할 수 있다. 유용한 평가 지표에는 임무 처리량(Mission Throughput), 평균 지연시간, 전체 완료 시간(Makespan), 이동 거리, 에너지 소비량, 충돌 빈도, 교착 상태 발생률, 통신 부하, 계획 지연시간, 복구 시간 등이 있다. 따라서 아키텍처 선택은 알고리즘 자체의 우아함보다 실제 운용 성능을 기준으로 이루어져야 한다.

실제 시스템 배치(Real-World Deployment)에서는 중앙집중형 전략 조정(Centralized Strategic Coordination)과 분산형 전술 자율성(Decentralized Tactical Autonomy)을 결합하는 방식이 가장 강건한 구조가 되는 경우가 많다. 전역 정보는 로봇군 전체에 실질적인 가치를 제공하는 영역에 사용하고, 시간에 민감한 센싱과 충돌 대응은 각 로봇 가까이에서 수행한다. 이를 통해 전체 로봇군은 공유 지능(Shared Intelligence)의 장점을 활용하면서도 모든 움직임이 지속적인 네트워크 연결이나 중앙 플래너의 가용성에 의존하지 않도록 할 수 있다.

로봇군이 대규모 자율 시스템(Large-Scale Autonomous System)으로 발전함에 따라 다중 로봇 내비게이션은 단순한 경로 계획 문제가 아니라 점차 오케스트레이션 문제(Orchestration Problem)로 확장되고 있다. 로봇은 자신의 움직임뿐만 아니라 임무, 기반시설, 충전, 사람의 활동, 다른 자율 에이전트와도 조정되어야 한다. 중앙집중형, 분산형, 하이브리드 아키텍처는 이러한 지능을 분배하는 상호 보완적인 메커니즘을 제공하며, 성공적인 시스템은 지연시간, 규모, 불확실성, 안전성, 운용 목표에 따라 각 계층의 역할과 경계를 결정한다.

07.02. Conflict Based Search CBS for Multi Robot [w/Code]

충돌 기반 탐색(Conflict-Based Search, CBS)은 다중 에이전트 경로 탐색(Multi-Agent Path Finding, MAPF)을 위한 2단계 알고리즘(Two-Level Algorithm)으로, 전역적인 충돌 해결(Global Conflict Resolution)과 개별 로봇의 경로 계획(Individual Path Planning)을 분리한다. 모든 로봇의 거대한 결합 구성 공간(Joint Configuration Space)을 직접 탐색하는 대신, CBS는 먼저 각 로봇의 경로를 독립적으로 계획한 후 이러한 경로 사이에서 발생하는 충돌을 탐지한다. 충돌이 발견되면 CBS는 관련 로봇이 서로 다른 결정을 내리도록 제약(Constraint)을 추가하고, 새롭게 발생한 충돌을 재귀적으로 해결한다.

CBS의 핵심 개념은 충돌 트리(Conflict Tree, CT)를 이용하여 다중 로봇 조정을 표현하는 것이다. 충돌 트리의 각 노드는 제약 조건 집합(Set of Constraints)과 이에 대응하는 개별 로봇 경로 집합(Collection of Individual Robot Paths)을 포함한다. 루트 노드(Root Node)는 빈 제약 집합으로 시작하므로 모든 로봇은 자신의 독립적인 최적 경로를 할당받는다. 이후 생성된 경로를 서로 비교하여 충돌을 탐색한다. 충돌이 없으면 해당 해는 유효한 해가 되며, 충돌이 존재하면 탐지된 충돌을 기반으로 충돌 트리를 확장한다.

일반적인 충돌은 두 로봇이 동일한 위치를 동일한 시간에 점유하거나 동일한 에지를 서로 반대 방향으로 통과하려고 할 때 발생한다. 정점 충돌(Vertex Conflict)은 로봇 A가 시간 t에 위치 v를 점유하는 동시에 로봇 B도 같은 위치 v를 점유하는 상황으로 표현할 수 있다. 에지 충돌(Edge Conflict)은 두 로봇이 동일한 연결 구간을 동일한 시간 간격에 서로 반대 방향으로 통과하는 경우에 발생한다. 이러한 충돌은 조정이 실패한 공간적·시간적 위치를 정확하게 나타내는 정보를 제공한다.

CBS가 두 로봇 사이의 충돌을 발견하면 대체 제약(Alternative Constraint)을 추가하여 자식 노드(Child Node)를 생성한다. 예를 들어 로봇 A와 로봇 B가 시간 t에 위치 v를 동시에 점유하려는 경우, 하나의 자식 노드는 로봇 A가 t 시점에 v를 점유하지 못하도록 제한하고, 다른 자식 노드는 로봇 B가 v를 점유하지 못하도록 제한할 수 있다. 따라서 각각의 자식 노드는 서로 다른 방식으로 해당 충돌을 해결한다. 이후 새롭게 추가된 제약 조건을 만족하도록 영향을 받은 로봇의 경로를 재계획한다.

CBS의 하위 계층(Lower Level)은 개별 로봇을 위한 단일 에이전트 경로 탐색(Single-Agent Path Finding, SAPF)을 수행한다. 일반적인 구현에서는 공간과 시간을 함께 표현하는 공간-시간 표현(Space-Time Representation) 위에서 A* 탐색을 사용하며, 하나의 상태(State)는 공간적 위치와 시간을 모두 포함한다. 플래너는 정적 장애물, 로봇별 제약 조건, 이동 능력 등을 고려하여 실행 가능한 경로를 탐색한다. 새로운 제약이 추가되었을 때 일반적으로 해당 제약의 영향을 받는 로봇만 재계획하면 되므로, CBS는 모든 로봇의 경로를 반복적으로 다시 계산하는 것을 피할 수 있다.

CBS의 상위 계층(High Level)은 비용 함수(Cost Function)를 기준으로 충돌 트리를 탐색한다. 일반적인 목적 함수는 총 비용 합(Sum of Costs, SoC)으로, 모든 로봇의 경로 비용을 합산한다. 또 다른 목적 함수는 전체 완료 시간(Makespan)으로, 전체 차량군이 임무를 완료하는 데 필요한 시간을 최소화한다. 어떤 목적 함수를 선택하는지에 따라 플래너의 행동이 달라진다. 전체 이동 비용을 최소화하는 해는 가장 느린 로봇의 완료 시간을 최소화하는 해와 서로 다를 수 있다.

CBS가 매력적인 이유는 어려운 조합적 문제(Combinatorial Problem)를 관리 가능한 구성 요소로 분해하기 때문이다. 개별 경로 계획은 비교적 단순하게 유지하면서 로봇 간 충돌은 상위 계층에서 명시적으로 처리한다. 이러한 구조는 특정한 해가 변경되는 이유도 설명할 수 있게 한다. 즉, 특정 로봇이 특정 공간적·시간적 충돌 때문에 재계획되었다는 것을 명확하게 추적할 수 있다. 이러한 명시적 추론 구조는 다중 로봇 내비게이션의 디버깅(Debugging)이나 검증(Validation)에도 유용하다.

CBS의 효과는 충돌의 수와 구조에 크게 좌우된다. 독립적으로 생성된 경로가 거의 상호작용하지 않는 경우에는 루트 노드 자체가 이미 유효한 해가 되거나 몇 번의 충돌 해결만 필요할 수 있다. 반면 밀집된 환경에서는 여러 로봇이 동일한 복도, 교차로 또는 병목 구간을 반복적으로 이용하려 할 수 있다. 이 경우 충돌 트리가 빠르게 증가할 수 있으며, 하나의 충돌이 여러 분기를 생성하면서 상위 계층 탐색의 계산 부담이 크게 증가한다.

따라서 충돌 선택(Conflict Selection)은 실제 성능에 중요한 영향을 미친다. 플래너는 시간상 가장 먼저 발생하는 충돌, 가장 제약이 많은 충돌, 또는 탐색 공간을 효과적으로 분할할 것으로 예상되는 충돌을 선택할 수 있다. 최신 CBS 변형에서는 충돌의 카디널리티(Cardinality)를 활용하기도 한다. 카디널 충돌(Cardinal Conflict)은 충돌을 해결할 경우 관련된 로봇 중 적어도 하나의 경로 비용이 반드시 증가하는 충돌이며, 비카디널 충돌(Non-Cardinal Conflict)은 목적 함수의 비용을 증가시키지 않고 해결할 가능성이 있는 충돌이다. 중요한 충돌을 우선적으로 처리하면 불필요한 탐색을 상당히 줄일 수 있다.

제약 전파(Constraint Propagation) 역시 중요한 고려사항이다. 제약 조건은 발견된 충돌을 방지할 수 있을 만큼 정확하게 표현되어야 하지만, 다른 실행 가능한 해를 불필요하게 제한해서는 안 된다. 지나치게 제한적인 제약은 유용한 경로를 제거하여 탐색량을 증가시킬 수 있고, 반대로 제약이 충분하지 않으면 동일한 충돌이 다시 발생할 수 있다. 따라서 제약 표현의 품질은 알고리즘의 정확성과 계산 효율성 모두에 직접적인 영향을 미친다.

CBS는 분리 분할(Disjoint Splitting)과 같은 기법을 통해 확장할 수 있다. 분리 분할은 제약 조건을 보다 효과적으로 할당하여 해 공간(Solution Space)을 효율적으로 분할할 수 있도록 한다. 일반적인 분할(Standard Splitting)은 충돌에 관련된 각 로봇에 하나의 제약을 생성한다. 반면 분리 분할은 양의 제약(Positive Constraint)과 음의 제약(Negative Constraint)을 사용하여 한 분기에서는 특정 로봇이 특정 행동을 반드시 수행하도록 요구하고, 다른 분기에서는 해당 행동을 금지한다. 이러한 방식은 특정한 문제 구조에서 중복 탐색을 줄일 수 있다.

단일 에이전트 플래너(Single-Agent Planner) 역시 전체 CBS 성능에 큰 영향을 미친다. 효율적인 휴리스틱(Heuristic)은 각 재계획 과정에서 탐색해야 하는 상태 수를 줄일 수 있다. 공간-시간 A*(Space-Time A*)는 대기 행동(Waiting Action)과 시간적 제약을 고려하면서 목표까지의 거리를 기반으로 한 허용 가능한 휴리스틱(Admissible Heuristic)을 사용할 수 있다. 그리드 기반 창고 환경에서는 사전에 계산된 최단 경로 거리(Precomputed Shortest-Path Distance), 방향별 비용(Directional Cost), 지도 특화 휴리스틱(Map-Specific Heuristic) 등을 활용하여 반복적인 하위 계층 탐색을 더욱 빠르게 만들 수 있다.

실제 CBS 구현에서는 시간 모델(Temporal Model)을 신중하게 정의해야 한다. 로봇은 이산적인 그리드 셀(Discrete Grid Cell)과 이산적인 시간 단계(Discrete Time Step)에서 위치하는 것으로 표현할 수도 있고, 연속적인 상태 사이의 에지를 따라 이동하는 것으로 표현할 수도 있다. 한 위치에서 대기하는 행동도 명시적으로 표현해야 한다. 로봇은 충돌을 해결하기 위해 단순히 이동을 지연시키는 것만으로도 충분한 경우가 있기 때문이다. 그러나 실제 물리 로봇에서는 이러한 이산적인 계획을 결국 가속도, 속도, 회전 반경, 정지 거리 등을 만족하는 연속 궤적(Continuous Trajectory)으로 변환해야 한다.

이산적인 MAPF에서 실제 물리적 내비게이션으로 전환하는 과정은 가장 중요한 엔지니어링 고려사항 중 하나이다. 그리드상에서 충돌이 없는 CBS 해가 실제 로봇에서도 자동으로 안전하다는 의미는 아니다. 위치 추정 불확실성(Localization Uncertainty), 추적 오차(Tracking Error), 로봇의 실제 크기, 제동 거리(Braking Distance), 제어기 지연(Control Latency), 동적 장애물(Dynamic Obstacle) 등을 적절한 안전 여유(Safety Margin) 또는 후단 궤적 검증(Downstream Trajectory Validation)을 통해 반영해야 한다. 따라서 CBS 계층은 완전한 물리적 안전 제어기라기보다는 조정 플래너(Coordination Planner)로 보는 것이 적절하다.

CBS는 내비게이션 그래프(Navigation Graph)로 효과적으로 표현할 수 있는 환경에 특히 적합하다. 창고 통로, 공장 복도, 구조화된 물류 구역, 실내 운송 네트워크 등은 자연스럽게 로봇이 이동하는 노드(Node)와 에지(Edge)로 표현할 수 있다. 교차로와 좁은 통로는 충돌이 집중되는 영역(Conflict Hotspot)이 되며, 이를 명시적으로 식별하고 관리할 수 있다. 따라서 CBS는 운용 환경이 비교적 구조화되어 있고 로봇의 움직임을 과도한 현실성 손실 없이 이산화할 수 있는 경우에 유용하다.

그러나 대규모 산업용 차량군(Large Industrial Fleet)에서 고전적인 CBS를 수백 대의 로봇에 직접 적용하는 것은 계산적으로 어려울 수 있다. 밀집된 교통에서는 많은 충돌이 발생하고, 이에 따라 충돌 트리가 불리한 상황에서 지수적으로 증가할 수 있다. 따라서 실제 시스템에서는 CBS를 계층적 분할(Hierarchical Decomposition), 지역 계획(Regional Planning), 우선순위 기반 계획(Prioritized Planning), 교통 구역(Traffic Zone), 롤링 호라이즌 재계획(Rolling-Horizon Replanning), 차량군 수준 스케줄링(Fleet-Level Scheduling) 등과 결합한다. 먼저 로봇을 특정 지역이나 통로에 할당한 후 더 작은 계획 문제 내부에서 CBS를 적용할 수 있다.

CBS는 예약 기반 교통 관리(Reservation-Based Traffic Management)와도 자연스럽게 결합할 수 있다. 상위 수준의 차량군 시스템은 교차로, 충전 스테이션, 엘리베이터, 좁은 통로와 같은 핵심 자원을 예약하고, CBS는 그 이후 남아 있는 로봇 간 충돌을 처리할 수 있다. 이렇게 하면 장기적인 자원 할당(Long-Term Resource Allocation)과 단기적인 경로 충돌 해결(Short-Term Path Conflict Resolution)을 서로 분리할 수 있다. 이러한 분리는 CBS가 전체 시설의 모든 운용 결정을 동시에 탐색해야 하는 부담을 줄여준다.

CBS는 작업 할당(Task Allocation)과도 자연스럽게 연계된다. 두 로봇에 동일한 제한 구역을 동시에 사용해야 하는 작업이 할당되었다면, 발생하는 내비게이션 충돌은 순수한 기하학적 경로 계획 문제라기보다 상위 단계의 작업 할당 문제를 반영할 수 있다. 따라서 차량군 지능 시스템(Fleet Intelligence System)은 CBS에서 발생하는 충돌 정보를 작업 할당, 경로 선택, 스케줄링 계층에 피드백할 수 있다. 반복적으로 충돌이 발생한다면 작업을 다른 로봇에 재할당하거나 운용 우선순위를 변경해야 한다는 신호로 해석할 수 있다.

강건성(Robustness)을 확보하려면 실행 불확실성(Execution Uncertainty)을 고려해야 한다. CBS 경로는 로봇이 자신의 궤적을 충분히 정확하게 따라간다는 가정을 전제로 한다. 한 로봇이 지연, 위치 추정 오류, 장애물 발생, 일시적인 통신 문제 등을 경험하면 기존의 충돌 없는 계획이 더 이상 유효하지 않을 수 있다. 따라서 런타임 모니터링(Runtime Monitoring)은 예측된 로봇 상태와 실제 상태를 비교하고, 상태 편차가 정의된 임계값을 초과하면 국부 또는 전역 재계획을 실행해야 한다.

CBS는 개별 로봇 자율성(Individual Robot Autonomy)과 협력적인 차량군 지능(Coordinated Fleet Intelligence)을 연결하는 가교로 볼 수 있다. 하위 수준 플래너는 로봇별 내비게이션 능력을 유지하고, 상위 수준의 충돌 트리는 로봇 간 상호작용을 해결하기 위한 명시적인 메커니즘을 제공한다. 이러한 분리 구조는 개념적으로 명확하며, 기본적인 조정 원리를 변경하지 않고도 다양한 단일 로봇 플래너, 비용 함수, 제약 모델을 통합할 수 있도록 한다.

Physical AI 차량군 아키텍처에서 CBS는 완전한 내비게이션 스택(Navigation Stack)이 아니라 전술적 다중 로봇 조정 계층(Tactical Multi-Robot Coordination Layer)으로 배치하는 것이 가장 자연스럽다. 임무 오케스트레이션(Mission Orchestration)은 로봇이 무엇을 수행해야 하는지를 결정하고, 작업 할당(Task Allocation)은 어떤 로봇이 해당 작업을 수행할지를 결정하며, 전역 계획(Global Planning)은 큰 범위의 경로를 설정하고, CBS는 이러한 경로 사이의 충돌을 해결하며, 로컬 제어기(Local Controller)는 최종 경로를 동적으로 실행 가능한 움직임으로 변환한다. 안전 감독(Safety Supervision)은 이러한 계획 체계와 독립적으로 유지되어야 한다.

따라서 CBS의 핵심 가치는 단순히 충돌 없는 경로를 생성하는 데 있는 것이 아니라, 독립적으로 계획된 로봇의 행동이 왜 서로 양립할 수 없게 되었는지를 구조적으로 추론하고 이러한 충돌을 체계적으로 해결할 수 있다는 데 있다. 2단계 아키텍처(Two-Level Architecture), 명시적인 제약 조건(Explicit Constraints), 충돌 기반 분기(Conflict-Driven Branching), 그래프 기반 환경과의 높은 호환성은 CBS를 다중 로봇 조정을 위한 강력한 기반으로 만든다. 다만 확장성(Scalability), 연속 동역학(Continuous Dynamics), 불확실성(Uncertainty), 실시간 실행(Real-Time Execution)은 적절한 확장 기법과 시스템 아키텍처 통합을 통해 별도로 해결해야 한다.

07.03. Priority Based Planning for Fleet Navigation [w/Code]

우선순위 기반 계획(Priority-Based Planning)은 로봇에게 명시적 또는 동적으로 계산된 우선순위(Priority)를 부여하고, 우선순위가 높은 로봇부터 계획하는 실용적인 다중 로봇 내비게이션(Multi-Robot Navigation) 전략이다. 우선순위가 높은 로봇의 경로를 먼저 생성한 후, 우선순위가 낮은 로봇은 이미 계획된 로봇의 궤적(Trajectory)이나 예약된 자원(Resource)을 회피하도록 경로를 생성한다. 전체 차량군(Fleet)을 하나의 결합 최적화 문제로 해결하는 대신, 여러 개의 단일 로봇 계획 문제로 분해하여 조정을 수행한다.

이 방식의 근본적인 목적은 확장성(Scalability)을 확보하는 것이다. 차량군 규모가 증가하면 모든 로봇의 궤적을 동시에 계획하는 비용이 급격하게 증가하는데, 이는 각각의 로봇이 다른 많은 로봇과 상호작용할 수 있기 때문이다. 우선순위 기반 계획은 로봇 사이의 순서를 설정하여 이러한 복잡도를 줄인다. 계획 순서가 결정되면 이미 계획된 로봇의 궤적을 제약 조건으로 취급하면서 다음 로봇의 경로를 계산할 수 있으므로, 실시간 산업용 차량군 내비게이션에 적합하다.

우선순위는 정적(Static) 또는 동적(Dynamic)으로 설정할 수 있다. 정적 우선순위는 로봇의 식별자, 임무 등급, 차량 능력, 운용 구역, 사전에 정의된 서비스 규칙 등에 따라 결정될 수 있다. 반면 동적 우선순위는 남은 이동 거리, 작업 긴급도, 배터리 상태, 예상 지연시간, 대기 시간, 적재 요구사항, 충돌 발생 가능성 또는 특정 구역과의 근접성 등을 고려할 수 있다. 동적 우선순위를 사용하면 영구적으로 고정된 계층에 의존하지 않고 변화하는 운용 조건에 대응할 수 있다.

계획 과정은 일반적으로 현재 활성화된 모든 로봇에 우선순위를 할당하는 것에서 시작한다. 가장 높은 우선순위의 로봇은 낮은 우선순위 로봇을 계획 제약으로 고려하지 않고 자신의 경로를 계획하며, 이후의 로봇은 이미 할당된 상위 우선순위 로봇의 궤적과 충돌하지 않는 경로를 탐색해야 한다. 예를 들어 로봇 A가 로봇 B보다 높은 우선순위를 가진다면 먼저 A의 실행 가능한 경로를 생성하고, 이후 A와 충돌하지 않는 B의 경로를 탐색한다. 이 과정은 모든 로봇이 계획될 때까지 반복된다.

우선순위 기반 계획은 로봇의 경로가 위치와 시간을 모두 포함하는 공간-시간 표현(Space-Time Representation)을 사용할 수 있다. 따라서 낮은 우선순위의 로봇은 상위 우선순위 로봇이 점유하는 위치뿐만 아니라 해당 로봇이 그 위치를 점유하는 시간 구간도 회피해야 한다. 이러한 특성은 좁은 통로와 교차로에서 특히 중요하다. 두 로봇이 충분히 다른 시간에 동일한 물리적 영역을 통과한다면 안전하게 해당 영역을 공유할 수 있기 때문이다.

우선순위 순서의 품질은 최종적인 차량군 행동에 큰 영향을 미친다. 적절한 순서는 대기 시간을 최소화하면서 효율적인 경로를 생성할 수 있지만, 잘못된 순서는 낮은 우선순위 로봇이 불필요하게 긴 우회 경로를 선택하거나 상위 우선순위 로봇 뒤에서 대기하도록 만들 수 있다. 따라서 차량군 성능이 중요한 경우 우선순위 할당은 단순한 구현 세부사항이 아니라 계획의 중요한 변수로 취급해야 한다.

일반적인 방법은 긴급하거나 시간 제약이 있는 임무를 수행하는 로봇에 우선순위를 부여하는 것이다. 긴급 운송, 안전 관련 검사, 중요한 생산 작업 또는 중요한 자원에 접근하고 있는 로봇에는 일시적인 우선순위를 부여할 수 있다. 또 다른 방법은 오랫동안 대기한 로봇을 우선하는 것이다. 대기 시간을 우선순위에 포함하면 특정 로봇이 계속 우선순위를 잃고 다른 로봇들이 계속 자원을 사용하는 동안 장시간 차단되는 기아 상태(Starvation)를 방지할 수 있다.

우선순위는 기반시설 자원(Infrastructure Resource)과 연결할 수도 있다. 예를 들어 교차로에서 하나의 로봇에 중요한 통과 구간에 대한 일시적인 예약(Reservation)을 부여하고, 다른 로봇들은 해당 예약을 피해 경로를 계획하도록 할 수 있다. 동일한 메커니즘은 엘리베이터, 좁은 통로, 도킹 스테이션(Docking Station), 충전 구역, 상하차 구역, 일방통행 구간에도 적용할 수 있다. 이러한 형태의 우선순위 기반 계획은 교통 스케줄링(Traffic Scheduling) 및 자원 관리(Resource Management)와 밀접하게 연결된다.

중요한 한계 중 하나는 완전성(Completeness)이다. 하나의 우선순위 순서로 계획하면 낮은 우선순위 로봇에 실행 가능한 경로가 존재하지 않는 상황이 발생할 수 있으며, 다른 순서로 로봇을 계획했다면 해결책이 존재했을 수도 있다. 이는 앞서 수행된 계획 결정이 이미 고정되었기 때문에 발생한다. 높은 우선순위 로봇이 전략적으로 중요한 통로 또는 시간 구간을 점유하면 낮은 우선순위 로봇이 선택할 수 있는 실행 가능한 대안이 사라질 수 있다.

우선순위 역전(Priority Inversion) 역시 실제 운용에서 중요한 문제이다. 처음에는 낮은 우선순위를 가지고 있던 로봇이 현재의 임무 상태가 우선순위에 제대로 반영되지 않아 운영상 중요한 로봇의 이동을 방해할 수 있다. 동적 우선순위 재조정(Dynamic Reprioritization)은 이러한 문제를 해결할 수 있지만, 우선순위가 지나치게 자주 변경되면 시스템이 불안정해지거나 로봇이 반복적으로 자신의 계획을 수정할 수 있다. 따라서 강건한 시스템에서는 우선순위를 언제, 어떤 조건에서 변경할 수 있는지 명확한 규칙을 정의해야 한다.

교착 상태 방지(Deadlock Prevention)는 우선순위 기반 시스템에서 특히 중요하다. 두 개 이상의 로봇이 할당된 우선순위 규칙을 따르더라도 서로 차단되는 상황이 발생할 수 있다. 이는 좁은 통로, 폐쇄 루프 또는 공유 교차로 주변에서 발생할 수 있다. 실제 구현에서는 대기 관계 그래프(Wait-for Graph), 타임아웃 감지(Timeout Detection), 진행 상태 모니터링(Progress Monitoring), 통로 예약(Corridor Reservation), 일시적인 우선순위 상승(Priority Escalation) 등을 사용하여 이러한 상황을 탐지하고 복구할 수 있다.

우선순위 기반 계획은 로컬 반응형 충돌 회피(Local Reactive Collision Avoidance)와 결합할 수 있다. 우선순위 계층은 전략적인 통행권(Right-of-Way)을 결정하고 제한된 구역을 통과할 로봇을 지정하며, 로컬 플래너(Local Planner)는 예상하지 못한 장애물과 작은 위치 편차에 대응한다. 예를 들어 차량군 관리자가 하나의 로봇에 교차로를 먼저 통과하도록 허가하는 동안, 각 로봇의 로컬 제어기는 사람, 장애물 및 다른 차량과 안전한 거리를 유지하도록 속도를 지속적으로 조정할 수 있다.

이 방식은 교통 규칙을 명확하게 표현할 수 있는 구조화된 환경에 특히 유용하다. 창고, 공장, 물류 센터, 병원, 캠퍼스 등은 일반적으로 명확한 통로, 교차로, 충전 위치 및 운용 구역을 가지고 있다. 내비게이션 그래프(Navigation Graph)는 이러한 구조를 표현할 수 있으며, 우선순위 규칙은 어떤 로봇이 제한된 그래프 자원에 접근할 수 있는지를 결정한다. 이를 통해 계산 비용이 높은 전역 결합 계획(Global Joint Planning)을 사용하지 않고도 예측 가능한 행동을 구현할 수 있다.

대규모 차량군에서는 계층적 우선순위 계획(Hierarchical Priority Planning)을 통해 확장성을 더욱 향상시킬 수 있다. 차량군 수준 플래너(Fleet-Level Planner)는 임무 또는 구역 사이의 우선순위를 설정하고, 지역 플래너(Regional Planner)는 로컬 교차로에서 우선순위를 결정하며, 각 로봇은 독립적으로 단기 궤적 계획(Short-Horizon Trajectory Planning)을 수행할 수 있다. 이러한 계층 구조는 하나의 플래너가 모든 상호작용을 동시에 해결해야 하는 부담을 줄이고, 교통 밀도와 충돌 가능성이 높은 영역에 연산 자원을 집중할 수 있도록 한다.

우선순위 기반 계획은 작업 할당(Task Allocation)과 내비게이션 사이의 유용한 인터페이스도 제공한다. 작업 할당은 각 로봇이 무엇을 수행해야 하는지를 결정하고, 우선순위 계획은 경쟁하는 이동을 어떻게 조정할지를 결정한다. 여러 로봇에 동일한 제한 자원을 사용해야 하는 작업이 할당되어 반복적으로 충돌이 발생한다면, 시스템은 이러한 정보를 작업 할당기로 피드백할 수 있다. 이후 작업을 재스케줄링하거나 다른 로봇에 재할당하거나 시간적으로 분리하여 동일한 내비게이션 충돌을 반복적으로 해결하는 상황을 줄일 수 있다.

이 방법을 완전한 안전 메커니즘(Safety Mechanism)으로 간주해서는 안 된다. 우선순위는 운용상의 통행권을 결정하지만, 예측하지 못한 사람의 움직임, 센서 오류, 위치 추정 실패, 통신 장애 또는 기계적 고장에 대한 안전을 보장할 수는 없다. 따라서 각 로봇은 독립적인 장애물 탐지, 속도 제한, 비상 정지(Emergency Stop), 보호 동작(Protective Behavior)을 유지해야 한다. 우선순위 기반 계획은 이러한 기능보다 상위에서 동작하는 조정 계층이며, 교통 효율성을 유지하기 위해 안전 제약을 무시해서는 안 된다.

성능 평가는 모든 로봇이 최종적으로 목적지에 도달하는지만을 확인해서는 충분하지 않다. 중요한 지표에는 임무 완료 시간(Mission Completion Time), 평균 및 최대 대기 시간, 이동 거리, 차량군 처리량(Fleet Throughput), 혼잡도(Congestion), 교착 상태 발생 빈도, 우선순위 변경 횟수, 계산 지연시간(Computational Latency), 로봇 간 공정성(Fairness) 등이 포함된다. 처리량이 매우 높더라도 동일한 로봇 집합이 반복적으로 지연된다면 운용 측면에서는 바람직하지 않을 수 있으며, 반대로 지나치게 강한 공정성 제약은 전체 차량군 효율을 감소시킬 수 있다.

실제 차량군 시스템에서는 우선순위 기반 계획이 다른 플래너와 결합되는 하이브리드 구조(Hybrid Arrangement)가 효과적이다. 일반적인 교통 상황은 우선순위와 예약을 이용하여 관리하고, 심각한 충돌은 충돌 기반 탐색(Conflict-Based Search, CBS), 최적화 기반 계획(Optimization-Based Planning), 중앙집중형 개입(Centralized Intervention)으로 확대 처리할 수 있다. 이러한 구조는 단순한 문제는 낮은 계산 비용으로 처리하고 어려운 문제에 대해서만 추가적인 계획 연산을 수행하는 계산 계층(Computational Hierarchy)을 형성한다.

Physical AI 차량군 아키텍처에서 우선순위 기반 계획(Priority-Based Planning)은 전역 임무 오케스트레이션(Global Mission Orchestration)과 로봇 수준 내비게이션(Robot-Level Navigation) 사이의 전술적 교통 조정 계층(Tactical Traffic Coordination Layer)으로 활용할 수 있다. 임무 오케스트레이션은 운용 목표를 설정하고, 작업 할당은 로봇의 책임을 결정하며, 우선순위 계획은 통행권과 자원 접근을 설정하고, 로컬 플래너는 실행 가능한 궤적을 생성하며, 독립적인 안전 기능은 물리적 실행을 감독한다. 이러한 역할 분리는 확장성, 응답성, 예측 가능성, 차량군 수준의 조정 능력 사이에서 실용적인 균형을 제공한다.

07.04. Space Time A Star for Multi Robot [w/Code]

공간-시간 A*(Space-Time A*)는 내비게이션 상태에 시간(Time)을 직접 포함시켜 기존의 A* 탐색을 확장한 방법이다. 일반적인 A*가 상태를 공간적 위치만으로 표현하는 것과 달리, 공간-시간 A*는 상태를 위치-시간 쌍(Position-Time Pair), 예를 들어 (x, y, t)로 표현한다. 이를 통해 플래너는 로봇이 어디로 이동해야 하는지뿐만 아니라 각 위치를 언제 점유해야 하는지도 결정할 수 있다. 이러한 시간적 추론(Temporal Reasoning)은 여러 로봇이 복도, 교차로, 도킹 구역, 기타 제한된 공간을 공유할 때 필수적이다.

기존 A* 계획에서는 일반적으로 정적 장애물을 회피하면서 시작 위치에서 목표 위치까지 비용이 낮은 경로를 찾는 것이 주요 목적이다. 그러나 다중 로봇 내비게이션에서는 이러한 표현만으로 충분하지 않다. 다른 로봇이 서로 다른 시간에 동일한 위치를 점유한다면 반드시 충돌이 발생하는 것은 아니기 때문이다. 따라서 공간-시간 A*는 탐색 영역을 2차원 또는 3차원의 공간 그래프에서 공간-시간 그래프(Space-Time Graph)로 확장한다. 각 전이는 공간적인 이동과 그에 대응하는 시간의 변화를 동시에 나타낸다.

일반적인 공간-시간 A* 상태는 s = (v, t)로 표현할 수 있으며, 여기서 v는 공간 노드(Spatial Node), t는 해당 시간 단계(Time Step)를 의미한다. 이 상태에서 로봇은 인접 노드로 이동하거나 현재 노드에서 하나 이상의 시간 단계 동안 대기할 수 있다. 대기 행동(Waiting Action)은 매우 중요하다. 많은 다중 로봇 충돌은 로봇이 장거리 우회 경로를 선택하는 대신 단순히 이동을 지연시키는 것만으로 해결할 수 있기 때문이다. 따라서 플래너는 시간적 대기를 명시적인 내비게이션 의사결정으로 취급한다.

충돌 회피(Collision Avoidance)는 다른 로봇의 예측된 점유 상태를 공간-시간 제약(Space-Time Constraint)으로 표현하여 수행한다. 다른 로봇이 시간 t에 노드 v를 점유할 것으로 예상된다면 현재 로봇은 동일한 시간에 v로 진입할 수 없다. 두 로봇이 동일한 연결 구간을 동일한 시간 간격에 서로 반대 방향으로 통과하려는 경우에는 에지 충돌(Edge Conflict)도 고려해야 한다. 따라서 유효한 공간-시간 A* 플래너는 후보 상태를 확장할 때 정점 점유(Vertex Occupancy)와 에지 통과(Edge Traversal) 제약을 모두 평가해야 한다.

비용 함수(Cost Function)는 이동 비용(Movement Cost), 대기 비용(Waiting Cost), 목표까지의 남은 비용을 추정하는 휴리스틱(Heuristic)을 결합한다. 일반적인 표현은 f(s) = g(s) + h(s)로 나타낼 수 있으며, g는 시작점부터 현재 상태까지 누적된 비용을 나타내고 h는 현재 상태에서 목표까지의 남은 비용을 추정한다. 휴리스틱은 다른 로봇을 무시한 목표까지의 최단 공간 거리(Shortest Spatial Distance)를 사용할 수 있다. 휴리스틱이 허용 가능한 휴리스틱(Admissible Heuristic) 조건을 유지한다면 A*는 정의된 이산 계획 모델(Discrete Planning Model)에 대해 최적성을 유지할 수 있다.

시간적 계획(Temporal Planning)은 탐색 공간의 크기와 계획 정확성 사이에 중요한 균형을 만든다. 매우 작은 시간 단계를 사용하면 움직임을 더욱 정밀하게 표현할 수 있지만 훨씬 많은 상태를 탐색해야 한다. 반대로 큰 시간 단계를 사용하면 계산량을 줄일 수 있지만 중요한 시간 관계를 놓치거나 실제 물리 로봇에서 실행하기 어려운 궤적이 생성될 수 있다. 따라서 실제 시스템에서는 로봇 속도, 제어 주기, 지도 해상도, 안전 거리, 예상 교통 밀도 등을 기준으로 시간 해상도(Temporal Resolution)를 결정한다.

계획 지평(Planning Horizon) 역시 중요한 설계 변수이다. 긴 계획 지평은 미래 충돌에 대한 더 많은 정보를 제공하고 전역적으로 일관된 경로를 생성할 수 있지만 메모리와 계산량이 증가한다. 짧은 지평은 빠른 재계획(Replanning)을 지원하고 동적 환경에 잘 적응할 수 있지만 현재 로봇 위치 주변에서 이루어진 결정이 이후 충돌을 발생시킬 수 있다. 롤링 호라이즌 공간-시간 A*(Rolling-Horizon Space-Time A*)는 제한된 미래 구간을 반복적으로 계획하고 새로운 로봇 상태와 환경 정보를 반영하여 해를 갱신함으로써 이러한 문제를 해결한다.

공간-시간 A*는 예약(Reservation)과 결합할 때 특히 유용하다. 예약 테이블(Reservation Table)은 특정 시간 구간 동안 어떤 위치 또는 에지가 점유될 것으로 예상되는지를 기록한다. 플래너는 상태를 확장하는 과정에서 이 테이블을 참조하고 기존 예약을 위반하는 전이를 거부한다. 예약 정보는 이미 계획된 다른 로봇의 궤적, 차량군 수준 교통 관리(Fleet-Level Traffic Management), 교차로 스케줄링(Intersection Scheduling), 충전 작업, 엘리베이터 접근 또는 기타 공유 자원 관리에서 생성될 수 있다.

로봇이 공간-시간 경로를 생성하는 순서 역시 최종 결과에 큰 영향을 미친다. 순차적 플래너(Sequential Planner)는 먼저 한 로봇의 경로를 생성한 다음 그 경로를 다음 로봇의 계획에서 예약으로 취급할 수 있다. 이 방식은 각각의 탐색이 단일 로봇 문제로 유지되기 때문에 계산적으로 유리하지만 우선순위 순서가 좋지 않으면 문제가 발생할 수 있다. 나중에 계획되는 로봇은 불필요하게 긴 대기나 우회 경로를 선택해야 할 수 있으며, 다른 계획 순서를 사용했다면 훨씬 효율적인 차량군 해를 얻을 수 있었을 가능성이 있다.

공간-시간 A*는 더욱 고도화된 다중 로봇 알고리즘의 하위 수준 플래너(Low-Level Planner)로도 사용할 수 있다. 예를 들어 충돌 기반 탐색(Conflict-Based Search, CBS)에서는 상위 수준 충돌 트리(Conflict Tree)가 충돌을 식별하고 제약을 추가하는 반면, 공간-시간 A*는 해당 제약 조건을 적용하여 영향을 받은 로봇의 경로를 재계획할 수 있다. 이러한 분리는 상위 수준 알고리즘이 차량군 전체의 충돌을 처리하고 하위 수준 플래너는 개별 로봇의 공간적·시간적으로 일관된 경로를 생성하도록 하기 때문에 매우 강력하다.

실제 로봇에서는 이산적인 공간-시간 A* 해를 최종적으로 연속 궤적(Continuous Trajectory)으로 변환해야 한다. 이산 계획은 특정 시간 단계에 로봇이 일련의 그래프 노드를 점유하도록 지정하지만, 물리적 제어기는 이에 대응하는 속도, 가속도, 회전, 정지 동작을 실행해야 한다. 따라서 로봇의 크기, 위치 추정 불확실성(Localization Uncertainty), 추적 오차(Tracking Error), 제동 거리(Braking Distance), 제어 지연(Control Latency), 동적 장애물(Dynamic Obstacle) 등을 고려하여 명목상의 공간-시간 계획 주변에 안전 여유(Safety Margin)를 설정해야 한다. 계획 계층을 독립적인 충돌 감지 및 안전 제어의 대체 수단으로 취급해서는 안 된다.

이 방법은 내비게이션을 그래프로 표현할 수 있는 구조화된 환경에서 특히 효과적이다. 창고, 공장, 병원, 공항, 물류 시설에는 예측 가능한 복도, 교차로, 문, 엘리베이터, 충전 스테이션, 도킹 위치 등이 존재하는 경우가 많다. 이러한 구조를 공간 노드와 에지로 표현하고 시간적 점유 정보를 통해 각 자원을 언제 사용할 수 있는지를 결정할 수 있다. 따라서 공간-시간 A*는 기하학적 경로 계획(Geometric Path Planning)과 교통 스케줄링(Traffic Scheduling)을 연결하는 자연스러운 방법을 제공한다.

확장성(Scalability)은 여전히 중요한 문제이다. 시간 차원을 추가하면 탐색해야 하는 상태의 수가 크게 증가하기 때문이다. 기존에는 하나의 공간 노드로 표현할 수 있었던 위치가 이제 여러 시간 단계에서 각각 고려되어야 한다. 대규모 차량군에서는 확인해야 할 점유 제약의 수도 증가한다. 따라서 실제 구현에서는 제한된 계획 지평(Bounded Planning Horizon), 효율적인 휴리스틱, 계층적 지도(Hierarchical Map), 충돌 중심 재계획(Conflict-Focused Replanning), 예약 정보 압축(Reservation Compression), 지역 분할(Regional Decomposition) 등을 사용하여 계산 복잡도를 관리한다.

강건한 구현에서는 예측된 로봇 궤적의 불확실성도 고려해야 한다. 몇 초 전에 생성된 예약 정보는 로봇이 속도를 늦추거나 장애물을 만나거나 위치 추정 정확도가 떨어지거나 통신 지연이 발생하면 실제 상황과 달라질 수 있다. 예약을 영구적으로 고정된 것으로 취급하는 대신 불확실성 여유(Uncertainty Margin)와 유효 시간 구간(Validity Interval)을 연결할 수 있다. 런타임 모니터링(Runtime Monitoring)은 예측 상태와 실제 상태를 비교하고 편차가 사전에 정의된 임계값을 초과하면 재계획을 실행할 수 있다.

공간-시간 A*는 전체 차량군 내비게이션 아키텍처에서 전술적 궤적 계획(Tactical Trajectory Planning) 구성요소로 통합할 수 있다. 임무 오케스트레이션(Mission Orchestration)은 운용 목표를 결정하고, 작업 할당(Task Allocation)은 어떤 로봇이 각 작업을 수행할지 결정하며, 전역 계획(Global Planning)은 전체적인 경로를 설정하고, 교통 조정(Traffic Coordination)은 공유 자원을 관리한다. 이후 공간-시간 A*는 이러한 제약을 만족하는 시간 일관적 경로(Time-Consistent Path)를 지역 또는 전술 수준에서 생성하고, 로컬 제어기(Local Controller)는 해당 궤적을 실행하며 독립적인 안전 계층(Safety Layer)은 물리적 움직임을 감독한다.

공간-시간 A*의 핵심 가치는 다중 로봇 내비게이션을 순수한 공간 문제에서 공간-시간 조정 문제(Space-Time Coordination Problem)로 전환한다는 데 있다. 두 로봇이 서로 다른 시간에 동일한 경로를 안전하게 사용할 수 있다면 반드시 서로 다른 경로를 선택할 필요는 없다. 대기, 시간적 점유, 에지 통과, 예약, 미래 충돌을 명시적으로 표현함으로써 공간-시간 A*는 협력적인 차량군 내비게이션을 위한 실용적인 기반을 제공한다. 궁극적인 성능은 적절한 시간 해상도, 탐색 지평, 휴리스틱 설계, 예약 관리, 그리고 상위 수준의 차량군 지능 및 하위 수준의 안전 제어와의 통합에 달려 있다.

07.05. Deadlock Detection and Resolution in Fleet [w/Code]

로봇 차량군(Robot Fleet)에서 교착 상태(Deadlock)는 두 대 이상의 로봇이 정상적으로 작동하고 서로 충돌하지도 않지만, 서로의 움직임을 방해하여 의미 있는 진행을 할 수 없는 상황을 의미한다. 직접적인 충돌과 달리 교착 상태는 물리적인 접촉 없이도 무기한 지속될 수 있다. 대표적인 상황으로는 좁은 복도에서 서로 마주 보는 로봇, 교차로에서 여러 로봇이 서로 대기하는 상황, 공유 자원 주변에서 차량들이 서로를 차단하는 상황 등이 있다. 따라서 신뢰성 있는 차량군 내비게이션(Fleet Navigation)을 위해서는 교착 상태 탐지(Deadlock Detection)와 해결(Resolution)이 필수적인 구성 요소이다.

교착 상태는 로봇 사이의 의존성 문제(Dependency Problem)로 이해할 수 있다. 로봇 A가 현재 로봇 B가 점유하고 있는 통로를 기다리고 있고, B는 로봇 C가 사용하는 영역을 기다리며, C는 다시 A가 사용하는 영역을 기다릴 수 있다. 각 로봇은 개별적으로 자신의 내비게이션 규칙을 정상적으로 따르고 있지만, 전체 시스템은 순환 의존성(Circular Dependency)에 빠진 상태가 된다. 따라서 단순한 충돌 회피만으로는 충분하지 않다. 차량군 내비게이션 시스템은 진행 상태(Progress), 대기 관계(Waiting Relationship), 자원 의존성(Resource Dependency), 현재 교통 상태가 스스로 해결될 가능성이 있는지를 함께 판단해야 한다.

교착 상태 분석에서 가장 유용한 표현 중 하나는 대기 그래프(Wait-for Graph, WFG)이다. 각각의 로봇을 하나의 노드(Node)로 표현하고, 로봇 A에서 로봇 B로 향하는 방향성 에지(Directed Edge)는 A가 B가 점유한 자원이나 공간 영역을 해제하기를 기다리고 있다는 것을 의미한다. A가 B를 기다리고, B가 C를 기다리며, C가 다시 A를 기다리는 것과 같은 방향성 사이클(Directed Cycle)이 그래프에서 발견되면 순환형 교착 상태(Circular Deadlock)가 발생했다는 강한 신호가 된다. 이 그래프는 예약(Reservation), 궤적(Trajectory), 로봇 상태가 변화함에 따라 지속적으로 갱신할 수 있다.

모든 장시간 대기가 교착 상태를 의미하는 것은 아니다. 로봇은 다른 로봇이 교차로를 빠져나가기를 기다리거나, 문이 열리기를 기다리거나, 우선순위가 높은 차량이 먼저 통과하기를 기다리는 것이 정상일 수 있다. 따라서 교착 상태 탐지기는 일시적인 정상 대기와 지속적인 진행 불능 상태를 구분해야 한다. 유용한 지표에는 대기 시간, 반복적인 진행 실패, 로봇 위치의 변화 없음, 차단된 자원의 지속 시간, 순환 의존성, 실질적인 개선 없이 반복되는 재계획 등이 포함된다.

시간 임계값(Time Threshold)은 의심스러운 동작을 탐지하는 간단한 방법이다. 로봇이 정의된 진행 기준(Progress Threshold)을 일정 시간 이상 충족하지 못하면 차량군 관리자는 해당 로봇을 잠재적인 차단 상태로 표시할 수 있다. 그러나 고정된 타임아웃(Fixed Timeout)은 모든 환경에 적합하지 않다. 작은 창고 교차로와 혼잡한 생산 시설에서는 정상적인 예상 대기 시간이 다르기 때문이다. 따라서 더욱 강건한 시스템은 타임아웃뿐만 아니라 공간적 의존성, 교통 밀도, 임무 긴급도, 과거 이동 패턴 등을 함께 사용한다.

교착 상태는 차량군 운용의 여러 수준에서 발생할 수 있다. 국부 교착 상태(Local Deadlock)는 하나의 복도나 교차로 주변에서 두세 대의 로봇 사이에 발생할 수 있으며, 지역 교착 상태(Regional Deadlock)는 여러 로봇과 연결된 여러 자원에 걸쳐 발생할 수 있다. 시스템 전체 교착 상태(System-Wide Deadlock)는 여러 구역에 혼잡이 전파되어 전체 차량군의 의미 있는 진행을 방해할 때 발생할 수 있다. 따라서 교착 상태 탐지 아키텍처는 모든 교착 상태가 하나의 로봇의 국부 궤적을 수정하는 것만으로 해결될 수 있다고 가정하지 않고 여러 공간적 수준을 지원해야 한다.

자원 예약(Resource Reservation)은 교착 상태의 주요 원인이다. 한 로봇이 좁은 통로에 진입하기 전에 downstream 영역을 예약하고, 다른 로봇이 동시에 첫 번째 로봇이 필요로 하는 통로를 예약할 수 있다. 두 로봇이 자신의 예약을 계속 유지하면서 서로 기다리면 어느 쪽도 진행할 수 없게 된다. 이를 보유 후 대기(Hold-and-Wait) 조건이라고 볼 수 있다. 이러한 상황을 방지하려면 예약 정책이 현재 점유하고 있는 자원뿐만 아니라 로봇이 계획된 이동을 완료하기 위해 앞으로 필요로 하는 자원까지 고려해야 한다.

우선순위 기반 내비게이션(Priority-Based Navigation) 역시 우선순위가 지나치게 엄격하게 적용되면 교착 상태를 발생시킬 수 있다. 높은 우선순위의 로봇이 공유 자원에 지속적으로 접근할 수 있도록 허용되면 낮은 우선순위 로봇이 그 뒤에 계속 쌓일 수 있다. 반대로 동적 우선순위 재조정(Dynamic Reprioritization)이 잘못 설계되면 우선순위가 계속 변경되어 안정적인 교통 흐름이 형성되지 않을 수 있다. 따라서 실제 시스템에서는 차단된 로봇에 대해 일시적인 우선순위 상승(Temporary Priority Escalation)을 허용하면서도 통제되지 않은 우선순위 진동(Priority Oscillation)은 방지해야 한다.

교착 상태 해결(Deadlock Resolution)은 어떤 의존성 또는 예약이 진행을 방해하고 있는지를 식별하는 것에서 시작한다. 차량군 관리자는 이후 계획을 수정해야 하는 하나 이상의 로봇을 선택할 수 있다. 가능한 조치에는 경로 재계획(Replanning), 안전한 대기 위치로 후퇴, 예약 취소, 통행권 변경, 다른 로봇의 이동 지연, 대체 통로 개방, 혼잡 구역에서 특정 로봇을 일시적으로 제거하는 방법 등이 있다. 선택된 개입은 차량군의 전체적인 운영을 최소한으로 방해하면서 의미 있는 진행 경로를 다시 확보할 수 있어야 한다.

국부적 복구(Local Recovery)는 교착 상태가 제한된 공간에서 발생했을 때 일반적으로 선호된다. 두 로봇이 좁은 복도에서 마주쳤다면 한 로봇을 사전에 정의된 대피 또는 통과 대기 위치로 후퇴시키고 다른 로봇이 계속 이동하도록 할 수 있다. 여러 로봇이 교차로를 경쟁하는 경우에는 낮은 가치의 예약을 취소하고 새로운 통과 순서를 설정할 수 있다. 이러한 국부 복구는 전체 차량군을 불필요하게 재계획하지 않기 때문에 계산 비용, 통신 부하, 운영 중단을 줄일 수 있다.

보다 복잡한 교착 상태는 전역 개입(Global Intervention)을 필요로 할 수 있다. 혼잡이 여러 구역으로 전파되면 하나의 로봇 경로만 변경하는 것이 문제를 다른 장소로 이동시키는 결과를 만들 수 있다. 이 경우 상위 수준 플래너는 작업 할당(Task Allocation), 전역 경로(Global Route), 자원 예약(Resource Reservation), 로봇 우선순위 등을 다시 검토할 수 있다. 충돌 기반 탐색(Conflict-Based Search, CBS), 최적화 기반 계획(Optimization-Based Planning), 중앙집중형 차량군 재계획(Centralized Fleet Replanning) 등을 단순한 복구 방법으로 진행을 회복할 수 없을 때 선택적으로 호출할 수 있다.

안전(Safety)은 교착 상태 해결과 독립적으로 유지되어야 한다. 복구 조치는 교통을 해소하기 위해 로봇에게 충돌 제약을 위반하거나, 출입 금지 구역에 진입하거나, 물리적 한계를 초과하거나, 사람의 존재를 무시하도록 지시해서는 안 된다. 로봇은 계속해서 국부 장애물 탐지(Local Obstacle Detection), 비상 정지(Emergency Stop), 속도 제한(Speed Restriction), 최소 분리 거리(Minimum Separation) 등의 안전 기능을 유지해야 한다. 따라서 교착 상태 복구는 독립적인 안전 계층(Safety Layer)이 설정한 범위 내에서 작동하는 운용 조정 기능(Operational Coordination Function)이다.

교착 상태 예방(Deadlock Prevention)은 반복적인 교착 상태 복구보다 효율적인 경우가 많다. 일방통행 규칙(One-Way Traffic Rule), 복도 예약(Corridor Reservation), 교차로 스케줄링(Intersection Scheduling), 선행 계획(Look-Ahead Planning), 제한된 자원 점유(Limited Resource Holding), 경로 다양화(Route Diversification), 진입 제어(Admission Control) 등을 활용하면 교착 상태 발생 가능성을 줄일 수 있다. 로봇이 제한된 구역에 진입하기 전에 플래너는 로봇이 이동을 완료할 수 있도록 충분한 downstream 공간이 존재하는지 확인할 수 있다. 이를 통해 로봇이 이후 영구적으로 차단될 수 있는 영역에 진입하는 것을 방지할 수 있다.

대규모 차량군에서는 교착 상태 관리(Deadlock Management)를 임무 오케스트레이션(Mission Orchestration) 및 차량군 수준 지능(Fleet-Level Intelligence)과 통합해야 한다. 동일한 위치에서 교착 상태가 반복적으로 발생한다면 이는 개별적인 내비게이션 실패가 아니라 시스템 아키텍처의 문제일 가능성이 있다. 시스템은 과거의 교착 상태 이벤트를 분석하여 문제가 있는 교차로, 부족한 대기 공간, 잘못된 경로 할당, 특정 작업에 대한 과도한 집중, 비효율적인 예약 정책 등을 식별할 수 있다. 이러한 분석 결과는 지도, 교통 규칙, 스케줄링 정책, 작업 할당을 개선하는 데 활용할 수 있다.

Physical AI 차량군 아키텍처에서는 교착 상태 탐지 및 해결을 교통 조정(Traffic Coordination)과 로컬 내비게이션(Local Navigation) 사이에 배치할 수 있다. 임무 오케스트레이션은 운용 목표를 정의하고, 작업 할당은 책임을 배분하며, 전역 계획은 경로를 설정하고, 교통 조정은 공유 자원을 관리한다. 교착 상태 모니터링(Deadlock Monitoring)은 진행 상태와 의존성을 지속적으로 평가하고, 필요한 경우 로컬 플래너가 복구 동작을 수행하도록 한다. 국부 복구가 실패하면 문제를 상위 수준 플래너로 전달하여 보다 광범위한 재계획을 수행할 수 있다.

교착 상태 관리의 궁극적인 목적은 단순히 로봇이 움직이지 않고 있다는 사실을 탐지하는 것이 아니다. 강건한 차량군 시스템은 발생 가능성이 높은 의존성 사이클을 사전에 인식하고, 정상적인 대기와 비정상적인 차단을 구분하며, 가장 작은 개입으로 효과적인 해결책을 선택하고, 실제로 진행 상태가 회복되었는지를 검증해야 한다. 대기 그래프(Wait-for Graph) 분석, 시간 모니터링(Temporal Monitoring), 예약 관리(Reservation Management), 우선순위 제어(Priority Control), 국부 복구(Local Recovery), 선택적 전역 재계획(Selective Global Replanning)을 결합하면 교착 상태 처리는 내비게이션이 실패한 이후에 추가되는 비상 기능이 아니라 차량군 지능(Fleet Intelligence)의 핵심 구성 요소가 될 수 있다.

07.06. Traffic Management Rules for Robot Intersections [w/Code]

로봇 교차로(Robot Intersection)의 교통 관리는 다중 로봇 차량군 내비게이션(Multi-Robot Fleet Navigation)의 핵심 구성 요소이다. 교차로는 여러 이동 궤적(Trajectory)이 제한된 공간에 집중되는 영역이기 때문이다. 각 로봇이 개별적으로 유효한 경로를 가지고 있더라도 동일한 교차로에 동시에 도착하면 충돌, 과도한 대기 또는 교착 상태(Deadlock)가 발생할 수 있다. 따라서 효과적인 교통 관리 시스템은 교차로를 공유 운영 자원(Shared Operational Resource)으로 취급하고 공간 점유, 도착 시간, 우선순위, 로봇의 능력, 안전 제약에 따라 접근을 조정해야 한다.

로봇 교차로는 내비게이션 그래프(Navigation Graph)의 구조화된 자원으로 표현할 수 있다. 진입 차선(Incoming Lane), 진출 차선(Outgoing Lane), 충돌 구역(Conflict Zone), 정지선(Stop Line), 대기 영역(Waiting Area), 예약 경계(Reservation Boundary)를 명시적으로 모델링하면 차량군 관리자가 로봇의 교차로 진입과 이탈을 결정할 수 있다. 이러한 표현은 연속적인 내비게이션 문제를 경로 선택, 자원 할당, 시간 스케줄링, 로컬 궤적 실행의 조합으로 변환한다. 또한 서로 다른 회전 동작이 서로 다른 충돌 패턴을 만들 수 있으므로 교차로 모델은 회전 이동(Turning Movement)도 표현해야 한다.

기본적인 규칙은 서로 호환되는 로봇 이동만 충돌 구역을 동시에 점유하도록 허용하는 것이다. 두 로봇이 교차하지 않는 궤적을 따라 이동한다면 동시에 교차로를 통과할 수 있지만, 서로 교차하는 궤적은 일반적으로 시간적 분리(Temporal Separation)가 필요하다. 따라서 교통 관리자는 어떤 이동 조합이 호환되는지를 나타내는 충돌 행렬(Conflict Matrix)을 유지할 수 있다. 이 행렬은 새롭게 도착한 로봇이 교차로에 진입할 수 있는지 또는 보호 구역 밖에서 대기해야 하는지를 결정하기 위한 경량화된 기반을 제공한다.

예약 기반 교차로 관리(Reservation-Based Intersection Management)는 실용적인 구현 방법 중 하나이다. 로봇은 예상 도착 시간, 의도한 이동 방향, 예상 통과 시간, 필요한 안전 여유(Safety Margin)를 제공하면서 교차로 접근을 요청한다. 교통 관리자는 기존 예약과 비교하여 사용 가능한 시간 창(Time Window)이 있는지를 평가하고, 가능하면 해당 시간 창을 승인하거나 더 늦은 시간 창을 제안한다. 승인된 경우에도 필요한 조건이 계속 유효할 때만 로봇이 충돌 구역에 진입할 수 있다. 오래된 계획이 교차로를 영구적으로 차단하지 않도록 예약에는 만료 및 취소 규칙이 있어야 한다.

우선순위 규칙(Priority Rule)은 여러 요청이 동일한 시간 창을 경쟁할 때 어떤 로봇이 접근 권한을 받을지를 결정한다. 우선순위는 임무 긴급도, 대기 시간, 안전 관련 작업, 적재 요구사항, 배터리 상태, 운용 구역, 사전에 정의된 서비스 정책 등에 따라 결정할 수 있다. 그러나 우선순위는 안전 제약을 위반할 수 있는 권한을 의미해서는 안 된다. 높은 우선순위의 로봇이 더 먼저 접근할 수는 있지만, 충돌 회피, 속도 제한, 정지 거리, 기타 물리적 안전 요구사항은 여전히 만족해야 한다.

공정성(Fairness)은 특정 로봇이 계속해서 우선권을 받는 것을 방지하기 때문에 중요하다. 순수하게 우선순위만 사용하는 시스템에서는 동일한 로봇이 반복적으로 선택되고 다른 로봇의 대기 시간이 계속 증가하여 기아 상태(Starvation)가 발생할 수 있다. 따라서 대기 시간을 동적 우선순위 계산에 포함할 수 있다. 일정 임계값을 초과하여 대기한 로봇에는 일시적인 우선순위 상승(Temporary Priority Escalation)을 적용하여 다음 우선순위 요청이 처리되기 전에 해당 로봇이 교차로를 통과할 수 있도록 할 수 있다.

정지선 관리(Stop-Line Management)는 경로 계획과 교차로 접근 권한 사이의 물리적 경계를 제공한다. 교차로에 접근하는 로봇은 로컬 플래너(Local Planner)가 충돌 없는 궤적을 생성했다는 이유만으로 충돌 구역에 진입해서는 안 된다. 접근 권한이 부여되지 않았다면 로봇은 지정된 대기 위치에서 정지해야 한다. 승인이 이루어지면 로컬 플래너가 예약된 구역을 통과하는 궤적을 생성한다. 이러한 분리는 교통 행동을 더욱 예측 가능하게 만들고, 조정된 이탈 계획 없이 로봇이 교차로 공간을 점유하는 것을 방지한다.

선행 계획(Look-Ahead Planning)은 교차로 교착 상태를 방지하는 데 특히 중요하다. 접근 권한을 부여하기 전에 교통 관리자는 로봇이 교차로에 진입한 이후 실제로 빠져나갈 수 있는지를 확인해야 한다. downstream 차선이 이미 다른 로봇에 의해 막혀 있는 경우 로봇이 충돌 구역에 진입하도록 승인해서는 안 된다. 그렇지 않으면 로봇이 교차로 내부에서 정지하여 다른 로봇의 이동까지 막을 수 있으며, 전체적인 교통 정체(Gridlock)를 발생시킬 수 있다. 따라서 교차로 진입 허가는 현재 교차로의 가용성뿐만 아니라 downstream 용량(Downstream Capacity)까지 고려해야 한다.

교통 규칙에는 방향 제어(Directional Control)도 포함할 수 있다. 교통량이 많은 시간에는 조정을 단순화하고 처리량(Throughput)을 높이기 위해 일시적인 일방통행(One-Way Traffic)을 설정할 수 있다. 좁은 공유 통로에서는 방향을 교대로 허용할 수 있으며, 서로 호환되지 않는 이동 패턴을 분리하기 위해 특정 회전 동작에 대한 전용 통과 시간 창(Dedicated Turning Window)을 설정할 수도 있다. 이러한 규칙은 플래너가 해결해야 하는 동시 충돌의 수를 줄이며, 교통 패턴이 비교적 예측 가능한 구조화된 창고, 공장, 병원, 물류 시설에서 특히 유용하다.

밀집된 차량군에서는 교차로 관리가 단순한 반응형 충돌 회피(Reactive Collision Avoidance)가 아니라 스케줄링(Scheduling)을 사용할 수 있다. 관리자는 향후 접근 요청의 대기열을 유지하고 처리량, 대기 시간, 우선순위, 공정성을 균형 있게 고려하여 통과 순서를 결정한다. 스케줄링 지평(Scheduling Horizon)은 다음 몇 초 또는 예정된 여러 대의 로봇 도착을 포함할 수 있다. 다만 실제 로봇의 도착 시간이 예측과 달라질 수 있으므로 스케줄은 유연하게 유지되어야 한다. 지속적인 갱신을 통해 로봇의 작은 지연이 발생하더라도 전체 교통 구조를 유지하면서 완전한 재계획을 피할 수 있다.

로봇과 교통 관리자 사이의 통신(Communication)은 예약 기반 제어에 필수적이다. 로봇은 현재 상태, 의도한 이동, 예상 도착 시간, 예약 상태를 제공해야 하며, 교통 관리자는 진입 승인, 시간 변경, 예약 취소 또는 경로 변경 지시를 전달해야 한다. 예약이 정확한 시간 창을 기반으로 하는 경우 시간 동기화(Time Synchronization)가 특히 중요하다. 타임스탬프가 포함된 메시지와 동기화된 시계는 계획된 교차로 점유 시간과 실제 점유 시간 사이의 모호성을 줄여준다.

통신 장애가 발생하더라도 안전하지 않은 행동으로 이어져서는 안 된다. 교차로에 접근하는 로봇이 연결을 잃으면 충돌 구역 앞에서 정지하는 것과 같은 사전에 정의된 안전 상태(Safe State)로 전환해야 한다. 보호 구역에 진입한 이후 통신이 끊어진 경우에는 교통 관리자와 주변 로봇이 사전에 정의된 성능 저하 운용 규칙(Degraded-Mode Rule)을 따라야 한다. 차량군 수준 통신과 관계없이 로컬 인지(Local Perception)와 안전 제어(Safety Control)는 계속 활성화되어야 한다. 교차로 진입 승인은 독립적인 물리적 충돌 방지를 대체할 수 없기 때문이다.

교차로 관리는 이기종 로봇(Heterogeneous Robot)도 고려해야 한다. 서로 다른 로봇은 크기, 속도, 가속 한계, 회전 반경, 제동 거리, 센서 능력이 다를 수 있다. 소형 AMR은 교차로를 빠르게 통과할 수 있지만 견인 로봇(Towing Robot)이나 대형 실외 플랫폼은 훨씬 더 많은 공간과 시간을 필요로 할 수 있다. 따라서 예약 시간과 안전 여유는 차량군 전체에 동일한 고정값을 사용하는 것이 아니라 개별 로봇의 특성에 따라 계산해야 한다.

교통 관리자는 공간-시간 A*(Space-Time A*), 충돌 기반 탐색(Conflict-Based Search, CBS), 우선순위 기반 계획(Priority-Based Planning)과 통합할 수 있다. 공간-시간 A*는 시간적 예약을 만족하는 경로를 생성할 수 있고, 우선순위 기반 계획은 어떤 로봇이 먼저 접근할지를 결정할 수 있다. 국부적인 교차로 규칙으로 해결하기 어려운 복잡한 상호작용에는 충돌 기반 탐색을 호출할 수 있다. 이러한 계층적 접근은 일반적인 교차로 상황마다 계산 비용이 높은 전역 계획을 사용할 필요를 줄이면서도 복잡한 교통 상황을 처리할 수 있는 능력을 유지한다.

교착 상태 탐지(Deadlock Detection)는 충돌이 발생하지 않는 교통 상황에서도 전체 이동이 완전히 정지할 수 있기 때문에 교차로 관리의 필수적인 부분이다. 시스템은 대기 시간, 로봇 위치의 변화 없음, 예약 의존성(Reservation Dependency), 대기 관계(Wait-for Relationship)를 모니터링할 수 있다. 로봇들이 순환 의존성을 형성하거나 허용 가능한 임계값을 초과하여 차단되면 교통 관리자는 선택된 예약을 취소하거나 우선순위를 변경하거나 후퇴 동작을 요청하거나 보다 광범위한 재계획을 실행할 수 있다. 복구 메커니즘은 먼저 가장 작은 규모의 국부 개입을 시도하고, 필요한 경우에만 차량군 수준 재계획으로 확대해야 한다.

성능은 교차로 수준과 차량군 수준에서 모두 평가해야 한다. 유용한 지표에는 평균 대기 시간, 최대 대기 시간, 교차로 처리량, 통과 시간, 대기열 길이, 예약 거부율, 교착 상태 발생 빈도, 경로 변경 빈도, 전체 차량군 임무 완료 시간 등이 포함된다. 높은 처리량만으로는 충분하지 않다. 공격적인 교차로 활용이 다른 구역의 혼잡을 증가시킬 수 있기 때문이다. 목표는 용량(Capacity), 안전성(Safety), 공정성(Fairness), 운용 효율성(Operational Efficiency)을 균형 있게 유지하면서 예측 가능한 교통 흐름을 만드는 것이다.

Physical AI 차량군 아키텍처에서 교통 관리는 전역 계획(Global Planning)과 로봇의 로컬 제어(Local Robot Control) 사이에 위치하는 전술적 조정 계층(Tactical Coordination Layer)으로 동작할 수 있다. 임무 오케스트레이션(Mission Orchestration)은 운용 목표를 정의하고, 작업 할당(Task Allocation)은 로봇의 책임을 결정하며, 전역 계획은 큰 범위의 경로를 설정하고, 교통 관리자는 공유되는 교차로 자원에 대한 접근을 제어한다. 이후 공간-시간 A*, 우선순위 규칙, 예약, 로컬 플래너가 협력하여 실행 가능한 이동을 생성하고, 독립적인 안전 기능(Independent Safety Function)이 물리적 실행을 지속적으로 감독한다.

로봇 교차로 관리의 장기적인 목표는 공유 공간 내비게이션(Shared-Space Navigation)을 순수하게 반응적인 방식이 아니라 예측 가능한 방식으로 만드는 것이다. 모든 로봇이 각각의 만남을 독립적으로 협상하도록 하는 대신, 차량군은 접근, 예약, 우선순위, 대기, 진입 허가, 복구에 대한 명시적인 규칙을 설정한다. 이러한 규칙을 시간적 계획, 교착 상태 관리, 통신 동기화, 독립적인 안전 제어와 결합하면 교차로를 조정된 차량군 자원으로 운영할 수 있으며, 고밀도 자율 로봇 운용을 위한 확장 가능한 기반을 제공할 수 있다.

07.07. Nav2 Multi Robot Namespace and Fleet Integration [w/Code]

Nav2 다중 로봇 네임스페이스 및 차량군 통합(Nav2 Multi-Robot Namespace and Fleet Integration)은 여러 로봇이 하나의 공유 시설에서 동시에 Navigation2(Nav2)를 실행할 때 필요한 소프트웨어 아키텍처를 다룬다. 각 로봇은 독립적인 내비게이션 컨텍스트(Navigation Context)를 필요로 하는 동시에 차량군은 지도, 위치 추정, 계획, 교통, 임무, 공유 자원을 조정해야 한다. 따라서 핵심적인 아키텍처 과제는 로봇별 상태와 차량군 수준 상태를 분리하면서도, 서로 다른 책임 영역 사이에 통제된 인터페이스를 제공하는 것이다. 잘 설계된 네임스페이스 아키텍처(Namespace Architecture)는 ROS 2 통신 계층에서 로봇별 격리를 제공하면서 차량군 조정을 위한 명확한 인터페이스를 허용한다.

ROS 2에서 네임스페이스(Namespace)는 서로 다른 로봇에 속하는 토픽(Topic), 서비스(Service), 액션(Action), 파라미터(Parameter), 노드 이름(Node Name)을 분리하는 기본적인 메커니즘이다. 하나의 로봇은 /robot_01\과 같은 네임스페이스에서 동작하고 다른 로봇은 /robot_02\에서 동작할 수 있다. 따라서 Nav2 노드, 센서, 위치 추정 구성요소, 컨트롤러, 플래너, 코스트맵(Costmap), 라이프사이클 관리자(Lifecycle Manager)를 각각 독립적으로 실행할 수 있다. 이를 통해 /cmd_vel\, /scan\, /odom\과 같은 동일한 토픽 이름이 여러 로봇을 동시에 의미하는 상황을 방지할 수 있다.

일반적인 다중 로봇 Nav2 아키텍처에서는 각 로봇에 독립적인 내비게이션 스택(Navigation Stack) 인스턴스를 제공한다. 로봇 네임스페이스에는 맵 서버(Map Server), 위치 추정 시스템(Localization System), 플래너 서버(Planner Server), 컨트롤러 서버(Controller Server), 비헤이비어 서버(Behavior Server), 웨이포인트 팔로워(Waypoint Follower), 속도 평활화기(Velocity Smoother), 코스트맵, 라이프사이클 관리자 등이 포함된다. 센서 토픽 역시 로봇 네임스페이스에 배치한다. 이러한 구조를 통해 각 로봇은 자신의 내비게이션 상태와 로컬 인지(Local Perception)를 유지하면서, 차량군 시스템은 개별 Nav2 내부 구성요소를 직접 제어하지 않고 명확하게 정의된 인터페이스를 통해 로봇과 통신할 수 있다.

TF 아키텍처(TF Architecture)는 각 좌표 프레임이 고유하고 올바르게 연결되어야 하기 때문에 특별한 주의가 필요하다. 일반적으로 각 로봇은 robot_01/base_link\, robot_01/odom\, robot_01/base_footprint\와 같은 자체 프레임 계층(Frame Hierarchy)을 갖는다. 전역 프레임(Global Frame)은 개념적으로 공유할 수 있지만 로봇별 변환(Transform)은 다른 로봇의 변환과 충돌해서는 안 된다. 잘 설계된 TF 트리를 사용하면 모든 로봇이 공통 시설 지도(Facility Map) 안에서 자신의 위치를 추정하면서도 독립적인 오도메트리(Odometry) 및 센서 좌표계를 유지할 수 있다.

지도와 위치 추정 아키텍처(Map and Localization Architecture)는 공유형 또는 부분 분산형으로 구성할 수 있다. 동일한 시설에서 운용되는 로봇이라면 공통 정적 지도(Common Static Map)를 모든 로봇에 제공할 수 있으며, 각 로봇은 해당 지도에 대한 자신의 위치 추정값을 독립적으로 유지한다. 다른 운용 환경에서는 서로 다른 로봇이 서로 다른 구역에서 운용되거나 서로 다른 지도 계층(Map Layer)을 사용할 수도 있다. 따라서 차량군 아키텍처는 모든 Nav2 구성요소를 중앙에서 공유해야 한다고 가정하기보다 공유 환경 정보와 로봇별 상태를 구분해야 한다.

핵심적인 설계 원칙은 로봇 로컬 내비게이션(Robot-Local Navigation)과 차량군 수준 조정(Fleet-Level Coordination)을 분리하는 것이다. Nav2는 로컬 경로 실행, 장애물 회피, 복구 동작, 컨트롤러 수준의 내비게이션 의사결정을 담당해야 한다. 반면 차량군 관리자는 임무 할당, 로봇 선택, 경로 조정, 교통 규칙, 공유 자원 예약, 충전 일정, 운용 우선순위 등을 담당해야 한다. 이러한 경계를 유지하면 차량군 로직이 개별 Nav2 스택의 내부 구현과 지나치게 강하게 결합되는 것을 방지할 수 있다.

다중 로봇 내비게이션에서는 전역 계획(Global Planning) 역시 신중하게 다루어야 한다. 모든 로봇이 동일한 정적 지도에 대해 독립적으로 계획하면서 다른 로봇의 의도된 경로를 알지 못한다면 교차로, 좁은 통로, 도킹 스테이션, 공유 작업 영역에서 서로 충돌하는 궤적이 생성될 수 있다. 따라서 차량군 조정 계층은 각 로봇에 경로 제약(Route Constraint), 예약(Reservation), 시간적 제한(Temporal Restriction), 우선순위 정보(Priority Information)를 제공할 수 있다. 이후 Nav2는 이러한 차량군 수준 제약 안에서 로컬적으로 유효한 경로를 실행한다.

통신 아키텍처(Communication Architecture)도 중요한 고려사항이다. ROS 2 토픽, 서비스, 액션은 로봇 내부 통신에 적합하며, 차량군 수준 시스템에서는 별도의 조정 인터페이스(Coordination Interface)를 추가로 사용할 수 있다. 차량군 관리자는 적절한 로봇 네임스페이스에 임무 명령과 내비게이션 목표를 전달하고, 각 로봇은 상태, 위치, 진행률, 배터리 상태, 내비게이션 상태, 고장 정보를 차량군 계층으로 보고할 수 있다. 인터페이스는 명시적으로 정의되어야 하며, 차량군 애플리케이션이 문서화되지 않은 Nav2 내부 토픽에 의존하지 않도록 해야 한다.

ROS 2 Domain ID와 DDS 통신 구성(DDS Communication Configuration) 역시 다중 로봇 배치에 영향을 미친다. 동일한 네트워크에서 동작하는 로봇은 DDS를 통해 서로를 자동으로 발견할 수 있으며, 이는 차량군 조정에는 유용하지만 불필요한 디스커버리 트래픽이나 과도한 토픽 가시성을 발생시킬 수도 있다. 네임스페이스 분리만으로 완전한 통신 격리가 이루어지는 것은 아니다. 따라서 대규모 차량군에서는 Domain 분할, DDS 파티션, 토픽 리매핑(Topic Remapping), 접근 제어(Access Control), 정교한 디스커버리 구성을 사용하여 로봇과 차량군 서비스 사이에서 어떤 정보가 보이는지를 제어할 수 있다.

시뮬레이션과 실제 배치 환경에서도 동일한 네임스페이스 원칙을 사용해야 한다. 시뮬레이션에서는 여러 로봇 모델을 서로 다른 네임스페이스, 독립적인 TF 트리, 센서 스트림, Nav2 인스턴스로 생성할 수 있다. 이를 통해 실제 로봇을 배치하기 전에 차량군 소프트웨어를 여러 대의 로봇으로 테스트할 수 있다. 시뮬레이션과 실제 로봇의 네임스페이스 규칙을 일관되게 유지하면 통합 과정에서 발생하는 차이를 줄일 수 있으며, 반복 가능한 다중 로봇 환경에서 차량군 알고리즘을 검증할 수 있다.

파라미터 관리(Parameter Management)는 로봇 수가 증가할수록 더욱 중요해진다. 각 로봇은 공통 Nav2 설정 템플릿을 공유하면서도 로봇의 풋프린트(Footprint), 속도 제한, 센서 토픽, 컨트롤러 특성, 안전 제약 등에 대해서는 개별 파라미터가 필요할 수 있다. 따라서 파라미터 계층(Parameter Hierarchy)을 사용하여 차량군 공통 기본값, 로봇 종류별 파라미터, 개별 로봇 오버라이드(Override)를 분리할 수 있다. 이렇게 하면 모든 로봇에 대해 완전히 독립적인 설정 파일을 유지하지 않으면서도 이기종 플랫폼에 필요한 차이를 반영할 수 있다.

라이프사이클 관리(Lifecycle Management)도 신중하게 조정해야 한다. Nav2는 라이프사이클 노드(Lifecycle Node)를 사용하여 시작, 구성, 활성화, 비활성화, 종료를 제어한다. 차량군 환경에서는 하나의 로봇이 자신의 내비게이션 스택을 재시작하거나 복구할 때 다른 로봇에 불필요한 영향을 주지 않아야 한다. 차량군 관리자는 각 로봇의 라이프사이클 상태를 모니터링하고 로봇 로컬 내비게이션 장애와 차량군 수준 서비스 장애를 구분해야 한다. 이러한 분리는 장애 격리(Fault Containment)를 지원하고 한 로봇이 복구 중인 동안 정상적인 다른 로봇들이 계속 작업할 수 있도록 한다.

차량군 통합 계층(Fleet Integration Layer)은 개별 Nav2 구현 위에 안정적인 로봇 추상화(Robot Abstraction)를 제공해야 한다. 차량군 관점에서 하나의 로봇은 능력(Capability), 현재 위치, 임무 상태, 가용성, 배터리 상태, 내비게이션 상태, 고장 상태 등으로 표현할 수 있다. 실제 로봇은 서로 다른 Nav2 플래너, 컨트롤러, 센서, 연산 플랫폼을 사용하더라도 차량군 수준 인터페이스는 변경되지 않을 수 있다. 이러한 추상화는 실내 AMR, 견인 로봇, 실외 플랫폼, 특수 서비스 로봇 등이 혼재하는 이기종 차량군(Heterogeneous Fleet)에서 특히 중요하다.

공유 자원(Shared Resource)을 관리하려면 추가적인 조정 메커니즘이 필요하다. Nav2만으로는 완전한 차량군 수준 교통 관리를 제공할 수 없기 때문이다. 엘리베이터, 좁은 통로, 교차로, 도킹 스테이션, 충전 구역, 상하차 구역, 제한 작업 공간 등을 차량군 자원으로 표현할 수 있다. 차량군 관리자는 예약 또는 시간적 제약을 전달하고, 개별 로봇의 Nav2 스택은 그 결과로 생성된 내비게이션 계획을 실행하는 역할을 담당한다. 이를 통해 자원 조정(Resource Coordination)과 물리적 궤적 실행(Physical Trajectory Execution) 사이에 명확한 계층 구조를 형성할 수 있다.

다중 로봇 복구(Multi-Robot Recovery) 역시 로컬 수준과 차량군 수준으로 분리해야 한다. Nav2 비헤이비어 트리(Behavior Tree)는 코스트맵을 초기화하거나, 재계획하거나, 후진하거나, 대기하거나, 다른 복구 행동을 선택함으로써 로컬 내비게이션 장애를 해결할 수 있다. 그러나 다른 로봇이 공유 통로를 막아서 발생한 장애라면 차량군 수준의 개입이 필요할 수 있다. 차량군 관리자는 우선순위를 변경하거나, 예약을 취소하거나, 다른 로봇을 우회시키거나, 교착 상태 해결(Deadlock Resolution)을 실행할 수 있다. 동일한 로컬 복구 행동을 반복적으로 실행하기보다는 장애의 원인에 맞는 차량군 수준의 조정을 수행해야 한다.

대규모 차량군에서는 네임스페이스 설계를 관측성(Observability) 및 운용 모니터링(Operational Monitoring)과 결합해야 한다. 각 로봇은 내비게이션 상태, 플래너 지연시간, 컨트롤러 상태, 위치 추정 품질, 장애물 상태, 통신 상태, 복구 이벤트 등에 대해 일관된 지표(Metric)를 제공해야 한다. 중앙 집중형 대시보드와 로깅 시스템은 로봇별 내부 네임스페이스를 통합하지 않고도 이러한 신호를 집계할 수 있다. 이를 통해 각 로봇의 내비게이션 스택 독립성을 유지하면서 차량군 수준의 진단을 수행할 수 있다.

Physical AI 차량군 아키텍처에서 Nav2는 완전한 차량군 지능(Fleet Intelligence) 시스템이 아니라 로봇 수준 실행 계층(Robot-Level Execution Layer)으로 취급하는 것이 적절하다. 임무 오케스트레이션(Mission Orchestration)은 운용 목표를 결정하고, 작업 할당(Task Allocation)은 책임을 배분하며, 차량군 계획(Fleet Planning)은 전역 경로와 우선순위를 설정하고, 교통 조정(Traffic Coordination)은 공유 자원을 관리한다. 그리고 각 로봇의 네임스페이스 기반 Nav2 스택은 로컬 계획과 실행을 담당한다. 이러한 역할 분리는 집단적인 차량군 지능과 개별 로봇 자율성 사이에 확장 가능한 인터페이스를 제공한다.

결과적으로 이러한 아키텍처는 격리(Isolation), 조정(Coordination), 상호운용성(Interoperability)이라는 세 가지 상호 보완적인 특성을 제공한다. 네임스페이스 격리는 ROS 2 소프트웨어 수준에서 로봇들이 서로 간섭하는 것을 방지한다. 차량군 조정은 로봇들이 경로, 자원, 우선순위, 운용 정보를 공유할 수 있도록 한다. 상호운용성은 서로 다른 로봇 플랫폼과 Nav2 구성이 공통 차량군 인터페이스를 통해 하나의 시스템에 참여할 수 있도록 한다. 이러한 원칙을 적절한 DDS 구성, TF 격리(TF Isolation), 라이프사이클 관리, 예약 메커니즘, 모니터링, 안전 제어와 결합하면 Nav2는 대규모 다중 로봇 차량군을 위한 강건한 실행 기반(Robust Execution Found...