技術要約：実現可能性から望ましさへ：Plan, Learn, Adapt (PLA) フレームワーク

1. 問題提起

本論文は、モバイルデバイス上でパーソナライズされた数日間の旅行日程（イトネラリー）を生成するという課題に取り組んでいる。このタスクは、**「硬い組合せ論的な実現可能性（Feasibility）」と「軟らかい潜在的な望ましさ（Desirability）」**の間の根本的な緊張関係によって定義される：

• 実現可能性（Feasibility）： 日程は、POI（興味関心地点）の営業時間、移動時間、一日の時間予算、およびコスト制限を含む、時空間的な制約を厳格に遵守しなければならない。
• 望ましさ（Desirability）： 日程は、ペース配分、地理的な一貫性、カテゴリーの多様性といった主観的なユーザーの好みを満たさなければならないが、これらは静的で手作りの目的関数では捉えることが難しい。
• 生存可能性（Viability）： ソリューションは、エンドユーザーのデバイス（具体的にはオフライン優先のiOS環境）にデプロイ可能であり、厳格なレイテンシ要件（インタラクティブな速度）とプライバシー制約を満たす必要がある。そのため、クラウド依存の大規模言語モデル（LLM）は排除される。

既存のアプローチは、これら3つの要件を同時に満たすことができていない。古典的な最適化手法は実現可能性を確保するが、微細な嗜好モデリングに欠ける。学習ベースの手法は嗜好を捉えるが、しばしば硬い制約に違反する。LLMは自然言語生成には長けているものの、無効なスケジュールを生成することが多く（著者のベンチマークでは実現可能性0%）、オフラインかつ低レイテンシのモバイル展開とも互換性がない。

2. メソドロジー：PLAフレームワーク

著者らは、実現可能性、望ましさ、および生存可能性を共同で解決するために設計された3段階のフレームワークである**Plan, Learn, Adapt (PLA)**を提案している。

フェーズ1：PLAN（多様な実現可能な生成）

Planステージでは、共通の実現可能性レイヤーを共有する5つの軽量なプランニングアルゴリズムの**ヘテロジニアス・アンサンブル（異種混合アンサンブル）**を用いて、構造的に多様な実現可能な候補日程を生成する。

• アルゴリズム： Greedy（構成的）、Dynamic Programming (DP)、Beam Search、A* Search、およびSimulated Annealing (SA)。
• 実現可能性レイヤー： ハード制約（訪問時間、移動時間の整合性、時間/コスト予算、重複なし）を強制し、最も早い実現可能到着時刻を計算する共有ロジックモジュール。
• 目的： すべてのプランナーは共通の複合スコア（移動効率、待ち時間、緊急度、カテゴリーの多様性、POIの人気度のバランス）を最適化するが、それぞれの異なる探索パラダイムにより、構造的に異なる日程が生成される。この多様性は極めて重要である。なぜなら、単一のアルゴリズムがすべての旅行コンテキストにおいて支配的になることはないからである。

フェーズ2：LEARN（人間の嗜好モデリング）

Learnステージでは、POIごとのスコアに依存するのではなく、日程レベルでの潜在的なユーザー満足度を捉えるために、コンパクトな報酬モデルを適合させる。

• データ収集： 米国の100以上の都市における、完全な日程間の2,519組のペア比較による人間による比較データが収集された。アノテーターは、ソースを知らされない状態で、異なるプランナーによって生成された日程間での選択を行った。
• モデルアーキテクチャ： 約20個の解釈可能な日程レベルの特徴量（例：総移動時間、カテゴリーのエントロピー、一日の負荷バランス、スケジュールの余裕など）に基づき、Bradley-Terry報酬モデルが訓練される。
  • モデルは差分ベースの定式化を使用する：$P(x_a \succ x_b) = \sigma(R_\theta(x_a) - R_\theta(x_b))$。
  • 単調性制約： 最適化の過程で、ドメイン知識（例：移動時間の増加は報酬を増加させない）を直接的に強制する。
• 選択： 報酬モデルはセレクターとして機能し、Planステージで生成された多様なプールの中から、最もスコアの高い日程を選択する。

フェーズ3：ADAPT（デバイス上での洗練）

Adaptステージでは、厳格なデバイス認識計算予算内で、選択されたシード日程に対して報酬ガイド付きの局所的な洗練を行う。

