Towards an Efficient SAT Encoding for Temporal Reasoning

File Size Format
40653.pdf 191Kb Adobe PDF View
Title Towards an Efficient SAT Encoding for Temporal Reasoning
Author Pham, Duc Nghia; Thornton, John; Sattar, Abdul
Publication Title Principles and Practice of Constraint Programming - CP 2006
Editor Frédéric Benhamou
Year Published 2006
Place of publication Berlin
Publisher Springer-Verlag
Abstract In this paper, we investigate how an IA network can be effectively encoded into the SAT domain.We propose two basic approaches to modelling an IA network as a CSP: one represents the relations between intervals as variables and the other represents the relations between end-points of intervals as variables. By combining these two approaches with three different SAT encoding schemes, we produced six encoding schemes for converting IA to SAT. These encodings were empirically studied using randomly generated IA problems of sizes ranging from 20 to 100 nodes. A general conclusion we draw from these experimental results is that encoding IA into SAT produces better results than existing approaches. Further, we observe that the phase transition region maps directly from the IA encoding to each SAT encoding, but, surprisingly, the location of the hard region varies according to the encoding scheme. Our results also show a fixed performance ranking order over the various encoding schemes.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-173681505-0
Copyright Statement Copyright 2006 Springer. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. The original publication is available at www.springerlink.com
ISBN 3-540-46267-8
Conference name 12th International Conference on the Principles and Practice of Constraint Programming (CP 2006)
Location Nantes, France
Date From 2006-09-24
Date To 2006-09-29
URI http://hdl.handle.net/10072/13101
Date Accessioned 2007-03-09
Date Available 2007-09-26T06:04:02Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Engineering and Information Technology
Subject Other Artificial Intelligence
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Brief Record

Griffith University copyright notice