プランニング問題における部分グラウンディング手法：完全なグラウンディングとリフテッドアプローチの中間解

要約

古典的なプランニング問題は通常、コンパクトで汎用的なlifted first-order表現を用いて定義されるが、多くのプランナーは推論を簡素化するためにこれらの表現をgroundingする際、指数関数的なサイズ増大を引き起こす課題があった。最近の手法では完全にliftedレベルで操作することでfull groundingを回避するアプローチが取られている。本研究では、fully liftedとfully groundedプランニングの中間的な解決策として、アクションをliftedのまま保ちつつ述語を部分的にgroundingする3つのSATエンコーディング手法を提案している。従来のSATエンコーディングがプラン長に対して二次関数的にスケールしていたのに対し、提案手法は線形的にスケールするため、より長いプランに対してもより良いパフォーマンスを実現する。実験結果では、grounding困難なドメインにおけるlength-optimal planningにおいて、提案手法が最先端技術を上回る性能を示した。