Robots Evacuation in the Face-to-face Model
Saeed Mehrabi
Carleton University

Consider $k$ robots initially located at the centroid of an equilateral triangle $T$ with sides of length 1. The goal of the robots is to evacuate $T$ through an exit at an unknown location on the boundary of $T$. Each robot can move anywhere in $T$ independently of other robots with maximum speed 1. The objective is to minimize the evacuation time, which is defined as the time required for all $k$ robots to reach the exit. We consider this problem in the face-to-face model of communication: a robot can communicate with another robot only when they meet in $T$. For $k=2,3,4,5$ robots, we will show an equal-travel algorithm with early meeting that gives upper bounds of, respectively, 2.411, 2.088, 1.981, 1.876 on the evacuation time. For $k=2$ robots in particular, we show how to improve the evacuation time to 2.383 using a detour by the robots.

This is a joint work with Huda Chuangpishit, Lata Narayanan, and Jaroslav Opatrny.