索引付きポリシーが計画問題の空間を多項式に削減。1秒・100MiBで1,709タスクを解決。
この記事のポイント
- 計画問題の空間爆発を避けられなかった
- 言語モデルで選択深さを抑えるポリシーを学習
- 1890件中1709件を解く。ただし大半が1秒以内
どこで使えるか
arXivで論文公開済み IPC2023とAutoscale Agileで評価
スポンサーリンク
解説
かみくだいて説明します
Dominik Drexlerらの研究チームが、2026年10月8日に計画の探索で必要な記憶量を大幅に減らす手法を発表しました。1,890 のテスト課題のうち 1,709 を解き、大半を 1 秒と 100 MiB 以内で完了しています。従来の手法は解の候補を指数関数的にため込むのに対し、今回提案するのは多項式空間で動く手順です。
多項式空間で動くというのは、メモリの使い方が劇的に変わるということですね。選び方の回数が増えたとき、どこまで対応できるんですか?
選び方の回数、つまり選択の深さが増えると、かかる時間は指数関数的に増えますが、使うメモリは増えません。選択の深さが一定なら P、それ以上でも NP に含まれます。
時間はかかってもメモリが押さえられるなら、大きな問題にも挑戦できそうです。その選び方をどう決めているんですか。
言語モデルで学習した政策を使います。政策にはオブジェクトを格納するレジスタと、ルールを並べるモードがあり、choose というルールで一つだけ候補を選んでバックトラックの地点にします。迷路で分かれ道に一つだけ進み、戻り地点に目印を残すイメージです。
戻り地点に目印を残すのは、迷子にならないための安全装置ですね。でも、目印がどこにあるかどうやって管理しているんですか。
正確には、レジスタに現在の状態を一つだけ格納し、その状態から次のルールを適用します。目印は探索の手順自体が保持するので、別途リストを管理する必要はありません。
手順自体が記憶を持つなら、大量の候補をため込む必要がなくなりますね。学習のときはどうやって完成を確認しているんですか。
間違った例を出して修正を繰り返すループで学習します。無限実行を避ける構造的終端を証明し、訓練課題をすべて通ったか検証し、選択の深さが小さく保たれるように調整しています。
無限実行を避けるだけでメモリが押さえられるなら、設計の段階で終端性を確認する仕組みが鍵になりますね。既存の手法と比べてどれくらい差が出ているんですか。
IPC 2023 の Learning Track と Autoscale Agile suite で、LAMA、BFWS、Levitron を上回っています。特にメモリ使用量が 100 MiB 以下に収まる課題が多く、これが従来の探索手法との決定的な違いです。
では、選択の深さが制御できなくなった場合はどうなるんですか。
選択の深さが制御できなくなると、時間は指数関数的に伸びます。そこはまだ分かっていません。
最後に、この手法が実用化されるには何が足りないんですか。
学習モデルで選択深さを小さく保ち、高い成功率を達成したと述べています。
出典
この記事のもとになった情報
- arXiv:Learning How to Search for Plans with Exponentially Less Space
- 公開日:2026-10-08
※ 本文と音声は生成 AI が作成しています。内容は出典をご確認ください。
本作品のキャラクターには株式会社Live2Dの著作物であるサンプルデータが株式会社Live2Dの定める規約に従って用いられています。本作品は制作者の完全な自己の裁量で制作されています。このキャラクターモデルは株式会社Live2Dより許諾を得て商用利用しています。