HULK: Large-scale Hierarchical Coordination under Continual and Uncertain Temporal Tasks

기술 요약: HULK – 지속적이고 불확실한 시간적 작업 하의 대규모 계층적 조정

문제 제기
본 논문은 지속적이고 불확실한 시간적 작업 하에서 운영되는 대규모 이종 다중 에이전트 시스템의 조정 문제를 다룹니다. 정적이며 완전히 알려진 작업 집합을 오프라인 정수 계획법으로 해결한다고 가정하는 기존 접근법과 달리, 본 연구는 다음과 같은 시나리오를 고려합니다:

1. 온라인 생성되는 작업: 외부 수요에 따라 새로운 미션이 동적으로 발행되거나 취소되어 빈번한 계획 업데이트가 필요합니다.
2. 하위 작업의 불확실성: 미션 내 하위 작업의 정확한 수와 구체적인 위치는 발행 시점에 종종 알려지지 않습니다 (예: 구조 구역 내의 희생자 수 또는 배송 배치 내의 패키지 수).
3. 시간적 논리 제약: 작업은 협업 행위에 대한 구문론적 코-세이프 선형 시간 논리 (sc-LTL) 공식으로 지정되며, 복잡한 순서, 동시성, 그리고 자원 제약을 포함합니다.

기존의 중앙집중식 방법 (예: 혼합 정수 선형 계획법) 은 무한한 작업 시퀀스에 재귀적으로 적용될 때 계산적으로 처리 불가능해지며, 단순한 분산형 접근법은 전역 일관성과 최적성 확보에 어려움을 겪습니다.

방법론: HULK 프레임워크
저자들은 HULK(지속적이고 불확실한 시간적 작업 하의 대규모 계층적 조정) 를 제안합니다. 이는 전역 작업 할당과 지역 하위 작업 조정을 교차시키는 계층적 프레임워크입니다. 이 솔루션은 두 가지 명확한 계층에서 작동합니다:

1. 재귀적 지평 전역 작업 할당:

   • 분해: 온라인 미션은 sc-LTL 명세에 기반하여 부분적으로 순서화된 협업 작업 집합 (posets) 으로 분해됩니다.
   • 소그룹 형성: 개별 에이전트를 모든 작업에 할당하는 대신, 알고리즘은 최적의 소그룹 (subteams) 을 결정합니다. 유한 지평 ($H$) 내에서 작업 시퀀스를 소그룹에 할당하기 위해 검색 기반 알고리즘을 사용하여 용량 제약, 항해 비용, 작업 순서를 최적화합니다.
   • 중복 인식 할당: 혼합 정수 선형 계획법 (MILP) 솔버를 사용하여 특정 에이전트를 형성된 소그룹에 매핑하며, 각 소그룹 시퀀스의 첫 번째 작업에 대한 예상 시작 시간을 최소화합니다.

2. 동적 지역 하위 작업 조정:
   소그룹이 작업을 할당받으면, 하위 작업의 수와 위치가 불확실하다는 점에 맞춰 하위 작업의 특성에 맞는 지역 조정 전략을 실행합니다:

   • 정적 및 알려진 경우: 하위 작업의 위치와 수가 알려진 경우 (예: 표준 배송), 경로 최적화와 협업 행위를 최적화하기 위해 문제를 MILP 로 공식화합니다.
   • 정적 및 알려지지 않은 경우: 위치/수가 알려지지 않았으나 정적인 경우 (예: 수색 및 구조), 동시 탐색 및 조정 (SEC) 방법이 사용됩니다. 에이전트들이 하위 작업을 탐지하기 위해 지역을 탐색한 후, 탐지된 하위 작업을 배치로 할당하기 위한 롤링 할당 알고리즘이 수행됩니다.
   • 동적 및 알려진 경우: 하위 작업이 이동하는 경우 (예: 이동 표적 포획), 동적 연합 형성 (DCF) 전략이 사용됩니다. 에이전트들은 표적을 포위하기 위해 연합을 형성하고, 하위 작업이 완료됨에 따라 연합 계획을 업데이트합니다.

온라인 적응 및 재계획
프레임워크는 특정 조건에 따라 재계획 (전역 할당의 재실행) 을 트리거합니다:

• 할당된 지평 작업의 절반 이상이 완료된 경우.
• 새로운 미션이 발행된 경우.
• 소그룹의 지역 조정이 실행 불가능한 솔루션을 반환한 경우.
  중요하게는, 안정성을 보장하기 위해 현재 실행 중인 작업은 선점되지 않습니다.

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

1. 적용 가능성: 계층적 알고리즘은 이종 에이전트, 시간적 논리 명세, 그리고 협업 행위를 지원합니다.
2. 강건성: 시스템은 작업의 지속적 발행, 에이전트 고장의 조건부 발생, 그리고 하위 작업 수량과 위치의 불확실성에 대해 강건합니다.
3. 확장성 및 효율성: 이 접근법은 재귀적 지평 접근법과 지역 조정을 활용하여 전체 작업 집합에 대한 전역 최적화의 지수적 복잡성을 피함으로써 계산적으로 효율적입니다.

실험 결과
이 방법은 30 개의 미션 (492 개의 하위 작업 포함) 을 수행하는 80 대의 이종 에이전트 (A, B, C 형) 함대에 대한 시뮬레이션으로 검증되었습니다.

• 성능: 제안된 방법은 100% 성공률을 달성했으며, 평균 응답 시간은 62.7 초였습니다.
• 비교: 기준선 (C-MILP, 샘플링 기반 계획자, 탐욕적 접근법) 과 비교하여 HULK 는 훨씬 낮은 계획 시간을 보였으며 (C-MILP-1 보다 약 50 배 빠름) 더 높은 성공률을 입증했습니다.
• 확장성: 함대 규모 (최대 150 대 에이전트) 와 작업 수를 증가시킨 테스트에서 계획 시간은 미미하게만 증가했습니다 (예: 평균 1.6 초에서 1.8 초로), 에이전트 고장률 5% 에서도 100% 성공률을 유지했습니다.
• 효율성: 계층적 접근법은 무한 지평 방법의 경우 금지 수준 (>15 분) 이었던 최대 계획 시간을 5 초 미만으로 줄였습니다.

의의
본 논문은 HULK 를 실제 세계의 동적 환경에서 운영되는 다중 에이전트 시스템에 필수적인 진화로 위치시킵니다. 불확실한 매개변수를 가진 지속적 작업 스트림에는 정적 오프라인 솔루션이 부적절하다고 주장합니다. 전역 할당과 지역 실행을 분리하고 특수화된 조정 전략을 통해 불확실성을 처리함으로써, HULK 는 대규모 팀이 상시적인 전역 재계산 없이도 효율적이고 강건하게 운영될 수 있게 합니다. 이 연구는 불확실하고 시간적인 영역에서 계산적 처리 가능성과 전역 미션 만족 필요성 사이의 균형을 맞추기 위해 계층적 조정이 필수적임을 강조합니다.