Wireless Autonomous Robot Evacuation from Equilateral Triangles and Squares
Wireless Autonomous Robot Evacuation from Equilateral Triangles and Squares
复制标题
等边三角形和正方形的无线自主机器人疏散
DOI：
10.1007/978-3-319-19662-6_13
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Shende
中科院分区：
文献类型：
--
作者：
J. Czyzowicz;E. Kranakis;D. Krizanc;L. Narayanan;J. Opatrny;S. Shende
考虑一个等边三角形或正方形，其边长为 i3?$$1$$。需要从三角形或正方形周边的同一位置或三角形或正方形内部的相同位置出发的多个机器人从位于其周边未知位置的出口撤离。在任何时候，机器人都可以以等于 $$1$$ 的相同速度移动，并且它们可以通过无线通信相互协作。因此，如果机器人找到出口，它可以向其余机器人广播“找到出口”，然后其余机器人沿直线段朝出口移动以疏散。我们的任务是设计机器人轨迹，最大限度地减少机器人的疏散时间，即最后一个机器人从出口疏散的时间。设计这样的最优算法被证明是一个非常艰巨的问题，甚至等边三角形的情况也被证明是具有挑战性的。
我们为两个机器人设计了最佳疏散轨迹算法，其中任何起始位置为等边三角形，周界起始位置为正方形。结果表明，对于等边三角形，三个或三个以上从周边开始的机器人无法比两个机器人获得更好的疏散时间，但存在内部起点，三个机器人比两个机器人疏散速度更快。对于正方形，从一个角开始的三个或更多机器人无法比两个机器人获得更好的疏散时间，但在正方形的周边上存在一些点，从该点开始的三个机器人比从同一点开始的两个机器人疏散得更快。此外，在等边三角形或正方形中，可以证明简单算法在机器人数量 $$k$$ 中是渐近最优的，如 $$k \rightarrow \infty $$，前提是机器人从相应域的中心开始。
Consider an equilateral triangle or square with sides of lengthi¾?$$1$$. A number of robots starting at the same location on the perimeter or in the interior of the triangle or square are required to evacuate from an exit which is located at an unknown location on its perimeter. At any time the robots can move at identical speed equal to $$1$$, and they can cooperate by communicating with each other wirelessly. Thus, if a robot finds the exit it can broadcast "exit found" to the remaining robots which then move in a straight line segment towards the exit to evacuate. Our task is to design robot trajectories that minimize the evacuation time of the robots, i.e., the time the last robot evacuates from the exit. Designing such optimal algorithms turns out to be a very demanding problem and even the case of equilateral triangles turns out to be challenging.
We design optimal evacuation trajectories algorithms for two robots in the case of equilateral triangles for any starting position and for squares for starting positions on the perimeter. It is shown that for an equilateral triangle, three or more robots starting on the perimeter cannot achieve better evacuation time than two robots, while there exist interior starting points from which three robots evacuate faster than two robots. For the square, three or more robots starting at one of the corners cannot achieve better evacuation time than two robots, but there exist points on the perimeter of the square such that three robots starting from such a point evacuate faster than two robots starting from this same point. In addition, in either the equilateral triangle or the square it can be shown that a simple algorithm is asymptotically optimal in the number $$k$$ of robots, as $$k \rightarrow \infty $$, provided that the robots start at the centre of the corresponding domain.