Path planning and navigation for mobile robots, in par-
ticular the case where the environment is known, is a
well studied problem, see, for example, the book by
Latombe [4] and the references therein. In practice,
however, one problem is that often no complete knowl-
edge about the environment is available. Having a de-
tailed map with all the obstacles marked seems to be
unrealistic for most situations. In many outdoor appli-
cations the robots can determine their coordinates by
using, for example, GPS. However the knowledge about
the surroundings may often be very limited. Under such
conditions there is too much uncertainty for a very de-
tailed plan to make sense. For preplanning purposes a
coarser choice is probably good enough. Additionally it
is important to be able to replan the path online based
on new information obtained by sensors while navigat-
ing.
A natural way of updating plans is to first select a path
based on the present knowledge, then move along that
path for a short time while collecting new information.
Based on the new findings the path is then replanned.
This methodology is often used in the literature for path
planning in unknown areas. One of the original moti-


vations for studying this problem was the terrain acqui-
sition problem, where a robot is required to produce a
complete map of an unknown terrain. In many publica-
tions graph methods are used for solving the task. For
example, [6] considers disjoint convex polygonal obsta-
cles and presents proofs on convergence. [5] does not use
any constraint on the shape of the obstacles and tries to
minimize the length of the path during the operation.
In [7] results for more general graphs are presented.
In this paper an online path planning algorithm, based
on the so-called network simplex method, is proposed.
Compared with the aforementioned graph methods, the
information stored about the environment is strictly in-
tended for path planning and less details about the ob-
stacles are needed. Although the algorithm of this pa-
per to some extent is similar to the
D
?
algorithm [8, 9],
the two strategies differ in a number of ways. Firstly,
here a different discretization scheme is used. Instead of
modeling the environment as a set of squares this paper
uses a graph representation. Secondly, while producing
a path from the start to the goal
D
?
has to solve the
shortest path problem for every possible starting point.
The algorithm of this paper does not require these ex-
tra solutions. Here the shortest path problem is thought
of as a minimum cost flow problem and solved by the
network simplex method. Furthermore, in this paper
the feasibility of the algorithm is justified by integrat-
ing it with a generic navigation control strategy, since
the topic here is
online
path planning.
It is worth to mention that as a contrast a completely
different online path planning approach is presented in
[11]. There a path is computed using steepest gradient
descent on an updated harmonic function.
It should be emphasized that in this paper the range of
the sensors is assumed to be limited. A requirement for
the method to work is that the sensing range is longer
than the length of the longest arcs of the graph. I.e. the
lower the sensing range the closer the nodes need to be


placed. In [10] the sensing constraint is relaxed and an
extension of [8, 9] with special box patterns for sparse
environments is presented.
This paper is organized as follows. First the path plan-
ning approach, using network simplex, is presented. A
more general description of the planning approach is
followed by an example where parameter values have
been chosen. Then a navigation controller is described
and integrated with the path planning. Finally simula-
tion results illustrate the performance of the combined
strategy.