License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2020.12
URN: urn:nbn:de:0030-drops-129802
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12980/
Sioutis, Michael ;
Wolter, Diedrich
Dynamic Branching in Qualitative Constraint Networks via Counting Local Models
Abstract
We introduce and evaluate dynamic branching strategies for solving Qualitative Constraint Networks (QCNs), which are networks that are mostly used to represent and reason about spatial and temporal information via the use of simple qualitative relations, e.g., a constraint can be "Task A is scheduled after or during Task C". In qualitative constraint-based reasoning, the state-of-the-art approach to tackle a given QCN consists in employing a backtracking algorithm, where the branching decisions during search are governed by the restrictiveness of the possible relations for a given constraint (e.g., after can be more restrictive than during). In the literature, that restrictiveness is defined a priori by means of static weights that are precomputed and associated with the relations of a given calculus, without any regard to the particulars of a given network instance of that calculus, such as its structure. In this paper, we address this limitation by proposing heuristics that dynamically associate a weight with a relation, based on the count of local models (or local scenarios) that the relation is involved with in a given QCN; these models are local in that they focus on triples of variables instead of the entire QCN. Therefore, our approach is adaptive and seeks to make branching decisions that preserve most of the solutions by determining what proportion of local solutions agree with that decision. Experimental results with a random and a structured dataset of QCNs of Interval Algebra show that it is possible to achieve up to 5 times better performance for structured instances, whilst maintaining non-negligible gains of around 20% for random ones.
BibTeX - Entry
@InProceedings{sioutis_et_al:LIPIcs:2020:12980,
author = {Michael Sioutis and Diedrich Wolter},
title = {{Dynamic Branching in Qualitative Constraint Networks via Counting Local Models}},
booktitle = {27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
pages = {12:1--12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-167-2},
ISSN = {1868-8969},
year = {2020},
volume = {178},
editor = {Emilio Mu{\~n}oz-Velasco and Ana Ozaki and Martin Theobald},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12980},
URN = {urn:nbn:de:0030-drops-129802},
doi = {10.4230/LIPIcs.TIME.2020.12},
annote = {Keywords: Qualitative constraints, spatial and temporal reasoning, counting local models, dynamic branching, adaptive algorithm}
}
|
Keywords: |
|
Qualitative constraints, spatial and temporal reasoning, counting local models, dynamic branching, adaptive algorithm |
|
Collection: |
|
27th International Symposium on Temporal Representation and Reasoning (TIME 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
15.09.2020 |
