Formiche Digitali
Posted on 20. Jul, 2010 by THeK3nger in AI e Neuroscienze
Quello che segue è un altro piccolo esempio di come si possano scrivere programmi che implementano agenti intelligenti in una manciata di righe.
Supponiamo di voler replicare digitalmente il comportamento di una formica che insegue una traccia di ferormone fino ad un obiettivo. La traccia, per semplicità, non si sovrappone ed è sempre divisa da almeno una casella da un altra porzione di traccia.
Il comportamento di questa formica può essere emulato facendo uso di un agente reattivo con un bit di stato. Questi agenti hanno dei dati in ingresso che elaborano e trasformano in una serie di azione seguendo una o più regole di produzione. La nostra formica, ad esempio, può percepire solo se nella casella di fronte a lei c’è la traccia di ferormone oppure no.
La nostra formica è capace di effettuare solo le seguenti azioni:
- Avanzare: avanza di una casella.
- Ruotare a destra: ruota a destra.
- Ruotare a sinistra: ruota a sinistra.
- On: attiva il bit di stato.
- Off: disattiva il bi di stato.
- Sensi: riceve le informazioni sensoriali (nel nostro caso solo la presenza di ferormone nella casella di fronte) mettendo a Vero o Falso la variabile ferormone
A questo corrispondono le seguenti regole di produzioni.
- S1: Se ferormone = True e stato = 0 -> Avanzare
- S2: Se ferormone = False e stato = 0 -> On e Ruota a destra
- S3: Se ferormone = True e stato = 1 -> Off e Avanzare
- S4: Se ferormone = False e stato = 1 -> Ruota a destra x 2 e Off
Tutto questo è impleementato nel seguente codice:
# -*- coding: utf-8 -*-
"""
Questo modulo implementa una formica in grado di seguire
un percorso più un metodo per generare un percorso
casuale.
"""
import random
def generate_map(x, y) :
"""
Genera un percorso casuale su una mappa X x Y.
Args:
X (int) larghezza della mappa
Y (int) altezza della mappa
Return:
Una griglia X x Y contenente un percorso per la formica digitale.
"""
mappa = [[0 for i in range(x)] for j in range(y) ] # Inizializza mappa vuota.
i , j = 1, 1 # Posizione iniziale.
mappa[j][i] = 1
avaiable = ['right'] # Il primo passo va eseguito sempre a destra per semplicità.
while len(avaiable) > 0 :
next = random.sample(avaiable,1)
if next[0] == 'up' :
j -= 1
elif next[0] == 'down' :
j += 1
elif next[0] == 'left' :
i -= 1
elif next[0] == 'right' :
i += 1
mappa[j][i] = 1
avaiable = pick_avaiable(mappa,i,j)
else :
mappa[j][i] = 2 # Alla fine setta il punto obiettivo.
return mappa
def pick_avaiable(mappa, i, j) :
"""
Funzione ausiliaria per la generazione della mappa.
Data una mappa e la posizione attuale restituisce le direzioni
percorribili in accordo con la regola di non sovrapposizione.
Args:
mappa (mappa) La mappa corrente
i (int) attuale posizione x
j (int) attuale posizione y
Return:
Una lista di possibili direzioni.
"""
new_avaiable = []
if j > 1 :
t = mappa[j-1][i-1] == 0 and mappa[j-1][i] == 0 and mappa[j-1][i+1] == 0
t = t and mappa[j-2][i-1] == 0 and mappa[j-2][i] == 0 and mappa[j-2][i+1] == 0
if t:
new_avaiable.append('up')
if j < (len(mappa) - 2) : t = mappa[j+1][i-1] == 0 and mappa[j+1][i] == 0 and mappa[j+1][i+1] == 0 t = t and mappa[j+2][i-1] == 0 and mappa[j+2][i] == 0 and mappa[j+2][i+1] == 0 if t: new_avaiable.append('down') if i > 1 :
t = mappa[j-1][i-1] == 0 and mappa[j][i-1] == 0 and mappa[j+1][i-1] == 0
t = t and mappa[j-1][i-2] == 0 and mappa[j][i-2] == 0 and mappa[j+1][i-2] == 0
if t:
new_avaiable.append('left')
if i < (len(mappa[0]) - 2) :
t = mappa[j-1][i+1] == 0 and mappa[j][i+1] == 0 and mappa[j+1][i+1] == 0
t = t and mappa[j-1][i+2] == 0 and mappa[j][i+2] == 0 and mappa[j+1][i+2] == 0
if t:
new_avaiable.append('right')
return new_avaiable
class Ant(object) :
"""
Questa classe implementa la formica digitale.
"""
VERSO = {'up': 0, 'right': 1, 'down': 2, 'left':3}
def __init__(self, mappa) :
self.x = 1
self.y = 1
self.mappa = mappa
self.bit = False
self.verso = self.VERSO['right']
def r_rotate(self) :
"""
Ruota la formica a destra.
"""
self.verso += 1
if self.verso == 4 :
self.verso = 0
def l_rotate(self) :
"""
Ruota la formica a sinistra. Non usato attualmente.
"""
self.verso -= 1
if self.verso == -1 :
self.verso = 3
def forward(self) :
"""
Fa avanzare di una casela la formica.
"""
if self.verso == self.VERSO['up'] :
self.y -= 1
if self.verso == self.VERSO['down'] :
self.y += 1
if self.verso == self.VERSO['left'] :
self.x -= 1
if self.verso == self.VERSO['right'] :
self.x += 1
def est_ferormone(self) :
"""
Restituisce 1 se la casella daavanti al formica contiene
del ferormone, 2 se è la casella obiettivo e 0 se la cella è vuota.
"""
if self.verso == self.VERSO['up'] :
return self.mappa[self.y-1][self.x]
if self.verso == self.VERSO['down'] :
return self.mappa[self.y+1][self.x]
if self.verso == self.VERSO['left'] :
return self.mappa[self.y][self.x -1]
if self.verso == self.VERSO['right'] :
return self.mappa[self.y][self.x + 1]
def move(self) :
"""
Cervello della formica. Elabora il comportamento in base
alle regole di produzione sotto elencate.
"""
if self.est_ferormone() == 2 :
self.forward()
return 'COMPLETE'
if self.est_ferormone() and not self.bit :
self.forward()
return 'S1'
if not self.est_ferormone() and not self.bit :
self.bit = True
self.r_rotate()
return 'S2'
if self.est_ferormone() and self.bit :
self.bit = False
self.forward()
return 'S3'
if not self.est_ferormone() and self.bit :
self.r_rotate()
self.r_rotate()
self.bit = False
return 'S4'
def print_map_ant(self) :
"""
Stampa la mappa del percorso contrassegnando
la formica con una X.
"""
print "-"*(len(self.mappa[0])*3)
for j in range(len(self.mappa)) :
for i in range(len(self.mappa[j])) :
if i == self.x and j == self.y :
print 'X ',
elif self.mappa[j][i] == 0 :
print " ",
else :
print "%d " % self.mappa[j][i],
print ":"
print "-"*(len(self.mappa[0])*3)
Il codice contiene, oltre alla classe Ant che implementa la formica, una funzione per generare un percorso casuale che rispetta le regole che abbiamo fissato. Ad ogni chiamata del metodo move la formica digitale elabora i dati a sua disposizione e restituisce la regola di produzione prescelta (oppure COMPLETE se la formica ha raggiunto l’obbiettivo posto alla fine della traccia).
Inoltre la formica ha un metodo che stampa a schermo l’intera mappa del mondo, con la traccia e la posizione attuale della stessa (segnata con una X).
È un esempio carino che magari può essere espanso a piacimento, sia offrendo un output grafico più carino sia rendendo auomatica l’esecuzione dei vari move.
Sperando possiate trovare il codice interessante vi auguro una buona serata. 
UPDATE:
Potete scaricare il file da qui:Ant.py
c.realkiller
Jul 20th, 2010
File “pi.py”, line 25
while len(avaiable) > ; 0 :
come mai?
THeK3nger
Jul 20th, 2010
È wordpress che cambia la codifica di alcuni simboli come
c.realkiller
Jul 21st, 2010
in effetti lo avevo pensato e quindi con gedit avevo effettuato la sostituzione, ma mi da sempre errore ora lo posto:
File “pi.py”, line 25
while len(avaiable) >; 0 :
^
devo anche spostare o sostituire il punto e virgola?
c.realkiller
Jul 21st, 2010
scusa ho visto ora che hai corretto lo script.
c.realkiller
Jul 21st, 2010
continua a restituirmi errori e c’è ancora da correggere un > nello script controllalo alla linea 68 errore:
File “pi.py”, line 68
if j 1 :
^
c.realkiller
Jul 21st, 2010
magari apro una discussione su LQH che qui non mi fa inserire codice e se lo inserisce ci sono errori di copi e incolla
mi interesava vedere come funzionavano ste formiche intelligenti 
THeK3nger
Jul 21st, 2010
Ho aggiunto il download diretto in fondo al post così puoi scaricare il file originale. Purtroppo wordpress mi ha anche sputtanato qualche indentazione.
c.realkiller
Jul 21st, 2010
scaricato, questa volta non mi da errore ma neanche output, cioè mi restituisce niente nel terminale e in geany exit code 0.
sarò impedito io boh!
THeK3nger
Jul 21st, 2010
Non è uno script avviabile ma un modulo. Devi importarlo da python e giocarci a mano.