This paper studies the online problem of search and rescue on a (unit) ring. Assuming that an object is located somewhere unknown on the ring, we aim to find the object and deliver it to a designated destination by one or more mobile agents, so that the total time spent is minimized. The agent(s) can only move along the ring, and is initially located a distance of Formula: see text away from the destination. For single-agent search and rescue, we present an optimal deterministic algorithm with a competitive ratio of Formula: see text, and as well as randomized algorithms corresponding to Formula: see text and Formula: see text, whose expected competitive ratios can be accurately computed by non-linear programming. For the two-agent search and rescue, we propose deterministic algorithms with competition ratios depending on whether the agents can communicate through the radios.
Guo et al. (Wed,) studied this question.