HiMAP-Travel: 장기 제약 조건 여행 계획을 위한 계층적 멀티 에이전트 계획 프레임워크

기존 LLM 에이전트는 계획이 길어질수록 예산 같은 중요한 제약 조건을 잊어버리는 문제를 겪는다. HiMAP-Travel은 전략과 실행을 분리하고 병렬 처리를 도입하여 이 문제를 해결하고 복잡한 일정 수립의 정확도와 속도를 동시에 개선한다.

Transformer 기반 LLM은 시퀀스가 길어질수록 Attention 메커니즘이 초기 토큰보다 최근 토큰에 더 집중하게 된다. 여행 계획처럼 기간이 길어지면 도구 호출 결과와 추론 과정이 Context Window에 쌓이면서, 정작 중요한 전체 예산이나 중복 금지 같은 초기 제약 조건에 대한 집중도가 낮아지는 제약 조건 표류가 발생한다. HiMAP-Travel은 이를 해결하기 위해 문제를 계층화하여 Coordinator가 전체 자원을 배분하고, 여러 Executor가 각자의 날짜를 병렬로 처리하게 한다. 각 Executor는 자신의 날짜에 해당하는 짧은 Context만 유지하면 되므로 제약 조건에 대한 집중력을 잃지 않는다. 병렬 실행 중 발생하는 자원 충돌은 외부의 동기화된 전역 상태 모니터가 관리한다. 이는 에이전트가 행동을 확정하기 전에 예산과 중복 여부를 원자적으로 검사하여, 오류가 발생한 후에 수정하는 것이 아니라 생성 단계에서부터 오류를 방지하는 구조를 실현한다.

시스템은 Strategic Level(Coordinator)과 Tactical Level(Executors)로 나뉜다. Coordinator는 사용자 쿼리를 분석해 일별 하위 목표와 예산 힌트($b_d$)를 생성한다. [일별 예산 힌트 $b_d$들을 입력으로] → [모두 합산하는 연산을 수행해] → [전체 예산 $B_{total}$보다 작거나 같은지 확인하고] → [이 결과가 참이어야 전략적 자원 할당이 타당함을 의미한다.] 동기화된 전역 상태 $\Sigma$는 트랜잭션 모니터 역할을 수행한다. 에이전트의 행동 $a_t$가 발생하면 환경이 이를 가로채 $\Sigma$에 대해 검증한다. [현재까지의 누적 지출과 예약 목록을 입력으로] → [새로운 행동의 비용과 장소를 추가하는 원자적 연산을 수행해] → [성공 여부 또는 에러 코드를 반환하고] → [이를 통해 병렬 에이전트 간의 예산 초과나 장소 중복을 실시간으로 차단한다.] 학습은 단일 정책 $\pi_\theta$에 Role Conditioning을 적용하여 GRPO로 수행된다. GRPO는 $A_i = (R(\tau_i) - \mu_G)/(\sigma_G + \epsilon)$를 계산한다. [특정 궤적의 보상 $R(\tau_i)$와 그룹 평균 보상 $\mu_G$를 입력으로] → [차이를 구하고 표준편차 $\sigma_G$로 나누는 연산을 수행해] → [상대적 이득 $A_i$를 얻고] → [이 값이 클수록 해당 에이전트의 행동이 그룹 내 다른 시도보다 우수하여 학습 가중치를 높여야 함을 의미한다.]

TravelPlanner 테스트 세트에서 52.65%의 FPR을 달성하여 SOTA를 기록했다. 이는 순차적 RL 모델인 DeepTravel(43.98%)과 멀티 에이전트 프레임워크인 ATLAS(35.00%)를 크게 상회하는 수치이다. 7일 일정 생성 시 지연 시간을 189.5초에서 72초로 약 2.63배 단축했다. 병렬 처리를 통해 계획 기간 증가에 따른 지연 시간 증가율을 선형에서 하위 선형으로 개선했다. 오류 분석 결과, HiMAP-Travel은 예산 초과 오류를 기존 대비 67%, 장소 중복 오류를 83% 감소시켰다. 이는 동기화된 전역 상태와 계층적 구조가 제약 조건 준수에 결정적인 역할을 함을 보여준다.

아키텍처는 단일 백본 모델(Qwen3-8B)이 시스템 프롬프트에 따라 Coordinator와 Executor 역할을 번갈아 수행하는 구조이다. 이를 통해 전략적 판단과 세부 실행 간의 지식 전이가 가능해진다. 동기화된 전역 상태 $\Sigma$는 외부 Mutex로 보호되는 정형 데이터 저장소이다. Diversity Set(장소 중복 방지), Budget Ledger(누적 비용 관리), Transport Mode Lock(교통 수단 일관성)을 관리하며, CHECK, COMMIT, ROLLBACK 등의 원자적 인터페이스를 제공한다. 협력적 협상 프로토콜은 Executor가 INFEASIBLE 신호를 보낼 때 작동한다. [위반 유형과 부족 예산액을 입력으로] → [Coordinator가 이를 반영해 하위 목표를 수정하는 연산을 수행해] → [새로운 Meta-plan $Z^{(k)}$를 얻고] → [이를 통해 에이전트 간의 직접적인 대화 없이도 효율적인 계획 수정이 가능해진다.] 학습 시 메모리 효율을 위해 FIFO Rollout Buffer를 사용한다. 역할별로 G개의 궤적이 모이는 즉시 그래디언트 업데이트를 수행하고 버퍼를 비움으로써, 모든 에이전트의 궤적을 동시에 메모리에 유지해야 하는 부담을 (D+1)배 줄였다.

에이전트가 경로의 지리적/시간적 타당성(Route Feasibility)을 완벽히 검증하지 못하는 경우가 있으며, 이는 전역 상태 $\Sigma$가 아닌 학습된 정책의 능력에 의존하기 때문이다. 또한 데이터베이스의 가격 정보 오류($0 등)와 같은 데이터 품질 문제에 취약하다.