Groundingとnot Groundingの両方が悪い場合――部分的にグラウンディングされた計画をSATにエンコードする（拡張版）

arXiv cs.AI / 2026/3/23

📰 ニュースIdeas & Deep AnalysisModels & Research

共有:

要点

著者らは、アクションをリフトされたまま保ちながら、述語を部分的にグラウンディングする3つのSATエンコーディングを導入し、リフト計画とグラウンデッド計画のバランスを取る。
これらのエンコーディングは、リフト計画とグラウンデッド計画の中間の領域で動作することにより、完全にグラウンデッドな表現の指数的膨張を回避することを目的としています。
従来のSATエンコーディングは計画長に対して二次的にスケールするのに対し、提案手法は線形にスケールし、長い計画の効率を向上させます。
実証的な結果は、最良のエンコーディングが、グラウンディングが難しい領域における長さ最適化計画で最先端を上回ることを示しています。
本研究は、SATベースの計画における実用的な中間的アプローチを提供し、将来のプランナーや、スケーラブルで長さ最適な計画を必要とするアプリケーションに影響を与え得ると考えられます。

要旨：
古典的なプランニング問題は、通常、リフトされた一階表現を用いて定義され、これによりコンパクトさと一般性が提供されます。多くのプランナーは推論を簡略化するためにこれらの表現をグラウンディングしますが、これによりサイズが指数的に膨らむことがあります。最近のアプローチは、完全なグラウンディングを避けるために、リフトレベルで直接操作します。完全にリフトされた計画と完全にグラウンディングされた計画の間の中間点を探るために、アクションをリフトしたまま述語を部分的にグラウンディングする3つのSATエンコーディングを導入することにより、中間点を探索します。従来のSATエンコーディングは計画長に対して2次的にスケールしますが、我々のアプローチは線形にスケールし、長い計画での性能を向上させます。実証的には、私たちの最良のエンコーディングは、グラウンディングが難しいドメインにおける長さ最適化計画で最先端の手法を上回ります。