Speeding Up the Convergence of Online Heuristic Search and Scaling Up Offline Heuristic Search

Anytime search algorithms;Beam search;Real-time search;Heuristic search;Multiple sequence alignment

Furcy, David Andre ; Computing

University:Georgia Institute of Technology

Department:Computing

关键词: Anytime search algorithms;    Beam search;    Real-time search;    Heuristic search;    Multiple sequence alignment;   

Others  :  https://smartech.gatech.edu/bitstream/1853/4855/1/furcy_david_a_200412_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

The most popular methods for solving the shortest-path problem inArtificial Intelligence are heuristic search algorithms. The maincontributions of this research are new heuristic search algorithmsthat are either faster or scale up to larger problems than existingalgorithms. Our contributions apply to both online and offline tasks.For online tasks, existing real-time heuristic search algorithms learnbetter informed heuristic values and in some cases eventually convergeto a shortest path by repeatedly executing the action leading to asuccessor state with a minimum cost-to-goal estimate. In contrast, weclaim that real-time heuristic search converges faster to a shortestpath when it always selects an action leading to a state with aminimum f-value, where the f-value of a state is an estimate of thecost of a shortest path from start to goal via the state, just like inthe offline A* search algorithm. We support this claim by implementingthis new non-trivial action-selection rule in FALCONS and by showingempirically that FALCONS significantly reduces the number of actionsto convergence of a state-of-the-art real-time search algorithm.For offline tasks, we improve on two existing ways of scaling upbest-first search to larger problems. First, it is known that the WA*algorithm (a greedy variant of A*) solves larger problems when it iseither diversified (i.e., when it performs expansions in parallel) orcommitted (i.e., when it chooses the state to expand next among afixed-size subset of the set of generated but unexpanded states). Weclaim that WA* solves even larger problems when it is enhanced withboth diversity and commitment. We support this claim with our MSC-KWA*algorithm.Second, it is known that breadth-first search solveslarger problems when it prunes unpromising states, resulting in thebeam search algorithm. We claim that beam search quickly solves evenlarger problems when it is enhanced with backtracking based on limiteddiscrepancy search. We support this claim with our BULB algorithm. Weshow that both MSC-KWA* and BULB scale up to larger problems thanseveral state-of-the-art offline search algorithms in three standardbenchmark domains. Finally, we present an anytime variant of BULB andapply it to the multiple sequence alignment problem in biology.