GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

この論文は、大規模言語モデルを活用した進化アルゴリズムを用いて PDDL で記述された古典的計画タスク向けの汎用的なプランナーを自動生成する「GenePlan」という新しいフレームワークを提案し、既存の最先端プランナーと同等の性能を発揮しながら、他の LLM ベースの手法を大幅に上回る結果を示したことを報告しています。

要約

GenePlan: AI による「万能な計画屋」の進化

この論文は、「GenePlan（ジープラン）」という新しいシステムについて紹介しています。これは、人工知能（AI）を使って、複雑な問題解決の「レシピ」や「戦略」を自動的に作り出し、それをより良いものへと進化させる技術です。

わかりやすく、日常の例え話を使って説明しましょう。

---

1. 従来の AI の悩み：「一度きりの天才」

これまでの AI（特に大規模言語モデル）は、質問に答えたりコードを書いたりするのが得意でした。しかし、「計画（プラン）」を立てるタスクでは、少し苦手としていました。

• 例え話: 従来の AI は、**「その場限りの天才料理人」**のようです。
  • 「今日の夕食を作ってください」と言われれば、美味しい料理を作れます。
  • でも、「明日の朝も、明後日の夜も、来週の同じ条件で料理を作ってください」と言われると、毎回ゼロから考え直してしまい、効率が悪いだけでなく、失敗することもありました。
  • また、AI が作ったレシピが「少しだけ無駄な工程がある」など、最適ではないこともありました。

2. GenePlan のアイデア：「進化させる料理学校」

GenePlan は、AI に「その場限りの天才」ではなく、**「どんな状況でも通用する、完璧な料理の教科書（戦略）」を作らせることにしました。そして、その教科書を作るプロセスを、「進化（ダーウィンの進化論）」**に似せて設計しました。

この仕組みを 3 つのステップで説明します。

ステップ 1: 候補の生み出し（卵を産む）

まず、AI に「料理のレシピ（Python というプログラミング言語で書かれた戦略）」をいくつか書かせます。

• 例え話: 料理学校で、生徒たちがそれぞれ「どうすれば最短で料理ができるか？」というレシピを思いついて提出します。最初は、みんなのレシピはバラバラで、下手な人もいれば、天才的な人もいます。

ステップ 2: 厳しい審査（味見と採点）

次に、そのレシピが実際に使えるか、テストします。

• 例え話: 審査員（コンピューター）が、そのレシピを使って実際に料理を作ってみます。
  • 「失敗した！」→ 0 点。
  • 「成功したけど、手順が 100 回必要だった」→ 100 点（点数が高いほど悪い）。
  • 「成功して、手順がたったの 10 回だった」→ 10 点（点数が低いほど良い）。
  • 重要: 失敗したレシピや、点数が悪いレシピは、その場で「淘汰（はぶかれる）」されます。

ステップ 3: 優秀なレシピの「掛け合わせ」と「改良」（進化）

ここで GenePlan のすごいところが出ます。AI は、「点数の良かったレシピ」だけを集め、それらを混ぜ合わせて新しいレシピを作ります。

• 例え話:
  • 「A さんのレシピは『野菜を切る手順』が速い！」
  • 「B さんのレシピは『炒める手順』が効率的だ！」
  • AI は、A さんの「切る手順」と B さんの「炒める手順」を組み合わせて（交配）、新しいレシピを作ります。
  • さらに、**「ちょっとだけ変えてみよう（突然変異）」**という作業もします。例えば、「炒める時間を 1 秒短くしてみる」など、小さな変更を加えて、もっと良くなるか試します。

この「作って→テストして→良いものだけ残して→混ぜて→変える」というサイクルを、何回も何回も繰り返します。

3. 結果：「完璧な教科書」の完成

このサイクルを繰り返すうちに、AI は**「どんな状況でも、最短で、最も効率的に問題を解決できる、完璧な戦略」**を編み出します。

