no obstacles so no dilemma of local information vs knowledge of global geometry \cite{sali}
Still, however, tasks are extremely hard. 
We expect these two tasks work as good benchmarks  
In their article Knaden \& Wehner wrote 
"Desert ants use path integration as their predominant system of long-distance navigation, 
but they also make use of route-defining ...
the ants ... inside the nest are able to reset the path integrator to zero state. 
... 
In Tunisia they experimented with real ants and observed
"ants had reset their home vector to zero state, 
and had therefore been able to reload their learned feeder vector, 
and consequently departed from the nest in the feeder direction." 



[4] S. Aaronson and A. Ambainis, Quantum search of spatial regions
Proc. 44th IEEE Symposium
on Foundations of Computer Science, 200--209 (2003).

d-dimensional hypercube in time 
$O(\sqrt{n})$ for $d \ge 3$
$O\left( \sqrt {n \log^5 n}\right)$ for d = 2



, 2003. quant-ph/0303041. ? S. Aaronson. Quantum certificate complexity, Proceedings of IEEE Conference on Computational. Complexity, pp. ...
www.scottaaronson.com/vita.pdf  




\bibitem{knad}
Markus Knaden and Rudiger Wehner (2006)
Ant navigation: resetting the path integrator 
Journal of Experimental Biology 209, pp. 26--31.

[5] M.A. Salichs and L. Moreno. gNavigation of Mobile Robots: Open Questionsh,
Robotica, Vol. 18, pp. 227-234, Cambridge University Press, 2000. 6


Abstract
This survey paper is focused on the navigation of mobile robots. The most important associated problems and the solutions given by different researchers are discussed. Several aspects are not yet satisfactorily resolved and some promising research approaches are addressed.