論文の概要: Approximate Multiagent Reinforcement Learning for On-Demand Urban
Mobility Problem on a Large Map (extended version)
- arxiv url: http://arxiv.org/abs/2311.01534v3
- Date: Fri, 8 Mar 2024 14:36:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-11 10:55:39.340111
- Title: Approximate Multiagent Reinforcement Learning for On-Demand Urban
Mobility Problem on a Large Map (extended version)
- Title（参考訳）: 大規模地図を用いたオンデマンド都市モビリティ問題に対する近似マルチエージェント強化学習(拡張版)
- Authors: Daniel Garces, Sushmita Bhattacharya, Dimitri Bertsekas, Stephanie Gil
- Abstract要約: 大規模都市環境における自律型マルチエージェントタクシー経路問題について検討する。
最近の理論では、安定なベースポリシーを持つロールアウトアルゴリズムは、ほぼ最適に近い安定ポリシーを生成することが示されている。
本稿では,計算コストを削減できる近似マルチエージェントロールアウト方式の2相アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 9.32626005183482
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we focus on the autonomous multiagent taxi routing problem for
a large urban environment where the location and number of future ride requests
are unknown a-priori, but can be estimated by an empirical distribution. Recent
theory has shown that a rollout algorithm with a stable base policy produces a
near-optimal stable policy. In the routing setting, a policy is stable if its
execution keeps the number of outstanding requests uniformly bounded over time.
Although, rollout-based approaches are well-suited for learning cooperative
multiagent policies with considerations for future demand, applying such
methods to a large urban environment can be computationally expensive due to
the large number of taxis required for stability. In this paper, we aim to
address the computational bottleneck of multiagent rollout by proposing an
approximate multiagent rollout-based two phase algorithm that reduces
computational costs, while still achieving a stable near-optimal policy. Our
approach partitions the graph into sectors based on the predicted demand and
the maximum number of taxis that can run sequentially given the user's
computational resources. The algorithm then applies instantaneous assignment
(IA) for re-balancing taxis across sectors and a sector-wide multiagent rollout
algorithm that is executed in parallel for each sector. We provide two main
theoretical results: 1) characterize the number of taxis $m$ that is sufficient
for IA to be stable; 2) derive a necessary condition on $m$ to maintain
stability for IA as time goes to infinity. Our numerical results show that our
approach achieves stability for an $m$ that satisfies the theoretical
conditions. We also empirically demonstrate that our proposed two phase
algorithm has equivalent performance to the one-at-a-time rollout over the
entire map, but with significantly lower runtimes.
- Abstract（参考訳）: 本稿では,大都市環境における自律型マルチエージェントタクシー経路問題に焦点をあてる。これは,将来の乗車要求の場所と回数が未知であるが,実証的な分布から推定することができる。
最近の理論では、安定したベースポリシーを持つロールアウトアルゴリズムが最適に近い安定ポリシーを生成することが示されている。
ルーティング設定では、その実行が時間とともに一様に境界づけられた優れたリクエストの数を維持するとポリシーが安定する。
ロールアウト型アプローチは,今後の需要を考慮した協調型マルチエージェント政策の学習に適しているが,安定に必要なタクシーが多数存在するため,大規模都市環境への適用は計算コストがかかる可能性がある。
本稿では, 近似的マルチエージェントロールアウトに基づく2相アルゴリズムを提案し, 計算コストを低減しつつ, 安定な準最適ポリシを実現することで, マルチエージェントロールアウトの計算ボトルネックに対処することを目的とする。
提案手法では,予測された需要と,ユーザの計算資源を逐次的に考慮したタクシーの最大数に基づいて,グラフをセクターに分割する。
このアルゴリズムは、セクタ間のタクシーの再バランスと、セクタ毎に並列に実行されるセクタ全体のマルチエージェントロールアウトアルゴリズムに即時割り当て(ia)を適用する。
主な理論的結果は2つある。
1) IAが安定するのに十分なタクシー数$m$を特徴付ける。
2) 時間が無限に進むにつれて、IAの安定性を維持するために$m$で必要条件を導出する。
数値解析の結果,理論条件を満たす$m$の安定性が得られた。
また,提案した2相アルゴリズムは,マップ全体のワン・ア・ア・タイム・ロールアウトに匹敵する性能を持つが,実行時間が大幅に低いことを示す。
関連論文リスト
- Online Fair Allocation of Perishable Resources [1.4952056744888913]
我々は、標準オンラインフェアアロケーション問題の事実上の動機付け型を考察する。
意思決定者は、一定回数のラウンドを割り当てるために、パーシシブルなリソースの予算を持っている。
目標は、うらやましいほど効率的で効率的なアロケーションのシーケンスを構築することです。
論文 参考訳（メタデータ） (2024-06-04T15:14:10Z) - Safe Model-Based Multi-Agent Mean-Field Reinforcement Learning [48.667697255912614]
平均場強化学習は、同一エージェントの無限集団と相互作用する代表エージェントのポリシーに対処する。
モデルベースの平均場強化学習アルゴリズムであるSafe-M$3$-UCRLを提案する。
本アルゴリズムは,低需要領域におけるサービスアクセシビリティを確保しつつ,重要な領域における需要を効果的に満たす。
論文 参考訳（メタデータ） (2023-06-29T15:57:07Z) - Planning and Learning with Adaptive Lookahead [74.39132848733847]
ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。
近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。
本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
論文 参考訳（メタデータ） (2022-01-28T20:26:55Z) - H-TD2: Hybrid Temporal Difference Learning for Adaptive Urban Taxi
Dispatch [9.35511513240868]
H-TD2はモデルフリーで適応的な意思決定アルゴリズムであり、動的な都市環境下で多数の自動タクシーを協調する。
計算複雑性と個別のタクシー政策の限定された部分最適化とのトレードオフを明示的に制御するために、2つの行動の間のトリガ条件を記述・規定する。
最近の強化学習ディスパッチ法とは異なり、このポリシ推定はトレーニング外ドメインイベントに適応し、堅牢である。
論文 参考訳（メタデータ） (2021-05-05T15:42:31Z) - Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。
DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。
有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
論文 参考訳（メタデータ） (2021-02-23T18:56:13Z) - Equilibrium Inverse Reinforcement Learning for Ride-hailing Vehicle
Network [1.599072005190786]
疎結合グラフにおける客車マッチングの問題を定式化する。
マルチエージェント環境における平衡ポリシを導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-13T03:18:44Z) - Deep Reinforcement Learning for Stock Portfolio Optimization [0.0]
私たちは、タスクに強化学習を適切に適用できるように問題を定式化します。
市場に関する現実的な仮定を維持するためには、取引コストとリスクファクターを州にも組み込む予定です。
ストックサブセット選択のための最小分散ポートフォリオと多周波データパターン抽出のためのウェーブレット変換を用いたタスクのエンドツーエンドソリューションを提案する。
論文 参考訳（メタデータ） (2020-12-09T10:19:12Z) - Multiagent Rollout and Policy Iteration for POMDP with Application to
Multi-Robot Repair Problems [1.6939372704265414]
有限状態および制御空間,部分状態観測,マルチエージェント構造を有する無限地平面割引動的プログラミング問題を考える。
本手法は、部分的に観測可能なマルチエージェント問題の計算問題に特に対処する。
論文 参考訳（メタデータ） (2020-11-09T06:51:50Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z) - Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。
任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
論文 参考訳（メタデータ） (2020-02-12T18:59:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。