Constraint Programming and Planning, A.A. 2010/2011

Programma Svolto

1. 02/03/2011. Introduzione al corso. CSP/COP e loro sostanziale equivalenza. NP hardness di semplici CSP. Spazio e alberi di ricerca. Tecniche naive di ricerca. (LUCIDI)
2. 03/03/2011. 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/03/2011. SAT e ASP per sisovere CSP (LUCIDI).
4. 10/03/2011. Constraint Solver. Risolutori completi ed incompleti. Regole di risoluzione: domain reduction, transformation e introduction. Derivazioni e constraint propagation. Node consistency, e Arc consistency. Bounds Consistency. Directional Arc/Bounds Consistency. (LUCIDI)
5. 16/03/2011. 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)
6. 23/03/2011. Richiami di Prolog. Alfabeti, termini, formule. Clausole definite e di Horn. SLD derivazioni e unificazione.
7. 24/03/2011. Alberi SLD. Incompletezza di Prolog e completezza degli alberi. Ricerca con backtracking. Predicati di secondo ordine.
8. 31/03/2011. Constraint Logic Programming. Stati. Stati di fallimento e di succeso. Regola di derivazione. Le funzioni simpl e solv. Embedding nella SLD risoluzione. Uso della libreria clpfd di SICStus Prolog. Metodologia constrain & generate in CLP. Codifica delle N-regine (LUCIDI)
9. 06/04/2011. 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)
   • Codifica del problema del circuito hamiltoniano usando il vincolo built-in circuit e un grafo per testing.
10. 07/04/2011. Altri esempi di CSP modeling. Codifica dei problemi:
    • codici di Hamming (eliminazione di simmetrie con vincoli lessicografici)
    • sudoku (uso massivo di vincoli di alldifferent)
    • protein folding semplificato (alldifferent nello spazio, funzione di costo/energia definita con vincoli).
11. 13/04/2011. Tecniche per la ricerca dell'ottimo in CLP(FD) usando labeling, ricerca bottom-up con timeout, e ricerca locale. Esempio per SICStus 4. Applicazione delle tre tecniche su un semplice esempio e sul problema del protein folding.
12. 14/04/2011. 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/04/2011. Richiami della semantica osservazionale, modellistica e di punto fisso dei programmi definiti. Programmi generali. Principali problemi semantici. Direzionalità delle regole (LUCIDI).
14. 27/04/2011. 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. 28/04/2011. 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. 04/05/2011. Programmi e codici ASP. Tecniche di programmazione ASP. (LUCIDI) Codifica di CSP con codici ASP. Alcuni esempi:
    • Graph Coloring.
    • N-Queens.
17. 05/05/2011. 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. Rappresentazione e ragionamento sul problema della torre di Hanoi e su quesity di Smullyan. (LUCIDI e Codice Smullyan 1 Codice Smullyan 2 Codice Hanoi) Cenni al funzionamento dei principali solver per answer set programming.
19. 12/05/2011. Linguaggi per il planning (Action Description Languages). Sintassi del linguaggio B. (LUCIDI). Per approfondire TPLP 10(2), 2010 e (codici, altri articoli, interpreti, esempi etc.).
20. 18/05/2011. Semantica del linguaggio B. Non determinismo e static laws. Compilazione di B in ASP (si vedano lucidi lezione 12/05/2011). Esempi di problemi espressi nel linguaggio B ed esecuzione:
    • La capra e il cavolo
    • Le tre botti
    Traduttore da B ad ASP e Sito di riferimento
21. 19/05/2011. Soluzione di B con CLP(FD) (si vedano lucidi lezione 12/05/2011). Un interprete CLP(FD) del B Alcuni altri esempi di domini in B.
    • Un puzzle
    • Il solitario Peg
22. 25/05/2011. Evoluzioni di B (per altri dettagli si veda Sito CLPASP)
    • Confronti tra B/ASP e B/CLP e il linguaggio BMV. LUCIDI della presentazione invitata al convegno in onore di Michael Gelfond per i suoi 65 anni.
    • Evoluzione di B per il multiagent planning centralizzato: BMAP. LUCIDI della presentazione del lavoro al convegno italiano di logica computazionale. Il lavoro è stato presentato a LPNMR e poi maturato in una versione per rivista Fundamenta Informaticae 2010.
    • Evoluzione di B per l'Autonomous Multiagent Planning: BAAC. LUCIDI della presentazione al convegno italiano di logica computazionale. Il lavoro è poi maturato nella versione che sarà presentata a ICLP2011: ARTICOLO.
23. 26/06/2011. Altri recenti contributi:
    • Il solver GASP: LUCIDI, articolo (CILC'08, ICLP'09, Fundamenta Informaticae 2009).
      
    • Predizione di struttura di una proteina usando CLP(FD) e fragment assembly. LUCIDI ICLP 2010 (best paper). Per materiale: LINK.
24. 01/06/2011. Altri contributi.
    • Il tool GELATO per l'ottimizzazione usando constraint programming e local search. Lucidi presentati al convegno RCRA 2009. Per approfondire: ARTICOLO. Si veda anche la tesi di dottorato di Raffaele Cipriano.
    • Cenni all'uso di CUDA in logica computazionale.
    Conclusione del corso.