A geometric constraint over k-dimensional objects and shapes subject to business rules
Number of Authors: 3
2008 (English)Report (Other academic)
This report presents a global constraint that enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are compiled to generators of k-dimensional forbidden sets. Such generators are a generalization of the indexicals of cc(FD). Finally, the forbidden sets generated by such indexicals are aggregated by a sweep-based algorithm and used for filtering. The business rules allow to express a great variety of packing and placement constraints, while admitting efficient and effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures. The constraint was used to directly encode the packing knowledge of a major car manufacturer and tested on a set of real packing problems under these rules, as well as on a packing-unpacking problem.
Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2008, 1. , 37 p.
SICS Technical Report, ISSN 1100-3154 ; 2008:04
Global Constraint, Geometric Constraint, Rule, Sweep, Quantifier-Free Presburger Arithmetic
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22488OAI: oai:DiVA.org:ri-22488DiVA: diva2:1042053