Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

#### 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
*i*;_{0},..., i_{k} - Find paths from
*s*to*i*, from_{0}*i*to_{j-1}*i*for each_{j}*j*from*1*to*k*, and from*i*to_{k}*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.