論文の概要: Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents
in an Unknown Graph
- arxiv url: http://arxiv.org/abs/2403.07748v1
- Date: Tue, 12 Mar 2024 15:33:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 20:52:26.385178
- Title: Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents
in an Unknown Graph
- Title(参考訳): Ariadne と Theseus: 未知のグラフで2つのモバイルエージェントによる探索とレンデブー
- Authors: Romain Cosson
- Abstract要約: モバイルコンピューティングにおける2つの基本的な問題、探索とランデブーについて検討する。
我々は,深度優先探索の単純な変種が,同期時間ステップ$m$の集合探索を実現することを示す。
ランデブー問題では、エージェントはグラフの異なるノードから始まり、できるだけ早く満たさなければならない。
- 参考スコア(独自算出の注目度): 1.4685355149711303
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate two fundamental problems in mobile computing: exploration and
rendezvous, with two distinct mobile agents in an unknown graph. The agents can
read and write information on whiteboards that are located at all nodes. They
both move along one adjacent edge at every time-step. In the exploration
problem, both agents start from the same node of the graph and must traverse
all of its edges. We show that a simple variant of depth-first search achieves
collective exploration in $m$ synchronous time-steps, where $m$ is the number
of edges of the graph. This improves the competitive ratio of collective graph
exploration. In the rendezvous problem, the agents start from different nodes
of the graph and must meet as fast as possible. We introduce an algorithm
guaranteeing rendezvous in at most $\frac{3}{2}m$ time-steps. This improves
over the so-called `wait for Mommy' algorithm which requires $2m$ time-steps.
All our guarantees are derived from a more general asynchronous setting in
which the speeds of the agents are controlled by an adversary at all times. Our
guarantees also generalize to weighted graphs, if the number of edges $m$ is
replaced by the sum of all edge lengths.
- Abstract(参考訳): モバイルコンピューティングにおける2つの根本的な問題、探索とランデブーについて、未知のグラフに2つの異なるモバイルエージェントを用いて検討する。
エージェントは、すべてのノードにあるホワイトボードに関する情報を読み書きすることができる。
両者とも、各時間ごとに隣り合う縁に沿って移動する。
探索問題では、両方のエージェントはグラフの同じノードから始まり、すべてのエッジをトラバースしなければならない。
我々は,深度優先探索の単純な変種が,グラフのエッジ数として$m$の同期時間ステップの集合探索を実現することを示す。
これにより、集合グラフ探索の競争比が向上する。
ランデブー問題では、エージェントはグラフの異なるノードから始まり、できるだけ早く満たさなければならない。
我々は、最大$\frac{3}{2}m$時間ステップでランデブーを保証するアルゴリズムを導入する。
これにより、いわゆる‘Wait for Mommy’アルゴリズムよりも改善される。
すべての保証は、エージェントの速度が常に敵によって制御されるより一般的な非同期設定に由来する。
私たちの保証はまた、すべての辺の長さの和に$m$のエッジの数が置き換えられる場合、重み付きグラフにも一般化される。
関連論文リスト
- Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。
この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。
我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
論文 参考訳(メタデータ) (2024-02-27T18:12:58Z) - Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis [5.02063914741425]
Zhang, Johansson, Li が導入したグラフバンディット問題のマルチエージェント拡張として,マルチエージェントグラフバンディット問題を定式化する。
上信頼境界(UCB)に基づく学習アルゴリズムであるMulti-G-UCBを提案し、T$のステップに対する期待された後悔が$O(gamma Nlog(T)[sqrtKT + DK])$で束縛されていることを証明した。
論文 参考訳(メタデータ) (2024-01-18T21:36:17Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳(メタデータ) (2023-07-25T12:33:53Z) - GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。
不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。
我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
論文 参考訳(メタデータ) (2022-11-04T16:10:50Z) - Multi-armed Bandit Learning on a Graph [0.0]
そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。
我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。
提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
論文 参考訳(メタデータ) (2022-09-20T02:31:42Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-01T15:14:32Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳(メタデータ) (2022-05-28T15:37:03Z) - Best Arm Identification in Graphical Bilinear Bandits [9.052414772641011]
本稿では,学習者がグラフのノードにアームを割り当てる,新しいグラフィカル双線形帯域問題を提案する。
学習者が双線形報酬の合計を最大化するグラフ割り当てを見つけたいと思う最良の腕識別問題について研究する。
論文 参考訳(メタデータ) (2020-12-14T15:25:23Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳(メタデータ) (2020-12-10T15:40:07Z) - Structural Temporal Graph Neural Networks for Anomaly Detection in
Dynamic Graphs [54.13919050090926]
本稿では,動的グラフの異常エッジを検出するために,エンドツーエンドの時間構造グラフニューラルネットワークモデルを提案する。
特に,まずターゲットエッジを中心にした$h$ホップ囲むサブグラフを抽出し,各ノードの役割を識別するノードラベル機能を提案する。
抽出した特徴に基づき,GRU(Gated Recurrent Unit)を用いて,異常検出のための時間的情報を取得する。
論文 参考訳(メタデータ) (2020-05-15T09:17:08Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳(メタデータ) (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。