論文の概要: 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完全であることが確認され,ランダム化開始とゴール構成を仮定して最小値と高い確率定数因子を近似する多項式時間アルゴリズムが開発された。
関連論文リスト
- 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) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳(メタデータ) (2022-06-17T12:58:58Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳(メタデータ) (2020-06-15T21:55:34Z) - Low Complexity Sequential Search with Size-Dependent Measurement Noise [19.201555109949677]
本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。
アレイ処理における初期ビームアライメント、ネットワークにおける重ヒッタ検出、ロボット工学におけるビジュアルサーチといった実用的応用により、我々は事実上重要な複雑さの制約/指標を考察する。
新規検索戦略として$dyaPM$と$hiePM$が提案されている。
論文 参考訳(メタデータ) (2020-05-15T22:40:18Z) - Modeling and solving the multimodal car- and ride-sharing problem [0.0]
マルチモーダルカー・ライドシェアリング問題(MMCRP)を紹介する。
車両のプールは一連の乗車要求をカバーするために使用され、発見されていない要求は他の交通手段に割り当てられる。
カラム生成に基づく2層分解アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-01-15T09:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。