論文の概要: Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph
- arxiv url: http://arxiv.org/abs/2403.07748v2
- Date: Thu, 4 Jul 2024 15:40:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-08 23:33:46.550233
- Title: Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph
- Title（参考訳）: Ariadne と Theseus: 未知のグラフで2つのモバイルエージェントによる探索とレンデブー
- Authors: Romain Cosson,
- Abstract要約: モバイルコンピューティングにおける2つの基本的な問題、探索とランデブーについて検討する。
そこで本研究では,時間段階の集合探索を実現するアルゴリズムを提案する。
また,少なくとも frac32m$ の時間ステップでレンデブーを保証するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 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 may communicate by reading and writing information on whiteboards that are located at all nodes. They both move along one adjacent edge at every time-step. In the exploration problem, the agents start from the same arbitrary node and must traverse all the edges. We present an algorithm achieving collective exploration in $m$ time-steps, where $m$ is the number of edges of the graph. This improves over the guarantee of depth-first search, which requires $2m$ time-steps. In the rendezvous problem, the agents start from different nodes of the graph and must meet as fast as possible. We present an algorithm guaranteeing rendezvous in at most $\frac{3}{2}m$ time-steps. This improves over the so-called `wait for Mommy' algorithm which is based on depth-first search and which also requires $2m$ time-steps. Importantly, 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 generalize to weighted graphs, when replacing the number of edges $m$ with the sum of all edge lengths. We show that our guarantees are met with matching lower-bounds in the asynchronous setting.
- Abstract（参考訳）: モバイルコンピューティングにおける2つの基本的な問題、すなわち探索とランデブーについて、未知のグラフに2つの異なるモバイルエージェントを用いて検討する。
エージェントは、すべてのノードにあるホワイトボードで情報を読み書きすることで通信することができる。
どちらも、各段階ごとに隣接する端に沿って移動する。
探索問題では、エージェントは同じ任意のノードから始まり、すべてのエッジを横切る必要がある。
我々は,グラフのエッジ数として$m$の時間ステップで集合探索を行うアルゴリズムを提案する。
これにより、深さ優先検索の保証が改善される。
ランデブー問題では、エージェントはグラフの異なるノードから始まり、できるだけ早く満たさなければならない。
我々は,少なくとも$\frac{3}{2}m$の時間ステップでランデブーを保証するアルゴリズムを提案する。
このアルゴリズムは、深さ優先の検索をベースとし、200万ドル(約2億2000万円)のタイムステップを必要とする。
重要なことは、我々の保証はすべて、エージェントの速度が常に敵によって制御されるより一般的な非同期設定に由来する。
我々の保証は、すべての辺の長さの和に$m$のエッジの数を置き換えるとき、重み付きグラフに一般化する。
保証は、非同期環境での下位バウンドと一致していることが示されます。
関連論文リスト
- Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。
この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。
我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-02-27T18:12:58Z) - Improved Anonymous Multi-Agent Path Finding Algorithm [3.694001372535405]
エージェントの集合をグラフに限定する匿名多エージェントパスフィンディング(AMAPF)問題を考える。
我々は,検索空間を探索するアイデアを,個別の検索状態ではなく,一括して考えることによって活用する,特定の検索アルゴリズムを提案する。
その結果、AMAPFソルバは最先端の競合に比べて優れた性能を示し、30秒未満で利用可能なすべてのMAPFインスタンスを解決できる。
論文 参考訳（メタデータ） (2023-12-17T00:49:30Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Quantum walk based state transfer algorithms on the complete M-partite
graph [0.0]
量子ウォーク探索と状態伝達アルゴリズムについて検討し,各パーティションに$N$頂点を持つ完全$M$パーティイトグラフに着目した。
送信側と受信側が異なるパーティションにある場合、そのアルゴリズムは大きなグラフに対してユニティに近づく忠実度で成功することを示す。
しかし、送信側と受信側が同じパーティションにある場合、忠実度は正確には1つには達しない。
論文 参考訳（メタデータ） (2022-12-01T14:52:49Z) - GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。
不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。
我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
論文 参考訳（メタデータ） (2022-11-04T16:10:50Z) - Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。
予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。
本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
論文 参考訳（メタデータ） (2022-10-14T13:09:11Z) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳（メタデータ） (2022-07-07T06:16:19Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳（メタデータ） (2022-01-23T20:04:15Z) - Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか?
本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
論文 参考訳（メタデータ） (2021-06-08T16:10:36Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。