論文の概要: Approximate Multiagent Reinforcement Learning for On-Demand Urban
Mobility Problem on a Large Map (extended version)
- arxiv url: http://arxiv.org/abs/2311.01534v1
- Date: Thu, 2 Nov 2023 18:33:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-06 16:16:47.677993
- 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要約: 我々は大都市環境における自律型マルチエージェントタクシー経路問題に焦点をあてる。
最近の理論では、ベースポリシーが安定ならば、そのようなベースポリシーを持つロールアウトベースのアルゴリズムは、ほぼ最適に安定なポリシーを生成する。
ほぼ1対1のロールアウトに基づく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 follow an estimated empirical distribution. Recent
theory has shown that if a base policy is stable then a rollout-based algorithm
with such a base policy produces a near-optimal stable policy. 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. Large environments
tend to have a large volume of requests, and hence require a large fleet of
taxis to guarantee stability. In this paper, we aim to address the
computational bottleneck of multiagent (one-at-a-time) rollout, where the
computational complexity grows linearly in the number of agents. We propose an
approximate one-at-a-time rollout-based two-phase algorithm that reduces the
computational cost, while still achieving a stable near-optimal policy. Our
approach partitions the graph into sectors based on the predicted demand and an
user-defined maximum number of agents that can be planned for using the
one-at-a-time rollout approach. The algorithm then applies instantaneous
assignment (IA) for re-balancing taxis across sectors and a sector-wide
one-at-a-time rollout algorithm that is executed in parallel for each sector.
We characterize the number of taxis $m$ that is sufficient for IA base policy
to be stable, and derive a necessary condition on $m$ 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 comparable performance to the one-at-a-time
rollout over the entire map, but with significantly lower runtimes.
- Abstract（参考訳）: 本稿では,将来の乗車要求の場所や回数が不明な大規模都市環境における自律型マルチエージェントタクシー経路問題に着目し,推定実験分布について考察する。
最近の理論では、ベースポリシーが安定ならば、そのようなベースポリシーを持つロールアウトベースのアルゴリズムは、ほぼ最適の安定ポリシーを生成する。
ロールアウト型アプローチは, 今後の需要を考慮した協調マルチエージェント政策の学習に適しているが, 大規模都市環境への適用には計算コストがかかる可能性がある。
大きな環境には大量の要求があり、それゆえ安定性を保証するために大量のタクシーが必要となる。
本稿では,エージェント数で計算複雑性が線形に増加するマルチエージェント(ワン・ア・ア・タイム)ロールアウトの計算ボトルネックに対処することを目的とする。
そこで本研究では, 計算コストを低減しつつ, 安定な近似近似近似的ロールアウトに基づく二相アルゴリズムを提案する。
当社のアプローチでは,予測された需要と,ワン・ア・ア・タイム・ロールアウトアプローチを用いて計画可能な最大エージェント数に基づいて,グラフをセクターに分割する。
このアルゴリズムは、セクタ間のタクシーの再バランスと、セクタ毎に並列に実行されるセクタ全体のワン・ア・タイム・ロールアウトアルゴリズムに即時割り当て(ia)を適用する。
我々は、iaベースポリシーが安定するためには十分であるタクシーの数m$を特徴付け、時間が経つにつれて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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。