Capturing an Evader in a Building - Randomized and Deterministic Algorithms for Mobile Robots

A three-dimensional (3D) grid G_{ntimesntimesn}, n ges 2, is the set of points (vertices) with integer coordinates in [0,n-1]times[0,n-1] together with their connecting edges, which is viewed as a connected 3D set. Alternatively, G_{ntimesntimesn} can be viewed as the union of 2n² horizontal line segments, called corridors, and n² vertical line segments, called shafts. We view G_{ntimesntimesn} as representing a building and consider a vision-based pursuit-evasion problem in which a group of mobile robots (pursuers) are required to search for and capture an evader (intruder) hiding in it. The robots and the evader-all called players-are represented by points that move continuously along the edges of G_{ntimesntimesn}. (Two players can be at the same point at one time.) Any continuous move in G_{ntimesntimesn} is allowed within the speed limit constraint, which is for the evader without loss of generality, and a constant s for the robots The evader is considered captured if there exists a time during the pursuit when his position coincides with the position of one of the robots.