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

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

왜 중요한가

핵심 기여

제약 조건 표류(Constraint Drift) 현상 정의 및 분석

순차적 LLM 에이전트가 긴 도구 사용 기록이 누적됨에 따라 초기 글로벌 제약 조건에 대한 주의력이 희박해져 전역적 타당성이 저하되는 현상을 규명했다.

계층적 멀티 에이전트 아키텍처(HiMAP) 제안

자원 할당을 담당하는 전략적 Coordinator와 독립적으로 일일 계획을 수립하는 Tactical Executor로 역할을 분리하여 복잡한 최적화 문제를 구조화했다.

동기화된 전역 상태(Synchronized Global State) 모니터 도입

병렬 실행 중인 에이전트들이 예산 초과나 장소 중복을 방지할 수 있도록 원자적 연산을 지원하는 외부 트랜잭션 모니터를 통해 Correct-by-construction 패러다임을 구현했다.

협력적 협상 프로토콜(Cooperative Bargaining Protocol) 개발

실행 에이전트가 불가능한 하위 목표를 거부하고 Coordinator에게 구조화된 피드백을 전달하여 동적으로 계획을 수정할 수 있는 양방향 통신 구조를 구축했다.

핵심 아이디어 이해하기

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 등)와 같은 데이터 품질 문제에 취약하다.

실무 활용

예산, 시간, 중복 방지 등 엄격한 제약 조건이 있는 장기 계획 문제에 최적화된 프레임워크이다. 병렬 처리를 통해 대규모 에이전트 시스템의 응답 속도를 획기적으로 개선할 수 있다.

개인 맞춤형 다일정 여행 플래너
기업용 복합 자원 배분 및 일정 관리 시스템
자율 에이전트 기반의 소프트웨어 프로젝트 태스크 할당

코드 공개 여부: 비공개

키워드

LLM(대형 언어 모델)Multi-Agent(멀티 에이전트)Planning(계획 수립)GRPO(그룹 상대 정책 최적화)Constraint-Satisfaction(제약 조건 만족)

용어 해설

제약 조건 표류(Constraint Drift): — LLM 에이전트가 긴 추론 과정이나 도구 사용 기록이 누적됨에 따라 초기 설정된 전역 제약 조건(예: 전체 예산)에 대한 주의력을 잃고 이를 위반하는 현상이다. 컨텍스트가 길어질수록 초기 정보의 영향력이 약해지는 Transformer 아키텍처의 한계로 인해 발생하며, 계획의 일관성을 해치는 주요 원인이 된다.
그룹 상대 정책 최적화(GRPO): — DeepSeek-V3에서 제안된 강화학습 알고리즘으로, 별도의 Critic 모델 없이 샘플링된 그룹 내의 상대적 보상을 기준으로 정책을 업데이트한다. 계산 효율성이 높고 메모리 사용량을 줄이면서도 모델의 추론 능력을 효과적으로 정렬할 수 있어 멀티 에이전트 학습에 유리하다.
역할 조건화(Role Conditioning): — 단일 LLM 정책이 시스템 프롬프트나 입력 접두사를 통해 서로 다른 역할(예: 조정자, 실행자)을 수행하도록 유도하는 기법이다. 이를 통해 여러 모델을 개별적으로 학습시키지 않고도 하나의 모델 내에서 복잡한 협업 구조를 구현할 수 있으며, 역할 간의 지식 전이 효과를 기대할 수 있다.
최종 통과율(Final Pass Rate): — 에이전트가 생성한 전체 계획이 모든 하드 제약 조건(예: 예산, 기간, 장소 중복 금지 등)을 동시에 만족하는 비율을 측정하는 지표이다. 단순한 문법적 정확도를 넘어 실제 실행 가능한 계획의 품질을 평가하는 핵심 벤치마크 지표로 사용된다.
트랜잭션 모니터(Transactional Monitor): — 병렬로 실행되는 여러 에이전트가 공유 자원(예: 예산)을 사용할 때 데이터 무결성을 보장하기 위해 도입된 외부 제어 장치이다. 데이터베이스의 트랜잭션 개념을 차용하여 원자적(Atomic) 연산을 지원하며, 에이전트 간의 자원 충돌이나 중복 예약을 실시간으로 방지한다.

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

왜 중요한가

핵심 기여

핵심 아이디어 이해하기

방법론

주요 결과

기술 상세

한계점

실무 활용

키워드

용어 해설

관련 토론

댓글

관련 기사

비정형 텍스트로부터의 자동 온톨로지 생성: 멀티에이전트 LLM 접근 방식

왜 중요한가

핵심 기여

핵심 아이디어 이해하기

방법론

주요 결과

기술 상세

한계점

실무 활용

키워드

관련 토론

댓글

관련 기사

비정형 텍스트로부터의 자동 온톨로지 생성: 멀티에이전트 LLM 접근 방식