Bampas Evangelos, Czyzowicz Jurek, Gąsieniec Leszek, Ilcinkas David, Klasing Ralf, Kociumaka Tomasz, Pająk Dominik
1LIS, CNRS and Aix-Marseille University, Marseille, France.
2Département d'informatique, Université du Québec en Outaouais, Gatineau, Canada.
Algorithmica. 2019;81(1):317-342. doi: 10.1007/s00453-018-0447-0. Epub 2018 May 7.
Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely and . In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.
两个移动机器人最初放置在一条无限长直线上的同一点。每个机器人可以在线上沿任意方向移动，但速度不能超过其最大速度。机器人需要找到放置在直线上未知位置的一个固定目标。当两个机器人都到达目标点时，搜索完成。当任何一个机器人到达目标位置时，目标就被发现了。知道目标位置的机器人可以将其告知另一个机器人。我们要寻找一种搜索时间尽可能短的算法（即两个机器人在目标点相遇的最坏情况时间），该时间是目标到原点距离的函数（即以单位速度从起点直接移动到目标所需的时间）。我们考虑机器人之间两种标准的通信模型，即 和 。在通过相遇进行通信的情况下，一个机器人在与拥有该知识的机器人处于同一位置时了解到目标。在此，我们针对两个机器人提出一种最优搜索策略，包括相应的下界论证，适用于它们最大速度的整个范围。这扩展了Chrobak等人（收录于：Italiano, Margaria - Steffen, Pokorný, Quisquater, Wattenhofer（编）《计算机科学理论与实践的当前趋势》，SOFSEM，2015）的主要结果，该结果涉及较慢机器人速度至少为较快机器人速度三分之一时问题的精确复杂度。在无线通信模型中，一个机器人发送的消息会被另一个机器人立即接收，无论它们在线上的当前位置如何。对于这个模型，我们设计了一种策略，只要较快机器人的速度至多是较慢机器人的 倍，该策略就是最优的。我们还证明，否则无线通信相对于通过相遇进行的通信没有优势。
