Takafumi Horiuchi

Tesi di laurea sulla programmazione a vincoli

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.

Codice sorgente HydLa che definisce una palla in movimento orizzontale, che rimbalza su una superficie divisa in N segmenti adiacenti.
Un breve modello HydLa descrive una palla e una superficie suddivisa in N segmenti, ciascuno con un vincolo con guardia.

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 traiettoria rossa indica la palla che scende saltando i gradini neri della scala. L'area tratteggiata rappresenta i gradini già superati e ormai irrilevanti.
Mentre la palla si muove verso destra, la guardia associata a un gradino tratteggiato ormai alle sue spalle può essere ignorata.

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.

Una linea rossa sale da α al tempo 0 a β alla fine della simulazione, rappresentando una variabile che aumenta per tutto l’intervallo simulato.
La monotonicità uniforme indica che la direzione della variazione si mantiene per tutto l’intervallo simulato. Nell’asse orizzontale, t è il tempo e MaxT è la fine dell’intervallo simulato; α e β indicano i valori iniziale e finale.

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.

Cinque diagrammi mostrano un intervallo inizialmente ipotizzato come crescente, il fallimento di un’asserzione, un nuovo intervallo decrescente, un secondo fallimento e l’individuazione successiva degli intervalli monotoni.
Il fallimento delle asserzioni divide il comportamento in intervalli, ciascuno dei quali può essere trattato come monotono. Le croci rosse segnano i fallimenti delle asserzioni; la linea continua mostra il comportamento già simulato e quella tratteggiata il tratto ipotizzato. α₀, α₁, α₂ e β₀, β₁, β₂ delimitano gli intervalli successivi. t indica il tempo e MaxT la fine della simulazione.

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.

Tempo di simulazione in funzione di N, il numero di segmenti della superficie. Da 10 a 200 segmenti, il metodo proposto è sempre più veloce. Per N = 200 impiega circa 250 secondi, contro i circa 470 dell’algoritmo originale.
Nei modelli valutati, il metodo proposto (quadrati) impiega circa la metà del tempo dell’algoritmo originale (cerchi). Nel grafico, «original» indica l’algoritmo originale e «proposed» il metodo proposto. L’asse verticale, «Simulation Time (s)», mostra il tempo di simulazione in secondi; N, sull’asse orizzontale, è il numero di segmenti della superficie.

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