기술 요약: 실현 가능성에서 선호도로: 계획, 학습, 적응 (PLA) 프레임워크

1. 문제 정의

본 논문은 모바일 기기에서 개인화된 다일(multi-day) 여행 일정을 생성하는 과제를 다룹니다. 이 과제는 **하드한 조합론적 실현 가능성(hard combinatorial feasibility)**과 소프트한 잠재적 선호도(soft latent desirability) 사이의 근본적인 긴장 관계로 정의됩니다:

• 실현 가능성 (Feasibility): 일정은 POI(관심 지점) 영업 시간, 이동 시간, 일일 시간 예산, 비용 제한을 포함한 시공간적 제약 조건을 엄격히 준받아야 합니다.
• 선호도 (Desirability): 일정은 페이싱(pacing), 지리적 일관성, 카테고리 다양성 등 정적인 수작업 목적 함수로는 포착하기 어려운 주관적인 사용자 선호도를 충족해야 합니다.
• 생존 가능성 (Viability): 솔루션은 엔드 유저 기기(특히 오프라인 우선 iOS 환경)에 배포 가능해야 하며, 엄격한 지연 시간 요구 사항(대화형 속도)과 개인정보 보호 제약을 준수해야 하므로 클라우드 의존적인 대규모 언어 모델(LLLLM) 사용이 불가능합니다.

기존 방식들은 이 세 가지 요구 사항을 동시에 충족하지 못합니다. 고전적 최적화 도구는 실현 가능성은 보장하지만 미세한 선호도 모델링이 부족하고, 학습 기반 방식은 선호도는 포착하지만 종종 하드 제약을 위반하며, LLM은 자연어 생성 능력은 뛰어나지만 유효하지 않은 일정을 생성하는 경우가 많습니다(저자들의 벤치마크에서 실현 가능성 0%). 또한 LLM은 오프라인, 저지연 모바일 배포와 호환되지 않습니다.

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

저자들은 실현 가능성, 선호도, 생존 가능성을 공동으로 해결하기 위해 설계된 3단계 프레임워크인 **Plan, Learn, Adapt (PLA)**를 제안합니다.

1단계: PLAN (다양한 실현 가능한 생성)

Plan 단계는 통합된 실현 가능성 레이어를 공유하는 5가지 경량 플래닝 알고리즘의 **이질적 앙상블(heterogeneous ensemble)**을 사용하여 구조적으로 다양한 실현 가능한 후보 일정들을 생성합니다.

• 알고리즘: Greedy (구성적), Dynamic Programming (DP), Beam Search, A* Search, 그리고 Simulated Annealing (SA).
• 실현 가능성 레이어 (Feasibility Layer): 하드 제약 조건(방문 시간, 이동 시간 일관성, 시간/비용 예산, 중복 방문 금지)을 강제하고 가장 빠른 실현 가능한 도착 시간을 계산하는 공유 로직 모듈입니다.
• 목적: 모든 플래너가 공유된 복합 점수(이동 효율성, 대기 시간, 긴급도, 카테고리 다양성, POI 인기도의 균형)를 최적화하지만, 각기 다른 탐색 패러다임 덕분에 구조적으로 다른 일정을 산출합니다. 이러한 다양성은 단일 알고리즘이 모든 여행 맥락에서 우위를 점할 수 없기 때문에 매우 중요합니다.

2단계: LEARN (인간 선호도 모델링)

Learn 단계는 개별 POI 점수에 의존하는 대신, 일정 수준에서의 잠재적 사용자 만족도를 포착하기 위해 컴팩트한 보상 모델을 적합시킵니다.

• 데이터 수집: 100개 이상의 미국 도시를 대상으로 완성된 일정 간의 2,519건의 쌍체 비교(pairwise comparisons) 데이터를 수집했습니다. 주석 작성자들은 출처를 모르는 상태에서 서로 다른 플래너가 생성한 일정 중 하나를 선택했습니다.
• 모델 아키텍처: 약 20개의 해석 가능한 일정 수준 특징(예: 총 이동 시간, 카테고리 엔트로피, 일일 부하 균형, 스케줄 여유 시간)을 바탕으로 Bradley-Terry 보상 모델을 학습시킵니다.
  • 모델은 차이 기반 공식인 $P(x_a \succ x_b) = \sigma(R_\theta(x_a) - R_\theta(x_b))$를 사용합니다.
  • 단조성 제약 (Monotonicity Constraints): 최적화 과정에서 도메인 지식(예: 이동 시간이 증가하면 보상이 증가해서는 안 됨)을 직접적으로 강제합니다.
• 선택: 보상 모델은 Selector 역할을 수행하여, Plan 단계에서 생성된 다양한 풀(pool) 중에서 가장 높은 점수를 받은 일정을 선택합니다.

3단계: ADAPT (온디바이스 정교화)

Adapt 단계는 엄격한 디바이스 인지 컴퓨팅 예산 내에서 선택된 시드(seed) 일정에 대해 보상 가이드 기반의 국소 정교화(local refinement)를 수행합니다.

