The most popular methods for solving the shortest-path problem in
Artificial Intelligence are heuristic search algorithms. The main
contributions of this research are new heuristic search algorithms
that are either faster or scale up to larger problems than existing
algorithms. Our contributions apply to both online and offline tasks.
For online tasks, existing real-time heuristic search algorithms learn
better informed heuristic values and in some cases eventually converge
to a shortest path by repeatedly executing the action leading to a
successor state with a minimum cost-to-goal estimate. In contrast, we
claim that real-time heuristic search converges faster to a shortest
path when it always selects an action leading to a state with a
minimum f-value, where the f-value of a state is an estimate of the
cost of a shortest path from start to goal via the state, just like in
the offline A* search algorithm. We support this claim by implementing
this new non-trivial action-selection rule in FALCONS and by showing
empirically that FALCONS significantly reduces the number of actions
to convergence of a state-of-the-art real-time search algorithm.
For offline tasks, we improve on two existing ways of scaling up
best-first search to larger problems. First, it is known that the WA*
algorithm (a greedy variant of A*) solves larger problems when it is
either diversified (i.e., when it performs expansions in parallel) or
committed (i.e., when it chooses the state to expand next among a
fixed-size subset of the set of generated but unexpanded states). We
claim that WA* solves even larger problems when it is enhanced with
both diversity and commitment. We support this claim with our MSC-KWA*
algorithm. Second, it is known that breadth-first search solves
larger problems when it prunes unpromising states, resulting in the
beam search algorithm. We claim that beam search quickly solves even
larger problems when it is enhanced with backtracking based on limited
discrepancy search. We support this claim with our BULB algorithm. We
show that both MSC-KWA* and BULB scale up to larger problems than
several state-of-the-art offline search algorithms in three standard
benchmark domains. Finally, we present an anytime variant of BULB and
apply it to the multiple sequence alignment problem in biology.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/4855 |
| Date | 25 November 2004 |
| Creators | Furcy, David Andre |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | 2224191 bytes, application/pdf |
Page generated in 0.0021 seconds