When trying to develop a good search strategy, we have to balance theoretical quality with practical applicability. More precisely, we have to keep a close eye on the trade-off between these objectives: An increase in theoretical quality may come at the expense of higher mathematical difficulty, possibly requiring more complicated tools. In an online context, the use of such tools may cause both theoretical and practical difficulties: Complicated solutions may cause computational overhead that can change the solution itself by causing extra delay; on the practical side, actually applying such a solution may be difficult (due to limited accuracy of the robot's motion) and without significant use. To put relevant error bounds into perspective: The largest room available to us is the great hall of Schloss Birlinghoven; even there, the size of Kurt and the object is still in the order of 2% of the room diameter.
On the mathematical side, it should be noted that even in the theoretical paper [7], semi-circles are considered instead of the solution to the differential equation, in order to allow analysis of the resulting trajectories.
In the following, we will start by giving some basic mathematical observations and properties (Section 3.1); this is followed by a discussion of globally optimal strategies (Section 3.2). Section 3.3 describes a natural heuristic solution that is both easy to describe and fast to evaluate; we give a number of computational and empirical results that suggest our heuristic is within 2% of an optimal strategy. Finally, Section 3.4 provides a number of mathematical results, showing that our fast and easy heuristic is asymptotically optimal.