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.

探索与会合问题中，我们研究了移动计算中的两个基本问题：探索和会合。通过在未知图中使用两个不同的移动代理，代理可以在所有节点上读写信息。我们展示了一个简单的深度优先搜索变体，在 $m$ 个同步时间步骤内完成了集体探索，其中 $m$ 是图的边数。同时，我们引入了一个算法，保证在不超过 $rac {3}{2} m$ 个时间步骤内实现会合，这是对所谓的 “等待妈妈” 的算法（需要 $2m$ 个时间步骤）的改进。所有的保证都是从一个更一般的异步设置中推导出来的，在该设置中，代理的速度在任何时刻都由对手控制。如果将边数 $m$ 替换为所有边长度的总和，则我们的保证也推广到加权图。

Ariadne 与 Theseus：未知图中的两个移动代理的探索与会合

Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents  in an Unknown Graph

We train neural models to represent both the optimal policy (i.e. the optimal
thrust direction) and the value function (i.e. the time of flight) for a time
optimal, constant acceleration low-thrust rendezvous. In both cases we develop
and make use of the data augmentation technique we call backward generation of
optimal examples. We are thus able to produce and work with large dataset and
to fully exploit the benefit of employing a deep learning framework. We
achieve, in all cases, accuracies resulting in successful rendezvous (simulated
following the learned policy) and time of flight predictions (using the learned
value function). We find that residuals as small as a few m/s, thus well within
the possibility of a spacecraft navigation $\Delta V$ budget, are achievable
for the velocity at rendezvous. We also find that, on average, the absolute
error to predict the optimal time of flight to rendezvous from any orbit in the
asteroid belt to an Earth-like orbit is small (less than 4\%) and thus also of
interest for practical uses, for example, during preliminary mission design
phases.

利用神经模型和数据增强技术，在深度学习框架下，实现低推力阶段的快速、准确太空交会的优化、值函数预测，实验结果表明模型在预测太空航行中的速度和时间上拥有高的精度。