論文の概要: Multi-Agent Routing and Scheduling Through Coalition Formation
- arxiv url: http://arxiv.org/abs/2105.00451v1
- Date: Sun, 2 May 2021 11:53:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-05 02:47:17.448564
- Title: Multi-Agent Routing and Scheduling Through Coalition Formation
- Title（参考訳）: 連成形成によるマルチエージェントルーティングとスケジューリング
- Authors: Luca Capezzuto, Danesh Tarapore, Sarvapali D. Ramchurn
- Abstract要約: この問題をマルチエージェントルーティングと協調形成(marsc)によるスケジューリングと呼ぶ。
私たちは、Time Windowsで重要なチームオリエンテーション問題を一般化していることを示しています。
リアルタイムシステムで一般的に使用されるEarliest Deadline Firstアプローチよりも最大3.25倍優れたソリューションを見つけます。
- 参考スコア（独自算出の注目度）: 13.302347777866757
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In task allocation for real-time domains, such as disaster response, a
limited number of agents is deployed across a large area to carry out numerous
tasks, each with its prerequisites, profit, time window and workload. To
maximize profits while minimizing time penalties, agents need to cooperate by
forming, disbanding and reforming coalitions. In this paper, we name this
problem Multi-Agent Routing and Scheduling through Coalition formation (MARSC)
and show that it generalizes the important Team Orienteering Problem with Time
Windows. We propose a binary integer program and an anytime and scalable
heuristic to solve it. Using public London Fire Brigade records, we create a
dataset with 347588 tasks and a test framework that simulates the mobilization
of firefighters. In problems with up to 150 agents and 3000 tasks, our
heuristic finds solutions up to 3.25 times better than the Earliest Deadline
First approach commonly used in real-time systems. Our results constitute the
first large-scale benchmark for the MARSC problem.
- Abstract（参考訳）: 災害対応などのリアルタイムドメインのタスク割り当てでは、多数のタスクを実行するために限られた数のエージェントが広域に展開され、それぞれに前提条件、利益、タイムウインドウ、ワークロードがある。
時間的ペナルティを最小化しながら利益を最大化するためには、エージェントは連立の形成、解散、改革によって協力する必要がある。
本稿では,この問題をMARSC (Multi-Agent Routing and Scheduling through Coalition Formation) と命名し,タイムウインドウを用いたチームオリエンテーリング問題を一般化したことを示す。
我々は,バイナリ整数プログラムと,それを解決するためのいつでもスケーラブルなヒューリスティックを提案する。
ロンドン消防団の記録を使って,347588タスクのデータセットと,消防士の動員をシミュレートするテストフレームワークを作成しました。
最大150のエージェントと3000のタスクを持つ問題では、リアルタイムシステムで一般的に使用される最初期のdeadline firstアプローチよりも3.25倍のソリューションを見つけます。
この結果は,MARSC問題に対する最初の大規模ベンチマークとなる。
関連論文リスト
- Solving the Team Orienteering Problem with Transformers [46.93254771681026]
車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。
本稿では,チームオリエンテーリング問題を高速かつ高精度に解決できる多エージェント経路計画システムを提案する。
論文 参考訳（メタデータ） (2023-11-30T16:10:35Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure
of Costs [65.23158435596518]
チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。
我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
論文 参考訳（メタデータ） (2022-06-13T09:17:40Z) - Online Task Assignment Problems with Reusable Resources [44.87346665037376]
再利用可能な資源を用いたオンラインタスク割り当て問題について検討する。
本稿では,この設定に対して1/2$-competitiveのオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-15T02:48:13Z) - Reinforcement Learning for Assignment Problem with Time Constraints [0.0]
本稿では、労働者グループに複数のタスクをマッピングしたアサインメント問題のためのエンドツーエンドフレームワークを提案する。
我々は,課題に関連する総コストを最小化することにより,問題の最適解を見つけるための強化学習エージェントを訓練する。
また、同じフレームワークを用いて、ビンパッキングおよび静電容量化車両ルーティング問題に関する結果も示す。
論文 参考訳（メタデータ） (2021-06-05T10:10:52Z) - MALib: A Parallel Framework for Population-based Multi-agent
Reinforcement Learning [61.28547338576706]
人口ベースマルチエージェント強化学習(PB-MARL)は、強化学習(RL)アルゴリズムでネストした一連の手法を指す。
PB-MARLのためのスケーラブルで効率的な計算フレームワークMALibを提案する。
論文 参考訳（メタデータ） (2021-06-05T03:27:08Z) - Large-scale, Dynamic and Distributed Coalition Formation with Spatial
and Temporal Constraints [11.835884261097958]
空間的制約問題 (CFSTP) と時間的制約問題 (CFSTP) はマルチエージェントタスク割り当て問題である。
完了したタスクの数を最大化するために、エージェントは連立を結成し、解散し、改革することで協力する必要がある。
D-CTSは、最初の大規模、動的、分散CFSTPベンチマークを設定。
論文 参考訳（メタデータ） (2021-06-01T10:41:49Z) - A Multiperiod Workforce Scheduling and Routing Problem with Dependent
Tasks [0.0]
我々は新しいワークフォーススケジューリングとルーティング問題について研究する。
この問題では、顧客は企業からサービスを要求する。
サービスに属するタスクは異なるチームによって実行され、顧客は1日に1回以上訪問することができる。
論文 参考訳（メタデータ） (2020-08-06T19:31:55Z) - A Cordial Sync: Going Beyond Marginal Policies for Multi-Agent Embodied
Tasks [111.34055449929487]
エージェントが協力して家具をリビングルームに移動させるという,新しいタスクFurnMoveを紹介した。
既存のタスクとは異なり、FurnMoveはエージェントが各タイミングで調整する必要がある。
既存の分散化されたアクションサンプリング手順は、表現力のある共同アクションポリシーを許さない。
SynC-policiesとCORDIALを用いて、我々のエージェントはFurnMoveで58%の完成率を達成する。
論文 参考訳（メタデータ） (2020-07-09T17:59:57Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。