Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
3.7.5.2 Island-Driven Search
One of the ways that search may be made more efficient is to identify a limited number of places where the forward search and backward search can meet. For example, in searching for a path from two rooms on different floors, it may be appropriate to constrain the search to first go to the elevator on one level, then to the elevator on the goal level. Intuitively, these designated positions are islands in the search graph, which are constrained to be on a solution path from the start node to a goal node.
When islands are specified, an agent can decompose the search problem into several search problems, for example, one from the initial room to the elevator, one from the elevator on one level to the elevator on the other level, and one from the elevator to the destination room. This reduces the search space by having three simpler problems to solve. Having smaller problems helps to reduce the combinatorial explosion of large searches and is an example of how extra knowledge about a problem can be used to improve efficiency of search.
To find a path between s and g using islands:
- Identify a set of islands i0,..., ik;
- Find paths from s to i0, from ij-1 to ij for each j from 1 to k, and from ik to g.
Each of these searching problems should be correspondingly simpler than the general problem and therefore easier to solve.
The identification of islands is extra knowledge which may be beyond that which is in the graph. The use of inappropriate islands may make the problem more difficult (or even impossible to solve). It may also be possible to identify an alternate decomposition of the problem by choosing a different set of islands and search through the space of possible islands. Whether this works in practice depends on the details of the problem.
