論文の概要: Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning
- arxiv url: http://arxiv.org/abs/2105.01225v1
- Date: Tue, 4 May 2021 00:30:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-05 12:48:59.622564
- Title: Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning
- Title（参考訳）: 多エージェント最小容量計画のための多項式時間アルゴリズム
- Authors: Murat Cubuktepe, Franti\v{s}ek Blahoudek, and Ufuk Topcu
- Abstract要約: 共有タスクを達成するために協力する自律エージェントのリソース容量を最小化する問題を研究する。
消費マルコフ決定過程において、エージェントは限られた容量の資源を有する。
我々は,このグラフ問題をエージェント数,ターゲット位置,消費マルコフ決定過程の大きさで時間的に解くアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 19.614913673879474
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of minimizing the resource capacity of autonomous agents
cooperating to achieve a shared task. More specifically, we consider high-level
planning for a team of homogeneous agents that operate under resource
constraints in stochastic environments and share a common goal: given a set of
target locations, ensure that each location will be visited infinitely often by
some agent almost surely. We formalize the dynamics of agents by consumption
Markov decision processes. In a consumption Markov decision process, the agent
has a resource of limited capacity. Each action of the agent may consume some
amount of the resource. To avoid exhaustion, the agent can replenish its
resource to full capacity in designated reload states. The resource capacity
restricts the capabilities of the agent. The objective is to assign target
locations to agents, and each agent is only responsible for visiting the
assigned subset of target locations repeatedly. Moreover, the assignment must
ensure that the agents can carry out their tasks with minimal resource
capacity. We reduce the problem of finding target assignments for a team of
agents with the lowest possible capacity to an equivalent graph-theoretical
problem. We develop an algorithm that solves this graph problem in time that is
\emph{polynomial} in the number of agents, target locations, and size of the
consumption Markov decision process. We demonstrate the applicability and
scalability of the algorithm in a scenario where hundreds of unmanned
underwater vehicles monitor hundreds of locations in environments with
stochastic ocean currents.
- Abstract（参考訳）: 共有タスクを実現するために協力する自律エージェントの資源容量を最小化する問題について検討する。
より具体的には、確率的な環境でリソース制約の下で動作し、共通の目標を共有する、均質なエージェントのチームのためのハイレベルな計画を考える。
エージェントの動力学を消費マルコフ決定プロセスによって定式化する。
消費マルコフ決定過程において、エージェントは限られた容量の資源を有する。
エージェントの各アクションは、リソースの一部を消費することができる。
疲労を避けるため、エージェントは指定されたリロード状態においてリソースをフル容量に補充することができる。
リソース容量はエージェントの能力を制限する。
目的は、ターゲットロケーションをエージェントに割り当てることであり、各エージェントは、割り当てられたターゲットロケーションのサブセットを何度も訪問する責任のみを負う。
さらに、割り当ては、エージェントが最小限のリソース容量でタスクを実行できるようにする必要があります。
我々は、最小の能力を持つエージェントのチームの目標割り当てを見つける問題を、同等のグラフ理論的問題に還元する。
我々は,このグラフ問題をエージェント数,目標位置,消費マルコフ決定過程のサイズにおいて,emph{polynomial} である時間内に解くアルゴリズムを開発した。
無人水中車両数百台が確率的海流のある環境中数百箇所をモニタリングするシナリオにおいて、アルゴリズムの適用性とスケーラビリティを実証する。
関連論文リスト
- AI planning in the imagination: High-level planning on learned abstract
search spaces [68.75684174531962]
我々は,エージェントが訓練中に学習する抽象的な検索空間において,エージェントが計画することを可能にする,PiZeroと呼ばれる新しい手法を提案する。
本研究では,旅行セールスマン問題,ソコバン問題,2048年,施設立地問題,パックマン問題など,複数の分野で評価を行った。
論文 参考訳（メタデータ） (2023-08-16T22:47:16Z) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。
また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。
提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
論文 参考訳（メタデータ） (2022-10-07T00:40:59Z) - DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in
Complex Environments [55.204450019073036]
本稿では,倉庫環境における移動ロボットのためのタスク割り当てと分散ナビゲーションアルゴリズムを提案する。
本稿では,共同分散タスク割り当てとナビゲーションの問題について考察し,それを解決するための2段階のアプローチを提案する。
ロボットの衝突のない軌道の計算では,タスク完了時間において最大14%の改善と最大40%の改善が観察される。
論文 参考訳（メタデータ） (2022-09-07T00:35:27Z) - Task Allocation with Load Management in Multi-Agent Teams [4.844411739015927]
負荷管理を考慮したタスク割り当て学習のための多エージェントチームのための意思決定フレームワークを提案する。
負荷管理がチームのパフォーマンスに与える影響を説明し、例のシナリオでエージェントの振る舞いを探る。
コラボレーションにおけるエージェントの重要性の尺度は、潜在的な過負荷の状況に直面しているときにチームのレジリエンスを推測するために開発されます。
論文 参考訳（メタデータ） (2022-07-17T20:17:09Z) - Resource-Aware Distributed Submodular Maximization: A Paradigm for
Multi-Robot Decision-Making [3.5788754401889022]
Resource-Aware Distributed Greedyは、各ロボットのオンボードリソースを独立して考慮した最初のアルゴリズムである。
RAGは、中央集権化のトレードオフを、グローバルな準最適性、分散化、ほぼ最小のオンボード計算、通信、メモリリソースのトレードオフとバランス付けます。
論文 参考訳（メタデータ） (2022-04-15T15:47:05Z) - On the Use and Misuse of Absorbing States in Multi-agent Reinforcement
Learning [55.95253619768565]
現在のMARLアルゴリズムは、実験を通してグループ内のエージェントの数が固定されていると仮定している。
多くの実践的な問題において、エージェントはチームメイトの前に終了する可能性がある。
本稿では,吸収状態を持つ完全連結層ではなく,注意を用いた既存の最先端MARLアルゴリズムのアーキテクチャを提案する。
論文 参考訳（メタデータ） (2021-11-10T23:45:08Z) - Efficient Strategy Synthesis for MDPs with Resource Constraints [16.774128823546416]
我々は,消費マルコフ決定過程と呼ばれる形式に対する戦略合成を考える。
提示されたアルゴリズムは、モデルの表現に関して時間的に機能する。
論文 参考訳（メタデータ） (2021-05-05T14:59:30Z) - Resource allocation in dynamic multiagent systems [0.0]
MG-RAOアルゴリズムは,マルチエージェントシステムにおける資源配分問題を解決するために開発された。
シミュレーション環境における固定リソース割り当てに対する23～28%の改善を示す。
また、揮発性システムでは、mg-raoアルゴリズムを用いて、子エージェントがすべてのエージェントのリソース割り当てをモデル化するように構成されているため、複数のエージェント群をモデル化するときのパフォーマンスは46.5%である。
論文 参考訳（メタデータ） (2021-02-16T17:56:23Z) - Asynchronous Multi Agent Active Search [6.587280549237275]
SPATS (Sparse Parallel Asynchronous Thompson Smpling) とLATSI (Laplace Thompson Smpling with Information gain) という2つの異なる能動探索アルゴリズムを提案する。
ターゲットは、圧縮的な検知仮定に従って、環境の周囲にわずかに配置されているとみなす。
提案アルゴリズムの有効性を実証するために,シミュレーション結果と理論的解析結果を提供する。
論文 参考訳（メタデータ） (2020-06-25T22:17:20Z) - Randomized Entity-wise Factorization for Multi-Agent Reinforcement
Learning [59.62721526353915]
実世界のマルチエージェント設定は、エージェントや非エージェントエンティティのタイプや量が異なるタスクを伴うことが多い。
我々の方法は、これらの共通点を活用することを目的としており、「観察対象のランダムに選択されたサブグループのみを考えるとき、各エージェントが期待する効用は何か?」という問いを投げかける。
論文 参考訳（メタデータ） (2020-06-07T18:28:41Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。