日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

群制御arXiv:2510.24515

ランクベース確率的賞金収集ゲームにおける順序応答方策の学習

Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games

シェア:XThreadsFacebookLINEはてブBluesky

報酬が乏しい環境で自己利益を追求するエージェント群の経路計画を、チームオリエンテーリング問題の拡張として定式化し、順序ランクを条件とした局所情報方策が有効であることを示した研究。

詳しい要約

1. どんなもの?

- Team Orienteering Problem (TOP) を拡張した Stochastic Prize-Collecting Orienteering Games (SPCOG) を提案する論文。 - グラフ上で自己利益を追求するエージェント群が、エネルギー制約と確率的遷移の下で計画する設定を扱う。 - 複数エージェントの scheduling・routing タスク(autonomous mobility, aerial logistics, surveillance など)を動機とする。 - Ordinal Rank (OR) という表現と、Fictitious Ordinal Response Learning (FORL) というアルゴリズムも提案。

2. 先行研究と比べてどこがすごい?

- 既存の TOP の諸変種は全エージェントが単一目的に協力することを仮定しており、報酬が乏しい環境で競合する設定には拡張できない。 - 本論文は競合する self-interested agents を扱う SPCOG を定式化した点が新しい。 - complete graph と star graph について、rank-based conflict resolution の下で unique pure Nash equilibrium が存在し、等価な TOP の最適 routing 解と一致することを理論的に示す。 - OR を条件とした局所情報ポリシーが、global rank 条件のポリシーを上回り得ることを示す。

3. 技術・手法の肝は?

- SPCOG をグラフ上のゲームとして定式化し、エネルギー制約と stochastic transitions を含める。 - Ordinal Rank (OR): エージェントの大域的順位と、位相的に well-defined な近傍内での位置を簡潔に表す表現。 - rank-based conflict resolution の下での均衡と TOP 最適解の対応を理論解析。 - Fictitious Ordinal Response Learning (FORL): independent-learning 設定で収束ポリシーを得るための entropy-regulated アルゴリズム。 - parameter-sharing 設定で OR 条件の局所情報ポリシーを学習。

4. どうやって有効だと検証した?

- 実世界の road-network graphs 上で、dynamic と stationary の両方の prize distributions を用いて経験的評価を実施。 - parameter-sharing 設定において、OR に条件付けた局所情報ポリシーが global rank 条件のポリシーを上回る場合があることを示す。 - OR 条件ポリシーは、エージェント数が多いゲームへの汎化が global-rank 条件ポリシーより大幅に良いことを示す。 - FORL の収束性に関する検証は要旨からは不明。

5. 議論はある?

- OR がグラフ上のマルチエージェントゲームにおける強い inductive bias として働くことを示唆。 - 局所情報が大域情報を上回り得る条件(parameter-sharing 設定)が議論の焦点。 - 理論結果は complete graph と star graph に限られており、一般グラフへの拡張可能性は要旨からは不明。 - FORL の収束保証や independent-learning 設定での性能比較の詳細は要旨からは不明。

6. 次に読むべき論文は?

- Team Orienteering Problem (TOP) の原論文・諸変種。 - rank-based conflict resolution や pure Nash equilibrium に関するゲーム理論の文献。 - Fictitious Play / Fictitious Response Learning 系の学習手法。 - entropy-regulated なマルチエージェント強化学習(例: 関連する regularized policy learning)。 - グラフ上の multi-agent reinforcement learning における局所情報・近傍表現の研究。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Malintha Fernando, Petter Ögren, Silun Zhang

分類: cs.RO

原文アブストラクト

The Team Orienteering Problem (TOP) generalizes many real-world multi-agent scheduling and routing tasks that occur in autonomous mobility, aerial logistics, and surveillance applications. While many flavors of the TOP exist for planning in multi-agent systems, they assume that all the agents cooperate toward a single objective; therefore, they do not extend to settings when they compete in reward-scarce environments. We propose Stochastic Prize-Collecting Orienteering Games (SPCOG) as an extension of the TOP to plan in the presence of self-interested agents operating on a graph, under energy constraints and stochastic transitions. A theoretical discussion on complete and star graphs establishes that there is a unique pure Nash equilibrium in SPCOGs that coincides with the optimal routing solution of an equivalent TOP under rank-based conflict resolution. We propose the concept of Ordinal Rank (OR) as a concise representation of an agents' global rank and its location within a topological, well-defined neighborhood. Empirical evaluations conducted on real-world, road-network graphs under both dynamic and stationary prize distributions show that in parameter-sharing settings, the policies that leverage local information can outperform those policies leverage global information when the former is conditioned on the OR rather than the global rank, indicating that the OR acts as a strong inductive bias in multi-agent games on graphs. The OR-conditioned policies also generalize much better to games with large number of agents compared to global-rank conditioned policies. Finally, we also propose we propose Fictitious Ordinal Response Learning (FORL) as an entropy-regulated algorithm to obtain convergent policies in independent-learning settings in prize-collecting games on graphs.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI