# (参考訳) 新展開計画--制御・計画・強化学習における共通問題に対する幅ベースアルゴリズム [全文訳有]

Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning ( http://arxiv.org/abs/2106.04866v1 )

ライセンス: CC BY 4.0
Nir Lipovetzky(参考訳) 幅に基づくアルゴリズムは、状態の新規性の一般的な定義を通じて解を求める。 これらのアルゴリズムは、古典的な計画において最先端のパフォーマンスをもたらすことが示されており、シミュレーションエンジンによって問題のダイナミクスが与えられるモデルベースおよびモデルフリーの設定にうまく適用されている。 幅ベースのアルゴリズムのパフォーマンスは、計画幅の概念を通じて理論的に理解され、ランタイムとメモリ消費の多項式保証を提供する。 本稿では,研究コミュニティ間のシナジーを促進するために,幅ベースの計画の領域をまとめ,現在と将来の研究方向について調査する。

Width-based algorithms search for solutions through a general definition of state novelty. These algorithms have been shown to result in state-of-the-art performance in classical planning, and have been successfully applied to model-based and model-free settings where the dynamics of the problem are given through simulation engines. Width-based algorithms performance is understood theoretically through the notion of planning width, providing polynomial guarantees on their runtime and memory consumption. To facilitate synergies across research communities, this paper summarizes the area of width-based planning, and surveys current and future research directions.
公開日: Wed, 9 Jun 2021 07:46:19 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。


    Page: /      
Planning for Novelty: Width-Based Algorithms for Common Problems in Control, 新規性計画:制御の共通問題に対する幅ベースアルゴリズム 0.76
Planning and Reinforcement Learning ∗ School of Computing and Information Systems, University of Melbourne, Australia 計画と強化学習 ∗ メルボルン大学コンピュータ情報システム学部 0.60
nir.lipovetzky@unime lb.edu.au nir.lipovetzky@unime lb.edu.au 0.47
Nir Lipovetzky Nir Lipovetzky 0.85
1 2 0 2 n u J 1 2 0 2 n u J 0.85
9 ] I A . s c [ 9 【私】 A! sc [ 0.65
1 v 6 6 8 4 0 1 v 6 6 8 4 0 0.85
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Abstract search for Width-based algorithms solutions through a general definition of state novelty. 概要 検索 幅に基づくアルゴリズムは、状態の新規性の一般的な定義を通じて解決する。 0.50
These algorithms have been shown to result in state-of-the-art performance in classical planning, and have been successfully applied to model-based and model-free settings where the dynamics of the problem are given through simulation engines. これらのアルゴリズムは、古典的な計画において最先端のパフォーマンスをもたらすことが示されており、シミュレーションエンジンによって問題のダイナミクスが与えられるモデルベースおよびモデルフリーの設定にうまく適用されている。 0.71
Width-based algorithms performance is understood theoretically through the notion of planning width, providing polynomial guarantees on their runtime and memory consumption. 幅ベースのアルゴリズムのパフォーマンスは、計画幅の概念を通じて理論的に理解され、ランタイムとメモリ消費の多項式保証を提供する。 0.63
To facilitate synergies across research communities, this paper summarizes the area of width-based planning, and surveys current and future research directions. 本稿では,研究コミュニティ間のシナジーを促進するために,幅ベースの計画の領域をまとめ,現在と将来の研究方向について調査する。 0.67
1 Introduction Planning plays a central role defining artificial and human intelligence [Newell and Simon, 1963; Kahneman, 2011]. はじめに 人工知能と人間の知性を定義する中心的な役割は計画である[Newell and Simon, 1963; Kahneman, 2011]。 0.67
It is an active research area for different communities, each with their own set of assumptions, formulations and computational approaches. 異なるコミュニティのための活発な研究領域であり、それぞれ独自の仮定、定式化、計算アプローチを持っている。 0.62
The goal of this paper is to introduce one of the recent advances from the AI planning community, width-based planning [Lipovetzky and Geffner, 2012], and illustrate its wider applicability to problem formulations common in other communities such as optimal control [Bertsekas, 2017] and reinforcement learning (RL) [Sutton and Barto, 1998]. 本稿では,ai計画コミュニティの最近の進歩の一つである幅型計画 [lipovetzky and geffner, 2012] について紹介するとともに,最適制御 (bertsekas, 2017) や強化学習 (rl) [sutton and barto, 1998] など,他のコミュニティに共通する問題定式化への適用性について説明する。 0.79
Classical planning deals with the problem of generating a sequence of decisions (plan) traversing a transition system while meeting a specification of the intended behaviour, expressed as a logical goal condition to be satisfied, or as a utility function to be maximized. 古典的な計画では、満足すべき論理目標条件、または最大化すべき実用機能として表現される意図された行動の仕様を満たしながら、トランジッションシステムを横断する一連の決定(計画)を生成する問題を扱う。 0.84
The transition system of a planning problem is defined implicitly by a model which can vary along different dimensions. 計画問題の遷移システムは、異なる次元に沿って変化するモデルによって暗黙的に定義される。 0.77
The main ones explored in this paper impose assumptions on 1) the uncertainty about the initial condition and the effects of each decision, 2) the dynamics represented by the model, 3) the language used to specify the intended behaviour, and 4) whether access to the implicit representation of the model is available. 本稿では,1)初期条件と各決定の効果に関する不確実性,2)モデルで表されるダイナミクス,3)意図された動作を特定するのに使用される言語,4)モデルの暗黙的な表現へのアクセスが可能かどうかについて仮定する。 0.76
∗A position paper for IJCAI 2021 Early Career Spotlight Talk ∗a position paper for ijcai 2021 early careerspotlight talk 0.77
Width-Based algorithms search in the transition system guided by a measure of novelty, defined as a function of the set of features Φ characterising each state of the system. 幅に基づくアルゴリズムは、システムの各状態を特徴付ける特徴の集合の関数として定義される、新奇性の尺度によって導かれる遷移系を探索する。 0.80
The simplest set of features can be defined as an injective function mapping each state variable valuation into a unique feature. 最も単純な特徴のセットは、各状態変数のバリュエーションをユニークな特徴にマッピングする注入関数として定義することができる。
訳抜け防止モード: 最も単純な特徴集合は射影関数として定義できる 各状態変数のバリュエーションをユニークな特徴にマッピングする。
The novelty of a state is then measured in terms of the smallest subset of features made true for the first time in the search. 状態の新規性は、検索において初めて真になった機能の最小のサブセットによって測定される。 0.68
Note that this measure of novelty is agnostic on the model being solved, which lends itself to generalise well over different planning models. この新しさの尺度は、解決されるモデルに依存せず、異なる計画モデルに対してうまく一般化するのに役立つことに注意されたい。 0.59
Remarkably, this measure alone suffices to define the complexity of a problem Π in terms of its width w(Π), independent of the initial and goal conditions of the problem, as well as proving the existence of width-based algorithms which run in time and space exponential in the width of the problem. 注目すべきことに、この測度だけでは、問題の初期条件と目標条件とは独立に、その幅 w( ) で問題の複雑さを定義するのに十分であり、また、問題の幅で時間と空間を指数的に走る幅ベースのアルゴリズムの存在を証明するのに十分である。 0.78
These algorithms have been shown to yield state-of-the-art solvers over a wide range of problems. これらのアルゴリズムは様々な問題に対して最先端の解法をもたらすことが示されている。
訳抜け防止モード: これらのアルゴリズムは to yield state - of - the-art solver over a wide of problems.
Widthbased search departs from other blind search methods like Depth First Search and Breadth First Search, because it exploits the factorized structure of the states to guide its search. 幅ベースの検索は、深度優先探索や幅優先探索のような他の盲目の検索方法から離れる。
訳抜け防止モード: ウィジェットベースの検索は、Depth First SearchやBreadth First Searchなど、他の盲目的検索方法とは別物だ。 国家の因子構造を利用して 探索を導いてくれるからです
2 Novelty and Width-Based Search 2 新規性と幅に基づく検索 0.62
The main concept driving width-based search is the notion of state novelty [Lipovetzky and Geffner, 2012], which depends on states S− s generated before a state s, and the set of features Φ(s) = {f | f ∈ s} true in each state. 幅に基づく探索を駆動する主要な概念は状態の新規性の概念(Lipovetzky and Geffner, 2012)であり、状態 s 以前に生成される状態 S− s と、各状態において真となる特徴の集合 s(s) = {f | f ∈ s} に依存する。 0.79
Definition 1. The novelty of a newly generated state w(s) = minφ⊆Φ(s),φ6⊆Φ(s′),s′∈S− |φ| is the size of the smallest subset of features true in the state, and false in all previously generated states S− s . 定義1。 新しく生成された状態 w(s) = min φ φ(s), φ6 φ(s′),s′ψs− |φ| のノベルティは、状態において真となる特徴の最小部分集合の大きさであり、前もって生成された全ての状態 s− s において偽である。
訳抜け防止モード: 定義1。 新たに生成される状態 w(s ) = minφ(s) の新規性は、状態において真である最小の部分集合のサイズである。 そして、前述したすべての状態 S− s において偽となる。
s In classical planning, without loss of generality states are described in terms of boolean fluents F , it is natural then to define the state features as Φ(s) = {f | f ∈ s, f ∈ F }. s 古典的な計画では、一般状態を失うことなくブールフルート f を用いて記述され、状態特徴を φ(s) = {f | f ∈ s, f ∈ f } と定義するのは自然である。 0.80
Therefore, the novelty of states in classical planning ranges from 1 to |F |, given that the smallest subset of features contains a single fluent, while the largest contains all the fluents of the problem. したがって、古典計画における状態の新規性は 1 から |F | まで様々である。
訳抜け防止モード: したがって、古典的な計画における状態の新規性は 1 から |F | 特徴の最小の部分集合が 単一の流動性を含んでいることを考えると 最大のものは 問題の流動性です
The number of subsets, and hence the number of possible novel states is O(|P(F )|). 部分集合の数、したがって可能な新規状態の数は o(|p(f )|) である。 0.72
The simplest width-based search algorithm exploiting novelty is Iterative Width. 最も単純な幅ベースの検索アルゴリズムはIterative Widthである。 0.74
IW(k) is a breadth-first search (BrFS) pruning states whose novelty is greater than k. IW(k) considers features up to size k and runs in time and space exponential in k, i.e. iw(k) は幅優先探索 (brfs) であり、その新規性は k よりも大きい。
訳抜け防止モード: IW(k) は k よりも新規性が大きい幅優先探索 (BrFS ) プルーニング状態である。 時間と空間を指数関数的に K、すなわち
O(|F |k). Remarkably, in spite of IW being incomplete, Lipovetzky and Geffner [2012] showed that O(|F |k)。 驚くべきことに、iwが不完全であるにもかかわらず、lipovetzky と geffner [2012] は、 0.72
the linear and quadratic time IW(1) and IW(2) solve respectively 37% and 88% of 37,921 instances from benchmarks up to 2012, where each problem with a goal made of |G| fluents is split into |G| problems, each with a single goal fluent. 線形時間 IW(1) と IW(2) はそれぞれ、ベンチマークから2012年までの37,921のインスタンスの37%と88%を解く。
訳抜け防止モード: 線形時間 IW(1 ) と IW(2 ) はそれぞれ、ベンチマークから2012年までの37,921インスタンスの37 %と88 %を解いた。 ここで、|G| fluents のゴールを持つ各問題は |G| 問題に分割される。 それぞれに1つのゴールがある
This performance is not accidental, as it is possible to prove that any instance of most planning domains can be solved by IW(2) provided that the goal |G| = 1 is a single fluent. この性能は偶然ではなく、ゴール |G| = 1 が単流流であることを考えると、ほとんどの計画領域の任意のインスタンスが IW(2) によって解けることを証明できる。 0.71
The key notion exploited by IW, and many subsequent width-based algorithms is the notion of problem width [Lipovetzky and Geffner, 2012]. IWとその後の多くの幅に基づくアルゴリズムが活用する重要な概念は問題幅の概念である [Lipovetzky and Geffner, 2012]。 0.78
Similar treewidth notions have been proposed to bound algorithms over intractable problems in constraint satisfaction and bayesian networks [Dechter, 2003; Pearl, 1988]. 同様のツリー幅の概念は、制約満足度やベイジアンネットワーク(Dechter, 2003; Pearl, 1988)における難解な問題に対するアルゴリズムの有界性について提案されている。 0.63
Definition 2. The width w(P ) of a classical planning problem P is the minimum k for which there is a sequence ~Φ = (φ0, . 定義2。 古典的な計画問題 p の幅 w(p ) は、列 ~ φ = (φ0, ) が存在する最小 k である。 0.74
. . , φn) of feature subsets, each |φi| ≤ k with at most k features, such that 1) φ0 ⊆ Φ(s0) is true in the initial state, 2) any optimal plan achieving φi can be extended into an optimal plan for φi+1 with a single action, i = 0, . . . , φn) の特徴部分集合の各 |φi| ≤ k は、少なくとも k 個の特徴を持ち、(1) φ0 は初期状態において真であり、(2) φi を達成する任意の最適計画は、単一の作用 i = 0, で φi+1 の最適計画に拡張することができる。 0.85
. . , n − 1, 3) any optimal for φn is an optimal plan for the problem P . . . φn に対する任意の最適計画 , n − 1, 3) は問題 P に対する最適計画である。 0.84
If the goal is true in the initial state, for convenience we set w(P ) = 0, and w(p) = |F | + 1 if the problem is unsolvable. 初期状態でゴールが真であれば、都合の良いことに w(P ) = 0 と w(p) = |F | + 1 とすると、問題は解決不可能である。 0.78
Note that there is no assumption imposed upon how the transition function is specified, the definition only assumes a factored representation of the states in terms of state features. 遷移関数の指定方法に課せられる仮定は存在しないことに注意し、定義は状態特徴の観点から状態の因子的表現のみを仮定する。 0.87
Intuitively, ~Φ defines a sequence of sub-goals that constraints the search to ensure the goal will be reached optimally. 直感的には ~ φ は探索が最適に到達することを保証するために探索を制約する一連の部分ゴールを定義する。
訳抜け防止モード: 直感的には ~ は、サブゴールの列を定義する。 目標を最適に達成するために 探索を制約する
Width characterises the size of the biggest constraint needed. widthは、必要な最大の制約のサイズを特徴付ける。 0.71
If the width of a problem is known to be w(P ) = k, then IW(k) is guaranteed to solve the problem optimally (shortest path) 1. 問題の幅が w(p ) = k であると知られている場合、iw(k) は問題を最適(最短経路) 1 で解くことが保証される。 0.77
Lipovetzky [2014] has constructive proofs for several known domains such as Blocks world, Logistics, and 15puzzle, showing that independently of their size and initial situation, each single goal fluent can be reached with width 2. Lipovetzky [2014]は、Blocks world、Logistics、および15puzzleのようないくつかの既知のドメインに対して、そのサイズと初期状況とは独立して、それぞれのゴールが幅2で到達可能であることを示す建設的証明を持っている。 0.59
When the width of the problem is unknown, IW runs by iteratively increasing the bound from 1 to |F | until the problem is solved. 問題の幅が不明な場合、iw は問題を解くまで 1 から |f | への境界を反復的に増加させる。 0.70
IW(|F |) is equivalent to BrFS pruning only true state duplicates, if no solution is found, then the problem is unsolvable. IW(|F |) は BrFS と等価であり、真の状態の複製のみをプルーニングする。
訳抜け防止モード: IW(|F | ) は BrFS と等価であり、真の状態の複製のみをプルーニングする。 解決策が見つからなければ 問題は解決できない
While IW is not practical for planning with larger goals |G| > 1, it has been shown to work well for Finite Horizon Optimal Control and RL problems (Section 4), and it underpins the ideas in other state-of-the-art planners for satisficing planning known as best first width search (BFWS). IW はより大きな目標 |G| > 1 で計画するには実用的ではないが、有限水平最適制御と RL の問題(第4部)にはうまく機能し、BFWS として知られる計画に適合する他の最先端の計画立案者の考えを裏付けるものである。 0.78
State-of-the art classical planners rely on best first search algorithms (BFS) guided by goal-oriented heuristics derived automatically from the specification of the problem [Geffner and Bonet, 2013]. 最先端の古典的プランナーは、問題の仕様から自動的に導出されるゴール指向ヒューリスティックス(Geffner and Bonet, 2013)によって導かれる最良の第一探索アルゴリズム(BFS)に依存している。 0.67
One of the known pitfalls of BFS is that it can get trapped in large plateaus. BFSの既知の落とし穴の1つは、大きな高原に閉じ込められることである。 0.66
To avoid this, BFWS [Lipovetzky and Geffner, 2017a] balances exploration and exploitation by integrating novelty with goal directed heuristics through the evaluation function f = hwH , ~hi, where ~h is an ordered sequence of heuristics, and wH is the novelty measure. これを避けるため、BFWS [Lipovetzky and Geffner, 2017a] は、f = hwH , ~hi という評価関数を通して、新規性と目標指向ヒューリスティックスを統合することで、探索と搾取のバランスをとる。
訳抜け防止モード: これを避けるために。 BFWS [Lipovetzky and Geffner, 2017a ] は、評価関数 f = hwH を通じて、新規性と目標指向ヒューリスティックスを統合することにより、探索と搾取のバランスをとる。 ~hi, where ~h is a order of heuristics, wHは斬新な尺度です。
Given a state s, novelty in BFWS is computed with respect to states s′ ∈ S− s seen before with the same heuristic value h(s) = h(s′), for all h ∈ H. H 状態 s が与えられたとき、BFWS の新規性は、すべての h ∈ H に対して同じヒューリスティック値 h(s) = h(s′) を持つ状態 s′ ∈ S− に対して計算される。 0.85
1If the problem has non-uniform costs, in order to guarantee op- 1 問題に一様でないコストがある場合、op- 0.74
timality IW should run Dijkstra instead of BrFS. 最適性 IW は BrFS の代わりに Dijkstra を実行するべきである。 0.59
is a set of heuristics that partition the state space for a more refined computation of novelty. より洗練されたノベルティの計算のために状態空間を分割するヒューリスティックスの集合である。 0.67
The evaluation function f breaks ties lexicographically, preferring novel states first, and then breaking ties by goal-oriented heuristics. 評価関数fは、語彙的に結合を破り、まず新しい状態を好み、次に目標指向のヒューリスティックスによって結合を破る。 0.53
Preferring first the exploration term over the exploitation term is beneficial, as it limits the search effort spent escaping heuristic value plateaus. ヒューリスティックな価値高原から逃れるのに費やした探索努力を制限するので、最初に搾取期間を優先することは有益である。
訳抜け防止モード: 搾取期間よりも最初に探査期間を優先することは有益である。 探索に費やした ヒューリスティックな価値の高原を 逃がした
One of the best performing BFWS variant uses a single heuristic ~h = (#g) counting the number of unachieved goals, and novelty uses H = h#g, #ri the goal counting heuristic along with a counter #r keeping track of how many relevant fluents R ⊆ F have been achieved along the path to the current state s from the initial state. bfwsの最も優れた変種の一つは、1つのヒューリスティック ~h = (#g) で達成されていない目標の数を数え、ノベルティはh = h#g、#ri the goal counting heuristic を、カウンタ #r は現在の状態からsへの経路に沿ってどれだけのフルートが達成されたかを追跡する。
訳抜け防止モード: 最も優れたBFWS変種の一つは、単一のヒューリスティック ~h を用いる = (#g) 達成できない目標の数を数えます ノベルティは H = h#g, # ri を使ってヒューリスティックをカウントし、カウンター # r は、初期状態から現在の状態 s への経路に沿って、どれだけの関連する流れが達成されたかを追跡する。
The relevant set R is defined as the fluents that appear in a polynomial relaxation known as delete-relaxed plan [Geffner and Bonet, 2013]. 関連する集合 R は、削除緩和計画 (delete-relaxed plan) として知られる多項式緩和に現れる流束として定義される[Geffner and Bonet, 2013]。 0.62
This version won the agile track of the last international Planning Competition (IPC) [Frances et al , 2018], which measures the speed and number of solutions found in 5 minutes. このバージョンは、前回のinternational planning competition (ipc) [frances et al , 2018]のアジャイルトラックを獲得し、5分で見つかるソリューションのスピードと数を計測した。 0.67
An incomplete but polynomial version that instead uses the novelty measure to prune states with novelty WH > 1, solved 73% of the problems with |G| > 1, independent of the size of their goal. その代わりにノベルティ測度を用いてノベルティ w > 1 の状態をプルーンする不完全だが多項式版は、目標の大きさによらず |g| > 1 の73%の問題を解いた。 0.64
This polynomial version, 1-BFWS, can quickly solve or return no solution, and it can be used as a preprocessing step to find a solution. この多項式バージョンである1-BFWSは、解を素早く解いたり返したりすることができ、解を見つけるための前処理ステップとして使用できる。
訳抜け防止モード: この多項式バージョンは 1-BFWS であり、解を素早く解いたり返したりできる。 ソリューションを見つけるための 事前処理のステップとして使えます
This was instrumental for DUALBFWS second place on the satisficing track, where 1-BFWS run first, and a complete BFWS incorporating other planning heuristics was run if no solution was found by 1-BFWS. これは1-BFWSが最初に実行され、他の計画的ヒューリスティックを組み込んだ完全なBFWSが1-BFWSが解けなければ実行された。 0.63
In fact, it was shown that a family of polynomial k-BFWS algorithms can render close to state-of-the-art performance with provable bounds [Lipovetzky and Geffner, 2017b]. 実際、多項式 k-bfws アルゴリズムの族は、証明可能な境界 [lipovetzky and geffner, 2017b] で最先端の性能に近くレンダリングできることが示されている。 0.64
BFWS has performed well beyond classical planning. BFWSは、古典的な計画よりもうまく機能している。 0.53
It has been used for decentralized multi-agent planning [Gerevini et al , 2019], and regression for classical planning [Lei and Lipovetzky, 2021]. 分散マルチエージェント計画(gerevini et al, 2019)や,古典的計画(lei and lipovetzky, 2021)にも使用されている。
訳抜け防止モード: 分散マルチエージェント計画(Gerevini et al, 2019)に使用されている。 そして古典的な計画のための回帰[Lei and Lipovetzky, 2021 ].
Other notable width-based planners have shown great performance with an alternative novelty formulation [Katz et al , 2017] and integrated in Enforced Hill Climbing [Fickert, 2018] and BFS with lookaheads [Fickert, 2020]. その他の特筆すべき幅ベースプランナーは、代替のノベルティ定式化(Katz et al , 2017)とEnforced Hill Climbing(Fickert, 2018)とBFS(Fickert, 2020)で優れたパフォーマンスを示している。 0.65
3 Planning with Simulators シミュレータによる3つの計画 0.64
A model described formally by a planning language is a key requirement to enable the derivation of informed heuristics. 計画言語によって公式に記述されたモデルは、情報ヒューリスティックスの導出を可能にするための重要な要件である。
訳抜け防止モード: 計画言語によって正式に記述されるモデルは重要な要件である インフォームドヒューリスティックの導出を可能にする。
Having access to the structure of the actions and state variables resulted in an active area of research, improving performance of existing solvers through several relaxations underpinning existing heuristics [Geffner and Bonet, 2013]. 動作と状態変数の構造にアクセスできることは研究の活発な領域となり、既存のヒューリスティックスを支えるいくつかの緩和(Geffner and Bonet, 2013)を通じて、既存の解法の性能を改善した。 0.71
The language role was not only descriptive, but also computational. 言語の役割は記述的だけでなく計算的でもあった。 0.74
Yet, it is known that every language has its expressive limitations, some problems are easier to model than others. しかし、すべての言語に表現力のある制限があることは知られており、いくつかの問題は他の言語よりもモデリングが容易である。 0.57
Take for instance Pacman, the behaviours of the ghosts are easily specified pragmatically but not declaratively [Frances et al , 2017]. 例えばpacmanでは、ゴーストの振る舞いは実用的だが宣言的ではない(frances et al , 2017)。
訳抜け防止モード: 例えば、pacman。 ゴーストの振る舞いは実践的に簡単に特定できるが、宣言的には指定されない [frances et al, 2017]。
Other problems are just easier to specify by non-planning experts via simulation engines. その他の問題は、シミュレーションエンジンによる非計画専門家による指定が容易である。 0.66
Take the Atari games as an example, or platforms like OpenAIGym used to specify RL problems. Atariのゲームを例にとり、OpenAIGymのようなプラットフォームを使ってRLの問題を特定する。 0.77
The downside of using simulators to specify classical planning problems is that most solvers will not work, as their heuristics require access to the specification of the problem. 古典的な計画問題の特定にシミュレータを使うことの欠点は、ほとんどの解法が機能しないことである。
訳抜け防止モード: 古典的な計画問題を特定するためにシミュレータを使うことの欠点は、 ほとんどの解法は機能しない ヒューリスティックは問題の仕様に アクセスする必要がある
Frances et al [2017] insight was to realize that state-ofthe-art BFWS algorithms do not require access to the transition function, novelty and goal counting only rely on a factored representation of the states. frances et al [2017] insightは、最先端のbfwsアルゴリズムが遷移関数へのアクセスを必要とせず、新規性と目標カウントが状態の因子表現のみに依存していることに気付きました。 0.70
The only term that requires access to the action’ structure is the #r counter, as the set of relevant fluents are computed by the delete relaxation. アクションの構造にアクセスする必要のある唯一の用語は#rカウンタであり、関連する流れのセットは削除緩和によって計算される。 0.80
Hence, Frances et al [2017] proposed alternative methods to derive the relevant fluents over problems specified via simulators. したがって、Frances et al [2017] はシミュレータで指定された問題に対して関連する流動性を引き出す方法を提案した。 0.62
Namely, the linear IW(1) or quadratic IW(2) were used to create a lookahead at the initial state, and fluents on the way to paths achieving any single goal were marked as relevant. すなわち、線形IW(1)あるいは二次IW(2)は初期状態のルックアヘッドを作成するために用いられ、単一の目標を達成する経路への流れは関連しているとマークされた。 0.74
The experimental results over the set of problems from IPC-2014 showed that this version, which does not have access to the structure of the transition function and does not impose a restriction over how the model is specified, performed as well as other planners that had access to the model. ipc-2014の一連の問題に対する実験の結果、このバージョンは遷移関数の構造にアクセスできず、モデルをどのように指定するかの制限を課さず、モデルにアクセスした他のプランナーと同様に行われた。
訳抜け防止モード: ipc-2014の一連の問題に対する実験結果から,このバージョンが有効であることが判明した。 遷移関数の構造にアクセスできず モデルがどのように指定されるかという制限を課しません。 モデルにアクセスした他のプランナーと同様に実行される。
These results were a strong argument towards using planning solvers beyond the scope defined by a language, and a bridge towards other research areas whose techniques focus on problems specified through simulators (model-free). これらの結果は、言語が定義する範囲を超えたプランニング・ソルバの使用に対する強い議論であり、シミュレータ(モデルフリー)で指定された問題に焦点を当てた他の研究分野への橋渡しであった。 0.61
In fact, this enabled BFWS to be used over theories encoded via external reasoners for Task and Motion Planning [Ferrer-Mestres et al , 2017], track beliefs online over POMDPs for transparent planning [MacNally et al , 2018], and to reason over epistemic knowledge while planning [Hu et al , 2019]. 実際、これはbfwsをタスクおよびモーション計画の外部推論者(ferrer-mestres et al , 2017)によって符号化された理論上で使用し、透明な計画のためのpomdp(macnally et al , 2018)上でオンライン上の信念を追跡し、計画中の認識論的知識を推論することを可能にした [hu et al , 2019]。 0.61
4 Numeric Features So far, the discussion of width-based algorithms has focused on classical planning, as their performance is understood in terms width w(P ). 4つの数値的特徴 これまでのところ、幅に基づくアルゴリズムの議論は古典的な計画に焦点を合わせており、その性能は幅w(P)で理解されている。 0.64
This section discusses how these algorithms have been used beyond classical planning, but, without provable performance guarantees, given that a width notion for these problems is yet to be discovered. 本稿では、これらのアルゴリズムが古典的計画を超えてどのように使われているかについて論じるが、証明可能な性能保証がないため、これらの問題に対する幅の概念はまだ発見されていない。
訳抜け防止モード: この節では、これらのアルゴリズムが古典的計画を超えてどのように使われてきたかについて論じる。 しかし 証明可能な性能保証がなければ これらの問題の幅の概念はまだ見つかっていません
Classic Control Problems. Classic deterministic control problems differ from classical planning mainly in three dimensions: 1) state variables are numeric, 2) continuous or discrete dynamics are typically encoded via a simulator, 3) and the target behaviour is often expressed via a cost (reward) function to be maximized (minimized). 古典的な制御問題。 古典的な決定論的制御問題は、主に3次元の古典的な計画と異なる: 1) 状態変数は数値的であり、2) 連続的または離散的ダイナミクスはシミュレーターによって符号化され、3) ターゲットの振る舞いは最大化されるコスト(最小化)関数によって表現される。 0.73
None of these changes preclude the use of width-based algorithms, as long as state features are defined over numeric state variables. これらの変更は、数値状態変数上で状態が定義される限り、幅ベースのアルゴリズムの使用を妨げない。 0.80
Ramirez et al [2018] showed that complex non-lineal aircraft simulations can be controlled by running IW(1). ramirez氏ら[2018]は、複雑な非直線航空機シミュレーションはiw(1)で制御できることを示した。
訳抜け防止モード: Ramirez et al [2018 ] 複雑な非線形航空機シミュレーションはIW(1 )を実行することで制御できる。
In this context, IW(1) can be understood as an approximate dynamic programming algorithm, solving the model predictive control problem iteratively over a rolling horizon window [Bertsekas, 2017]. この文脈では、iw(1)は近似動的プログラミングアルゴリズムとして理解でき、モデル予測制御問題をローリングホライズンウィンドウ(bertsekas, 2017)上で反復的に解くことができる。 0.77
Each problem is a finite horizon optimal control problem which IW(1) solves, without optimality guarantees. 各問題は、iw(1) が最適性保証なしに解く有限地平線最適制御問題である。 0.72
IW(1) builds a lookahead by expanding novel states only, and returning the action leading to the state with the least accumulated cost. IW(1)は、新しい状態のみを拡大し、最小のコストで状態につながるアクションを返却することで、ルックアヘッドを構築する。 0.68
The features used for novelty map each state variable xi k ∈ R valuation into a unique feature f i x : xi 7→ [0, 2B − 1], where i is the i-th state variable, and B is the number of bits in the floating point representation, effectively, the binary encoding of the number. 新規性のために使われる特徴は、各状態変数 xi k ∈ R の評価値を、i を i 番目の状態変数とし、B を浮動小数点表現におけるビットの個数とする一意的な特徴 f i x : xi 7→ [0, 2B − 1] にマッピングする。 0.80
This definition of features is finite, given that existing models of computation only allow for finite arithmetic precision. この特徴の定義は、既存の計算モデルでは有限算術精度しか持たないため有限である。 0.86
IW(1) maps a state into its features Φ(xk) = {f i x |xi ∈ xk}, only expanding states with a variable whose real value has not been seen before. IW(1)地図 状態からその状態への特徴 φ(xk) = {f i x |xi ∈ xk} は、実数値がこれまで見られなかった変数を持つ状態だけを展開する。 0.81
This search, which ignores completely the objective of the optimization problem, is powerful enough to create real-time aircraft manoeuvres from first principles that follow dynamical constraints and the cost function. 最適化問題の目的を完全に無視するこの探索は、動的制約とコスト関数に従う最初の原理からリアルタイムの航空機操作を作成できるほど強力である。 0.90
In tasks with sparse rewards or with rewards attainable only if the goal is reached and maintained until a given horizon, these naive novelty features do not work well. わずかな報酬や報酬を持つタスクでは、目標が与えられた水平線まで到達して維持される場合のみ、これらのナイーブなノベルティ機能はうまく機能しない。 0.64
Teichteil-K¨onigsbuch et al [2020] proposed an alternative general dynamic encoding of state features taking into account the dynamics of the problem, and the choices made by the width-based search algorithm. teichteil-k sonigsbuch et al [2020] は、問題のダイナミクスと、幅ベースの探索アルゴリズムによる選択を考慮した、状態特徴のより一般的な動的符号化を提案した。 0.75
These features, known as Boundary Extension Encoding (BEE) features, are designed to mark as novel those states that push the boundaries of a state variable, keeping track of the valuations already discovered by the search. 境界拡張エンコーディング(BEE)機能と呼ばれるこれらの機能は、状態変数の境界を押し上げる新しい状態としてマークされ、検索によって既に発見されたバリュエーションを追跡するように設計されている。 0.75
If a state variable extends the boundaries, a new interval with a new unique index is created tracking the range of the extension, otherwise, the index of the interval where the state variable belongs is returned. 状態変数がバウンダリを拡張する場合、新しいユニークなインデックスを持つ新しいインターバルが、拡張の範囲を追跡するように作成され、そうでなければ、状態変数が属するインターバルのインデックスが返される。 0.78
Novelty is then computed by mapping a state into its BEE interval index for each state variable. 新規性は、各状態変数のBEE間隔インデックスに状態をマッピングすることで計算される。 0.73
This encoding is used by polynomial versions of k-BFWS with no heuristic information, where novelty alone outperforms Deep RL over classical control problems. このエンコーディングは、ヒューリスティックな情報を持たないk-bfwsの多項式バージョンで使われ、新しさだけが古典的な制御問題よりも深いrlを上回る。 0.55
It can solve Mountain Car in 4.6 seconds whereas PPO2 [Schulman et al , 2017] cannot learn a valid policy after 7 hours. マウンテンカーは4.6秒で解けるが、PPO2(Schulman et al , 2017)は7時間後に有効な政策を学ぶことができない。 0.74
In Acrobot, PPO2 takes 20 minutes longer than k-BFWS to find a policy of the same quality. Acrobotでは、PPO2は同じ品質のポリシーを見つけるのに、k-BFWSよりも20分長くかかる。 0.68
In CartPole, kBFWS finds the optimal solution stabilizing the pole across the full trajectory, whereas PPO2 takes 3 times longer to find such policy. CartPole では、kBFWS は極を全軌道にわたって安定化させる最適解を見つけ、一方 PPO2 はそのようなポリシーを見つけるのに3倍の時間がかかる。 0.63
If an alternative IW version known as RolloutIW [Bandres et al , 2018] is used, a decision limit of 200ms suffices to solve the problem in real time. RolloutIW (Bandres et al , 2018) と呼ばれる別の IW バージョンが使用されている場合、200ms という決定限界は、この問題をリアルタイムで解決するのに十分である。 0.64
Compared with LQR controllers, k-BFWS finds solutions of similar quality, but it is significantly better over Acrobot when initial states are perturbed, as this breaks the controllability guarantees of the LQR solution. lqrコントローラと比較すると、k-bfwsは同様の品質のソリューションを見つけるが、初期状態が摂動した場合はacrobotよりもかなり優れている。
訳抜け防止モード: LQRコントローラと比較して、k-BFWSは同様の品質のソリューションを見つける。 しかし、初期状態が乱れたとき、Acrobotよりもはるかに良いです。 これにより、LQRソリューションの可制御性が保証される。
Reinforcement Learning Problems. Deterministic RL problems differ from classical planning in the same dimensions as control problems, the transitions are encoded through a simulator, a goal region is absent but instead rewards are used, where the optimal solution aims to maximize the accumulated reward over a fixed horizon. 強化学習問題。 決定論的rl問題は、制御問題と同じ次元の古典的な計画と異なり、遷移はシミュレータを通して符号化され、ゴール領域は存在せず、代わりに報酬が使用され、最適な解は固定地平線上の累積報酬を最大化することを目的としている。
訳抜け防止モード: 強化学習問題。 決定論的RL問題は制御問題と同じ次元の古典的計画とは異なる。 遷移はシミュレータを通してコード化されます ゴールリージョンが欠落している 代わりに報酬が使われます 最適な解決策は 一定の地平線上で 蓄積された報酬を最大化することです
The Arcade Learning Environment is a popular simulator for testing RL algorithms [Bellemare et al , 2013], supporting 54 Atari games with a horizon of 18,000 steps, amounting for 5 minutes of real-time gameplay. Arcade Learning Environmentは、RLアルゴリズムをテストするための人気のあるシミュレータ(Bellemare et al , 2013)で、18,000ステップの水平線を持つ54のAtariゲームをサポートし、5分間のリアルタイムゲームプレイを行う。 0.76
RL approaches have been successfully applied over this benchmark. RLアプローチはこのベンチマークでうまく適用されている。 0.64
An alternative approach uses a approximate dynamic programming algorithms like IW over a fixed budget to build a lookahead tree, returning the best action, and moving to the next step. 別のアプローチでは、固定予算上でiwのような近似動的プログラミングアルゴリズムを使用してルックアヘッドツリーを構築し、ベストアクションを返却し、次のステップに移行する。 0.67
IW(1) was shown to outperform UCT, a Monte Carlo Tree Search algorithm akin to the one used in the solver that outperformed Lee Sedol in Go, using each byte of the 128 Bytes RAM as a novelty state features fi ∈ [0, 255], i = 1, . IW(1)は、128バイトのRAMの各バイトを新規状態として、i = 1 の fi ∈ [0, 255] を用いて、Go のLee Sedol を上回る解法に類似したモンテカルロ木探索アルゴリズムである UCT より優れていることを示した。 0.74
. . , 128 [Lipovetzky et al , 2015]. . . 128 [Lipovetzky et al , 2015]。 0.77
That is, a state would be novel if it has a byte value which has not been seen before. つまり、以前見たことのないバイト値を持つ状態は、新規である。 0.48
This measure allowed for the search to reach far away rewards, performing better than UCT over 31 out of この手段により、検索は遠く離れた報酬に到達でき、31人中31人以上でuctよりもパフォーマンスが良い 0.58
54 games, whereas UCT outperformed IW(1) in 19 games. 54試合, UCTは19試合でIW(1)を上回った。 0.71
IW(1) results were further improved by breaking ties in the expansion of states with the accumulated reward, and refining the definition of novelty by marking a feature as novel if it was achieved by a state with a larger accumulated reward than the best state seen so far with that feature [Shleyfman et al , 2016]. IW(1) は, 累積報酬を伴う状態の拡大の結びつきを打破し, その特徴を有する最高の状態(Shleyfman et al, 2016) よりも大きな累積報酬を有する状態によって達成された場合, 特徴を新規としてマークすることで, 新規性の定義を洗練することにより, さらに改善された。 0.74
This sufficed for IW to outperform UCT in 44 out of 53 games. この結果、IWは53試合中44試合でUTTを上回った。 0.63
Furthermore, when screen features capturing spacial and temporal relations of pixels taken from the screen input state are used to define novelty, along with RIW, a width-based search that uses depth-first rollouts instead of BrFS as the underlying search, then, RIW with a real-time budget of 0.5 seconds is the best in 30,6% of the games, while Deep RL, Shallow RL, and a human expert are best in 24.4%, 12.2% and 32.6% respectively. さらに、画面入力状態から取得した画素の空間的および時間的関係をキャプチャする画面特徴が、BrFSの代わりに深度優先のロールアウトを用いた幅ベースの検索であるRIWと共に、新規性を定義するために使用される場合、リアルタイム予算0.5秒のRIWは306%で、Deep RL、Shallow RL、および人間のエキスパートはそれぞれ24.4%、12.2%、32.6%でベストである。 0.79
With a higher budget of 32s per action RIW outperforms human experts in 75.5% of the games [Bandres et al , 2018]. アクション当たり32の予算を持つriwは、ゲーム[bandres et al , 2018]の75.5%で人間専門家を上回っている。 0.58
5 Research Directions Novelty Approximations for High Width. 5研究方向 高幅の新規近似。 0.64
Checking that a state has novelty k requires in the worst case keeping track in memory of all previously seen |Φ|k features, as well as enumerating the same amount of features per state. 状態 k が新規であることを確認するには、最悪の場合、前述した | |k のすべての特徴を記憶し、状態毎に同じ量の特徴を列挙する必要がある。 0.71
This computation makes it impractical to compute novelty values greater than 2. この計算は2より大きい新奇値を計算するのに実用的でない。 0.72
Recently, Singh et al [2021] have shown that sampling techniques can be used to enumerate state features, and Bloom filters can be used to track the features seen so far, bringing the complexity down to linear time, i.e. 最近、Singh et al [2021] は、サンプリング技術は状態特徴の列挙に利用でき、ブルームフィルタは、これまで見てきた特徴の追跡に利用でき、複雑さを線形時間に抑えることができることを示した。 0.77
O(k|Φ|). This novelty approximation can increase or decrease the width of the problems, but this error probability has been characterized and shown that in practice is quite low. O(k|)。 この斬新な近似は問題の幅を増大または減少させることができるが、この誤差確率は特徴づけられ、実際は極めて低いことが示されている。 0.77
Furthermore, Singh et al [2021] proposed an approximation of BFWS using an adaptive policy to forego the expansion of some states, controlling the exponential growth of states with novelty k, ensuring that states with high novelty can be expanded. さらに、Singh et al [2021] は適応的な政策を用いてBFWSの近似を提案し、いくつかの状態の膨張を予知し、新規性kによる状態の指数的成長を制御し、高い新規性を持つ状態の拡張を可能にする。 0.69
This algorithm manages to exploit a higher range of novelty values, and is faster than other state-of-the-art Widthbased planner. このアルゴリズムは、より広い範囲のノベルティ値を利用することができ、他の最先端の幅ベースのプランナーよりも高速である。 0.54
This line of research can enable solving high width problems with polynomial guarantees. この一連の研究は多項式保証で高幅問題を解くことができる。 0.71
Serializations and Width. Lipovetzky [2014] suggested that classical planning problems are hard to solve if they either have high atomic width, or their goals G are hard to serialize into a sequence of sub-problems, achieving one subgoal at a time. シリアル化と幅。 lipovetzky [2014] は、原子幅が高い場合や目標gが一連のサブプロブレムにシリアライズしにくく、一度に1つのサブゴールを達成する場合、古典的な計画問題を解くのは難しいと示唆した。 0.70
A simple serialized IW (SIW) algorithm doing hill-climbing over the set of goals, using IW to achieve one more single goal g ∈ G at a time until all goals are achieved, was sufficient to show that 71% of problems with |G| > 1 were solvable with low width, once this serialization was attempted. すべてのゴールを達成するまで一度に1つの単一のゴール g ∈ G を達成するために IW を用いて、ヒルクライミングを行う単純なシリアライズ IW (SIW) アルゴリズムは、|G| > 1 の問題の 71% が低幅で解決可能であることを示すのに十分であった。 0.81
Frances et al [2017] showed that novelty features can be encoded programmatically as control knowledge to lower the width of a problem and help such serializations. Frances et al [2017] は、新しい特徴を制御知識としてプログラム的に符号化し、問題の幅を低くし、そのようなシリアライズを支援することを示した。 0.61
This begs the question on whether such serializations can be encoded via domain knowledge or through state novelty features in such a way that problems with |G| > 1 have provable width w(P ) = 1. これは、そのような直列化が、ドメイン知識を通して、あるいは |g| > 1 の問題が証明可能な幅 w(p ) = 1 を持つような方法で、状態のノベルティ特徴を通してエンコードできるかどうかを問うものである。
訳抜け防止モード: このことは、そのようなシリアライゼーションがドメイン知識や状態の新規性機能を通じてコード化できるかどうかという疑問を提起する。 G| > 1 の問題は証明可能な幅 w(P ) = 1 である。
If such encoding can be generated automatically, planning problems could be solved with linear time guarantees with no restriction on the size of their goal. このようなエンコーディングが自動的に生成される場合、計画問題は目標のサイズに制限なく線形時間保証で解決できる。 0.74
Recently, Bonet and Geffner [2021] proved the connection be- 最近 bonet と geffner [2021] は、be の接続を証明した。 0.65
tween generalized planning and planning width. 計画と計画の幅を一般化した 0.72
Generalized plans take the form of a policy mapping state features into actions and solve multiple instances of a problem at once. 一般的な計画では、状態の特徴をアクションにマッピングし、一度に複数の問題のインスタンスを解決します。
訳抜け防止モード: 汎用プランは、状態特徴をアクションにマッピングするポリシーの形式を取る 一度に複数の問題を 解決するのです
The same language used to specified the rules of a general policy can be used to specify general serializations for planning problems, and their performance can also be understood in terms of their planning width. 一般的なポリシーのルールを指定するのに使用されるのと同じ言語は、計画問題の一般的なシリアライズを指定するのに使われ、その性能は計画幅の観点からも理解できる。 0.74
Drexler et al [2021] used this language to elaborate hand crafted serializations encoded as policy sketches to guide SIW with provable low polynomial bounds. drexler et al [2021]は、この言語を使って、ポリシースケッチとしてエンコードされた手作りの直列化を行い、siwを証明可能な低多項式境界で導く。
訳抜け防止モード: Drexler et al [2021 ] SIWを証明可能な低多項式境界でガイドするためにポリシースケッチとして符号化された精巧な手書き直列化を行う。
Known problems accepting polynomial suboptimal solutions such as Floortile, Barman, Childsnack, Driverlog have width w(P ) = 1 and Grid, Tpp, and Schedule have width w(P ) = 2 once a suitable serialization that works for all possible goals and initial states is provided. Floortile, Barman, Childsnack, Driverlog のような多項式準最適解を受け入れる問題は幅 w(P ) = 1 であり、Grid, Tpp, Schedule は幅 w(P ) = 2 である。
訳抜け防止モード: Floortile, Barman, Childsnack, Driverlog のような多項式準最適解を受け入れる既知の問題は、幅 w(P ) = 1 である。 and Grid, Tpp, and Schedule have width w(P ) = 2 once すべての可能な目標と初期状態に対応する適切なシリアライゼーションが提供される。
This line of research has the potential to enable the derivation of such serializations automatically, solving large family of problems with provable performance bounds. この研究の行は、証明可能な性能境界を持つ多数の問題を解くことで、このようなシリアライズを自動的に導出できる可能性を持っている。
訳抜け防止モード: この一連の研究は このような直列化の導出を自動で可能とし、性能限界を証明可能な大きな問題群を解決できるようにする。
Integration of Novelty Planning and Learning. 新奇な計画と学習の統合。 0.77
How to best integrate novelty planning and learning is an active research area. 新規計画と学習を最もうまく統合する方法は、活発な研究分野である。 0.69
Junyent et al [2019] showed over the Atari problems that a policy can be learnt to guide IW into promising search areas, and the last hidden layer of the neural network can be used to encode novelty features, improving the performance of IW further. junyent氏ら[2019]は、政策がiwを有望な検索領域に導くように学習できること、ニューラルネットワークの最後の隠れた層が新奇な特徴のエンコードに使用できること、さらにiwのパフォーマンスを向上させること、といったatariの問題について説明した。
訳抜け防止モード: Junyent et al [ 2019 ] は,Atari の問題について説明した。 IWを将来有望な検索分野に導くための政策を学ぶことができる。 ニューラルネットワークの最後の層は 斬新な特徴をコード化しています IWの性能をさらに向上する。
This suggests that suitable feature encodings can be learnt to improve width-based planners in classical planning, as well as learning goal serializations [Junyent et al , 2021]. このことは,古典的計画における幅に基づくプランナーの学習に適した特徴符号化と,目標シリアライズ学習 [Junyent et al , 2021] が可能であることを示唆している。 0.71
IW planners can also benefit learning algorithms if they are used to bootstrap the learning process, e g , finding a good first solution for problems like Mountain Car, and improve their sample efficiency. IWプランナは、学習プロセスをブートストラップして、例えばMountain Carのような問題に対する優れたファーストソリューションを見つけ、サンプル効率を改善するために使用する場合、学習アルゴリズムの恩恵を受けることができる。 0.70
These research lines can benefit from synergies in both fields. これらの研究線は両方の分野でシナジーの恩恵を受けることができる。 0.51
and Pseudo-Counts. そして Pseudo-Counts 0.73
PseudoNovelty [Bellemare et al , 2016] were introduced as an counts exploration bonus for RL algorithms, but their connection to novelty and width has not been studied yet. PseudoNovelty (Bellemare et al , 2016) は、RLアルゴリズムのカウント探索ボーナスとして導入されたが、その新規性と幅との関係についてはまだ研究されていない。
訳抜け防止モード: PseudoNovelty [ Bellemare et al, 2016 ] は RL アルゴリズムのカウント探索ボーナスとして導入された。 しかし 斬新さと幅との関係は まだ研究されていない
Novelty specific features have also been widely adopted over evolutionary algorithms, introduced by Lehman and Stanley [2011], but their performance have not been connected with a similar planning width bound. リーマンとスタンレーが2011年に導入した進化的アルゴリズムよりも特異な特徴が広く採用されているが、それらの性能は同様の計画幅境界に関連付けられていない。 0.74
If these connections are formalized, alternative exploration methods can be discovered for planning problems, novelty measures with provable bounds may be formulated over new classes of problems, along with new polynomial algorithms. これらの接続が形式化された場合、計画上の問題に対して代替探索法が発見できるが、証明可能な境界を持つ新規測度は、新しい多項式アルゴリズムとともに、新しい問題のクラスで定式化することができる。 0.61
Tractable fragments beyond Planning. 計画以上の難解な断片。 0.54
Planning width has been formulated over classical planning problems, explaining the good performance of width-based algorithms, yet, these algorithms have been shown to perform well over harder problems with a stochastic transition function [Geffner and Geffner, 2015; O’Toole et al , 2019]. 計画幅は古典的な計画問題に対して定式化され、幅に基づくアルゴリズムの優れた性能が説明されているが、これらのアルゴリズムは確率的遷移関数(Geffner and Geffner, 2015; O’Toole et al , 2019)で難しい問題に対してうまく機能することが示されている。 0.73
These problems are characterized as MDPs, the formal model underlying most RL problems. これらの問題は、ほとんどのRL問題の基礎となる形式モデルであるMDPとして特徴づけられる。 0.58
What remains open is to prove that a similar width parameter over MDPs exists. mdps上の同様の幅パラメータが存在することを証明するために、まだオープンである。 0.61
This may lead to new algorithms tapping into the proof’s insights. これは証明の洞察を取り入れた新しいアルゴリズムにつながるかもしれない。 0.77
Acknowledgments I thank IJCAI 2021 program committee for the invitation to speak at the early-career spotlight, my former Ph.D. super- 承認 ijcai 2021プログラム委員会 アーリーキャスターのスポットライトで話すよう招待されたことを感謝します。 0.52
visor, current collaborators, and the planning community for the opportunity to advance this research together. バイザー、現在の協力者、そして、この研究を共に進める機会のための計画コミュニティ。 0.62
References [Bandres et al , 2018] Wilmer. 参考資料[Bandres et al , 2018] Wilmer. 0.88
Bandres, Bonet Bonet, and Hector Geffner. バンドレス、ボーント・ボーント、ヘクター・ゲフナー。 0.45
Planning with pixels in (almost) real time. ピクセルを(ほぼ)リアルタイムに計画する。 0.79
In Proc. AAAI, 2018. Proc。 2018年、AAAI。 0.65
[Bellemare et al , 2013] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. [Bellemare et al , 2013]M.G. Bellemare, Y. Naddaf, J. Veness, M. Bowling. 0.98
The arcade learning environment: An evaluation platform for general agents. アーケード学習環境:一般エージェントのための評価プラットフォーム。 0.67
JAIR, 2013. 2013年、JAIR。 0.75
[Bellemare et al , 2016] Marc G Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and R´emi Munos. Bellemare et al , 2016] Marc G Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, R ́emi Munos。
訳抜け防止モード: [ Bellemare et al, 2016 ] Marc G Bellemare, Sriram Srinivasan, Georg Ostrovski氏、Tom Schaul氏、David Saxton氏、R ́emi Munos氏。
Unifying count-based exploration and intrinsic motivation. 数に基づく探索と本質的な動機の統合。 0.49
In NIPS, 2016. 2016年、NIPS。 0.76
[Bertsekas, 2017] D. Bertsekas. [Bertsekas, 2017]D. Bertsekas. 0.89
Dynamic Programming and Optimal Control. 動的プログラミング 最適制御。 0.64
Athena Scientific, 2017. Athena Scientific, 2017年。 0.92
[Bonet and Geffner, 2021] Blai Bonet and Hector Geffner. [bonet and geffner, 2021] blai bonet と hector geffner です。 0.65
In General policies, serializations, and planning width. 院 一般的な方針、シリアライズ、計画幅。 0.58
Proc. AAAI, 2021. Proc AAAI、2021年。 0.63
[Dechter, 2003] Rina Dechter. [dechter, 2003]rina dechter。 0.74
Constraint Processing. Mor- gan Kaufmann, 2003. 制約処理。 モル ガン・カウフマン、2003年。 0.54
[Drexler et al , 2021] Dominik Drexler, Jendrik Seipp, and Hector Geffner. Drexler et al , 2021] Dominik Drexler, Jendrik Seipp, Hector Geffner. 0.72
Expressing and exploiting the common subgoal structure of classical planning domains using sketches: Extended version. スケッチを用いた古典的な計画ドメインの共通部分構造表現と活用: 拡張バージョン。 0.82
arXiv, 2021. arxiv、2021年。 0.48
[Ferrer-Mestres et al , 2017] Jonathan [Ferrer-Mestres et al , 2017]ジョナサン 0.81
Ferrer-Mestres, Guillem Frances, and Hector Geffner. Ferrer-Mestres、Guillem Frances、Hector Geffner。 0.68
Combined task and motion planning as classical ai planning. 古典的AI計画としてのタスクと動作計画の組み合わせ。 0.64
arXiv, 2017. 2017年、arXiv。 0.56
[Fickert, 2018] Maximilian Fickert. [fickert, 2018] maximilian fickert. 0.65
Making hill-climbing great again through online relaxation refinement and novelty pruning. ヒルクライミングは、オンライン緩和と新奇な刈り取りによって再び素晴らしいものとなった。 0.41
In Proc. SOCS, 2018. Proc。 SOCS、2018年。 0.68
[Fickert, 2020] Maximilian Fickert. フィッカート、2020年 マクシミリアン・フィッカート。 0.48
A novel lookahead strategy for delete relaxation heuristics in greedy best-first search. 欲求最優先探索における緩和ヒューリスティックの除去のための新しいルックアヘッド戦略 0.61
In Proc. ICAPS, 2020. Proc。 ICAPS、2020年。 0.68
[Frances et al , 2017] Guillem Frances, Miquel Ramırez, Nir Lipovetzky, and Hector Geffner. [frances et al, 2017] guillem frances, miquel ramırez, nir lipovetzky, hector geffner。 0.62
Purely declarative action representations are overrated: Classical planning with simulators. 純粋に宣言的なアクション表現は過大評価されている。 0.44
In Proc. IJCAI, 2017. Proc。 IJCAI、2017年。 0.68
[Frances et al , 2018] Guillem Frances, Hector Geffner, Nir Lipovetzky, and Miquel Ramirez. [frances et al, 2018] guillem frances, hector geffner, nir lipovetzky, miquel ramirez。 0.62
Best-first width search in the IPC 2018: Complete, simulated, and polynomial variants. IPC 2018のベストファースト幅検索: 完全、シミュレート、多項式の変種。 0.59
In Int. Planning Competition Booklet (IPC-9), 2018. int所属。 企画コンペティションブックレット(ipc-9)、2018年。 0.55
[Geffner and Bonet, 2013] Hector Geffner and Blai Bonet. Geffner and Bonet, 2013] Hector Geffner and Blai Bonet 0.63
A concise introduction to models and methods for automated planning. 自動化計画のためのモデルと方法の簡潔な紹介。 0.82
Morgan & Claypool Publishers, 2013. モーガン&クレイプール、2013年。 0.55
[Geffner and Geffner, 2015] Tomas Geffner [Geffner and Geffner, 2015]Tomas Geffner 0.75
and Hector Geffner. そしてヘクター・ゲフナー。 0.57
Width-based planning for general video-game playing. 汎用ゲームプレイのための幅ベースのプランニング。 0.53
In Proc. AIIDE, 2015. Proc。 2015年、AIIDE。 0.69
[Gerevini et al , 2019] Alfonso [Gerevini et al , 2019]Alフォンソ 0.77
Nir Lipovetzky, Francesco Percassi, Alessandro Saetti, and Ivan Serina. Nir Lipovetzky、Francesco Percassi、Alessandro Saetti、Ivan Serina。 0.64
Best-first width search for multi agent privacy-preserving planning. マルチエージェント・プライバシ保存計画のためのベストファースト幅検索 0.57
In Proc. ICAPS, 2019. Proc。 2019年、ICAPS。 0.71
Emilio Gerevini, エミリオ・ジェレヴィニ 0.48
[Hu et al , 2019] Guang Hu, Tim Miller, and Nir Lipovetzky. [Hu et al , 2019]Guang Hu、Tim Miller、Nir Lipovetzky。 0.72
What you get is what you see: Decomposing epistemic planning using functional strips. 目に見えるのは、機能的なストリップを使った認識計画の分解です。 0.49
arXiv, 2019. arxiv、2019年。 0.47
[Junyent et al , 2019] Miquel Junyent, Anders Jonsson, and Vicenc¸ G´omez. Junyent et al , 2019] Miquel Junyent、Anders Jonsson、Vicenc G omez。 0.67
Deep policies for width-based planning in pixel domains. ピクセル領域における幅ベースの計画のための深いポリシー 0.66
In Proc. ICAPS, 2019. Proc。 2019年、ICAPS。 0.71
[Junyent et al , 2021] Miquel Junyent, Vicenc¸ G´omez, and Anders Jonsson. [Junyent et al , 2021] Miquel Junyent, Vicenc , G ́omez, and Anders Jonsson. 0.98
Hierarchical width-based planning and learning. 階層的な幅に基づく計画と学習。 0.64
In Proc. ICAPS, 2021. Proc。 ICAPS、2021年。 0.62
[Kahneman, 2011] Daniel Kahneman. ダニエル・カーネマン、2011年。 0.48
Thinking, fast and slow. 考え、速く、そして ゆっくり 0.62
Macmillan, 2011. 2011年、マクミラン。 0.68
[Katz et al , 2017] Michael Katz, Nir Lipovetzky, Dany Moshkovich, and Alexander Tuisov. Katz et al , 2017] Michael Katz氏、Nir Lipovetzky氏、Dani Moshkovich氏、Alexander Tuisov氏。 0.80
Adapting novelty to classical planning as heuristic search. 古典的計画に新鮮さを取り入れたヒューリスティック検索 0.66
In ICAPS, 2017. 2017年、ICAPS。 0.71
[Lehman and Stanley, 2011] Joel Lehman and Kenneth O Stanley. (lehman and stanley, 2011) ジョエル・リーマンとケネス・オ・スタンレー。 0.60
Abandoning objectives: Evolution through the search for novelty alone. 目標の放棄: 新規性のみの探索による進化。 0.79
Evolutionary computation, 2011. 2011年、進化計算。 0.76
[Lei and Lipovetzky, 2021] Chao Lei and Nir Lipovetzky. [Lei and Lipovetzky, 2021]Chao Lei and Nir Lipovetzky. 0.83
Width-based backward search. 幅に基づく後方探索。 0.67
In Proc. ICAPS, 2021. Proc。 ICAPS、2021年。 0.62
[Lipovetzky and Geffner, 2012] Nir Lipovetzky and Hector Geffner. [lipovetzky and geffner, 2012] nir lipovetzkyとhector geffner。 0.71
Width and serialization of classical planning problems. 古典的計画問題の幅とシリアライズ。 0.74
In Proc. ECAI, 2012. Proc。 2012年、ECAI。 0.62
[Lipovetzky and Geffner, 2017a] Nir Lipovetzky and Hector Geffner. [lipovetzky and geffner, 2017a] nir lipovetzkyとhector geffner。 0.77
Best-first width search: Exploration and exploitation in classical planning. best-first width search: 古典的な計画における探索と活用。 0.68
In Proc. AAAI, 2017. Proc。 2017年、AAAI。 0.67
[Lipovetzky and Geffner, 2017b] Nir Lipovetzky and Hector Geffner. [lipovetzky and geffner, 2017b] nir lipovetzkyとhector geffner。 0.77
A polynomial planning algorithm that beats lama and ff. lama と ff を打ち負かす多項式計画アルゴリズム。 0.67
In Proc. ICAPS, 2017. Proc。 2017年、ICAPS。 0.67
[Lipovetzky et al , 2015] N. Lipovetzky, M. Ramirez, and H. Geffner. [Lipovetzky et al , 2015]N. Lipovetzky, M. Ramirez, H. Geffner. 0.93
Classical planning with simulators: Results on the atari video games. シミュレータによる古典的な計画:atariのビデオゲームの結果。 0.81
In Proc. IJCAI, 2015. Proc。 IJCAI、2015年。 0.61
[Lipovetzky, 2014] Nir Lipovetzky. [Lipovetzky, 2014]Nir Lipovetzky。 0.79
Structure and Inference in Classical Planning. 構造と推論 古典的な計画です 0.73
AI Access, 2014. 2014年、AIアクセス。 0.86
[MacNally et al , 2018] Aleck M MacNally, Nir Lipovetzky, Miquel Ramirez, and Adrian R Pearce. [macnally et al , 2018] aleck m macnally, nir lipovetzky, miquel ramirez, adrian r pearce。
訳抜け防止モード: MacNally et al, 2018] Aleck M MacNally, Nir Lipovetzky, ミケル・ラミレスとエイドリアン・R・ピアス。
Action selection for transparent planning. 透明な計画のためのアクション選択。 0.69
In Proc. AAMAS, 2018. Proc。 AAMAS、2018年。 0.68
[Newell and Simon, 1963] A. Newell and H. Simon. (newell and simon, 1963) a・ニューウェルとh・サイモン 0.64
GPS: a program that simulates human thought. GPS:人間の思考をシミュレートするプログラム。 0.83
In Computers & Thought. コンピュータと思考。 0.53
1963. [O’Toole et al , 2019] Stefan O’Toole, Miquel Ramirez, Nir Lipovetzky, and Adrian Pearce. 1963. O’Toole et al , 2019] Stefan O’Toole、Miquel Ramirez、Nir Lipovetzky、Adrian Pearce。 0.78
Width-based lookaheads augmented with base policies for stochastic shortest paths. 確率的最短経路のベースポリシーを付加した幅ベースのルックアヘッド。 0.52
In Proc. HSDIP, 2019. Proc。 HSDIP、2019年。 0.67
[Pearl, 1988] Judea Pearl. [pearl, 1988]judea pearl。 0.75
Probabilistic Reasoning in Intel- Intelにおける確率的推論- 0.57
ligent Systems. インテリジェントシステム。 0.52
Morgan Kaufmann, 1988. モーガン・カウフマン 1988年。 0.58
[Ramirez et al , 2018] Miquel Ramirez, Michael [Ramirez et al , 2018]Miquel Ramirez, Michael 0.84
Papasimeon, Nir Lipovetzky, Lyndon Benke, Tim Miller, Adrian R Pearce, Enrico Scala, and Mohammad Zamani. Papasimeon、Nir Lipovetzky、Lyndon Benke、Tim Miller、Adrian R Pearce、Enrico Scala、Mohammad Zamani。
訳抜け防止モード: Papasimeon, Nir Lipovetzky, Lyndon Benke, Tim Miller, Adrian R Pearce Enrico ScalaとMohammad Zamani。
Integrated hybrid planning and programmed control for real time uav maneuvering. リアルタイムUav操作のための統合型ハイブリッド計画とプログラム制御 0.81
In Proc. AAMAS, 2018. Proc。 AAMAS、2018年。 0.68
[Schulman et al , 2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. schulman et al , 2017] john schulman, filip wolski, prafulla dhariwal, alec radford, oleg klimov。
訳抜け防止モード: He Schulman et al, 2017 ] John Schulman, Filip Wolski, Prafulla Dhariwal、Alec Radford、Oleg Klimov。
Proximal policy optimization algorithms. 近似ポリシー最適化アルゴリズム。 0.83
arXiv, 2017. 2017年、arXiv。 0.56
[Shleyfman et al , 2016] Alexander Shleyfman, Alexander Tuisov, and Carmel Domshlak. (Shleyfman et al , 2016)Alexander Shleyfman、Alexander Tuisov、Carmel Domshlak。 0.66
Blind search for atari-like online planning revisited. atariライクなオンライン計画のブラインド検索が再訪した。 0.48
In IJCAI, 2016. 2016年、IJCAI。 0.56
[Singh et al , 2021] Anubhav Singh, Nir Lipovetzky, Miquel Ramirez, and Javier Segovia-Aguas. [Singh et al , 2021]Aubhav Singh, Nir Lipovetzky, Miquel Ramirez, そしてJavier Segovia-Aguas。 0.84
Approximate novelty search. In Proc. ほぼ新奇な探索です Proc。 0.56
ICAPS, 2021. ICAPS、2021年。 0.72
[Sutton and Barto, 1998] R. Sutton and A. Barto. [Sutton and Barto, 1998]R. SuttonとA. Barto。 0.94
Introduc- tion to Reinforcement Learning. Introduc- 強化学習への参加。 0.74
MIT Press, 1998. 1998年、MIT出版。 0.63
[Teichteil-K¨onigsbuch et al , 2020] F. Teichteil-K¨onigsbuch, M. Ramirez, and N. Lipovetzky. [teichteil-k sonigsbuch et al , 2020] f. teichteil-k sonigsbuch, m. ramirez, n. lipovetzky。 0.63
Boundary extension features for width-based planning with simulators on continuous-state domains. 連続状態領域におけるシミュレータを用いた幅計画のための境界拡張機能 0.63
In Proc. IJCAI, 2020. Proc。 IJCAI、2020年。 0.70

翻訳にはFugu-Machine Translatorを利用しています。