Constraint Programming and Planning, A.A. 2014/2015
Orario
LUN 8.30-10.15 aula N
MAR 8.30-10.15 aula N
Programma Svolto
29/09.
Introduzione al corso. CSP/COP e loro
sostanziale equivalenza. NP hardness di semplici CSP.
Spazio e alberi di ricerca. Tecniche naive di ricerca.
(LUCIDI)
Applicazioni del constraint programming.
30/09.
Implementazione delle tecniche naive di ricerca in Prolog
(codice).
Tecniche (note) per risolvere CSP e COP.
Local search, e (Integer) Linear Programming
(LUCIDI)
SAT per risolvere CSP
(LUCIDI).
06/10. Turing completezza di Prolog e limiti di ASP.
ASP per codificare CSP.
Constraint Solver.
(LUCIDI).
Risolutori completi ed incompleti.
Regole di risoluzione: domain reduction, transformation e
introduction.
Derivazioni e constraint propagation.
Node consistency, e Arc consistency.
07/10.
Bounds Consistency. Directional Arc/Bounds Consistency.
Hyperarc (e Bounds) consistency.
Path Consistency.
Cenni ai vincoli globali.
Alberi di ricerca: prop labeling trees.
Esempi ed effetti della scelta delle
variabili sulle dimensioni degli alberi di ricerca.
Constraint Programming (vari formalismi).
(LUCIDI)
13/10.
Richiami di Logica del prim'ordine.
Alfabeti, termini, formule. Clausole definite
e di Horn.
Fatti e regole e interpretazione delle quantificazioni.
14/10.
Interpretazioni e modelli.
Modelli di Herbrand. Modello minimo e
conseguenze logiche di un programma P.
20/10.
L'operatore TP e la sua iterazione.
Unificazione.
21/10.
SLD derivazioni.
Alberi SLD.
Correttezza e completezza della SLD risoluzione.
Incompletezza di Prolog e
ricerca con backtracking.
Incompletezza della risoluzione lineare al di fuori delle clausole di Horn.
23/10. [14.00-15.30]
Seminario: Multi-Criteria Optimal Planning for Energy Policies in CLP.
A cusa di Marco Gavanelli (univ. di Ferrara)
27/10.
Constraint Logic Programming.
Stati. Stati di fallimento e di succeso.
Regola di derivazione.
Le funzioni simpl e solv.
Embedding nella SLD risoluzione.
Uso di BProlog (Manuale)
per CLP(FD).
Metodologia constrain & generate in CLP.
Codifica delle
N-regine
(LUCIDI)
28/10.
Analisi delle opzioni del labeling di B-Prolog.
Esempi di CSP Modeling:
numeri di Schur
(eliminazione delle simmetrie, partizione dello spazio di ricerca,
definizione ricorsiva del for annidato)
03/11.
Esempi di codifiche clp(fd).
knapsack
(efficienza nell'uso del vincolo globale
scalar_product)
codici di Hamming
(eliminazione di simmetrie con vincoli lessicografici e table)
04/11.
Altri esempi di CSP modeling.
Due codifiche dell'Haplotype inference.
Definizione di formule Booleane a vincoli
e conteggio di un insieme vincolato.
Il problema del
protein folding semplificato
(alldifferent nello spazio, funzione di costo/energia definita con vincoli):
(si veda
Scuola ACP a Wroclaw)
10/11.
Introduzione ai vincoli globali.
Vincoli di all_different. Richiami sulle tecniche
di risoluzione al problema di ricerca di un matching massimale
in un grafo bipartito. (LUCIDI)
Tecniche per il filtering di vincoli all_different.
11/11.
Tecniche per la ricerca dell'ottimo
in CLP(FD) usando labeling (branch and bound), ricerca bottom-up con
timeout, e ricerca locale.
Esempio per B Prolog.
Applicazione delle tre tecniche su un semplice esempio e sul
problema del protein folding.
sudoku
(uso massivo di vincoli di alldifferent)
17/11.
Monotonia e non monotonia nella rappresentazione della conoscenza.
Richiami della semantica osservazionale,
modellistica e di punto fisso
dei programmi definiti.
Programmi generali.
Principali problemi semantici.
Direzionalità delle regole
(LUCIDI).
18/11.
La negazione in Prolog: CWA e NaF.
Esempi e limiti della NaF.
Implementazione con cut & fail.
Completamento (regola di Herbrand)
e relazioni tra le semantiche.
(LUCIDI)
Completamento di programmi generali.
Modelli del completamento e cenno
ai modelli well-founded.
Grounding.
Modelli stabili. Definizione.
(LUCIDI)
24/11.
Esempi esempi e NP-completezza del problema dell'esistenza
di un modello stabile.
Programmi e codici ASP.
Tecniche di programmazione ASP.
(LUCIDI)
Codifica di CSP con codici ASP.
Alcuni esempi:
Una Dispensina su questo materiale
(pensata per studenti a digiuno di conoscenze di logica).
02/12.
Linguaggi per il planning (Action Description Languages).
Sintassi del linguaggio B.
(LUCIDI).
Semantica del linguaggio B.
Non determinismo e static laws.
09/12.
Compilazione di B in ASP (si vedano lucidi lezione precedente).
Esempi di problemi espressi nel linguaggio B ed esecuzione:
Per approfondire
Altro materiale disponibile per approfondimento: SOKOBAN e il suo modeling in B, BMV, e Tabled Prolog.
Il solver GASP: LUCIDI
Predizione di struttura di una proteina usando CLP(FD) e fragment assembly.
LUCIDI ICLP 2010 (best paper).
Logic programming e coinduzione. Lucidi
Logic Programming e Bisimulazione. Lucidi
Versioni (su rivista) testuali dei quei lavori si
trovano QUI