Constraint Programming and Planning, A.A. 2012/2013

Orario

Programma Svolto

1. 02/08/2012. [12:30-14:30] 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.
2. 04/10/2012. [12:30-14:30] Implementazione delle tecniche naive di ricerca in Prolog (codice). Tecniche (note) per risolvere CSP e COP. Local search, e (Integer) Linear Programming (LUCIDI)
3. 09/10/2011. SAT e ASP per sisovere CSP (LUCIDI). Constraint Solver. (LUCIDI). Risolutori completi ed incompleti. Regole di risoluzione: domain reduction, transformation e introduction. Derivazioni e constraint propagation. Node consistency, e Arc consistency.
4. 11/10/2012. Bounds Consistency. Directional Arc/Bounds Consistency. Hyperarc (e Bounds) consistency. Path Consistency. K-consistency (cenno). 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)
5. 16/10/2012. Richiami di Prolog. Alfabeti, termini, formule. Clausole definite e di Horn. Modelli di Herbrand. Modello minimo e conseguenze logiche di un programma P. L'operatore TP e la sua iterazione.
6. 23/10/2012. Unificazione. SLD derivazioni. Alberi SLD. Incompletezza di Prolog e completezza degli alberi. Ricerca con backtracking.
7. 25/10/2012. 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)
8. 30/10/2012. Esempi di CSP Modeling:
   • knapsack (efficienza nell'uso del vincolo globale scalar_product)
   • numeri di Schur (eliminazione delle simmetrie, partizione dello spazio di ricerca, definizione ricorsiva del for annidato)
   • codici di Hamming (eliminazione di simmetrie con vincoli lessicografici)
9. 06/11/2012. Altri esempi di CSP modeling. Codifica dei problemi:
   • Codifica del problema del circuito hamiltoniano usando il vincolo built-in circuit e un grafo per testing.
   • sudoku (uso massivo di vincoli di alldifferent)
   • Il problema dell'Haplotype Inference (si veda Materiale dalla scuola dell'ACP)
10. 08/11/2012. Il problema del protein folding semplificato (alldifferent nello spazio, funzione di costo/energia definita con vincoli): (Materiale dalla scuola dell'ACP)
11. 13/11/2012. 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.
12. 15/11/2012. 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.
13. 20/11/2012. 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).
14. 22/11/2012. 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)
15. 27/11/2012. Completamento di programmi generali. Modelli del completamento e cenno ai modelli well-founded. Grounding. Modelli stabili. Definizione, primi esempi e NP-completezza del problema dell'esistenza di un modello stabile. (LUCIDI)
16. 29/11/2012. Programmi e codici ASP. Tecniche di programmazione ASP. (LUCIDI) Codifica di CSP con codici ASP. Alcuni esempi:
    • Graph Coloring.
    • N-Queens.
17. 04/05/2012. Altre codifiche di CSP con codici ASP.
    • Numeri Schur.
    • Hamilton Circuit.
    • Protein Folding.
    Rappresentazione della conoscenza statica e dinamica con ASP:
    • La zebra evasa.
    • La capra e il cavolo.
18. 06/12/2012. Rappresentazione e ragionamento sul problema della torre di Hanoi e su quesity di Smullyan. (LUCIDI e Codice Smullyan 1 Codice Smullyan 2 Codice Hanoi) Linguaggi per il planning (Action Description Languages). Sintassi del linguaggio B. (LUCIDI).
19. 12/05/2011. Semantica del linguaggio B. Non determinismo e static laws. Compilazione di B in ASP (si vedano lucidi lezione precedente). Esempi di problemi espressi nel linguaggio B ed esecuzione: Per approfondire TPLP 10(2), 2010 e (codici, altri articoli, traduttori, interpreti, esempi etc.) In particolare, codici aggiornati si trovano in "The Updated and Fastest version ..." link) Esempio di B encoding e solving:
    • La capra e il cavolo
20. 13/12/2012. Altri esempi di B encoding e loro risoluzione in ASP.
    • Le tre botti
    • Un puzzle
    • Il solitario Peg
    • La torre di Hanoi.
    Soluzione di B con CLP(FD) (si vedano lucidi e riferimenti delle lezioni precedenti). Un interprete CLP(FD) del B in B Prolog Esempi di esecuzione.
21. 18/12/2012. Evoluzioni di B. Confronti tra B/ASP e B/CLP e il linguaggio BMV. LUCIDI e LAVORO (LNC 6565) M. Gelfond book. Multiagent planning centralizzato: BMAP. LUCIDI e LAVORO (Fundamenta Informaticae 2010). Autonomous Multiagent Planning: BAAC. LUCIDI e LAVORO (TPLP 2012)
22. 20/12/2012. Espressività e relative classi di complessità dei linguaggi per KR. LUCIDI
23. 08/01/2013. Il problema SOKOBAN e il suo modeling in B, BMV, e Tabled Prolog. Il lavoro che lo spiega (Fundamenta Informaticae). Smodels: una visione astratta. Il solver GASP: LUCIDI, articolo (CILC'08, ICLP'09, Fundamenta Informaticae 2009).
    
24. 10/01/2013. Predizione di struttura di una proteina usando CLP(FD) e fragment assembly. LUCIDI ICLP 2010 (best paper). Per materiale: LINK. Uso di CUDA nella logica computazionale.