TY - GEN
T1 - Set-theoretic duality
T2 - 21st European Conference on Artificial Intelligence, ECAI 2014
AU - Slaney, John
N1 - Publisher Copyright:
© 2014 The Authors and IOS Press.
PY - 2014
Y1 - 2014
N2 - The duality between conflicts and diagnoses in the field of diagnosis, or between plans and landmarks in the field of planning, or between unsatisfiable cores and minimal co-satisfiable sets in SAT or CSP solving, has been known for many years. Recent work in these communities (Davies and Bacchus, CP 2011, Bonet and Helmert, ECAI 2010, Haslum et al., ICAPS 2012, Stern et al., AAAI 2012) has brought it to the fore as a topic of current interest. The present paper lays out the set-theoretic basis of the concept, and introduces a generic implementation of an algorithm based on it. This algorithm provides a method for converting decision procedures into optimisation ones across a wide range of applications without the need to rewrite the decision procedure implementations. Initial experimental validation shows good performance on a number of benchmark problems from AI planning.
AB - The duality between conflicts and diagnoses in the field of diagnosis, or between plans and landmarks in the field of planning, or between unsatisfiable cores and minimal co-satisfiable sets in SAT or CSP solving, has been known for many years. Recent work in these communities (Davies and Bacchus, CP 2011, Bonet and Helmert, ECAI 2010, Haslum et al., ICAPS 2012, Stern et al., AAAI 2012) has brought it to the fore as a topic of current interest. The present paper lays out the set-theoretic basis of the concept, and introduces a generic implementation of an algorithm based on it. This algorithm provides a method for converting decision procedures into optimisation ones across a wide range of applications without the need to rewrite the decision procedure implementations. Initial experimental validation shows good performance on a number of benchmark problems from AI planning.
UR - http://www.scopus.com/inward/record.url?scp=84923169093&partnerID=8YFLogxK
U2 - 10.3233/978-1-61499-419-0-843
DO - 10.3233/978-1-61499-419-0-843
M3 - Conference contribution
T3 - Frontiers in Artificial Intelligence and Applications
SP - 843
EP - 848
BT - ECAI 2014 - 21st European Conference on Artificial Intelligence, Including Prestigious Applications of Intelligent Systems, PAIS 2014, Proceedings
A2 - Schaub, Torsten
A2 - Friedrich, Gerhard
A2 - O'Sullivan, Barry
PB - IOS Press BV
Y2 - 18 August 2014 through 22 August 2014
ER -