• 실현 가능성을 보존하는 편집: 시스템은 원자적 연산자(Drop, Insert, Replace, Swap, Relocate, MoveDay)를 일정에 적용합니다. 결정적으로, 모든 편집은 제약 조건을 검증하는 증분 재타이밍(incremental re-timing) 절차를 따릅니다. 만약 편집이 제약을 위반하면 해당 편집은 폐기됩니다. 이를 통해 모든 중간 상태가 실현 가능함을 보장하며, 이는 사후 수정(post-hoc repair) 방식과는 다릅니다.
• 탐색 전략: 확률적 이웃 샘플링을 사용하는 힐 클라이밍(hill-climbing) 접근법을 통해 보상 점수를 개선하는 이동(move)을 선택합니다.
• 자원 인식: 정교화 과정은 코어 수, 메모리, 전력 모드와 같은 디바이스 신호에 따라 조정되는 동적 시간 예산(통상 ~200–500 ms)에 의해 제한되어 인터랙티브한 지연 시간을 보장합니다.

3. 주요 기여

1. 이질적 플래너 앙상블: 저자들은 단일 플래닝 알고리즘이 지배적이지 않다는 것을 경험적으로 입증했습니다. 5가지 서로 다른 알고리즘을 결합함으로써, 쌍체 비교에서 67.8%의 승률을 달이트며, 이는 최적의 단일 플래너(DP)보다 11.2 퍼센트 포인트 향상된 결과입니다.
2. 일정 수준의 선호도 모델링: 개별 POI 점수를 넘어, 완성된 일정 비교를 통해 학습된 컴팩트한 Bradley-Terry 모델을 도입했습니다. 이 모델은 창발적 특성(페이싱, 일간 균형 등)을 포착하며, leave-one-city-out 교차 검증에서 67.6%의 정확도를 달성했습니다.
3. 온디바이스 실현 가능성 보존 정교화: Adapt 단계는 구성 단계부터 100% 실현 가능성을 보장하면서 선호도를 개선합니다. 이 단계는 평균 109.9 ms의 온디바이스 지연 시간을 달성하여 완전한 오프라인 인터랙티브 실행을 가능하게 합니다.

4. 실험 결과

• 실현 가능성 vs LLM: 294개의 일정에 대해 세 가지 프런티어 LLM(GPT-5, Claude Opus 4.5, Gemini 3 Pro)과 벤치마크를 수행한 결과, LLM은 이동 시간 및 방문 시간과 같은 제약을 위반하여 0%의 엄격한 실현 가능성을 기록했습니다. 반면, PLA는 100%의 실현 가능성을 유지했습니다.
• 앙상블 성능: 보상 가이드 앙상블은 단일 플래너 중 최고 모델보다 11.2 포인트 더 높은 성능을 보였습니다(67.8% vs 56.6% 승률). 선택 분포는 높은 엔트로피(최대치의 97.6%)를 보여, 서로 다른 알고리즘이 맥락에 따라 고유하게 기여함을 확인했습니다.
• 정교화 효과 (Refinement Uplift): Adapt 단계는 모든 시드 알고리즘에 대해 통계적으로 유의미한 점수 향상을 제공했습니다. 예를 들어, A* 시드는 11.7%의 개선을 보였고, 이미 높은 점수를 가진 앙상블 시드는 3.9% 개선되었습니다.
• 프로덕션 임팩트: FlyEnjoy iOS 앱에 배포된 결과, PLA는 단일 휴리스틱 베이스라인 대비 일정 완료율을 91%, 시작률을 83% 증가시켰으며, 사용자당 평균 세션 시간은 38% 감소시켰습니다.

5. 의의 및 주장

본 논문은 PLA가 **실제 배포 제약 조건 하에서 인간과 정렬된 계획(human-aligned planning)**을 위한 실행 가능한 청사진을 제공한다고 주장합니다. 그 의의는 클라우드 기반 AI에 의존하지 않고 실현 가능성과 선호도 사이의 트레이드오프를 해결하는 데 있습니다:

• 강건성 (Robustness): 실현 가능성(Plan)과 선호도 학습(Learn)을 분리하고, 실현 가능성을 보존하는 정교화(Adapt)를 사용함으로써, 학습 기반 및 생성형 AI에서 흔히 발생하는 "유효하지 않은 스케줄" 문제를 방지합니다.
• 휴대성 (Portability): 컴팩트하고 해석 가능한 보상 모델과 경량화된 탐색 연산자를 사용하여 시스템 전체를 온디바이스에서 실행할 수 있으며, 클라우드 API를 사용할 수 없는 상황(공항, 기내 등)에서의 오프라인 사용을 지원합니다.
• 실용성 (Practicality): 본 프레임워크는 복잡한 다일 계획이 현재의 프런티어 LLM이 갖지 못한 엄격한 제약을 준수하면서도 인터랙티브한 지연 시간(<300 ms) 내에 실행될 수 있음을 입증합니다.

저자들은 LLM이 하드 제약 조건에 어려움을 겪는 반면, 고전적 최적화, 선호도 학습, 제약 조건이 있는 국소 탐색을 결래한 구조적 하이브리드 접근 방식이 개인화된 일정 생성에 있어 더 우수하고 프로덕션 준비가 된 결과를 제공할 수 있다고 결론짓습니다.