Fugu-MT 論文翻訳(概要): On Solving the Rubik's Cube with Domain-Independent Planners Using Standard Representations

論文の概要: On Solving the Rubik's Cube with Domain-Independent Planners Using Standard Representations

arxiv url: http://arxiv.org/abs/2307.13552v2
Date: Mon, 21 Aug 2023 12:35:36 GMT
ステータス: 処理完了
システム内更新日: 2023-08-22 22:45:41.704483
Title: On Solving the Rubik's Cube with Domain-Independent Planners Using Standard Representations
Title（参考訳）: 標準表現を用いた領域独立プランナーによるルービックキューブの解法について
Authors: Bharath Muppasani, Vishal Pallagani, Biplav Srivastava, Forest Agostinelli
Abstract要約: 本稿では,人気のあるPDDL言語における最初のルービックキューブ表現について述べる。 1つの比較実験で、DeepCubeAは様々な複雑さを持つ全ての問題を解き、78.5%しか最適計画ではないことがわかった。我々の研究は、表現的選択と計画最適性の間のトレードオフに関する貴重な洞察を提供する。
参考スコア（独自算出の注目度）: 7.470087627607195
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Rubik's Cube (RC) is a well-known and computationally challenging puzzle that has motivated AI researchers to explore efficient alternative representations and problem-solving methods. The ideal situation for planning here is that a problem be solved optimally and efficiently represented in a standard notation using a general-purpose solver and heuristics. The fastest solver today for RC is DeepCubeA with a custom representation, and another approach is with Scorpion planner with State-Action-Space+ (SAS+) representation. In this paper, we present the first RC representation in the popular PDDL language so that the domain becomes more accessible to PDDL planners, competitions, and knowledge engineering tools, and is more human-readable. We then bridge across existing approaches and compare performance. We find that in one comparable experiment, DeepCubeA (trained with 12 RC actions) solves all problems with varying complexities, albeit only 78.5% are optimal plans. For the same problem set, Scorpion with SAS+ representation and pattern database heuristics solves 61.50% problems optimally, while FastDownward with PDDL representation and FF heuristic solves 56.50% problems, out of which 79.64% of the plans generated were optimal. Our study provides valuable insights into the trade-offs between representational choice and plan optimality that can help researchers design future strategies for challenging domains combining general-purpose solving methods (planning, reinforcement learning), heuristics, and representations (standard or custom).
Abstract（参考訳）: ルービックキューブ(英: Rubik's Cube、RC)は、AI研究者が効率的な代替表現や問題解決方法を探求する動機となった、よく知られた、計算的に難しいパズルである。ここでの計画の理想的な状況は、問題を汎用的な解法とヒューリスティックスを用いて標準表記で最適かつ効率的に表現することである。 rcで現在最も高速に解決できるのは、カスタム表現のdeepcubeaであり、もう1つのアプローチは状態-action-space+ (sas+)表現のscorpion plannerである。本稿では,PDDL言語における最初のRC表現を提示し,PDDLプランナやコンペティション,知識工学ツールにドメインがよりアクセスしやすくし,より可読性が高いことを示す。その後、既存のアプローチをブリッジしてパフォーマンスを比較します。 1つの比較実験では、DeepCubeA (12 RC アクションで訓練) は様々な複雑さを持つ全ての問題を解くが、78.5%しか最適計画ではない。 SAS+表現とパターンデータベースヒューリスティックスを備えたScorpionは61.50%の問題を最適に解き、PDDL表現とFFヒューリスティックを備えたFastDownwardは56.50%の問題を解き、うち79.64%が最適である。本研究は,汎用解法(計画,強化学習),ヒューリスティックス,表現(標準あるいは習慣)を組み合わせた課題領域における今後の戦略設計を支援する,表現選択と計画最適性のトレードオフに関する貴重な知見を提供する。

関連論文リスト

Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文参考訳（メタデータ） (2024-11-04T15:17:19Z)
Automatic Algorithm Selection for Pseudo-Boolean Optimization with Given Computational Time Limits [0.9831489366502301]
機械学習(ML)技術は、解決者のポートフォリオから最適な解法を自動選択するために提案されている。これらのメソッドはメタソルバと呼ばれ、問題のインスタンスと解決者のポートフォリオを入力として取ります。「Anytime」メタソルバは、指定された時間制限内で最高の性能の解決器を予測する。
論文参考訳（メタデータ） (2023-09-07T03:04:50Z)
MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文参考訳（メタデータ） (2023-04-28T07:09:23Z)
Learning To Dive In Branch And Bound [95.13209326119153]
グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
論文参考訳（メタデータ） (2023-01-24T12:01:45Z)
Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文参考訳（メタデータ） (2022-10-31T09:46:26Z)
The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
ML4COは、キーコンポーネントを置き換えることで最先端の最適化問題を解決することを目的としている。このコンペティションでは、最高の実現可能なソリューションを見つけること、最も厳密な最適性証明書を生成すること、適切なルーティング設定を提供すること、という3つの課題があった。
論文参考訳（メタデータ） (2022-03-04T17:06:00Z)
Leveraging Experience in Lazy Search [37.75223642505171]
遅延グラフ探索アルゴリズムは、エッジ評価が計算ボトルネックとなる動き計画問題の解法において効率的である。我々は,この問題を探索問題の状態に関するマルコフ決定過程 (MDP) として定式化する。我々は,訓練中にMDPを解くことができる分子セレクタを計算可能であることを示す。
論文参考訳（メタデータ） (2021-10-10T00:46:44Z)
Self-Supervision is All You Need for Solving Rubik's Cube [0.0]
この研究は、ルービックキューブで表される、あらかじめ定義されたゴールで問題を解決するためのシンプルで効率的なディープラーニング手法を導入する。このような問題に対して、目標状態から分岐するランダムスクランブル上でディープニューラルネットワークをトレーニングすることは、ほぼ最適解を達成するのに十分であることを示す。
論文参考訳（メタデータ） (2021-06-06T15:38:50Z)
Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
論文参考訳（メタデータ） (2021-03-18T14:49:52Z)
Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文参考訳（メタデータ） (2020-11-19T10:00:54Z)
Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization [5.669790037378094]
目標は、有限個の可能性の集合の中で最適解を見つけることである。深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。制約プログラミング(CP)は最適化問題を解決する汎用ツールである。本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
論文参考訳（メタデータ） (2020-06-02T13:54:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。