Approximate Search Methods
Approximate search applies modifications to the search processes that address the problem of limited computational and/or time resources at the cost of producing plans that might be sub-optimal or that might not always reliable lead to a goal state.
Examples of Approximate Search Methods
-
Island-driven search
-
Hierarchical search
-
Limited-horizon search
-
Real time A* search
-
Building reactive procedures
Reducing the Computational Costs
The computational costs associated with graph search algorithms may be alleviated to some extent by considering the following options:
-
Searching for a complete path to a goal node without requiring that it be optimal.
-
Relaxing the requirement of producing optimal plans often reduces the computational cost of a finding a plan.
-
-
Searching for a partial path that does not take us all the way to a goal node.
-
Anytime algorithm [Dean and Boddy, 1988][Hornitz, 1998] can be used to work in both the methods
-
Discontinuing search before reaching the goal is an example of anytime algorithm.
-
Anytime algorithms are the ones that can be stopped at any time; the quality of the result generally improves with larger running time.
-
Island-Driven Search
In Island-driven search, heuristic knowledge from the problem domain is used to establish a sequence of "island nodes" in the search space through which it is suspected that good paths pass.
This search strategy divides a larger space into smaller, more manageable subspaces, called "islands".
Each island represents a separate search path or sub-population in the context of EAs or parallel search techniques.
The search process is then conducted on these islands independently, but periodic information exchange between then occurs to promote exploration across the whole search space.
Algorithm
Let:
-
\(n_0 \rightarrow\) start node
-
\(n_g \rightarrow\) goal node
-
\(n_1, n_2, \ldots, n_k \rightarrow\) sequence of islands
Steps:
-
With \(n_0\) as the start node and \(n_1\) as the goal node (usually heuristic function approximate for that goal), initiate a heuristic search.
-
When the search finds a path to \(n_1\), start another search with \(n_1\) as the start node and so on until a path to \(n_g\) is found.