The Multi-source Beachcombers’ Problem

The Beachcombers’ Problem (c.f. [1]) is an optimization problem in which a line segment is to be searched by a set of mobile robots, where each robot has a searching speed \(s_i\) and a walking speed \(w_i\), such that \(s_i < w_i\). We explore a natural generalization of the Beachcombers’ Problem, the \(t\)-Source Beachcombers’ Problem (\(t\)-SBP), where the robots are not constrained to start at a single source: Consider \(n\) mobile robots labelled \(1,2,\ldots , n\). We choose \(t\) sources and we assign each robot to one of them. The problem is to choose the sources and develop mobility schedules (algorithms) for the robots which maximizes the speed of the fleet, or minimize the time that the robots need to collectively search the domain. We propose several algorithms for solving problems of this nature. We prove that \(2\)-SBP is NP-hard even when the robots have identical walking speeds. This contrasts with the case when the robots have identical search speeds, where we give a polynomial time algorithm for \(t\)-SBP. We also give a \(0.5569\)-approximation for \(2\)-SBP with arbitrary walking and searching speeds. For \(t\)-SBP with arbitrary walking and searching speeds, we give an oblivious randomized algorithm and prove that it provides an expected \(1 - 1/e\) approximation, asymptotically in \(t\).