Parallel best-first search : optimizing the number of expansions per iteration on slaves

Several classes of problems can be solved by searching a graph. The bestfirst (BF) search algorithm can be used to generate a minimum cost solution. BF search Iteratively selects the best node using heuristic information and then expands the best node. Parallel best-first (BF) search iteratively selects the K best nodes (beam search) where K is the number of processors available. These K nodes are expanded simultaneously (in parallel). The effect of the choice for how many expansions each processor should do per each iteration is investigated through experiments. The effect of different parameters on the optimal choice of number of expansions per iteration (E) is also illustrated. The parameters are number of expansions per iteration, number of slaves, heuristics, computation time (c₁) and communication time(c₂). A simple mathematical model is developed to estimate the computation time per each expansion (c₁) and communication time (c₂). Intuitively, E is directly proportional to communication time. This is discussed and results are presented. Using the traveling salesman problem as a testbed, this thesis investigates the optimal value for E as a function of communication and computation time.