Realizzazione di un algoritmo di pianificazione basato su euristiche che operano su modelli rilassati
Autore
Leonardo Perria - Università degli Studi di Cagliari - [2002-03]
Documenti
Abstract
La tesi ha come scopo lo sviluppo e l’implementazione di un algoritmo di pianificazione automatica da incorporare in agenti software per dotarli di comportamento proattivo. La pianificazione automatica è finalizzata al raggiungimento di un particolare obiettivo (goal), da ottenere partendo da uno stato iniziale tramite l'applicazione di azioni elementari. Nell'ambito della tesi si assume che l'ambiente su cui si opera (descritto secondo il formalismo logico STRIPS) sia deterministico, statico e totalmente accessibile. Si assume inoltre che gli effetti delle azioni intraprese siano tutti deterministici.
In generale un problema di pianificazione può essere rivisto come un problema di ricerca i cui ingressi sono una descrizione del dominio su cui si opera, lo stato iniziale e il goal. Data la complessità della ricerca, principalmente dovuta all'elevato branching factor e alla numerosità degli oggetti in gioco, tipicamente non è possibile effettuare una ricerca esaustiva. Uno dei modi per trattare la complessità dei problemi di pianificazione consiste nell'utilizzare algoritmi di ricerca informata, dotandoli di euristiche opportune – tipicamente finalizzate alla riduzione del branching factor. Il pianificatore sviluppato, basato sull’algoritmo di ricerca informata denominato “A*” (A-star), è incentrato sulla definizione della funzione euristica da utilizzare per orientare la ricerca nello spazio degli stati. Tale funzione è da considerarsi come una variante di quella implementata all'interno del pianificatore HSP (Heuristic Search Planner), in cui le alternative di espansione dei nodi vengono ordinate operando su una versione rilassata del problema di pianificazione. In particolare nella variante proposta si ottengono miglioramenti significativi della capacità predittiva utilizzando anche le informazioni relative ai nodi immediatamente adiacenti a quello corrente.
Il prototipo che implementa l'algoritmo di pianificazione è stato interamente sviluppato in linguaggio C++, utilizzando criteri di modularità e riusabilità del codice. La fase di sperimentazione dell'algoritmo ha messo in evidenza sostanziali miglioramenti rispetto all'euristica HSP proposta in letteratura. I risultati sperimentali, ottenuti su problemi di media ed elevata complessità hanno infatti evidenziato miglioramenti in relazione sia al tempo richiesto per ottenere una soluzione sia alla capacità di risolvere i problemi all'aumentare della complessità degli stessi.
In generale un problema di pianificazione può essere rivisto come un problema di ricerca i cui ingressi sono una descrizione del dominio su cui si opera, lo stato iniziale e il goal. Data la complessità della ricerca, principalmente dovuta all'elevato branching factor e alla numerosità degli oggetti in gioco, tipicamente non è possibile effettuare una ricerca esaustiva. Uno dei modi per trattare la complessità dei problemi di pianificazione consiste nell'utilizzare algoritmi di ricerca informata, dotandoli di euristiche opportune – tipicamente finalizzate alla riduzione del branching factor. Il pianificatore sviluppato, basato sull’algoritmo di ricerca informata denominato “A*” (A-star), è incentrato sulla definizione della funzione euristica da utilizzare per orientare la ricerca nello spazio degli stati. Tale funzione è da considerarsi come una variante di quella implementata all'interno del pianificatore HSP (Heuristic Search Planner), in cui le alternative di espansione dei nodi vengono ordinate operando su una versione rilassata del problema di pianificazione. In particolare nella variante proposta si ottengono miglioramenti significativi della capacità predittiva utilizzando anche le informazioni relative ai nodi immediatamente adiacenti a quello corrente.
Il prototipo che implementa l'algoritmo di pianificazione è stato interamente sviluppato in linguaggio C++, utilizzando criteri di modularità e riusabilità del codice. La fase di sperimentazione dell'algoritmo ha messo in evidenza sostanziali miglioramenti rispetto all'euristica HSP proposta in letteratura. I risultati sperimentali, ottenuti su problemi di media ed elevata complessità hanno infatti evidenziato miglioramenti in relazione sia al tempo richiesto per ottenere una soluzione sia alla capacità di risolvere i problemi all'aumentare della complessità degli stessi.
Questa tesi è correlata alla categoria
segnala questa pagina ::.