論文の概要: Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Movable Obstacles
- arxiv url: http://arxiv.org/abs/2509.01022v1
- Date: Sun, 31 Aug 2025 23:27:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 15:17:03.505391
- Title: Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Movable Obstacles
- Title（参考訳）: 移動可能な障害物を持つ超高密度環境におけるシンボルプランニングとマルチエージェントパス
- Authors: Bo Fu, Zhe Chen, Rahul Chandan, Alex Barbosa, Michael Caldara, Joey Durham, Federico Pecora,
- Abstract要約: ブロック再配置問題(BRaP)は、ターゲット状態を達成するために、高密度グリッド内のストレージブロックを並べ替えることである。
共同構成空間探索,古典計画,マルチエージェントパスフィンディング,エキスパート再構成の5つの解法を提案する。
- 参考スコア（独自算出の注目度）: 4.632969733634998
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the Block Rearrangement Problem (BRaP), a challenging component of large warehouse management which involves rearranging storage blocks within dense grids to achieve a target state. We formally define the BRaP as a graph search problem. Building on intuitions from sliding puzzle problems, we propose five search-based solution algorithms, leveraging joint configuration space search, classical planning, multi-agent pathfinding, and expert heuristics. We evaluate the five approaches empirically for plan quality and scalability. Despite the exponential relation between search space size and block number, our methods demonstrate efficiency in creating rearrangement plans for deeply buried blocks in up to 80x80 grids.
- Abstract（参考訳）: 本稿では,大規模倉庫管理の課題であるBlock Rearrangement Problem (BRaP)を紹介する。
我々はBRaPをグラフ探索問題として公式に定義する。
スライディングパズル問題からの直感に基づいて,共同構成空間探索,古典計画,マルチエージェントパスフィンディング,エキスパートヒューリスティックスを活用する5つの探索型解法を提案する。
計画品質とスケーラビリティを実証的に評価する。
探索空間の大きさとブロック数との間に指数関数的関係があるにもかかわらず, 最大80×80の格子に埋没したブロックに対して, 再配置計画を作成する際の効率性を示す。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳（メタデータ） (2025-02-14T15:21:27Z) - What Matters in Hierarchical Search for Combinatorial Reasoning Problems? [0.5007502976837217]
近年の取り組みでは,階層的な高次探索戦略を取り入れたサブゴアル手法による計画の強化が試みられている。
有望ではあるが、従来の低レベルのプランナに対する彼らのパフォーマンスは一貫性がなく、アプリケーションコンテキストに関する疑問を提起している。
難解な値関数、複雑なアクション空間、環境におけるデッドエンドの存在、あるいは多様な専門家から収集されたデータなど、ハイレベル検索の利点を活用する上で重要な属性を同定する。
論文 参考訳（メタデータ） (2024-06-05T15:14:58Z) - PathFinder: Guided Search over Multi-Step Reasoning Paths [80.56102301441899]
木探索に基づく推論経路生成手法であるPathFinderを提案する。
動的デコードの統合により、多様な分岐とマルチホップ推論を強化する。
我々のモデルは、大きな分岐因子を持つビームサーチに類似した複雑さを反映して、よく、長く、目に見えない推論連鎖を一般化する。
論文 参考訳（メタデータ） (2023-12-08T17:05:47Z) - Decision Diagram-Based Branch-and-Bound with Caching for Dominance and
Suboptimality Detection [9.175779296469194]
本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。
鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。
このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
論文 参考訳（メタデータ） (2022-11-22T10:18:33Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。
頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。
特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文 参考訳（メタデータ） (2022-01-18T11:16:40Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。
我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。
提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文 参考訳（メタデータ） (2021-12-05T06:42:48Z) - Maximizing Store Revenues using Tabu Search for Floor Space Optimization [0.0]
我々は、この問題を、さらに大域的な制約を伴って連結多重選択knapsack問題として定式化する。
タブ検索に基づくメタヒューリスティックを提案する。
論文 参考訳（メタデータ） (2020-11-04T22:42:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。