Fugu-MT 論文翻訳(概要): On the Completeness of Conflict-Based Search: Temporally-Relative Duplicate Pruning

論文の概要: On the Completeness of Conflict-Based Search: Temporally-Relative Duplicate Pruning

arxiv url: http://arxiv.org/abs/2408.09028v1
Date: Fri, 16 Aug 2024 21:49:39 GMT
ステータス: 処理完了
システム内更新日: 2024-08-20 23:06:45.871599
Title: On the Completeness of Conflict-Based Search: Temporally-Relative Duplicate Pruning
Title（参考訳）: コンフリクトに基づく探索の完全性について:時間的関係の重複処理
Authors: Thayne T Walker, Nathan R Sturtevant,
Abstract要約: TRDPはCBSの長期的理論的不完全性の抜け穴を塞ぐ単純な方法である。 TRDPでは性能が著しく向上することが示されている。
参考スコア（独自算出の注目度）: 14.291485078702543
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Conflict-Based Search (CBS) algorithm for the multi-agent pathfinding (MAPF) problem is that it is incomplete for problems which have no solution; if no mitigating procedure is run in parallel, CBS will run forever when given an unsolvable problem instance. In this work, we introduce Temporally-Relative Duplicate Pruning (TRDP), a technique for duplicate detection and removal in both classic and continuous-time MAPF domains. TRDP is a simple procedure which closes the long-standing theoretic loophole of incompleteness for CBS by detecting and avoiding the expansion of duplicate states. TRDP is shown both theoretically and empirically to ensure termination without a significant impact on runtime in the majority of problem instances. In certain cases, TRDP is shown to increase performance significantly
Abstract（参考訳）: マルチエージェントパスフィンディング(MAPF)問題に対する競合ベースサーチ(CBS)アルゴリズムは、解を持たない問題に対して不完全である。本研究では,古典的かつ連続的なMAPFドメインの重複検出・削除技術であるTRDP(Temporally-Relative Duplicate Pruning)を紹介する。 TRDPは、CBSの長期的理論上の不完全性の抜け穴を、重複状態の検出と回避によって閉じる単純な手順である。 TRDPは理論的にも経験的にも、ほとんどの問題インスタンスのランタイムに大きな影響を与えることなく、終了を確実にするために示されています。ある場合、TRDPは性能を著しく向上させる。

関連論文リスト

Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
この研究は、正則決定過程(RDP)と呼ばれる非マルコフ環境のクラスにおけるオフライン強化学習(RL)を研究する。インスは、未来の観測と過去の相互作用からの報酬の未知の依存を実験的に捉えることができる。多くのアルゴリズムは、まずこの未知の依存関係を自動学習技術を用いて再構築する。
論文参考訳（メタデータ） (2024-09-04T14:26:58Z)
PSDiff: Diffusion Model for Person Search with Iterative and Collaborative Refinement [59.6260680005195]
本稿では,拡散モデルであるPSDiffに基づく新しいPerson Searchフレームワークを提案する。 PSDiffは、ノイズの多いボックスとReID埋め込みから地上の真実へのデュアルデノケーションプロセスとして検索する人を定式化する。新しいパラダイムに従って、我々は、反復的かつ協調的な方法で検出とReIDサブタスクを最適化する新しいコラボレーティブ・デノナイジング・レイヤ(CDL)を設計する。
論文参考訳（メタデータ） (2023-09-20T08:16:39Z)
The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model [61.87673435273466]
本稿では,強化学習(RL)におけるモデルロバスト性を検討した。我々は,デプロイ環境が,名目MDPに規定された不確実性に陥る場合に,最悪の場合のパフォーマンスを最適化する政策を学習することを目的とした,分布的に堅牢なマルコフ決定プロセス(RMDP)の枠組みを採用する。
論文参考訳（メタデータ） (2023-05-26T02:32:03Z)
Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。 MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
論文参考訳（メタデータ） (2023-03-30T14:42:41Z)
B$^3$RTDP: A Belief Branch and Bound Real-Time Dynamic Programming Approach to Solving POMDPs [17.956744635160568]
我々は,Belief Branch and Bound RTDP (B$3$RTDP) と呼ぶRTDP-Belアルゴリズムの拡張を提案する。我々のアルゴリズムは有界値関数表現を使い、これを2つの新しい方法で活用する。 B$3$RTDPは、既知のPOMDP問題に対する最先端のSARSOP解法よりも少ない時間で大きなリターンが得られることを実証的に実証した。
論文参考訳（メタデータ） (2022-10-22T21:42:59Z)
STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations [27.353023427198806]
我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。 POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
論文参考訳（メタデータ） (2021-05-28T18:07:16Z)
Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
論文参考訳（メタデータ） (2021-04-18T07:46:28Z)
Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
論文参考訳（メタデータ） (2021-02-23T18:56:13Z)
Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。 LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
論文参考訳（メタデータ） (2020-11-27T16:42:12Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)

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