• 実現可能性を維持する編集： システムは、日程に対して原子的なオペレーター（Drop, Insert, Replace, Swap, Relocate, MoveDay）を適用する。決定的なのは、すべての編集の後に、制約を検証する**インクリメンタルな再タイミング（re-timing）**手順が続くことである。もし編集が制約に違反した場合、その編集は破棄される。これにより、事後的な修復方法とは異なり、すべての中間状態が実現可能であることが保証される。
• 探索戦略： 報酬スコアを向上させる動きを選択する、確率的な近傍サンプリングを用いたヒルクライミング法を用いる。
• リソース認識： 洗練プロセスは、インタラクティブなレイテンシを確保するために、デバイス信号（コア数、メモリ、パワーモード）に基づいて調整される動的なタイムバジェット（通常は約200〜500ミリ秒）によって制限される。

3. 主な貢献

1. ヘテロジニアス・プランナー・アンサンブル： 著者らは、単一のプランニングアルゴリズムが支配的になることはないことを実証的に示している。5つの異なるアルゴリズムを組み合わせることで、ペア比較において67.8%の勝率を達成し、最良の単一プランナー（DP）よりも11.2パーセントポイント向上させた。
2. 日程レベルの嗜好モデリング： POIごとのスコアリングを超え、完全な日程の比較に基づき訓練されたコンパクトなBradley-Terryモデルを導入した。このモデルは創発的な特性（ペース配分、一日のバランス）を捉え、Leave-one-city-outクロスバリデーションにおいて67.6%の精度を達成した。
3. デバイス上での実現可能性維持型のリファインメント： Adaptステージは、実現可能性を構築によって保証しながら、望ましさを向上させる。平均109.9 msのデバイス上レイテンシを実現し、完全なオフラインでのインタラクティブな実行を可能にした。

4. 実験結果

• 実現可能性 vs LLM： 294の日程を用いた3つのフロンティアLLM（GPT-5, Claude Opus 4.5, Gemini 3 Pro）とのベンチマークにおいて、LLMは0%の厳格な実現可能性を達成し、移動時間や訪問時間などの制約に違反した。対照的に、PLAは100%の実現可能性を維持した。
• アンサンブルの性能： 報酬ガイド付きアンサンブルは、単独の最良プランナーを11.2ポイント上回った（勝率67.8% vs 56.6%）。選択分布は高いエントロピー（最大値の97.6%）を示しており、異なるアルゴリズムがコンテキストに応じて一意に寄与していることを裏付けている。
• リファインメントによる向上： Adaptステージは、すべてのシードアルゴリズムに対して統計的に有意なスコア向上を提供した。例えば、A*をシードとした場合は11.7%の改善が見られ、すでに高スコアであったアンサンブルシードでも3.9%の改善が見られた。
• プロダクションへの影響： iOSアプリのFlyEnjoyにデプロイされた結果、PLAは単一のヒューリスティック・ベースラインと比較して、日程の完了率を91%向上させ、開始率を83%向上させた一方で、ユーザーあたりの平均セッション時間を38%削減した。

5. 重要性と主張

本論文は、PLAが現実世界のデプロイ制約下における人間との整合性をとったプランニングの実行可能なブループリントを提供すると主張している。その重要性は、クラウドベースのAIに頼ることなく、実現可能性と望ましさのトレードオフを解決している点にある：

• 堅牢性： 実現可能性（Plan）を嗜好学習（Learn）から分離し、実現可能性を維持するリファインメント（Adapt）を使用することで、学習ベースおよび生成AIに共通する「無効なスケジュール」の問題を回避している。
• ポータビリティ： コンパクトで解釈可能な報酬モデルと軽量な探索オペレータを使用することで、システム全体をデバイス上で実行可能にし、クラウドAPIが利用できない、あるいはコストがかかりすぎるケース（空港、機内など）でのオフライン利用をサポートしている。
• 実用性： フレームワークは、複雑な数日間のプランニングが、現在のフロンティアLLMが苦手とする領域において、厳格にハード制約を遵守しながら、インタラクティブなレイテンシ（<300 ms）で実行できることを示している。

著者らは、LLMがハード制約に苦戦する一方で、古典的な最適化、嗜好学習、および制約付き局所探索を組み合わせた構造化されたハイブリッド・アプローチが、パーソナライズされた日程生成においてより優れた、プロダクション対応の結果を提供できると結論づけている。