文章基本信息

标题：Robot Evacuation on a Line Assisted by a Bike
本地全文：下载
作者：Khaled Jawhar ; Evangelos Kranakis
期刊名称：Information
电子版ISSN：2078-2489
出版年度：2021
卷号：12
期号：1
页码：28
DOI：10.3390/info12010028
出版社：MDPI Publishing
摘要：Two robots and a bike are initially placed at the origin of an infinite line. The robots are modelled as autonomous mobile agents whose communication capabilities are either in the wireless or face-to-face model, while the bike neither can move nor communicate on its own. Thus, the bike is not autonomous but rather requires one of the robots to ride it. An exit is placed on the line at distance d from the origin; the distance and direction of the exit from the origin is unknown to the robots. Only one robot may ride the bike at a time and the goal is to evacuate from the exit in the minimum time possible as measured by the time it takes the last robot to exit. The robots can maintain a constant walking speed of 1, but when riding the bike they can maintain a constant speed v>1 (same for both robots). We develop algorithms for the evacuation of the two robots from the unknown exit and analyze the evacuation time defined as the time it takes the second robot to evacuate. In the wireless model we present three algorithms: in the first the robots move in opposite direction with max speed, in the second with a specially selected “optimal” speed, and in the third the robot imitates the biker (i.e., robot riding the bike). We also give three algorithms in the Face-to-Face model: in the first algorithm the robot pursues the biker, in the second the robot and the biker use zig-zag algorithms with specially chosen expansion factors, and the third algorithm establishes a sequence of specially constructed meeting points near the exit. In either case, the optimality of these algorithms depends on v>1. We also discuss lower bounds.
关键词：arrival time; bike; evacuation; line; robots; search; speed; optimal trajectory arrival time ; bike ; evacuation ; line ; robots ; search ; speed ; optimal trajectory