Improving Reasoning in Constraint Logic Programming: an Application to Route Planning and Qualitative Temporal Reasoning Problems

La programmazione (logica) a vincoli (Constraint Logic Programming (CLP)) è un paradigma di programmazione nato per risolvere problemi di soddisfacimento di vincoli (Constraint Satisfaction Problem (CSP)) e problemi di ottimizzazione vincolata (Constraint Optimization Problem (COP)) in intelligenza artificiale. Le tecniche di risoluzione per i problemi di soddisfacimento di vincoli, dette anche di constraint reasoning, possono essere suddivise in due strategie distinte e ortogonali: inferenza (detta anche “propagazione dei vincoli”) e ricerca nello spazio degli stati. L’obiettivo della ricerca presentata in questa tesi è quello di sviluppare algoritmi di constraint reasoning per due popolari domini applicativi: la pianificazione dei percorsi dei veicoli e il ragionamento temporale qualitativo. Per quanto riguarda i problemi di pianificazione dei percorsi dei veicoli, studieremo il problema del commesso viaggiatore euclideo (Euclidean Traveling Salesperson Problem (ETSP)), un caso speciale del più noto problema del commesso viaggiatore (Traveling Salesperson Problem (TSP)). Molte istanze di problemi reali appartengono alla sottoclasse dell’ETSP, in cui i nodi da visitare sono punti nel piano euclideo, e la distanza tra loro è la distanza euclidea. L’approccio più comune in CLP per risolvere l’ETSP è quello di costruire una matrice di distanza, e poi affrontare il problema in modo più generale come un TSP. Invece, in questo lavoro proponiamo di utilizzare le informazioni geometriche, presenti nelle istanze dell’ETSP, per migliorare la propagazione dei vincoli. Applichiamo anche tecniche di apprendimento automatico (foreste casuali, reti neurali) con l’obiettivo di imporre solo il sottoinsieme più efficiente di vincoli per aumentare le prestazioni globali di risoluzione. Il ragionamento temporale qualitativo, d’altra parte, è un’area che ha notevolmente beneficiato delle tecniche di programmazione a vincoli da quando James F. Allen ha proposto un’algebra, nel 1983, che in seguito è diventata nota come Allen’s Interval Algebra (IA). Quando i vincoli di un problema riguardano le relazioni temporali tra eventi, il problema viene definito CSP temporale. La Branching Interval Algebra (BA) è la naturale generalizzazione della IA in cui il tempo non è più rappresentato come una linea retta ma piuttosto come un albero che può ramificarsi nel futuro. Anche BA ha molte potenziali applicazioni in diverse aree dell’intelligenza artificiale; ma sfortunatamente, il problema di coerenza dei CSP temporali espressi in BA è NP-difficile, come nel caso lineare. Per poter risolvere il problema di coerenza in modo efficiente, un approccio consiste nello sfruttare i frammenti trattabili dell’algebra. In questa tesi viene presentato uno studio sulla trattabilità di alcuni frammenti di BA e viene proposta una versione migliorata di un algoritmo di ricerca che sfruttando tali frammenti trattabili è in grado di ottenere migliori prestazioni computazionali.

Constraint (Logic) Programming (CLP) is a popular paradigm to deal with Constraint Satisfaction Problems (CSPs) and Constraint Optimization Problems (COPs) in artificial intelligence. Constraint solving techniques, also known as constraint reasoning algorithms, can be divided into two distinct and orthogonal strategies: inference (or constraint propagation) and search. In this research we address constraint reasoning algorithms for two popular application domains: vehicle route planning and qualitative temporal reasoning. Regarding vehicle route planning, we study the Euclidean TSP (ETSP), a special case of the better known Traveling Salesperson Problem (TSP). Many real-life instances belong to the subclass of ETSP, where more information is available than in the general TSP: the nodes to be visited are points in the Euclidean plane, and the distance between them is the Euclidean distance. The usual approach in constraint programming to solve the ETSP is to build a distance matrix, and then address the problem as a general TSP. Instead, in this work we propose to use geometric information, present in Euclidean TSP instances, to improve constraint propagation. We also apply machine learning techniques (random forests, neural networks) with the aim of imposing only the most efficient subset of constraints to increase overall solving performance. Qualitative temporal reasoning, on the other hand, is an area that has greatly benefited from constraint programming techniques since James F. Allen proposed an algebra, in 1983, that later became known as Allen’s Interval Algebra (IA). When the constraints of a problem concern the temporal relations between events, the problem is identified as temporal CSP. Branching Interval Algebra (BA) is the natural branching-time generalization of IA where time is no longer seen as a straight line but rather as a tree that can branch in the future. BA also has many potential applications in different areas of artificial intelligence; but unfortunately, the consistency problem of temporal CSPs expressed in BA is NP-hard, as in the linear case. In order to be able to solve the consistency problem efficiently, one approach consists of exploiting the tractable fragments of the algebra. Here, we develop algorithms to study tractability of BA fragments and then we propose an enhanced version of a search algorithm exploiting such tractable fragments to improve its computational performance.