Persistent search: a bridge between depth-first and breadth-first search for physical agents.
Loading...
Authors
Mayer, Michael McClanahan
Subjects
artificial intelligence
search
path planning
complexity analysis
search
path planning
complexity analysis
Advisors
Shing, Man-Tak
Date of Issue
1989-06
Date
June 1989
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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 required by the physical agent attempting to
reach a desired goal location. In order to overcome the failings of these algorithms in
dealing with searches of this particular nature, a new algorithm called persistent search was
created.
Persistent search differs from most other algorithms because it focuses on
minimizing the physical movement of an active agent traversing an unknown search space,
coping with the physical aspects of the problem which are too often ignored. Persistent
search uses several standard search techniques but applies them in such a way as to change
the semantics of the search. An interesting additional property of this algorithm is that
through the manipulation of a single control variable, termed the persistence factor, the
operation of the basic algorithm can be changed to span the continuum of behaviors
between depth-first and breadth-first search.
Type
Thesis
Description
Series/Report No
Department
Computer Science
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funding
Format
69 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.