Solving set constraint satisfaction problems using ROBDDS
Author
Hawkins, P; Lagoon, V; Stuckey, PJDate
2005-01-01Source Title
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCHPublisher
AI ACCESS FOUNDATIONAffiliation
Computer Science and Software EngineeringMetadata
Show full item recordDocument Type
Journal ArticleCitations
Hawkins, P., Lagoon, V. & Stuckey, P. J. (2005). Solving set constraint satisfaction problems using ROBDDS. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 24, pp.109-156. https://doi.org/10.1613/jair.1638.Access Status
This item is currently not available from this repositoryAbstract
<jats:p>In this paper we present a new approach to modeling finite set domain constraint problems using Reduced Ordered Binary Decision Diagrams (ROBDDs). We show that it is possible to construct an efficient set domain propagator which compactly represents many set domains and set constraints using ROBDDs. We demonstrate that the ROBDD-based approach provides unprecedented flexibility in modeling constraint satisfaction problems, leading to performance improvements. We also show that the ROBDD-based modeling approach can be extended to the modeling of integer and multiset constraint problems in a straightforward manner. Since domain propagation is not always practical, we also show how to incorporate less strict consistency notions into the ROBDD framework, such as set bounds, cardinality bounds and lexicographic bounds consistency. Finally, we present experimental results that demonstrate the ROBDD-based solver performs better than various more conventional constraint solvers on several standard set constraint problems.</jats:p>
Keywords
Artificial Intelligence and Image ProcessingExport Reference in RIS Format
Endnote
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
Refworks
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References