Persistence search -- a new search strategy for the dynamic shortest path problem
By: Man-Tak Shing, Michael M. Mayer
Contributors: Mayer, Michael McClanahan; Naval Postgraduate School (U.S.). Dept. of Computer Science
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1991
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 35
Subjects: Searching
Other titles: NPS-CS-91-011.
Description: The research reported in this paper deals with the problem of searching through an      unknown terrain by a physical agent such as a robot. The unknown terrain over which the      agent will travel is represented by an undirected graph. The agent has no prior knowledge      of the graph. It can only learn about its environment by physically roaming it. Given a      starting location s, the agent tries to reach a target location t using the minimum amount of      physical movement. This problem, which is a natural generalization of the classical      shortest path problem, will be referred to as the dynamic shortest path problem. Most of      the classical shortest path algorithms perform very poorly in the scenario of a physical      agent traversing an initially unknown search space. They do not attempt to minimize the      amount of physical movement required by the agent to reach the goal location. In order to      overcome the failings of these search algorithms in dealing with searches of this particular      nature, a new search strategy, called persistence search, is developed and presented in      this paper.
Notes: Title from cover.

"NPS-CS-91-011."

"April 1991."

AD A238 741.

Includes bibliographical references (p. 18).

aq/aq cc:9116 06/08/98