論文の概要: On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles

• arxiv url: http://arxiv.org/abs/2312.10887v1
• Date: Mon, 18 Dec 2023 02:24:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-19 14:12:40.804284
• Title: On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
• Title（参考訳）: 一般化スライディングタイルノズルの最適解法について
• Authors: Marcus Gozon and Jingjin Yu
• Abstract要約: 15ドル(約1万5000円)のゲームでは、ラベル付き四角いタイルが4時間4ドル(約4万4000円)のボードにリセットされ、それぞれの(時間)ステップで隣のタイルがスライドし、それまでタイルが占めていたスペースが新しいエスコートとして残る。 汎用スライディングタイルパズル(GSTP)について検討し,(1)エスコートが1ドル以上、(2)複数タイルが1ステップで同期動作可能であることを示した。 一般的な離散マルチエージェント/ロボットモーションモデルと比較して、GSTPは幅広い高ユーティリティアプリケーションに対してより正確なモデルを提供する。
• 参考スコア（独自算出の注目度）: 20.93478961897733
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the $15$-puzzle game, $15$ labeled square tiles are reconfigured on a $4\times 4$ board through an escort, wherein each (time) step, a single tile neighboring it may slide into it, leaving the space previously occupied by the tile as the new escort. We study a generalized sliding-tile puzzle (GSTP) in which (1) there are $1+$ escorts and (2) multiple tiles can move synchronously in a single time step. Compared with popular discrete multi-agent/robot motion models, GSTP provides a more accurate model for a broad array of high-utility applications, including warehouse automation and autonomous garage parking, but is less studied due to the more involved tile interactions. In this work, we analyze optimal GSTP solution structures, establishing that computing makespan-optimal solutions for GSTP is NP-complete and developing polynomial time algorithms yielding makespans approximating the minimum with expected/high probability constant factors, assuming randomized start and goal configurations.
• Abstract（参考訳）: 15ドルのゲームでは、15ドルのラベル付き正方形のタイルがエスコートを通じて4ドルの4ドルのボードに再構成され、各ステップ(時間)に隣接する1つのタイルがスライドして、以前タイルが占めていたスペースを新しいエスコートとして残す。 一般化されたスライディングタイルパズル(GSTP)について検討し,(1)1ドル以上のエスコートがあり,(2)複数タイルは1ステップで同期動作可能であることを示した。 一般的な離散型マルチエージェント/ロボットモーションモデルと比較すると、gstpは倉庫の自動化や自動駐車場など、幅広い高機能アプリケーションに対してより正確なモデルを提供するが、より関連するタイルの相互作用のため、あまり研究されていない。 本研究では,GSTPの最適解構造を解析し,GSTPの最適解がNP完全であることが確認され,ランダム化開始とゴール構成を仮定して最小値と高い確率定数因子を近似する多項式時間アルゴリズムが開発された。

関連論文リスト

• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  最適輸送理論はそのような写像を構築するための原則化された枠組みを提供する。 本稿では,Wasserstein-1に基づく新しい最適輸送解法を提案する。 実験により,提案した解法は,2次元データセット上に一意かつ単調な写像を求める際に,$W$ OTソルバを模倣できることを示した。
  論文  参考訳（メタデータ） (2024-11-01T14:23:19Z)
• Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds [17.720810091374776]
  GSTP (Generalized Sliding-Tile Puzzle) は、ボード上の多くの正方形タイルを平行に移動させ、隣接するタイルの運動に自然な幾何学的衝突制約を課す。 この研究は、CGSP (Colored Generalized Sliding-Tile Puzzle) と呼ばれるGSTPのさらなる一般化を検証し、タイルは様々な区別可能性を持つようになった。 本研究は、CGSPとその鍵となるサブプロブレムの計算複雑性を、可能条件の幅広いスペクトルの下で確立し、ほとんどの対数係数によって異なる解が下限と上限を特徴づけるものである。
  論文  参考訳（メタデータ） (2024-10-19T02:34:13Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level Optimization [11.638394339813154]
  本稿では,ソーシャルミニゲームにおけるリアルタイム非協調型マルチロボットナビゲーションのための,完全に分散化されたアプローチを提案する。 我々のコントリビューションは新しいリアルタイムバイレベル最適化アルゴリズムであり、トップレベルの最適化は公正で衝突のない順序付けを演算する。 F$1/10のロボット、Clearpath Jackal、Boston Dynamics Spotを使って提案したアルゴリズムを現実世界に展開することに成功しました。
  論文  参考訳（メタデータ） (2023-06-15T02:18:21Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。 提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。 本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
  論文  参考訳（メタデータ） (2023-04-28T07:09:23Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Non-reversible Parallel Tempering for Deep Posterior Approximation [26.431541203372113]
  並列テンパリング(英: Parallel tempering、PT)は、マルチモーダル分布のシミュレーションのためのゴートワークホースである。 一般的な決定論的偶律(DEO)スキームは、非可逆性を利用して通信コストを$O(P2)$から$O(P)$に下げることに成功した。 我々は、非可逆性を促進するためのDECスキームを一般化し、幾何学的停止時間に起因するバイアスに対処するためのいくつかの解決策を提案する。
  論文  参考訳（メタデータ） (2022-11-20T01:18:40Z)
• T*$\varepsilon$ -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems [7.277760003553328]
  本研究では,障害物の存在下での曲率制約系の衝突のない経路を見つけることの問題点を考察する。 有界-準最適解を求めることにより、使用した時間-最適遷移の数を劇的に削減できることを示す。
  論文  参考訳（メタデータ） (2022-04-04T17:38:36Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Modeling and solving the multimodal car- and ride-sharing problem [0.0]
  マルチモーダルカー・ライドシェアリング問題(MMCRP)を紹介する。 車両のプールは一連の乗車要求をカバーするために使用され、発見されていない要求は他の交通手段に割り当てられる。 カラム生成に基づく2層分解アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-15T09:43:55Z)

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

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