기술 요약: HECTOR – 로봇 군집의 인간 중심 계층적 조정 및 감독

1. 문제 제기

본 논문은 동적이고 부분적으로 알려지지 않은 환경에서 지속적인 시간적 작업 하에 대규모 이종 로봇 군집 (예: UAV 및 UGV) 을 조정하는 과제를 다룹니다. 로봇 군집은 협력을 통해 효율성을 제공하지만, 개별 장치를 직접 인간이 제어하는 것은 비현실적입니다. 기존 접근 방식은 종종 다음 세 가지 중요한 격차를 동시에 해결하지 못합니다:

1. 동적 온라인 상호작용: 대부분의 방법은 정적이고 사전 정의된 작업 집합을 가정하여, 운영자가 실시간으로 미션을 추가, 취소 또는 우선순위를 재조정할 필요성을 간과합니다.
2. 불확실성 하의 확장성: 전통적인 중앙 집중식 계획 (예: MILP) 은 결합적 폭발 (combinatorial explosion) 로 고통받는 반면, 분산형 방법은 복잡한 시간적 제약에 대한 보장을 제공하지 못하거나 불확실한 서브작업 수와 위치를 처리하지 못합니다.
3. 인간 - 루프 통합: 현재 프레임워크는 종종 인간 상호작용을 사후 고려사항으로 취급하거나 소규모 팀으로만 제한하여, 대규모 작전에서의 고위급 감독 및 개입을 위한 프로토콜이 부족합니다.

핵심 목표는 선형 시간 논리 (LTL) 명세, 용량 제약, 그리고 동적 운영자 요청 (새로운 미션, 취소, 우선순위 변경, 수동 재할당) 을 만족시키면서 평균 미션 응답 시간을 최소화하는 집단 계획을 수립하는 것입니다.

2. 방법론: HECTOR 프레임워크

제안된 솔루션인 HECTOR는 글로벌 조정을 로컬 실행과 분리하여 확장성과 강력한 인간 상호작용을 가능하게 하는 3 계층 계층 구조 아키텍처를 사용합니다.

계층 I: 인간 - 군집 상호작용 프로토콜

이 계층은 운영자가 4 가지 유형의 온라인 요청을 발행할 수 있도록 하는 양방향 멀티모달 인터페이스 (텍스트, 음성, 템플릿) 를 구축합니다:

• $\kappa_1$ (새로운 미션): 불확실한 서브작업 수와 위치를 가진 새로운 sc-LTL (구문론적으로 안전한 LTL) 명세를 발행합니다.
• $\kappa_2$ (취소): 진행 중인 작업을 방해하지 않고 미완성 미션을 제거합니다.
• $\kappa_3$ (수정): 기존 미션의 마감일과 우선순위를 업데이트합니다.
• $\kappa_4$ (재할당): 특정 로봇을 특정 미션에 수동으로 할당합니다.
  이 프로토콜은 이러한 요청을 작업 분해 모듈 및 시각화 인터페이스에 매핑하여 군집 상태 및 계획 실행 가능성에 대한 폐루프 피드백을 보장합니다.

계층 II: 후퇴형 시간 범위 (Receding-Horizon) 작업 할당 및 팀 구성

이 계층은 로봇 모델과 작업 오토마타의 전체 동기식 곱 (계산적으로 금지적임) 대신 오토마타 기반 검색 트리를 사용하여 미션을 팀에 글로벌하게 할당합니다.

• 동시 분해 및 할당: 이 알고리즘은 노드가 부분 팀 계획과 미션 오토마타의 현재 도달 가능 상태를 나타내는 트리에서 검색합니다. 이는 최적의 팀 수 ($K$), 그 구성, 그리고 작업 순서를 동시에 결정합니다.
• 값 함수 및 경계 설정: 휴리스틱 값 함수 $\chi(\nu)$는 작업 완료 시간, 비용, 그리고 미션 진행 상황을 균형 있게 조절합니다. 노드는 성능 프로파일 $\zeta(\nu)$에 기반한 우위 관계 (dominance relation) 를 사용하여 가지치기되어, 검색이 비우세 프론티어에 집중되도록 보장합니다.
• 후퇴형 시간 범위: 동적 업데이트를 처리하기 위해 계획기는 유한한 시간 범위 $H$로 작동합니다. $H$개의 작업이 할당되면 일시 정지하고, 재계획 트리거 (예: 작업 완료, 새로운 요청, 또는 비실행 가능성) 가 발생하면 재개합니다.
• 중복 인식 팀 구성: 작업이 추상적 팀에 할당되면, 혼합 정수 선형 계획법 (MILP) 수식이 특정 로봇을 할당합니다. 이 단계는 서브작업 불확실성과 잠재적 로봇 고장을 고려하기 위해 중복 마진($\alpha$) 을 포함하며, 용량 제약을 만족하면서 팀 구성원을 분리되게 보장합니다.

계층 III: 팀 내 로컬 조정

