University of Regina (CANADA)
CADP (Construction and Analysis of Distributed Processes)
17 data types (500 lines of LOTOS)
Solving a CSP (constraint satisfaction problem) consists in computing
for a set of variables (defined on finite domains) an assignment that
respects a set of constraints. This case study describes the use of
LOTOS and CADP for CSP solving.
The basic idea is to represent the constraints in the data type part of LOTOS, so that the process part of LOTOS corresponds to the process of solving the CSP. In this way, the same LOTOS specification can be used to address different aspects of a CSP. First, the CSP is consistent if the LOTOS specification contains no deadlock. Second, simulation (respectively state space generation) corresponds to the generation of one solution (respectively all possible solutions).
To reduce the execution time of the state space generation, the C code generated by CAESAR.ADT for the data type part of the LOTOS specification is combined with an external library, providing implementations of dedicated constraint propagation algorithms, such as arc consistency. Using this combination, the execution time is significantly reduced: in the 29-queens example, state space generation time is reduced by a factor of almost three.
The combination of the C code generated for LOTOS data types with
dedicated alogrithms for constraint propagation allows to
significantly reduce the execution time of the state space
The authors also note the quality of the code generated by CAESAR.ADT:
M. Mouhoub and S. Sadaoui.
"Improving Lotos Simulation Using Constraint Propagation". In
Proceedings of the 17th IEEE International Conference on Tools with
Artificial Intelligence ICTAI'05 (Hong-Kong), December 2005.
Available on-line from our FTP site in PDF or PostScript
Dr. Samira Sadaoui-Mouhoub
Department of Computer Science
University of Regina
3737 Wascana Parkway
Regina, SK S4S 0A2
Tel: +1 306-337-2340
Fax: +1 306-585-4745
|Further remarks:||This case study, amongst others, is described on the CADP Web site: http://cadp.inria.fr/case-studies|