Scatter Search on a Disk

Consider a unit disk with two objects at unidentified locations. We examine the problem of two or more robots in search of both objects in the wireless communication model. We begin with two robots and both are needed to carry an object. Subsequently, we design several algorithms that describe robots trajectories in search of the objects. We were able to achieve a minimum worst-case search time of 6.7518 and a lower bound of 3 + π 2 . Additionally, we define two general cases and bound the worst-case search time for both. The first of the cases is for n ≥ 3 robots and an object can be moved by one robot. The second case is where we have n ≥ 3 robots and two robots are needed to carry an object. We achieve an upper bound of 1 + 2π n + sin (⌊n 2 ⌋ π n ) for the first case and an upper bound of 3 + 2π n + sin π n for the second case, with lower bounds of 2 + π n and 3 + π n respectively.