Learning To Navigate on A Graph
.
Learning to Navigate on a Graph.
In IUW, I:789-795, 1994
Online Version
A pdf version is available for download.
Abstract
If a robot has to repeatedly perform navigational tasks in a complex environment, it can improve its performance by "learning" the layout of the environment. This paper is the first of a planned series on navigational applications of learning. It deals with a "street network" environment, modeled by a graph embedded in the plane; and with a "taxi-driver" agent which initially finds a path to its destination, and afterwards tries to find shorter paths to it. For a class of graphs that correspond to planar mazes, we compare several basic search strategies for finding the destination; we show that once it has been reached, a much shorter return path can usually be found; and we also define a simple path-shortening strategy that searches for shortcuts in given paths. Finally, we discuss types of partial information about the environment that might be especially useful to store if the agent has limited memory.
Co-authors
Bibtex Entry
@inproceedings{KhullerRR94i,
title = {Learning to Navigate on a Graph},
author = {Samir Khuller and Ehud Rivlin and Azriel Rosenfeld},
year = {1994},
booktitle = {IUW},
pages = {I:789-795},
abstract = {If a robot has to repeatedly perform navigational tasks in a complex environment, it can improve its performance by "learning" the layout of the environment. This paper is the first of a planned series on navigational applications of learning. It deals with a "street network" environment, modeled by a graph embedded in the plane; and with a "taxi-driver" agent which initially finds a path to its destination, and afterwards tries to find shorter paths to it. For a class of graphs that correspond to planar mazes, we compare several basic search strategies for finding the destination; we show that once it has been reached, a much shorter return path can usually be found; and we also define a simple path-shortening strategy that searches for shortcuts in given paths. Finally, we discuss types of partial information about the environment that might be especially useful to store if the agent has limited memory.}
}