Gli algoritmi genetici (o Genetic Algorithms) sono sfruttati per la risoluzione dei più disparati problemi computazionali. Per rendersene conto basta visitare questa pagina su Wikipedia.
Io e altri quattro studenti del corso di Intelligenza Artificiale (Laurea Specialistica in Ingegneria Informatica) abbiamo pensato di applicare questo paradigma di programmazione alla risoluzione di un problema di motion-planning, ovverosia far trovare ad un robot, posizionato in un ambiente ad esso ignoto, la strada che lo conduca a una posizione obiettivo, da noi definita col termine Goal.
Abbiamo allora sviluppato un’applicazione in Java con lo scopo di simulare il processo algoritmico evolutivo che fa trovare al robot il percorso verso il suo goal e abbiamo chiamato questa applicazione Genetic Algortihm for Motion Planning (o G.A.M.P. per gli amici). Alla fine del corso questo lavoro ci ha fatto quadagnare un bel 30, ed abbiamo pensato di renderlo disponibile in licenza GPL.
Abbiamo anche realizzato un video che mostra il nostro programma in azione.
Riporto qui di seguito il link all’applicazione e al PDF della tesina da noi preparata per coloro che fossero interessati.
Cosa sono i Genetic Algorithms
I Genetic Algorithms operano simulando il processo genetico di evoluzione per mezzo della selezione naturale, pertanto, per risolvere un problema computazionale, è necessario operare una mappatura dei concetti specifici del problema in questione in concetti specifi ci degli algoritmi genetici. Una soluzione ad un problema è costituita da un certo numero di variabili che la caratterizzano: essa viene dunque associata al concetto di individuo biologico (o meglio ai suoi cromosomi), mentre le variabili che la costituiscono sono i geni all’interno dei cromosomi.
A partire da una popolazione iniziale di n individui, l’algoritmo opera ordinando gli individui dal migliore al peggiore, attraverso opportune politiche basate su un voto dato ad ogni individuo. Tale voto, detto fitness, riassume in sè la bontà dell’individuo a cui è associato ed è calcolato da una fitness function. Attraverso questa fase, chiamata selezione, gli individui migliori ottengono una probabilità di tramandare il loro corredo genetico maggiore rispetto a quella degli individui peggiori. A questo punto si entra nella fase di crossover, o ricombinazione, in cui si effettua la creazione di una nuova generazione fi glia attraverso diverse tecniche di crossover genico. In accoppiata a questo meccanismo viene anche realizzata la possibilità che un individuo subisca, con una certa probabilità, una mutazione genetica. Evento sporadico che accade anche in natura, essa consente, nel parallelo algoritmico, di far variare gli individui in modo da allontanarsi da ottimi locali per esplorare altre parti dello spazio delle configurazioni delle variabili e sperabilmente dirigersi verso un ottimo globale.
Una volta ottenuti n nuovi individui si itera nuovamente la procedura di selezione, crossover e mutazione appena descritti fintanto che non si raggiunge una condizione per cui la soluzione trovata è soddisfacente.
Il problema che abbiamo risolto
Nel nostro lavoro abbiamo risolto un problema di motion planning su ambiente statico sconosciuto di un robot car-like che si muove in uno spazio bidimensionale. È importante precisare che l’ambiente sia sconosciuto a priori e quindi al robot non è nota la posizione degli ostacoli. Tale agente conosce solo la propria distanza dal goal e dallo start, fornita ad sempio tramite un segnale GPS oppure, ipotesi meno stringente, da due radiofari la cui distanza può essere calcolata in termini di attenuazione dei segnali.
L’obiettivo del robot è trovare la strada che lo conduca al goal, utilizzando un algoritmo genetico che costruisca percorsi che di volta in volta lo avvicinano sempre di più al suo obiettivo.