Anytime Heuristic Search

Details Anytime Heuristic Search Anytime Heuristic Search

2011-10-12

arxiv.org/abs/1110.2737v1

Journal Of Artificial Intelligence Research, Volume 28, pages 267-297, 2007

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.2096

We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.

Affiliated with

Also associated with

No associations

Rating

Anytime Heuristic Search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Anytime Heuristic Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Anytime Heuristic Search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-634483