Searching with Two-Speed Autonomous Mobile Robots

We introduce and study various search problems using mobile robots. Specifically we study the problems of exploration and patrolling using a new two-speed model of robots, as well as studying the problems of rendezvous and evacuation using a more traditional one-speed model of robots. The problems are executed on a continuous finite domain by a swarm of n robots. For the two-speed model, each robot r_i has a walking speed w_i and a searching speed s_i, where s_i < w_i. At each moment a robot either moves through the domain with a speed w_i, or it searches the domain with speed s_i.A search of an interval is completed when each of its points have been searched by at least one of the robots. We want to develop efficient mobility schedules (algorithms) for the robots which complete the search of the interval as quickly as possible. More exactly, we want to maximize the speed of the mobility schedule, defined as the ratio of the interval length compared to the time of completion of the schedule.For patrolling, a unit interval is to be patrolled collectively by n two-speed robots. A robot patrols a portion of the domain by searching it. Each robot is allowed to patrol only in one of the two directions. We want to schedule the perpetual movements of the robots to minimize the idle time, defined as the maximal time interval any point is not visited by some patrolling robot.We also study randomized rendezvous on a circle: Two one-speed robots begin at different locations on a circle and want to minimize the time required to find each other. The robots have different speeds, are unaware of their own speed, are equipped with identical chronometers, and each have access to one or more random bits.Finally, we study the evacuation problem: Distributed on a unit circle are k exits; two identical one-speed robots are placed on the circle. The goal of the evacuation problem is to give an algorithm for the robots which minimizes the time required for both robots to reach an exit.