Persistence Search - A New Search Strategy for the Dynamic Shortest Path Problem
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
NPS Report Number
NPS-CS-91-011Related items
Showing items related by title, author, creator and subject.
-
Persistent search: a bridge between depth-first and breadth-first search for physical agents.
Mayer, Michael McClanahan (Monterey, California. Naval Postgraduate School, 1989-06);Current search algorithms and heuristics perform very poorly in the highly realistic scenario of a physical agent traversing an initially unknown search space. They do not attempt to minimize the amount of movement ... -
Genetic algorithms for the development of real-time multi-heuristic search strategies
Parker, Gary B. (Monterey, California. Naval Postgraduate School, 1992-09);Search of an unknown space by a physical agent (such as an autonomous vehicle) is unique in search as the customarily most important goal (to reduce the computation time required to obtain the shortest distance) is not as ... -
Homeland Security Affairs Journal, Supplement - 2012: IEEE 2011 Conference on Technology for Homeland Security: Best Papers
Naval Postgraduate School Center for Homeland Defense and Security (CHDS) (Monterey, California. Naval Postgraduate SchoolCenter for Homeland Defense and Security, 2012);IEEE Supplement 2012. Supplement: IEEE 2011 Conference on Technology for Homeland Security: Best Papers. As the field of homeland defense and security expands and matures, the contributions from various disciplines become ...