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

  1. 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.
  2. 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).
  3. 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.
  4. 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)
  5. 13/10. Richiami di Logica del prim'ordine. Alfabeti, termini, formule. Clausole definite e di Horn. Fatti e regole e interpretazione delle quantificazioni.
  6. 14/10. Interpretazioni e modelli. Modelli di Herbrand. Modello minimo e conseguenze logiche di un programma P.
  7. 20/10. L'operatore TP e la sua iterazione. Unificazione.
  8. 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.
  9. 23/10. [14.00-15.30] Seminario: Multi-Criteria Optimal Planning for Energy Policies in CLP. A cusa di Marco Gavanelli (univ. di Ferrara)
  10. 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)
  11. 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)
  12. 03/11. Esempi di codifiche clp(fd).
  13. 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)
  14. 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.
  15. 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)
  16. 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).
  17. 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)
  18. 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:
  19. 25/11. Altre codifiche di CSP con codici ASP.
  20. 01/12. Rappresentazione e ragionamento sul problema della torre di Hanoi e su quesiti di Smullyan. (LUCIDI e Codice Smullyan 1 Codice Smullyan 2 Codice Hanoi) Rappresentazione della conoscenza statica e dinamica con ASP: Una Dispensina su questo materiale (pensata per studenti a digiuno di conoscenze di logica).
  21. 02/12. Linguaggi per il planning (Action Description Languages). Sintassi del linguaggio B. (LUCIDI). Semantica del linguaggio B. Non determinismo e static laws.
  22. 09/12. Compilazione di B in ASP (si vedano lucidi lezione precedente). Esempi di problemi espressi nel linguaggio B ed esecuzione: Per approfondire 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.
  23. 15/12. Una descrizione ad alto livello di un solver per ASP (LUCIDI). Un cenno ai linguaggi/dialetti usati nelle competitions. (LUCIDI).

    Evoluzioni di B.

    Versioni (su rivista) testuali di quei lavori si trovano QUI oltre a "Perspectives on ..." citato sopra.
  24. 16/12. Espressività e relative classi di complessità dei linguaggi per KR. LUCIDI

    Sfruttare l'architettura CUDA:

  25. 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

Home Page