Artificial Intelligence/Search/Heuristic search/Beam search

Definition

Beam search is a restricted, or modified, version of either a breadth-first search or a best-first search. It is restricted in the sense that the amount of memory available for storing the set of alternative search nodes is limited, and in the sense that non-promising nodes can be pruned at any step in the search (Zhang, 1999). The pruning of non-promising nodes is determined by problem-specific heuristics (Zhang, 1999). The set of most promising, or best alternative, search nodes is called the “beam” (Xu and Fern, 2007). Essentially, beam search is a forward-pruning, heuristic search.

Search Components and Algorithm

A beam search takes three components as its input: a problem to be solved, a set of heuristic rules for pruning, and a memory with a limited available capacity (Zhang, 1999). The problem is the problem to be solved, usually represented as a graph, and contains a set of nodes in which one or more of the nodes represents a goal. The set of heuristic rules are rules specific to the problem domain and prune unfavourable nodes from the memory in respect to the problem domain. The memory is where the “beam” is stored, where when memory is full and a node is to be added to the beam, the most costly node will be deleted, such that the memory limit is not exceeded.

The following algorithm for a beam search, as a modified best-first search, is adapted from Zhang’s 1999:

beamSearch(problemSet, ruleSet, memorySize)
     openMemory = new memory of size memorySize
     nodeList = problemSet.listOfNodes
     node = root or initial search node
     Add node to openMemory;
     while (node is not a goal node)
          Delete node from openMemory;
          Expand node and obtain its children, evaluate those children;
          If a child node is pruned according to a rule in ruleSet, delete it;
          Place remaining, non-pruned children into openMemory;
          If memory is full and has no room for new nodes, remove the worst
              node, determined by ruleSet, in openMemory;
          node = the least costly node in openMemory;

Advantages, Disadvantages, and Practical Applications

Beam search has the advantage of potentially reducing the computation, and hence the time, of a search (Xu and Fern, 2007). As well, the memory consumption of the search is far less than its underlying search methods (Furcy and Koenig). This potential advantage rests upon the accuracy and effectiveness of the heuristic rules used for pruning, and having such rules can be somewhat difficult due to the expert knowledge required of the problem domain (Zhang, 1999). The main disadvantages of a beam search are that the search may not result in an optimal goal and may not even reach a goal at all. In fact, the beam search algorithm terminates for two cases: a required goal node is reached, or a goal node is not reached and there are no nodes left to be explored (Zhang, 1999). Beam search has the potential to be incomplete. Despite these disadvantages, beam search has found success in the practical areas of speech recognition, vision, planning, and machine learning (Zhang, 1999).

References

• Zhang, W. (1999). State-space search: Algorithms, complexity, extensions, and applications. Springer: New York.
• Xu, Y., Fern, A. (2007). On learning linear ranking functions for beam search. Retrieved on March 8, 2009, from http://www.machinelearning.org/proceedings/icml2007/papers/168.pdf
• Furcy, D., Koenig, S. Limited discrepancy beam search. Retrieved on March 8, 2009, from http://www.ijcai.org/papers/0596.pdf