HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel

이 논문은 예산과 다양성 같은 제약 조건을 가진 장거리 여행 계획 문제를 해결하기 위해, 전략적 조정과 병렬 실행을 결합하고 거래형 모니터링 및 협상 프로토콜을 통해 제약 준수를 보장하는 계층적 다중 에이전트 프레임워크 'HiMAP-Travel'을 제안하며, TravelPlanner 벤치마크에서 기존 Sequential 기반 방법론들을 크게 능가하는 성능을 입증합니다.

핵심

HiMAP-Travel: 여행 계획을 잘 짜는 '팀워크'의 비밀

이 논문은 인공지능 (AI) 이 장거리 여행을 계획할 때 자주 겪는 실수를 해결한 새로운 방법을 소개합니다. 마치 혼자서 모든 일을 다 하려다 지쳐서 실수하는 사람과 각자 역할을 나누어 맡아 완벽하게 협동하는 팀의 차이점을 설명한다고 생각하시면 됩니다.

🎒 문제: "혼자서 모든 걸 하려다 망친다" (기존 방식의 한계)

기존의 AI 여행 계획 프로그램은 보통 한 명의 AI가 처음부터 끝까지 모든 일정을 순서대로 짰습니다.

• 상황: 1 일차부터 7 일차까지 계획을 세우는데, 1 일차에 너무 비싼 호텔을 예약해서 2 일차에 돈이 모자라게 됩니다.
• 문제: AI 는 1 일차 계획을 세울 때는 "돈이 충분해"라고 생각했지만, 5 일차나 6 일차가 되면 기억이 흐려져서 (Context Drift) 처음에 정한 "총 예산 100 만 원"이라는 규칙을 잊어버립니다.
• 결과: 여행 계획이 중간에 깨지거나, 예산을 초과하는 엉뚱한 결과가 나옵니다.

🏗️ 해결책: HiMAP-Travel (팀워크와 역할 분담)

이 논문은 HiMAP-Travel이라는 새로운 시스템을 제안합니다. 이는 한 명의 천재가 모든 것을 하는 대신, **팀장 (Coordinator)**과 **현장 직원들 (Executors)**이 협력하는 방식입니다.

1. 역할 분담 (팀장 vs 현장 직원)

• 팀장 (Coordinator): "이번 여행은 총 3 일이고, 예산은 1700 달러야. 1 일차는 이동, 2 일차는 관광, 3 일차는 귀가야. 그리고 1 일차 예산은 600 달러 정도로 잡아줘."라고 **큰 그림 (전략)**을 그립니다.
• 현장 직원들 (Executors): 팀장이 준 지침을 바탕으로 각 날짜별로 독립적으로 계획을 세웁니다.
  • 1 일차 팀원: "네, 1 일차만 집중해서 비행기 표와 저렴한 호텔을 찾겠습니다."
  • 2 일차 팀원: "저는 2 일차만 집중해서 맛집과 관광지를 찾겠습니다."
  • 장점: 1 일차 팀원이 2 일차 팀원의 일을 방해하지 않고, 서로의 기억 (문맥) 이 섞이지 않아 실수가 줄어듭니다.

2. 공유된 지갑 (동기화된 전역 상태)

여러 팀원이 동시에 일할 때 가장 큰 문제는 돈을 두 번 쓰는 것입니다.

• 문제: 1 일차 팀원이 호텔을 예약하고, 2 일차 팀원도 같은 호텔을 예약할 수 있습니다.
• 해결책 (동기화된 지갑): 모든 팀원은 **하나의 공유된 지갑 (Global State)**을 봅니다.
  • 1 일차 팀원이 호텔을 예약하면, 지갑에서 그 호텔 이름이 "예약됨"으로 표시되고 돈이 차감됩니다.
  • 2 일차 팀원이 같은 호텔을 찾으려 하면, 시스템이 **"이미 예약됐어요!"**라고 즉시 경고합니다.
  • 이는 마치 실시간으로 공유되는 엑셀 시트처럼 작동하여, 중복 예약이나 예산 초과를 막아줍니다.

3. 협상과 수정 (Bargaining Protocol)

만약 팀장이 "1 일차에 뉴욕으로 가라"고 지시했는데, 현장 직원이 "뉴욕은 너무 비싸서 예산이 부족합니다!"라고 말하면 어떨까요?

• 기존 방식: 그냥 무조건 따르다가 나중에 예산이 모자라게 됩니다.
• HiMAP-Travel 방식: 현장 직원이 **"이건 불가능합니다. 예산이 200 달러 부족해요"**라고 정중하게 보고합니다.
• 팀장의 반응: 팀장은 즉시 계획을 수정합니다. "알겠어, 뉴욕 대신 더 저렴한 시카고로 바꾸자."
• 이 협상 과정을 통해 처음부터 불가능한 계획을 바로잡아 줍니다.

