This is a Small Grant for Exploratory Research (SGER) to apply existing techniques in parallel processing to the problem ofplanning with multiple agents. A model is designed which allows a view of the problem as a sequence of interleaved tree search and satisfaction steps. The research investigates various factors influencing the performance of this model when the search and constraint satisfaction are performed on parallel computers. These factors include partitioning the plan generation process among various processors, the nature of various distributed data structures and the effect of ordering heuristics on complexity of search space. The new models developed are implemented and validated on the new generation CM% and the nCUBE2 parallel computers.
