Processing...

### An on-line algorithm for improving performance in navigation

**1994-09-21**

9409224 | math.CO

Recent papers have shown optimally-competitive on-line strategies for a robot
traveling from a point $s$ to a point $t$ in certain unknown geometric
environments. We consider the question: Having gained some partial information
about the scene on its first trip from $s$ to $t$, can the robot improve its
performance on subsequent trips it might make? This is a type of on-line
problem where a strategy must exploit {\em partial information \/} about the
future (e.g., about obstacles that lie ahead). For scenes with axis-parallel
rectangular obstacles where the Euclidean distance between $s$ and $t$ is $n$,
we present a deterministic algorithm whose {\em average\/} trip length after
$k$ trips, $k \leq n$, is $O(\rootnbyk)$ times the length of the shortest
$s$-$t$ path in the scene. We also show that this is the best a deterministic
strategy can do. This algorithm can be thought of as performing an optimal
tradeoff between search effort and the goodness of the path found. We improve
this algorithm so that for {\em every\/} $i \leq n$, the robot's $i$th trip
length is $O(\rootnbyi)$ times the shortest $s$-$t$ path length. A key idea of
the paper is that a {\em tree\/} structure can be defined in the scene, where
the nodes are portions of certain obstacles and the edges are ``short'' paths
from a node to its children. The core of our algorithms is an on-line strategy
for traversing this tree optimally.

**Login to like/save this paper, take notes and configure your recommendations**