🚀 왜 이 방식이 더 좋은가요?

1. 병렬 처리 (동시 작업): 3 일짜리 여행을 계획할 때, 1 일차, 2 일차, 3 일차 팀원이 한 번에 동시에 계획을 세웁니다. 기존 방식처럼 하나씩 순서대로 하면 시간이 3 배 걸리지만, 이 방식은 2.5 배 이상 빨라집니다.
2. 실수 방지: 팀장이 예산을 미리 나누어 주고, 공유 지갑이 중복을 막아주므로, 여행이 끝날 때까지 예산을 지키는 능력이 훨씬 뛰어납니다.
3. 학습 효과: 이 시스템은 GRPO라는 학습 방법을 통해, 팀장과 직원들이 서로의 역할을 배우며 더 똑똑해집니다.

📊 실제 성과

이 시스템을 테스트한 결과, 기존 방식 (DeepTravel) 보다 성공률이 8.67% 더 높았고, 특히 예산을 지키는 능력은 약 2 배나 개선되었습니다. 또한, 여행 일정이 길어질수록 실수가 늘어나는 기존 방식과 달리, 이 방식은 일정이 길어져도 실수가 거의 늘지 않았습니다.

💡 요약

HiMAP-Travel은 "혼자서 모든 걸 하려다 지치는 AI"를 **"팀장님이 큰 그림을 그리고, 직원들이 동시에 일하며 서로의 실수를 막아주는 팀"**으로 바꾼 것입니다. 이를 통해 복잡한 여행 계획도 빠르고 정확하게, 예산을 지키며 완성할 수 있게 되었습니다.

기술 요약

1. 문제 정의 (Problem Statement)

• 배경: 대규모 언어 모델 (LLM) 기반 에이전트는 짧은 범위의 작업에서는 탁월한 성능을 보이지만, 엄격한 제약 조건 (예산, 다양성, 시간적 일관성 등) 이 있는 장기 계획 (Long-Horizon Planning) 작업에서는 취약합니다.
• 핵심 문제: 제약 조건 드리프트 (Constraint Drift under Long Tool Traces)
  • 기존의 단일 에이전트 (Sequential Monolithic) 아키텍처 (예: ReAct, Chain-of-Thought) 는 계획이 길어질수록 툴 출력과 추론 로그가 누적되어 컨텍스트 길이가 증가합니다.
  • 이로 인해 모델이 초기에 설정된 전역 제약 조건 (예: 총 예산) 에 대한 주의를 잃고, 국소적 일관성 (Local Coherence) 에만 집중하게 됩니다.
  • 결과적으로 계획의 후반부 (예: 여행 5 일차) 로 갈수록 예산 초과나 중복 예약과 같은 치명적인 오류가 발생하여 전체 계획의 실패율이 급증합니다.
• 기존 방법의 한계: "생성 후 수정 (Generate-then-Fix)" 방식 (예: ATLAS) 은 전체 계획을 생성한 후 제약 조건을 검증하고 수정하는 방식으로, 계산 비용이 비효율적이며 지연 시간 (Latency) 이 계획 길이에 따라 2 차 함수적으로 증가합니다.

2. 방법론 (Methodology: HiMAP-Travel)

저자들은 HiMAP-Travel이라는 계층적 다중 에이전트 프레임워크를 제안하여 문제를 해결합니다. 핵심 아이디어는 전략적 조정 (Strategic Coordination) 과 전술적 실행 (Tactical Execution) 을 구조적으로 분리하고 병렬화하는 것입니다.

2.1. 계층적 아키텍처

• 조정자 (Coordinator, 전략적 레벨):
  • 사용자의 전체 여행 요청을 분석하여 일별 하위 목표 (Sub-goals) 로 분해합니다.
  • 전역 예산을 일별로 할당하고, 도시 선택 및 이동 경로의 대략적인 구조를 설정합니다.
  • 각 일 (Day) 에 대한 '소프트 가이드라인' (예: 일별 예산 힌트) 을 제공합니다.
• 실행자 (Executors, 전술적 레벨):
  • 조정자가 할당한 일별 목표에 따라 병렬 (Parallel) 로 개별 일별 일정을 생성합니다.
  • 각 실행자는 격리된 컨텍스트 윈도우에서 작동하여, 다른 날의 추론 로그에 영향을 받지 않습니다.

2.2. 세 가지 핵심 메커니즘

1. 동기화된 전역 상태 (Synchronized Global State, $\Sigma$):
   • 병렬 실행 중 발생할 수 있는 자원 충돌 (예산 초과, 장소 중복 예약 등) 을 방지하기 위한 원자적 트랜잭션 모니터입니다.
   • 모든 에이전트가 공유하는 상태 (사용된 예산, 예약된 장소 집합, 이동 수단 잠금) 를 유지하며, CHECK 및 COMMIT 연산을 통해 제약 조건 위반 시 즉시 거부하고 재시도를 유도합니다.
   • 이는 "공지의 비극 (Tragedy of the Commons)"을 방지하고 결정론적 (Deterministic) 인 안전성을 보장합니다.
