Ciao a tutti, sono Vincenzo Lomonaco, ricercatore e docente all’Università di Pisa.
Nella puntata di oggi parliamo ancora di ragionamento complesso nel contesto dell’intelligenza artificiale e in particolare di problemi combinatori tra i più complicati da risolvere anche per l’intelligenza naturale più acuta.
Parliamo di Constraints Satisfaction Problems: perché è interessante approfondirli e soprattutto abbiamo delle metodologie computazionali tali che possano risolverli in maniera efficace ed efficiente? Scopriamolo insieme in questa puntata di Le Voci dell’AI.
I problemi combinatori sono una classe di problemi matematici e computazionali che consistono nel trovare, enumerare o ottimizzare combinazioni, permutazioni o disposizioni di elementi secondo determinate regole o vincoli.
La caratteristica principale di questi problemi è che coinvolgono la scelta o l’organizzazione degli oggetti in modi diversi, cercando una soluzione ottimale o valida in uno spazio di possibilità che può crescere rapidamente con la dimensione del problema.
Molti di questi problemi possono essere descritti più formalmente come Constraint Satisfaction Problems, CSP, una classe di problemi molto nota nel contesto dell’intelligenza artificiale.
In questi compiti si riesce a descrivere il problema come un insieme di variabili in cui ogni variabile può assumere un valore da un dominio predefinito e da una serie di vincoli che impongono specifiche restrizioni sulle combinazioni di valori ammissibili. L’obiettivo è trovare una soluzione in cui tutti i vincoli siano rispettati.
I problemi combinatori risolvibili con CSP includono sfide come l’assegnazione delle risorse e la pianificazione.
Un esempio reale è la programmazione degli esami universitari, dove ogni esame deve essere assegnato a una fascia oraria e a un’aula, rispettando i vincoli di disponibilità di studenti e aule stesse.
Un altro esempio, forse ancor più classico, è il gioco del sudoku, dove ogni cella è una variabile che deve rispettare vincoli di riga, colonna e sotto-griglia.
Anche la pianificazione di rotte per i veicoli in logistica, scegliendo un esempio magari più concreto, soggetta a vincoli di capacità e tempi di consegna, può essere affrontata con approcci CSP per trovare soluzioni ottimali.
Per risolvere questi problemi potremmo certamente utilizzare i più sofisticati Large Language Models come OpenAI o1, ma è bene sottolineare che esistono metodologie di ricerca in AI capaci di risolvere questo tipo di problemi.
I CSP Solver – Risolutori sono strumenti specializzati in questo, progettati per risolvere in modo efficiente problemi combinatori come l’assegnazione di risorse o la pianificazione, sfruttando algoritmi di ricerca e propagazione di vincoli.
I vantaggi principali dei CSP solver risiedono nella loro precisione e ottimizzazione, quindi essi sono in grado di trovare soluzioni ottimali o verificare rapidamente l’inconsistenza di un problema, sfruttando tecniche algoritmiche robuste come il backtracking, il branch and bound o la propagazione dei vincoli, come accennavamo poc’anzi.
Tuttavia, i CSP solver richiedono una definizione precisa del problema e possono diventare inefficaci se le dimensioni dello spazio di ricerca crescono esponenzialmente.
Dall’altra parte, i Large Language Models, sebbene non siano progettati specificatamente per risolvere problemi combinatori, possono essere utilizzati per affrontare problemi con vincoli tramite simulazione o guida all’utente nell’implementazione di algoritmi di questo tipo, o infine riscrivendo ed eseguendo loro stessi l’algoritmo di un CSP solver minimale.
I Large Language Models, quindi, sono flessibili e capaci di comprendere il linguaggio naturale, fornendo soluzioni creative o intuitive, anche per problemi piuttosto complessi.
Tuttavia sono meno efficienti in termini di calcolo, tempo impiegato per una soluzione e precisi in questi calcoli rispetto ai CSP solver; non garantiscono soluzioni ottimali per problemi specifici, specialmente se richiedono un ottimizzazione che sia rigorosa, quindi sound, in un qualche modo consistente.
In sintesi, se riusciamo a descrivere opportunamente un problema in termini chiari e formali come un constraint satisfaction problem, allora probabilmente utilizzare un CSP solver già disponibile costituisce la scelta più efficiente e sicura.
Cerchiamo di capire dunque, con un esempio come potremmo fare in pratica.
In questa immagine vediamo il classico gioco del sudoku. Il sudoku è un puzzle di logica composto da una griglia nove per nove suddivisa in nove riquadri, tre per tre. L’obiettivo è riempire la griglia con numeri da 1 a 9, assicurandosi che ogni riga, colonna e riquadro contengano ciascun numero senza ripetizioni. Questo gioco richiede ovviamente ragionamenti ed enumerazioni complesse, quindi non è facile da risolvere, soprattutto per un Large Language Model.
Invece potremmo descrivere il problema come un CSP, un constraint satisfaction problem costituito da variabili valori ammissibili per ogni variabile e vincoli tra le stesse.
In particolare avremo una variabile per ogni cella da x11, la prima cella in alto a sinistra a x99, l’ultima cella in basso a destra. I valori ammissibili, per ognuna di queste celle, sono un numero intero tra 1 e 9, come il gioco impone, mentre i vincoli possono essere illustrati come vincoli su riga, ossia le variabili sulla stessa riga non possono assumere lo stesso valore sulla colonna. Variabili sulla stessa colonna non possono assumere lo stesso valore e infine, come vincoli di blocco, le variabili con lo stesso gioco appartenenti allo stesso blocco non possono assumere lo stesso valore.
Il nostro obiettivo è trovare l’assegnamento di valori da uno a nove, il dominio di riferimento a tutte le variabili, le celle ancora vuote nel puzzle rispettando tali vincoli.
Iin questa tabella vediamo un’analisi empirica pubblicata in uno studio recente di un algoritmo classico di backtracking, l’algoritmo principale dei CSP solver in cui si testa lo stesso su dieci Sudoku puzzle di difficoltà crescente. Vedete nella seconda colonna il numero di caselle vuote che caratterizza anche la difficoltà del problema. Come vediamo sulla terza colonna, il tempo richiesto in millisecondi è davvero esiguo.
Per risolvere il problema, per trovarne una soluzione valida si passa da un minimo di 71.000 millisecondi, equivalenti a circa 1 minuto a un massimo di 300.000 millisecondi, equivalenti a circa 5 minuti per trovare quindi una soluzione idonea, comunque significativamente meno del tempo atteso per un umano esperto per risolvere un Sudoku, che si aggira quindi dai pochi minuti a venti 30 minuti a seconda della difficoltà.
Bene, in questa puntata abbiamo discusso di problemi molto complessi per i quali non esiste una facile soluzione e che richiedono ragionamenti complessi, i Constraints Satisfaction Problems, ovvero problemi di soddisfacimento di vincoli.
Per questo tipo di problemi non possiamo rifarci a ChatGPT alla tecnologia dei Large Language Models, ma piuttosto ad un ragionamento di esplorazione sistematica delle soluzioni che possa portarci velocemente a una soluzione di cui possiamo fidarci.
La buona notizia è che esistono dei sistemi software basati su algoritmi di ricerca, i solver che possono risolverli.
Nel futuro sono sicuro che vedremo sempre di più l’integrazione naturale tra Large language models, capaci di interagire naturalmente con gli utenti tramite linguaggio naturale e solver specifici, più potenti e sicuri, basati su metodologie diverse che possano garantire la coerenza e consistenza del ragionamento e quindi della soluzione trovata.
Ciao e dalla prossima puntata di Le Voci dell’AI
