Tesi di laurea sulla programmazione a vincoli
giugno 2019
Panoramica
Più eventi possibili include una simulazione, più condizioni deve valutare ripetutamente. Ma se il suo avanzamento permette di stabilire che una condizione non potrà più diventare vera, è possibile smettere di verificarla senza alterare i risultati? Ho progettato e implementato un metodo per HydLa, un linguaggio di modellazione dei sistemi ibridi, che usa la direzione di variazione delle variabili per eliminare le condizioni che non richiedono più verifiche.
Nel modello di valutazione, il metodo ha ridotto il tempo di esecuzione a circa la metà di quello dell’algoritmo originale, senza modificare i risultati della simulazione. Il miglioramento deriva dall’uso della struttura del problema per ridurre le possibilità da considerare.
La prospettiva della programmazione a vincoli sviluppata in questa ricerca è oggi alla base del mio approccio ai progetti del mio portfolio: invece di specificare direttamente ogni risultato, definire regole, priorità e confini, per poi ricavare soluzioni che li rispettino.
Il problema: più possibilità significano tempi di esecuzione più lunghi
HydLa descrive i sistemi ibridi, che combinano variazioni continue ed eventi discreti, attraverso vincoli matematici e logici. Anziché specificare ogni passaggio della procedura, il modello dichiara le condizioni che devono valere e il simulatore trova un comportamento che le soddisfa.
Nei modelli con molte regole condizionali, il simulatore verifica ripetutamente un ampio insieme di candidati. Anche le condizioni che non possono più diventare vere rimangono in quell’insieme. Al crescere del modello, queste verifiche inutili aumentano il lavoro computazionale.
Il modello: combinare variazioni continue e discrete
Una palla che rimbalza è un esempio chiaro di un sistema ibrido. In aria, posizione e velocità cambiano continuamente, mentre nel momento in cui tocca il pavimento avviene un evento discreto, il rimbalzo. Anche termostati, automobili e robot, pur su scale diverse, possiedono internamente gli stessi due tipi di cambiamento.
La valutazione ha usato un modello di una palla che si muove orizzontalmente e rimbalza su una superficie suddivisa in segmenti. A ogni segmento è associata una regola condizionale che fa rimbalzare la palla quando raggiunge quell’area. Aggiungere segmenti permette di rappresentare più oggetti, ma aumenta anche il numero di condizioni che il simulatore deve verificare.
Il collo di bottiglia: più condizioni aumentano il tempo di esecuzione
Una regola che si attiva soltanto quando una condizione è soddisfatta si chiama vincolo con guardia. Nel modello di valutazione, la regola di rimbalzo di un segmento si attiva solo quando la palla raggiunge il suolo e la sua posizione orizzontale ricade in quel segmento.
Aumentando il numero di segmenti da 10 a 200, il tempo di esecuzione del simulatore originale cresceva approssimativamente con il quadrato di quel numero. Nei modelli più grandi, il maggior numero di oggetti, zone di contatto ed eventi possibili può amplificare il problema.
L’indagine: a che cosa serviva il 96% del tempo di esecuzione?
L’analisi dei tempi del modello con 100 segmenti ha mostrato che FindMinTime assorbiva il 96% del tempo totale. Questa procedura individua il primo evento futuro possibile valutando ripetutamente tutte le condizioni di guardia candidate.
È emersa così una possibilità di miglioramento ben circoscritta: ridurre in sicurezza i candidati passati a FindMinTime. L’obiettivo era evitare soltanto le possibilità che non richiedevano più una valutazione, preservando i risultati della simulazione.
L’approccio: eliminare le condizioni che non possono più diventare vere
Immagina una palla che rimbalza scendendo una scala. Quando la palla supera un gradino e continua a muoversi in avanti, quel gradino non può più influenzare la palla. Chi guarda il diagramma ignora immediatamente i gradini dietro la palla. L'algoritmo originale continuava invece a esaminarli uno a uno.
La difficoltà consiste nel dimostrare che una guardia eliminata non servirà più. Rimuoverla solo perché al momento è falsa potrebbe produrre un risultato errato senza segnalarlo, qualora tornasse vera. Il metodo proposto usa quindi la monotonicità: la possibilità di garantire che una variabile continui ad aumentare o a diminuire in un dato intervallo.
Quando la direzione della variazione rimane invariata
Il primo approccio si applica quando una variabile varia in una sola direzione per tutta la simulazione. Nel modello della superficie segmentata, la posizione orizzontale della palla aumenta sempre. Una volta superato un segmento, la sua guardia non potrà più diventare vera. Tecniche di model checking possono verificare questa proprietà prima della simulazione, consentendo di rimuovere le guardie in sicurezza man mano che diventano irrilevanti durante l’esecuzione.
Quando la direzione della variazione si inverte
Molti sistemi non variano indefinitamente in una sola direzione: una variabile può aumentare, invertire la direzione e poi diminuire. La tesi ha quindi proposto un secondo approccio, che ipotizza una direzione di variazione e la controlla mediante asserzioni. Quando la direzione cambia, il processo di riduzione riparte, ripristinando le guardie eliminate nel precedente intervallo monotono. In questo progetto l’approccio è stato progettato, ma non implementato né valutato.
Il risultato: circa metà del tempo di esecuzione nel modello di valutazione
Ho implementato l’approccio basato sulla monotonicità uniforme e l’ho valutato con il modello della superficie segmentata. Per entrambi gli algoritmi il tempo di esecuzione cresceva con il numero di segmenti, ma il metodo proposto richiedeva sistematicamente meno tempo. Nelle curve adattate ai dati, il coefficiente del termine di grado più alto è sceso da 1,1463 a 0,6083. In questo benchmark, il tempo complessivo di simulazione si è ridotto di circa la metà.
Il risultato è specifico di questo benchmark. Il metodo è utile quando il modello contiene molti oggetti con guardia, la direzione della variazione è dimostrabile e alcune guardie diventano definitivamente irrilevanti durante l’esecuzione. Questo non significa che ogni modello HydLa venga eseguito in metà del tempo.
Che cosa ho imparato
Questa ricerca ha usato proprietà note del comportamento di un sistema per ridurre l’insieme di possibilità che il simulatore doveva considerare. Restringere lo spazio di ricerca preservando i risultati è un punto di forza della programmazione a vincoli.
L’implementazione e la valutazione riguardavano variabili che continuavano a variare in una sola direzione. La gestione delle inversioni è rimasta allo stadio di progettazione e richiedeva ancora una valutazione. Anche proprietà diverse dalla monotonicità potrebbero aiutare a individuare vincoli inutili.
Questa esperienza alimenta il mio attuale interesse per la progettazione delle condizioni e dei confini entro cui l’IA può cercare soluzioni. Quando si lavora con risultati complessi, definire che cosa si possa ignorare in sicurezza conta tanto quanto definire che cosa calcolare.
Takafumi Horiuchi e Kazunori Ueda. “Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa.” Proceedings of the 33rd Annual Conference of the Japanese Society for Artificial Intelligence, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02