A*を超えて: トランスフォーマーを活用したより良い計画立案

Beyond A*: トランスフォーマーを用いたより良い計画立案

• トランスフォーマーモデルはさまざまな応用分野で大きな進展を遂げてきたが、複雑な意思決定課題を解く点では、従来の記号ベースの計画立案手法に後れを取っていた。
• 研究チームは、トランスフォーマーを訓練して複雑な計画課題を解く方法を提示し、Searchformerというモデルを開発した。これは既存のA*探索より最大26.8%少ない探索ステップを使いながら、未見のSokobanパズルを93.7%の割合で最適に解く。
• Searchformerは、A探索の動作を予測するよう訓練されたエンコーダー・デコーダー型トランスフォーマーモデルで、エキスパート反復によってファインチューニングされ、A探索より少ない探索ステップで最適な計画を生成する。

訓練方法と性能

• 訓練方法では、A*の探索動作を、記号計画において探索木へ状態が追加・削除される時点を表すトークン列として表現する。
• 迷路探索に関するアブレーション研究では、Searchformerは最適計画を直接予測するベースラインモデルを大きく上回り、モデルサイズは5〜10倍小さく、訓練データセットは10分の1で済む。
• 研究チームは、SearchformerがSokobanのような、より大規模で複雑な意思決定課題に対して、解ける課題の割合を高め、探索動作を短縮するうえで効果的であることを示した。

GN⁺の見解

• この研究は、人工知能分野におけるトランスフォーマーモデルの新たな活用可能性を示している。複雑な意思決定課題を解くうえで、従来の記号ベース手法より効率的なアプローチを提示することで、AIの応用範囲を拡張する重要な前進といえる。
• Searchformerモデルは、より少ない資源で、より高速かつ効率的な問題解決能力を示している。これは特に、資源が限られた環境でAIを実装する際に大きな利点となりうる。
• 本研究は、AI技術の進歩が、単により多くのデータやより大きなモデルに依存するのではなく、知的な方法論とアルゴリズムの改善によっても実現できることを示唆している。これは、AI研究の持続可能性と効率性の観点から非常に興味深く有益なアプローチである。

[GN⁺]

Hacker Newsの意見

• ロボットのモーションプランニングにトランスフォーマーを使う興味深い研究がある。ロボットアームが物体にぶつからずにある地点から別の地点へ移動するのは非常に難しい問題で、この問題は高次元かつ連続的である。従来の計画手法は計算コストが高く、あまり良くなかった。これが、ロボットの動きが「不自然」に見え、私たちが望む多くの作業をロボットがうまくこなせない理由の一つである。このアプローチは他の計画手法と十分競争力があるように見え、より高速な最適経路計画を示している。
• ゲームグラフ／経路探索向けのAアルゴリズムの最適化版である改良Jアルゴリズムを、この研究路線を始める前に試したのか気になる。興味のある人向けに『Game AI Pro 2』に関する情報がある。
• 計画はすでに、グラフ探索、SATソルバー、OR、Prolog などの既存技術で十分うまく扱われている。問題は通常、複数の実行可能な代替案の間での最適化であり、トランスフォーマーがそれを行うのに適しているのかは疑問である。LLM技術の役割は、自然言語の説明を実行可能なプログラムに変換することにより近いように見えるし、Prolog は結局のところ古典的なNLP向けに設計されたので、かなり近い。
• 機械翻訳には複雑な文法解析と探索が含まれていたが、今ではMTにトランスフォーマーを使い、探索をほとんど必要としない、はるかに単純なデコードを使っている。現在の最高の予測モデルを使ってニューラルアーキテクチャ探索（NAS）のためのヒューリスティックを学習し、トランスフォーマーやMambaより優れた新しいニューラルブロックを探索する「完全な始まり」に到達できるかもしれない。
• 「標準A探索より26.8%少ない探索ステップ」という文句は、Aよりやや良い性能を示しているが、Sokobanでは最先端技術（SOTA）には及ばない。この論文の何が印象的なのか、そしてなぜHacker Newsに載ったのか疑問である。
• トランスフォーマーが計画を立てられるなら、AGI（汎用人工知能）は単により良い教育だけが必要なのかもしれない。
• 聴覚学習者向けに、この論文を要約したオーディオブック形式が提供されている。
• この論文は、昨日HNのトップページにあった Neural Network Diffusion の論文を思い出させる。前者ではSGDステップを迂回するモデルを訓練し、この論文ではA探索ステップを迂回している。一方で、Sokoban向けのAのヒューリスティック選択は良くない。論文を読みながら20分ほどSokobanを遊んでみたが、進行のためにはしばしば目標状態から箱を遠ざけて動かす必要があり、探索ヒューリスティックが非常に不十分だと感じた。
• ディープラーニングを使うことで、今ではより良く解けるようになった古典アルゴリズムやNP完全問題の一覧を保守している人がいるのか気になる。
• A*やFocal探索のような離散アルゴリズムで学習済みヒューリスティックを使うことには非常に楽観的である。たいていの現代的な離散最適化ライブラリでは、CPLEXのように性能を左右するのはヒューリスティックとチューニングである。よく理解されている最適探索ルーチンを置き換えるためにエンドツーエンドの学習アプローチを使うことについては、あまり理解できていないが、それは過剰な心配かもしれない。著者たちはその機会を逃したのだと思う。