Progetto

La programmazione con vincoli è un campo di ricerca multi-disciplinare in cui le competenze spaziano dalla Intelligenza Artificiale, alla Ricerca Operativa, ai Linguaggi di Programmazione, alle Basi di Dati, e le cui applicazioni sono presenti in molti discipline.

La programmazione con vincoli è un paradigma di programmazione fondamentalmente diverso da molti altri, dato che richiede solo la modellazione di un problema in modo dichiarativo (specificando i suoi "vincoli") e poi la sua soluzione tramite una procedura generale che esplora lo spazio delle soluzioni e ne taglia parti inutili per mezzo di un uso attivo dei vincoli. Tipiche applicazioni della programmazione dei vincoli che hanno avuto molto successo sono i problemi di scheduling e di allocazione di risorse, i problemi di vehicle routing, gli orari, l'assegnamento delle frequenze. Nuovi campi applicativi che sono stati considerati negli ultimi anni sono la bioinformatica, la configurazione online, la ricerca su web, e l'analisi di programmi e sistemi informatici.

La ricerca nel campo della programmazione con vincoli è iniziata negli anni '70 nell'ambito dell'Intelligenza Artificiale e dal 1995 ha visto un aumento significativo dell'interesse sia teorico che pratico, con una conferenza internazionale annuale dedicata alla programmazione con vincoli, un'associazione internazionale, molti workshop e volumi, una rivista internazionale, e cinque libri. L'Europa guida la ricerca in questo campo, ma molti altri gruppi sono sparsi per il mondo. In Italia, la ricerca nell'ambito della programmazione con vincoli è svolta soprattutto dai gruppi coinvolti in questo progetto, che ha come uno degli scopi principali quello di far comunicare tali gruppi e incoraggiare la loro collaborazione, in modo da poter sfruttare le competenze comuni per una facile comunicazione, ma anche le competenze complementari per una fruttuosa collaborazione che porti a nuovi risultati sia teorici che pratici.

Più precisamente, l'obbiettivo di questo progetto è quello di studiare estensioni dei formalismi e delle tecniche esistenti per la programmazione con vincoli, con particolare riferimento ad applicazioni innovative sia a sistemi informatici (es. sicurezza, analisi di programmi) che a problemi reali (es. scheduling,bioinformatica). Utilizzeremo quindi i vincoli come formalismo unificante, e le applicazioni come spunto per le estensioni dei linguaggi e delle tecniche di risoluzione dei vincoli.

In particolare, studieremo come

estendere i formalismi per poter modellare preferenze positive e negative, condizionate e non, qualitative e quantitative
modellare e risolvere situazioni con più agenti, e studiarne le proprietà fondamentali
sviluppare tecniche per situazioni con più criteri di ottimizzazione
gestire vincoli su intervalli e su insiemi.

I campi applicativi che considereremo sono:

soluzione di problemi di scheduling
verifica di proprietà di sistemi concorrenti a stati infiniti
analisi di protocolli di sicurezza multilivello
bioinformatica.

Ogni unità ha competenze comuni che finora sono state usate in modo indipendente ma complementare. Il progetto servirà a sfruttare le competenze comuni e anche quelle complementari per ottenere risultati innovativi sia nell'ambito fondazionale e teorico, sia in quello applicativo.