Two Simple Robots Can Now Catch a Moving Target Together
This math breakthrough could lead to smarter drones and search-and-rescue bots.
We study a problem of searching for a mobile target in an $m$-ray star graph, a natural generalization of linear search to multiple directions. The target is placed adversarially on one of the rays and may move with constant speed.
We investigate a two-robot setting, where cooperation and communication play a central role. We study two communication models: the Face-to-Face (F2F) model, where robots communicate only upon meeting, and the Sender-Receiver (S/R) model, where communication is asymmetric.
We focus on the {\em away model}, in which the target moves {\em away} from the origin with speed $v<1$. We design search strategies that minimize the competitive ratio and analyze the problem under three knowledge assumptions: \emph{NoDistance}, \emph{NoSpeed}, and \emph{NoKnowledge}. For each setting, we derive upper bounds on the competitive ratio and for some cases, we derive the lower bound. Our results highlight how the number of rays and the communication model influence the competitive ratio.
- Two simple robots can catch a moving target on a star-shaped map if they communicate.
- Researchers proved it's always possible and found the fastest strategy.
- This could lead to better teamwork in drones and robots for tasks like search-and-rescue.
Why It Matters
Could lead to smarter robot teams for search-and-rescue, delivery, and security.