Exploiting Parallelism in Constraint Satisfaction for Qualitative Simulation

Marco Platzner (ITI, Graz University of Technology, Austria)

Bernhard Rinner (ITI, Graz University of Technology, Austria)

Reinhold Weiss (ITI, Graz University of Technology, Austria)

Abstract: Constraint satisfaction is very common in many artificial intelligence applications. This paper presents results from parallelizing constraint satisfaction in a special application --- the algorithm for qualitative simulation QSim [Kuipers 94]. A parallel-agent based strategy (PAB) is used to solve the constraint satisfaction problem (CSP). Two essential steps of PAB are studied in more detail to achieve a good performance of the parallel algorithm. Partitioning heuristics to generate independent parts of the overall search space are investigated. Sequential CSP algorithms are compared in order to reveal the most efficient one for QSim. The evaluation of these heuristics and algorithms is based on runtime measurements using CSPs traced from QSim. These runtimes allow a best- and worst-case estimation of the expected speedup of the parallel algorithms. The comparison of sequential CSP algorithms leads to following strategy for solving partitioned problems. Less complex problems are solved with simple backtracking, and more complex models are solved with graph-directed backjumping (GBJ).

Keywords: Parallel constraint satisfaction, QSim, distributed AI

Categories: C.3, F.2.2, I.2.11