The Marco Polo Problem: A Combinatorial Approach to Geometric Localization

We introduce and study the Marco Polo problem, which is a combinatorial approach to geometric localization. In this problem, we are told there are one or more points of interest (POIs) within distance $n$ of the origin that we wish to localize. Given a mobile search point, $\Delta$, that is initially at the origin, a localization algorithm is a strategy to move $\Delta$ to be within a distance of $1$ of a POI. In the combinatorial localization problem we study, the only tool we can use is reminiscent of the children's game, "Marco Polo," in that $\Delta$ can issue a probe signal out a specified distance, $d$, and the search algorithm learns whether or not there is a POI within distance $d$ of $\Delta$. For example, we could imagine that POIs are one or more hikers lost in a forest and we need to design a search-and-rescue (SAR) strategy to find them using radio signal probes to a response device that hikers carry. Unlike other known localization algorithms, probe responses do not inform our search algorithm of the direction or distance to a POI. The optimization problem is to minimize the number of probes and/or POI responses, as well as possibly minimizing the distance traveled by $\Delta$. We describe a number of efficient combinatorial Marco Polo localization strategies and we analyze each one in terms of the size, $n$, of the search domain. Moreover, we derive strong bounds for the constant factors for the search costs for our algorithms, which in some cases involve computer-assisted proofs. We also show how to extend these strategies to find all POIs using a simple, memoryless search algorithm, traveling a distance that is $\mathcal{O}(\log{k})$-competitive with the optimal traveling salesperson (TSP) tour for $k$ POIs.