Rendezvous search on a graph
Rendezvous search on a graph
复制标题
图上的集合点搜索
DOI：
10.1239/jap/1032374243
复制
发表时间：
1999
影响因子：
1
通讯作者：
Skander Essegaier
中科院分区：
文献类型：
--
作者：
S. Alpern;V. Baston;Skander Essegaier
将两个代理随机放置在已知图的节点上。他们知道自己的位置，直到图的某些对称性，但不是其他代理人。在每一步中，每个智能体可以停留在他所在的位置或移动到相邻的节点。它们的共同目标是最小化满足（占用同一节点）所需的预期步骤数。我们考虑两种情况下确定的球员是否被限制使用相同的策略。这项工作扩展了安德森和韦伯的“离散位置”（完整的图形），并与连续（时间和空间）会合制定的阿尔珀恩。概率的概念出现在随机的初始位置，在随机对称性确定的空间不确定性的代理，并通过使用混合策略。
Two agents are placed randomly on nodes of a known graph. They are aware of their own position, up to certain symmetries of the graph, but not that of the other agent. At each step, each agent may stay where he is or move to an adjacent node. Their common aim is to minimize the expected number of steps required to meet (occupy the same node). We consider two cases determined by whether or not the players are constrained to use identical strategies. This work extends that of Anderson and Weber on ‘discrete locations’ (complete graph) and is related to continuous (time and space) rendezvous as formulated by Alpern. Probabilistic notions arise in the random initial placement, in the random symmetries determining spatial uncertainty of agents, and through the use of mixed strategies.