Persistence Search - A New Search Strategy for the Dynamic Shortest Path Problem
Loading...
Authors
Shing, Man-Tak
Mayer, Michael McClanahan
Subjects
persistence search, path planning, maze exploration, dynamic shortest path
Advisors
Date of Issue
1991-04
Date
1991-04
Publisher
Monterey, California. Naval Postgraduate School
Language
eng
Abstract
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
Type
Technical Report
Description
Series/Report No
Department
Computer Science
Identifiers
NPS Report Number
NPS-CS-91-011
Sponsors
Naval Postgraduate School, Department of Computer Science, Code CS
Funder
O&MN, Direct Funding
Format
NA
Citation
Distribution Statement
Approved for public release; distribution is unlimited.