• 従来の AI（CoT など）: 毎回ゼロから考え直すので、時間がかかり、ミスも多い（平均スコア 0.64）。
• GenePlan: 進化させて完成した「戦略」を使うので、非常に速く、非常に正確（平均スコア 0.91）。
  • 速さ: 1 つの問題を解くのに、わずか0.49 秒！
  • コスト: 1 つの分野（ドメイン）の戦略を作るのに、**約 1.82 ドル（約 270 円）**という安さ。

4. なぜこれがすごいのか？

GenePlan が作り出したのは、単なる「答え」ではなく、**「答えを出すための考え方のルール（Python プログラム）」**です。

• 例え話:
  • 従来の AI は、「この問題の答えは『A』です」と教えてくれます。
  • GenePlan は、「この分野の問題に遭遇したら、**『この手順で考えれば、どんな問題でも最短で解決できる』**というマニュアル」を渡してくれます。
  • そのマニュアルさえあれば、新しい問題が来ても、AI が考える必要なく、マニュアル通りに瞬時に解決できます。

まとめ

GenePlan は、**「AI に、失敗から学び、良いアイデアを組み合わせ、より良い戦略を進化させる」**という仕組みを作りました。

これにより、AI は単に「答えを言う」だけでなく、「問題を解決する賢いルール」を自分で作り出し、人間が作った最高の専門家（Fast Downward という従来の最強の計画システム）と肩を並べるレベルの成果を出しました。しかも、そのルールは人間にも読み解ける（解釈可能）もので、非常に安価に作れます。

これは、AI が「答え」だけでなく、「知恵」そのものを進化させる第一歩と言えるでしょう。

技術概要

以下は、J.P. Morgan AI Research によって提出された論文「GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models」の技術的な要約です。

1. 概要と背景

この論文は、古典的な計画タスク（PDDL で記述された問題）に対して、大規模言語モデル（LLM）と進化アルゴリズムを組み合わせることで、**「汎用的な計画器（Generalized Planner）」**を自動生成する新しいフレームワーク「GenePlan」を提案しています。

従来の LLM を用いた計画アプローチは、特定のインスタンスに対して直接プランを生成するものや、推論プロセス（Chain-of-Thought）を伴うものが主流でしたが、計画の品質（プランの長さやコスト）の最適化が不十分であるという課題がありました。GenePlan は、汎用計画を「最適化問題」として再定義し、LLM を進化計算のエンジンとして活用することで、高品質で解釈可能な Python プランナーを生成することを目指しています。

2. 問題定義

• 汎用計画（Generalized Planning）: 特定のドメイン内で、オブジェクトや初期状態、目標が異なる複数の問題インスタンスに対して有効な戦略（計画器）を生成するタスク。
• 最適化目標: 訓練セットに含まれるすべての問題インスタンスにおいて、生成された計画器が出力するプランの長さ（アクション数）の平均を最小化する Python 関数（get_plan）を見つけること。
• 課題: LLM は単発のプロンプトでは高品質な最適解を導き出せないことが多く、また、従来の検索ベースのソルバー（例：Fast Downward）は計算コストが高く、解釈性が低い場合がある。

3. 手法：GenePlan のアーキテクチャ

GenePlan は、Romera-Paredes ら（2024）の「進化 LLM」の枠組みを PDDL 計画に応用したものです。主なプロセスは以下の通りです。

1. 進化ループの構築:

   • 個体（Population）: 候補となる Python プランナー（get_plan メソッド）の集合。
   • 適応度関数（Fitness Function）: 訓練タスク群における平均プラン長の逆数（短いほど良い）。プランが失敗した場合は大きなペナルティスコアを付与。
   • 評価: 生成されたコードは AST（抽象構文木）パーサーで構文チェックされ、PDDL バリデーターを用いて実行可能か、かつ正しいプランを生成するかを確認します。

