Constraint-based and SAT-based diagnosis of automotive configuration problems
| Autor: | Rouven Walter, Wolfgang Küchlin, Alexander Felfernig |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Computer Networks and Communications business.industry Computer science Automotive industry Minimum weight Context (language use) 0102 computer and information sciences 02 engineering and technology User requirements document 01 natural sciences Constraint (information theory) Set (abstract data type) Knowledge-based systems 010201 computation theory & mathematics Artificial Intelligence Hardware and Architecture 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing business Greedy algorithm Software Information Systems |
| Zdroj: | Journal of Intelligent Information Systems |
| ISSN: | 0925-9902 |
| DOI: | 10.1007/s10844-016-0422-7 |
| Popis: | We compare the concepts and computation of optimized diagnoses in the context of Boolean constraint based knowledge systems of automotive configuration, namely the preferred minimal diagnosis and the minimum weighted diagnosis. In order to restore the consistency of an over-constrained system w.r.t. a strict total order of the user requirements, the preferred minimal diagnosis tries to keep the most preferred user requirements and can be computed, for example, by the FASTDIAG algorithm. In contrast, partial weighted MinUNSAT solvers aim to find a set of unsatisfied clauses with the minimum sum of weights, such that the diagnosis is of minimum weight. It turns out that both concepts have similarities, i.e., both deliver an optimal minimal correction subset. We show use cases from automotive configuration where optimized diagnoses are desired. We point out theoretical commonalities and prove the reducibility of both concepts to each other, i.e., both problems are FPNP-complete, which was an open question. In addition to exact algorithms we present greedy algorithms. We evaluate the performance of exact and greedy algorithms on problem instances based on real automotive configuration data from three different German car manufacturers, and we compare the time and quality tradeoff. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink