Best-first heuristic search is the cornerstone of many AI applications, the success of which often depend on the effectiveness and efficiency of their search engines. SYNCHEM, a well-established problem-solving system for organic synthesis route discovery, is such an application. With an anticipated tenfold increase in SYNCHEM's knowledge base (and a comparable increase in the branching factor), the already large search space is expected to mushroom. Without a corresponding improvement in the power of the search engine, this increase in SYNCHEM's knowledge of the domain will have been in vain. We, therefore, have begun to explore methods of distributing SYNCHEM's heuristic search engine over a network of workstations.
In this talk, I will briefly describe the sequential version of SYNCHEM's search algorithm and discuss possible models for distributing the algorithm in terms of the overall goals we would like to achieve. I will then describe the model we adopted and its implementation, and report some of our experimental results. Raw speedup and response time are two measures of the success of a distributed algorithm, but they are not the only ones. Just as important for heuristic search is the quality of the search. So, to conclude the talk I will discuss ways of measuring that quality, and possible improvements in the ``best-first'' nature of our distributed search algorithm.