Fugu-MT 論文翻訳(概要): Exploiting Search in Symbolic Numeric Planning with Patterns

論文の概要: Exploiting Search in Symbolic Numeric Planning with Patterns

arxiv url: http://arxiv.org/abs/2606.16329v1
Date: Mon, 15 Jun 2026 07:32:46 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-16 16:21:34.149786
Title: Exploiting Search in Symbolic Numeric Planning with Patterns
Title（参考訳）: パターン付き記号的数値計画における爆発的探索
Authors: Matteo Cardellini, Enrico Giunchiglia,
Abstract要約: 記号パターン計画(SPP)に基づく数値計画手法を提案する。数値計画問題$$が与えられた場合、パターン$prec$は公式を定義するために使用される一連のアクションである。本稿では,探索空間を探索するための異なる戦略に対応する,このような公式を生成するための異なる手法を提案する。
参考スコア（独自算出の注目度）: 6.600299648478795
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: In this paper, we present a procedure for numeric planning based on Symbolic Pattern Planning (SPP). Given a numeric planning problem $Π$, a pattern $\prec$ is a sequence of actions used to define a formula encoding the subsequences of $\prec$ executable from a starting state $S$. Cardellini, Giunchiglia, and Maratea (2024a) follow the Planning as Satisfiability approach by defining, at each step $n \ge 0$, a formula $Π^\prec_n$ in which $(i)$ the pattern $\prec$ is computed only for $n=0$ in the initial state $I$ of $Π$, and then exploited at each step $n$, $(ii)$ the starting state $S$ is set to $I$, and $(iii)$ the set $G$ of goals is required to hold in the last state that can be reached by one of the subsequences of $\prec$ concatenated $n$ times. The procedure begins with $n=0$, terminates as soon as $Π^\prec_n$ is satisfiable, and otherwise proceeds by incrementing $n$. In this paper, possibly at each step, $(i)$ we symbolically search for an intermediate state $P$ reachable from $I$, closer to a goal state, $(ii)$ dynamically recompute the pattern $\prec_h$ -- to be used in the next step -- in $P$, $(iii)$ refine the pattern $\prec_g$ used to reach $P$, and $(iv)$ start the new search from the state $S$ which can be either the initial state $I$ or the last computed intermediate state $P$, exploiting the computed patterns $\prec_g$ and $\prec_h$ to define the pattern $\prec$ to be used in the search. In particular, at each step, we define a formula $Π^{\prec}_{S,P}$ encoding the existence of a state $P'$ closer than $P$ to a goal state, with $P'$ reachable from the starting state $S$ when using the pattern $\prec$. We present different techniques for producing such formulas, each corresponding to a different strategy for exploring the search space. We prove their correctness and completeness, the latter under certain conditions.
Abstract（参考訳）: 本稿では,記号パターン計画(SPP)に基づく数値計画手法を提案する。数値計画問題$$が与えられたとき、パターン$\prec$は、開始状態$S$から$\prec$実行ファイルのサブシーケンスをコードする式を定義するために使われる一連のアクションである。 Cardellini, Giunchiglia, and Maratea (2024a) は、各ステップ $n \ge 0$, a formula $ ^\prec_n$, which $ を定め、Planning as Satisfiability アプローチに従う。 (i)$ パターン $\prec$ は初期状態で$n=0$ に対してのみ計算され、その後、各ステップ $n$, $ で悪用される。 (ii)$ start state $S$ is set to $I$, and $ (iii)$のセット$G$は、$\prec$ concatenated $n$ timesのサブシーケンスの1つに到達可能な最後の状態に保持する必要がある。手順は$n=0$から始まり、$ ^\prec_n$ が満足すればすぐに終了し、そうでなければ$n$ を増す。この論文では、おそらく各ステップで$ (i)$ シンボル的に$P$ reachable を $I$ から検索し、ゴール状態に近い$ (ii)$は、次のステップで使われるパターン $\prec_h$ -- を動的に再計算します。 (iii)$ refine the pattern $\prec_g$ used to reach $P$, and $ (iv)$ new search from the state $S$ which can be the initial state $I$ or the last computerd intermediate state $P$, exploiting the computerd pattern $\prec_g$ and $\prec_h$ to define the pattern $\prec$ to be used in the search。特に、各ステップにおいて、パターン $\prec}_{S,P}$ がゴール状態に $P'$ よりも近い状態の存在を符号化する公式 $\^{\prec}_{S,P}$ が定義され、パターン $\prec$ を使用すると $P'$ が開始状態 $S$ から到達可能である。本稿では,探索空間を探索するための異なる戦略に対応する,このような公式を生成するための異なる手法を提案する。我々はそれらの正しさと完全性、すなわち後者を一定の条件下で証明する。

論文の概要: Exploiting Search in Symbolic Numeric Planning with Patterns

関連論文リスト