JUCS - Journal of Universal Computer Science 1(12): 811-820, doi: 10.3217/jucs-001-12-0811
Exploiting Parallelism in Constraint Satisfaction for Qualitative Simulation
expand article infoMarco Platzner‡, Bernhard Rinner‡, Reinhold Weiss‡
‡ ITI, Graz University of Technology, Austria

Corresponding author: Marco Platzner ( marco@iti.tu-graz.ac.at )

© Marco Platzner, Bernhard Rinner, Reinhold Weiss.
This article is freely available under the J.UCS Open Content License.
Citation: Platzner M, Rinner B, Weiss R (1995) Exploiting Parallelism in Constraint Satisfaction for Qualitative Simulation. JUCS - Journal of Universal Computer Science 1(12): 811-820. https://doi.org/10.3217/jucs-001-12-0811
Open Access
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