  We consider three related problems of robot movement in arbitrary dimensions:
coverage, search, and navigation. For each problem, a spherical robot is asked
to accomplish a motion-related task in an unknown environment whose geometry is
learned by the robot during navigation. The robot is assumed to have tactile
and global positioning sensors. We view these problems from the perspective of
(non-linear) competitiveness as defined by Gabriely and Rimon. We first show
that in 3 dimensions and higher, there is no upper bound on competitiveness:
every online algorithm can do arbitrarily badly compared to the optimal. We
then modify the problems by assuming a fixed clearance parameter. We are able
to give optimally competitive algorithms under this assumption.
