論文の概要: Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes

• arxiv url: http://arxiv.org/abs/2103.04496v1
• Date: Mon, 8 Mar 2021 00:57:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-09 15:24:24.639090
• Title: Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes
• Title（参考訳）: 遅延コンパイル方式における高速最適マルチロボットパス計画のためのスパーシフィケーション
• Authors: Pavel Surynek
• Abstract要約: 複数のロボット(MRPP)の経路計画は、ロボットが最初の位置から指定された目標位置までナビゲートできる非衝突経路を見つけるタスクを表します。 本稿では,既存の SAT ベースの MRPP アルゴリズムを,対象の Boolean 符号化を導出する各ロボットの候補経路の集合を分割することで拡張する。
• 参考スコア（独自算出の注目度）: 7.766921168069532
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots through which they can navigate from their initial positions to specified goal positions. The problem is usually modeled using undirected graphs where robots move between vertices across edges. Contemporary optimal solving algorithms include dedicated search-based methods, that solve the problem directly, and compilation-based algorithms that reduce MRPP to a different formalism for which an efficient solver exists, such as constraint programming (CP), mixed integer programming (MIP), or Boolean satisfiability (SAT). In this paper, we enhance existing SAT-based algorithm for MRPP via spartification of the set of candidate paths for each robot from which target Boolean encoding is derived. Suggested sparsification of the set of paths led to smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach have been kept.
• Abstract（参考訳）: 複数のロボット(MRPP)の経路計画は、ロボットが最初の位置から指定された目標位置までナビゲートできる非衝突経路を見つけるタスクを表します。 問題は通常、ロボットがエッジを横切って頂点間を移動する非方向グラフを使用してモデル化される。 現代の最適解アルゴリズムには、この問題を直接解決する専用の検索ベース手法や、制約プログラミング(CP)、混合整数プログラミング(MIP)、ブール適合性(SAT)などの効率的な解法が存在する別の形式にMRPPを還元するコンパイルベースアルゴリズムが含まれる。 本稿では,既存の SAT ベースの MRPP アルゴリズムを,対象の Boolean 符号化を導出する各ロボットの候補経路の集合を分割することで拡張する。 経路の集合のスパーシフィケーションにより、より小さな目標ブール公式が構築され、より早く解くことができ、そのアプローチの最適性保証が保たれた。

関連論文リスト

• Research on reinforcement learning based warehouse robot navigation algorithm in complex warehouse layout [13.945240113332352]
  本稿では, PPO と Dijkstra のアルゴリズム, Proximal Policy-Dijkstra (PP-D) の新たな手法を提案する。 PP-D法はPPOによる効率的な戦略学習とリアルタイム意思決定を実現し,Dijkstraアルゴリズムを用いてグローバル最適経路を計画する。
  論文  参考訳（メタデータ） (2024-11-09T09:44:03Z)
• A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems [6.853165736531941]
  マルチロボットアプリケーションは、衝突のない経路を確保しながら、各ロボットにユニークな目標を割り当てることを目的としている。 そこで本研究では,次の最適な割り当てを計算するための効率的な競合誘導手法を提案する。 複数のベンチマークワークスペース上で,最大100個のロボットに対して,我々のアルゴリズムを広範囲に評価した。
  論文  参考訳（メタデータ） (2024-02-19T19:04:19Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Intelligent Trajectory Design for RIS-NOMA aided Multi-robot Communications [59.34642007625687]
  目的は,ロボットの軌道とNOMA復号命令を協調的に最適化することで,マルチロボットシステムにおける全軌道の総和率を最大化することである。 ARIMAモデルとDouble Deep Q-network (D$3$QN)アルゴリズムを組み合わせたML方式を提案する。
  論文  参考訳（メタデータ） (2022-05-03T17:14:47Z)
• A distributed, plug-n-play algorithm for multi-robot applications with a priori non-computable objective functions [2.2452191187045383]
  マルチロボットアプリケーションでは、ミッションのユーザ定義の目的を一般的な最適化問題として当てはめることができる。 これらの問題には標準勾配の差分型アルゴリズムは適用できない。 本稿では,各ロボットのサブコスト関数を慎重に設計するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-14T20:40:00Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。 この問題をある程度緩和する手法を提案する。
  論文  参考訳（メタデータ） (2021-08-11T10:42:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• New Fusion Algorithm provides an alternative approach to Robotic Path planning [0.0]
  本稿では,カスタム2次元環境における経路計画問題の解法として,新しい,効率的な融合アルゴリズムを提案する。 新しい融合アルゴリズムは、スムーズな性能で実現可能であり、従来の経路計画のA*戦略に代わる、時間効率で安価な代替手段として満足できる。
  論文  参考訳（メタデータ） (2020-06-06T17:52:00Z)

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

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