論文の概要: A General Framework for Dynamic MAPF using Multi-Shot ASP and Tunnels
- arxiv url: http://arxiv.org/abs/2507.20703v1
- Date: Mon, 28 Jul 2025 10:55:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-29 16:23:58.083361
- Title: A General Framework for Dynamic MAPF using Multi-Shot ASP and Tunnels
- Title（参考訳）: マルチショットASPとトンネルを用いた動的MAPFのための汎用フレームワーク
- Authors: Aysu Bogatarkan, Esra Erdem,
- Abstract要約: MAPF問題は、エージェントが互いに衝突したり障害物を発生させたりしないように、所定の時間内に複数のエージェントの計画を見つけることを目的としている。
本研究では,動的MAPF(D-MAPF)問題について検討し,環境に侵入・退避するエージェントや除去・移動する障害物などの変更を可能にする。
1)D-MAPFの一般的な定義,2)D-MAPFを解くための新しいフレームワーク,3)D-MAPFを解くためのASPベースの新しい手法を紹介する。
- 参考スコア（独自算出の注目度）: 1.1816942730023883
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: MAPF problem aims to find plans for multiple agents in an environment within a given time, such that the agents do not collide with each other or obstacles. Motivated by the execution and monitoring of these plans, we study Dynamic MAPF (D-MAPF) problem, which allows changes such as agents entering/leaving the environment or obstacles being removed/moved. Considering the requirements of real-world applications in warehouses with the presence of humans, we introduce 1) a general definition for D-MAPF (applicable to variations of D-MAPF), 2) a new framework to solve D-MAPF (utilizing multi-shot computation, and allowing different methods to solve D-MAPF), and 3) a new ASP-based method to solve D-MAPF (combining advantages of replanning and repairing methods, with a novel concept of tunnels to specify where agents can move). We have illustrated the strengths and weaknesses of this method by experimental evaluations, from the perspectives of computational performance and quality of solutions.
- Abstract（参考訳）: MAPF問題は、エージェントが互いに衝突したり障害物を発生させたりしないように、所定の時間内に複数のエージェントの計画を見つけることを目的としている。
これらの計画の実行と監視に動機付けられ,動的MAPF (D-MAPF) 問題について検討した。
人間の存在下での倉庫における現実的応用の要件を踏まえて, 紹介する。
1)D-MAPFの一般的な定義(D-MAPFのバリエーションに適用可能)
2)D-MAPF(マルチショット計算を利用し、異なる方法でD-MAPFを解ける)を解決するための新しいフレームワーク。
3)D-MAPFを解く新しいASPベースの手法(エージェントの移動場所を特定するトンネルの概念を取り入れた再計画法と修復法の利点)。
本手法の長所と短所を,計算性能と解の質の観点から実験的評価により明らかにした。
関連論文リスト
- Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments [9.000023855628958]
ライフロングMAPF(英: Lifelong MAPF、LMAPF)は、エージェントが現在のターゲットに到達すると新たなターゲットを受信するMAPFのオンライン版である。
そこで本研究では,LMAPF問題に対して,各エージェントが最終的にターゲットを訪問することを目的とした修正MAPF問題の系列を解くことで,LMAPF問題を解くことを提案する。
本稿では、このMAPF変種をTransient MAPF (TMAPF) と呼び、既存のMAPFアルゴリズムに基づいたいくつかのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-05T15:37:29Z) - MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation [80.47072100963017]
Amortized Pareto Front (MAP) を用いた新しい低演算アルゴリズム Model Merging を導入する。
MAPは、複数のモデルをマージするためのスケーリング係数のセットを効率的に識別し、関連するトレードオフを反映する。
また,タスク数が比較的少ないシナリオではベイジアンMAP,タスク数の多い状況ではNested MAPを導入し,計算コストを削減した。
論文 参考訳（メタデータ） (2024-06-11T17:55:25Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement
in Large-Scale Warehouses [6.852682268049646]
自動倉庫におけるマルチロボット棚配置問題をモデル化した新しい問題定式化Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD)を導入する。
本稿では,DD-MAPD インスタンスを MAPF インスタンスに分解し,棚の軌道をコーディネートするMAPF-DECOMP と,エージェントの経路を計算するためのMAPD インスタンスを提案する。
実験の結果,MAPF-DECOMPの効率と有効性を示し,1000台以上の棚と数百台のエージェントをほんの数分で大規模インスタンスの高品質なソリューションを計算できることを示した。
論文 参考訳（メタデータ） (2023-04-27T16:26:05Z) - POGEMA: Partially Observable Grid Environment for Multiple Agents [64.88759709443819]
POGEMAは、部分的に観測可能なマルチエージェントパスフィンディング(PO-MAPF)問題に挑戦するためのサンドボックスである。
様々なPO-MAPFに合わせることができ、プランニングと学習のための優れた試験場として機能する。
論文 参考訳（メタデータ） (2022-06-22T09:39:50Z) - Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via
Environment Manipulation [12.401344261399613]
マルチエージェントパスフィニング(Multi-agent pathfinding)は、障害が散らばった環境において、開始時から目標地点まで、エージェントのチームが衝突のない経路を計画することに関心がある。
我々はMAPFの新たな拡張を導入し、Terraforming MAPF (tMAPF) と呼び、いくつかのエージェントが障害を移動して他のエージェントへの道をクリアする役割を担っている。
我々は、tMAPFに取り組むために、CBSとPBSという2つの最先端アルゴリズムを拡張し、静的な障害物設定で可能な限り優れた解を常に上回ることを示す。
論文 参考訳（メタデータ） (2022-03-20T12:18:35Z) - Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities [7.766921168069532]
このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。
最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
論文 参考訳（メタデータ） (2021-04-23T20:13:12Z) - Explanation Generation for Multi-Modal Multi-Agent Path Finding with
Optimal Resource Utilization using Answer Set Programming [1.7132914341329848]
mMAPFの実際の応用には柔軟性と説明性が必要である。
本稿では,ソリューションの実現可能性と最適性に関する質問に対する説明を生成する手法を提案する。
論文 参考訳（メタデータ） (2020-08-08T18:34:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。