팀에 할당된 작업이 주어지면, 이 계층은 서브작업의 성격에 따라 서브작업 실행 및 궤적 생성을 조정합니다:

1. 정적 및 알려진: 다중 차량 경로 문제 (MVRP) 를 해결합니다. 비홀로노믹 로봇의 경우, 운동 원시 (예: 더빈스 곡선) 와 하이브리드-A* 검색을 사용하여 궤적과 작업 순서를 동시에 최적화합니다.
2. 정적 및 알려지지 않은: 동시 탐사 및 조정 (SEC) 전략을 사용합니다. 로봇은 협력적으로 지역을 커버하여 서브작업을 드러내고, 발견된 서브작업을 로컬 계획에 동적으로 삽입하여 작업 완료 시간의 방해를 최소화합니다.
3. 동적 및 알려진: 분산 동적 연합 형성 (DCF) 알고리즘을 사용합니다. 로봇은 이동하는 표적을 추적하기 위해 로컬 비용 추정 및 동료 통신에 기반하여 연합 구성원을 업데이트하며, 분리된 연합과 균형 잡힌 작업 부하를 보장합니다.

3. 주요 기여

본 논문은 두 가지 주요 기여를 주장합니다:

1. 유연하고 확장 가능한 프레임워크: HECTOR 는 운영자가 불확실한 환경에서 대규모 이종 군집과 상호작용하고 조정할 수 있게 합니다. 이는 고위급 시간 논리 미션과 로컬 운동 실행 가능성 간의 상호작용을 명시적으로 처리합니다.
2. 실용적 측면의 명시적 처리: 이 프레임워크는 이종 기능, 매개변수화된 협력 유틸리티, 시간적 제약, 그리고 서브작업 분포의 변이성을 통합합니다. 이는 미션 변경 시 전체 시스템 재구성이 필요하지 않도록 하는 온라인 인간 개입을 위한 구체적인 프로토콜을 도입합니다.

4. 실험 결과

동적 환경에서 80 개의 이종 로봇이 30 개의 미션 (450 개의 서브작업) 을 수행하는 광범위한 인간 - 루프 시뮬레이션이 수행되었습니다.

• 성능 대 기준선: HECTOR 는 총 미션 응답 시간을 184.4 초로 달성하여, 중앙 집중식 MILP (327.8 초) 및 샘플링 기반 방법 (286.0 초) 을 크게 능가했습니다. 불확실성을 무시하는 방법들 (예: SAMP-Subtask, Flow) 이 86~96% 로 하락한 반면, 100% 성공률을 유지했습니다.
• 계산 효율성: 평균 계획 시간은 0.46 초 (최대 0.76 초) 였으며, 이는 계획 시간이 최대 415.8 초까지 소요된 무한 시간 범위 기준선 (Inf-H) 에 비해 계층적 접근법의 효율성을 입증했습니다.
• 확장성 및 견고성: 최대 170 개의 로봇과 100 개의 작업으로 수행된 테스트에서 로봇 고장률이 10% 일지라도 계획 시간이 2.0 초 미만으로 유지됨을 보여주었습니다. 시스템은 미션 성공을 잃지 않고 자원을 재할당하여 고장에서 성공적으로 복구했습니다.
• 고충실도 검증: 재해 구호 시나리오에서 12 대의 UAV 를 사용한 ROS 기반 시뮬레이션은 프레임워크가 실제 세계의 동적 특성, 곡률 제약, 그리고 실시간 운영자 개입 (취소, 재할당, 마감일 변경) 을 처리할 수 있음을 확인했습니다.

5. 중요성 및 주장

본 논문은 HECTOR 를 다중 로봇 시스템의 필수적인 진화로 위치시켜, 이론적 시간 논리 계획과 실용적 대규모 배포 간의 격차를 해소합니다.

• 실용적 관련성: 작업이 진화하고 불확실성이 내재된 재해 구호, 감시, 배송 분야에서 운영자가 군집을 관리해야 하는 "실용적 필요"를 해결합니다.
• 계층을 통한 효율성: 팀 구성, 작업 할당, 로컬 조정을 분리함으로써 전역 합성의 이중 지수적 복잡성을 피하면서도 정확성 보장을 유지합니다.
• 인간 중심 설계: 완전 자동화 시스템과 달리, HECTOR 는 "간결한 통신"과 고위급 감독을 명시적으로 지원하여 운영자가 로우 레벨 세부 사항에 압도되지 않고 효과적으로 개입할 수 있게 합니다.
• 한계: 저자들은 현재 작업이 "동적이고 알려지지 않은" 작업 (서브작업 위치와 수가 동시에 알려지지 않고 변화하는 경우) 을 다루지 않는다고 겸손하게 지적합니다. 이는 여기서 완전히 탐구되지 않은 탐사와 동적 연합 전략의 조합을 필요로 하기 때문입니다. 또한, 통신 제약 (지연, 패킷 손실) 은 향후 개선이 필요한 영역으로 인정됩니다.