Seminar: Searching the Plane for a Point with Distinct Speed Agents

Speaker: Matthew Madej, Department of Mathematics, TMU

Title: Searching the Plane for a Point with Distinct Speed Agents

Abstract: Consider the problem of minimizing the worst-case normalized search time for a hidden target in the plane using multiple mobile agents of differing speeds, that all start at the origin. The search cost is the maximum ratio between the time taken to discover a point and the point's distance from the origin. It is already known that for a single unit-speed agent the search cost is $\mathcal{U}_1 = 17.28935$ using logarithmic spirals. We extend this result to a spiral-based algorithm for $n$ unit-speed agents, where the $n$ agents are offset by equal angular phases. Our main contribution is a general upper bound on the worst-case normalized search time for $n$ arbitrary speed agents. We present an algorithm that allows for the selection of speed-dependent angular offsets. We have found that $n$ multi speed agents, where the fastest among them has speed 1, can outperform $k$ unit-speed agents. It must be noted that slow agents may be excluded from logarithmic spiral search if including them would reduce the geometric average too severely. Due to this fact, we have also developed non-spiral algorithms. We establish new upper bounds for searching for a point in cones and in conic complements using a single unit-speed agent. Combining the two upper bounds, we designed hybrid strategies that combine spiral and directional search techniques. We demonstrate that the hybrid strategies outperform spiral based search techniques when there are sufficiently slow agents. This implies that spiral search may be suboptimal in a multi speed search setting.