2. LLM による変異と交叉（Mutation & Crossover）:

   • 選択（Selection）: 現在の個体群から、適応度に基づいて親プランナーを選択します。温度パラメータ $T$ を用いたボルツマン選択（Boltzmann selection）を採用し、初期段階では探索（多様性）、後期段階では利用（高品質な解の洗練）をバランスさせます。
   • プロンプト構築: 選択された上位のプランナーのコードと、その実行結果（成功/失敗、スコア、エラーメッセージ）を例示（Few-shot）として LLM に提示します。
   • 生成: LLM は、交叉（既存の優れたロジックの組み合わせ）と変異（効率化や新規ヒューリスティクの導入）を行うよう指示され、新しい子孫プランナーを生成します。

3. 置換戦略（Replacement）:

   • 一定数の子孫が生成された後、最も性能の低い個体を削除し、次世代の個体群を形成します（$\mu + \lambda$ 選択）。
   • このプロセスを世代（Generation）ごとに繰り返し、最終的に最も優れた Python プランナーを抽出します。

4. 主要な貢献

• 最適化指向の汎用計画フレームワーク: 単に「解ける」プランを生成するだけでなく、LLM を最適化器として機能させ、プランの品質（長さ）を明示的に最小化するアプローチを確立しました。
• 解釈性と効率性の両立: 生成されるのは人間が読み解ける Python コードであり、ブラックボックスなニューラルネットワークではなく、従来のソルバーよりも高速に実行可能です。
• 低コストでの高性能化: 高価な検索アルゴリズムを毎回実行するのではなく、一度プランナーを生成すれば、その後のインスタンスに対して極めて低コスト・高速に解決できます。

5. 実験結果

8 つの PDDL ドメイン（既存のベンチマーク 6 つ＋新規作成 2 つ）で評価を行いました。

• 性能:
  • GenePlan の平均 SAT スコア（最適解に対する相対的な品質）は 0.91 でした。
  • これは、30 分の時間制限を設けた最先端のソルバー「Fast Downward (fd_1800)」のスコア（0.93）とほぼ同等であり、Chain-of-Thought プロンプティング（CoT）ベースの LLM ベースライン（0.64）を大幅に上回りました。
• 実行速度:
  • 生成されたプランナーは、新しいインスタンスを平均 0.49 秒 で解決します。
  • 一方、Fast Downward は 1 インスタンスあたり数秒〜数百秒を要します。
• コスト:
  • 1 ドメインあたりのプランナー生成コストは、GPT-4o を使用した場合でも平均 1.82 ドル と非常に安価です。
• アブレーション研究:
  • PDDL のドメイン記述を自然言語要約に置き換えると性能が低下し、具体的な PDDL 記述（述語やアクション名）の文脈情報が重要であることが示されました。
  • 名前を抽象化（ablation）すると LLM は失敗し、文脈情報の重要性が浮き彫りになりました。
• 限界:
  • 単純な戦略が存在しない複雑なドメイン（例：ソコバン）では、GenePlan は検索アルゴリズムを模倣しようとして失敗しましたが、これはドメインの特性によるものであり、GenePlan が「単純な戦略が存在するドメイン」に特化したアプローチであることを示唆しています。

6. 意義と将来展望

GenePlan は、LLM を単なる「推論エンジン」ではなく、「アルゴリズム設計者」として位置づける重要なステップです。

• 実用性: 繰り返し発生する計画タスク（物流、リソース管理など）において、一度高品質なプランナーを生成すれば、その後の運用コストを劇的に削減できます。
• ハイブリッドアプローチ: 将来的には、LLM をオーケストレーターとして使い、問題の難易度に応じて GenePlan 生成のプランナーと従来の検索ソルバーを動的に切り替えるシステムや、検索アルゴリズムのヒューリスティック関数自体を LLM で進化させる研究への応用が期待されます。

総じて、この研究は LLM を活用した自動化されたアルゴリズム設計の新たな可能性を示し、特に「解釈性」「高速性」「低コスト」の観点から、実世界の計画問題解決における有力なアプローチを提示しています。