2. 협력적 협상 프로토콜 (Cooperative Bargaining Protocol):
   • 실행자가 할당된 하위 목표가 비현실적 (예: 예산 부족) 인 경우, 조정자에게 구조화된 피드백 (JSON 형식의 위반 유형 및 부족분) 을 전송합니다.
   • 조정자는 이 피드백을 받아 도시 변경, 경로 재조정 등 역할 재할당을 수행하고 재계획을 시도합니다.
   • 이는 단순한 대화 방식이 아닌, 효율적인 신호 교환을 통해 재계획 오버헤드를 최소화합니다.
3. 통합 역할 조건부 정책 (Unified Role-Conditioned Policy):
   • 조정자와 실행자가 별도의 모델을 사용하는 것이 아니라, 단일 정책 ($\pi_\theta$) 을 공유합니다.
   • 시스템 프롬프트의 역할 조건 (Role Conditioning) 을 통해 동일한 모델이 전략적 조정자나 전술적 실행자로서 행동합니다.
   • GRPO (Group Relative Policy Optimization) 를 사용하여 학습하며, 메모리 효율적인 FIFO 업데이트 메커니즘을 통해 다중 에이전트 학습의 메모리 부담을 줄였습니다.

3. 주요 기여 (Key Contributions)

1. 제약 조건 드리프트의 규명 및 해결: 단일 순차 아키텍처의 근본적인 실패 모드를 식별하고, 계층적 분해를 통해 이를 해결하는 새로운 패러다임 ("Correct-by-Construction") 을 제시했습니다.
2. 시스템 혁신의 통합: 동기화된 제약 조건 강제, 구조화된 협상, 통합 정책 학습이라는 세 가지 메커니즘을 결합하여 병렬 실행 중에도 전역 일관성을 유지하도록 했습니다.
3. 최신 성능 달성 (SOTA): TravelPlanner 및 FlexTravelBench 벤치마크에서 기존 최상위 방법론들을 압도하는 성능을 기록했습니다.

4. 실험 결과 (Results)

• TravelPlanner 벤치마크:
  • Qwen3-8B 모델을 사용하여 **테스트 최종 통과율 (FPR) 52.65%**를 달성했습니다.
  • 기존 순차적 RL 기반 베이스라인 (DeepTravel) 보다 +8.67%p 향상되었으며, ATLAS 대비 +17.65%p, MTP 대비 +10.0%p 높은 성능을 보였습니다.
  • 지연 시간 (Latency) 2.5 배 감소: 병렬 실행을 통해 7 일 여행 계획 수립 시간을 189.5 초에서 72 초로 단축했습니다.
• FlexTravelBench (다중 턴 적응):
  • 제약 조건이 점진적으로 추가되는 시나리오에서도 2 턴 (44.34%) 및 3 턴 (37.42%) 에서 높은 성능을 유지하며, 협상 프로토콜의 효과성을 입증했습니다.
• 안정성:
  • 시드 (Seed) 간 변동성이 DeepTravel (std 7.18%) 대비 HiMAP-Travel (std 0.48%) 에서 93% 감소하여 매우 안정적인 수렴을 보였습니다.
• Ablation Study:
  • 동기화된 상태 ($\Sigma$) 제거 시 FPR 9.58%p 감소, 조정자 제거 시 12.98%p 감소 등 각 구성 요소의 필수성을 입증했습니다.

5. 의의 및 결론 (Significance)

• 이론적 의의: 장기 계획 문제에서 "생성 후 수정"의 비효율성을 극복하고, "구축 중 수정 (Correct-by-Construction)"을 통해 제약 조건을 사전에 강제하는 새로운 아키텍처를 제시했습니다.
• 실용적 확장성: 여행 계획뿐만 아니라 소프트웨어 모듈 개발, 공급망 최적화, 과학적 실험 설계 등 복잡한 자원 조정이 필요한 모든 장기 계획 작업에 적용 가능한 범용적인 프레임워크를 제공합니다.
• 학습 가능성: 단일 정책을 공유하며 GRPO 를 통해 엔드 - 투 - 엔드 학습이 가능한 최초의 계층적 다중 에이전트 프레임워크로서, 확장 가능한 계획 에이전트 개발의 새로운 길을 열었습니다.

요약하자면, HiMAP-Travel 은 병렬 실행의 효율성과 전역 제약 조건의 엄격한 통제를 동시에 달성하여, 기존 LLM 에이전트들이 겪던 장기 계획의 취약점을 해결한 획기적인 연구입니다.