論文の概要: Pushing the Envelope: From Discrete to Continuous Movements in
Multi-Agent Path Finding via Lazy Encodings
- arxiv url: http://arxiv.org/abs/2004.13477v1
- Date: Sat, 25 Apr 2020 13:21:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 21:51:52.528327
- Title: Pushing the Envelope: From Discrete to Continuous Movements in
Multi-Agent Path Finding via Lazy Encodings
- Title（参考訳）: エンベロープのプッシュ:遅延エンコーディングによるマルチエージェントパス探索における離散的から連続的な移動
- Authors: Pavel Surynek
- Abstract要約: Em satisfiability modulo theory (SMT) に基づいて,SMT-CBS$mathcalR$ と呼ばれる最適解を得るための新しい解法を提案する。
このアルゴリズムは、競合ベースのサーチ(CBS)から知られている衝突解決と、潜在的に可算でない検索空間における決定変数を選択する新しいスキームの上に、以前の不完全なSATエンコーディングを組み合わせている。
- 参考スコア（独自算出の注目度）: 15.99072005190786
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-agent path finding in continuous space and time with geometric agents
MAPF$^\mathcal{R}$ is addressed in this paper. The task is to navigate agents
that move smoothly between predefined positions to their individual goals so
that they do not collide. We introduce a novel solving approach for obtaining
makespan optimal solutions called SMT-CBS$^\mathcal{R}$ based on {\em
satisfiability modulo theories} (SMT). The new algorithm combines collision
resolution known from conflict-based search (CBS) with previous generation of
incomplete SAT encodings on top of a novel scheme for selecting decision
variables in a potentially uncountable search space. We experimentally compare
SMT-CBS$^\mathcal{R}$ and previous CCBS algorithm for MAPF$^\mathcal{R}$.
- Abstract（参考訳）: 本稿では,連続空間と時間におけるMAPF$^\mathcal{R}$によるマルチエージェントパス探索について述べる。
タスクは、事前に定義された位置から個々の目標へスムーズに移動するエージェントをナビゲートし、衝突しないようにすることだ。
本稿では, SMT-CBS$^\mathcal{R}$ という, SMT-CBS$^\mathcal{R}$ と呼ばれる最適解を得るための新しい解法を提案する。
このアルゴリズムは、競合ベースのサーチ(CBS)から知られている衝突解決と、潜在的に可算でない検索空間における決定変数を選択する新しいスキームの上に、以前の不完全なSATエンコーディングを組み合わせている。
MAPF$^\mathcal{R}$に対するSMT-CBS$^\mathcal{R}$と以前のCCBSアルゴリズムを実験的に比較した。
関連論文リスト
- Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。
我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。
古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
論文 参考訳（メタデータ） (2024-04-25T07:41:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。
本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。
MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文 参考訳（メタデータ） (2023-12-26T06:57:22Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。
LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。
実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
論文 参考訳（メタデータ） (2022-11-24T06:27:18Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。
提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
論文 参考訳（メタデータ） (2022-03-07T03:30:35Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal
Vertex Ordering [15.99072005190786]
本稿では,MAPF問題を一般化したマルチゴールマルチエージェントパス探索法(MAPF$MG$)を提案する。
我々は,MAPF$MG$に対処するために,異なるパラダイムを用いた2つの新しいアルゴリズムを提案する。Hamiltonian-CBS (HCBS) と呼ばれる検索ベース検索アルゴリズムと,SMTパラダイムを用いたコンパイルベースアルゴリズムであるSMT-Hamiltonian-CBS (SMT-HCBS) を提案する。
論文 参考訳（メタデータ） (2020-09-10T22:27:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。