L'idea alla base di questo progetto ha tratto ispirazione da una tecnologia utilizzata in ambito industriale per la gestione dello spazio in magazzini di grandi dimensioni (si veda [1]). A differenza del classico metodo di stoccaggio attraverso corridoi e scaffalature, con questo tipo di automazione lo spazio a disposizione è completamente occupato: saranno infatti gli agenti robotici a recuperare la risorsa desiderata occupandosi nel contempo di liberare il cammino verso la stessa se necessario.
Il lavoro qui presentato simula una situazione del tipo appena descritto, seppur semplificando alcuni aspetti per limiti di tempo e tecnologici.
L'esecuzione è concorrente, con un massimo di tre agenti gestiti.
L'immagine a fianco rappresenta lo spazio in cui operano gli agenti, una griglia quadrata di 3×5 celle più due zone laterali di dimensione 2×1, non tutte tuttavia collegate tra loro. In particolare si notano
scaffale #1 nel goal #3, scaffale #2 nel goal #1, scaffale #3 nel goal #2Per la versione originale del video si veda qui.
Per raggiungere tale obiettivo sono stati creati due livelli di pianificazione distinti ma tra loro collegati. Un tentativo monolitico era in realtà stato tentato inizialmente, ma subito abbandonato per le eccessive richieste computazionali necessarie all'elaborazione, sia in termini di memoria che di tempo d'esecuzione (a titolo d'esempio si pensi che a parità di configurazione l'approccio monolitco impiegava qualche decina di minuti per la risoluzione del problema, quando non eccedeva la quantità di memoria disponibile, mentre la divisione in livelli permette di ottenere una soluzione in una manciata di secondi).
Il primo livello lavora ad un livello di astrazione più alto, fornendo una soluzione al problema in termini di macro-azioni come "l'agente a raccoglie lo scaffale 3", ovvero senza tener conto di tutti i dettagli relativi alla configurazione del mondo e alla reale implementazione delle mosse calcolate, mentre il pianificatore di basso livello si occupa di elaborare l'effettiva sequenza di azioni necessarie all'esecuzione delle macro-azioni. Lo schema seguente descrive intuitivamente il servizio fornito da ogni livello e la sua posizione nella scala gerarchica.
In aggiunta ai due livelli citati ne esiste un terzo, preposto all'attuazione dei piani calcolati dai livelli superiori. Ricapitolando:
an1,an2,an3dove ani significa "l'azione n-esima eseguita dall'agente i-esimo" e può assumere i seguenti valori
S0 ... Sn --> an1,an2,an3 --> Sn+1 .... GOvvero partendo dallo stato iniziale S0 il goal G è raggiunto tramite una serie di cambiamenti di stato causati dalle macro-azioni an1,an2,an3 eseguite nello stato Sn, le quali portano nello stato Sn+1.
Chiarendo, il compito dell'alto livello è quello di decidere "chi e cosa", ovvero quale agente recupererà quale scaffale; tale scelta è effettuata in base alle sole distanze (misurate in celle) tra la posizione di partenza e quella di arrivo, compatibilmente con i vincoli di eseguibilità delle singole azioni (si veda il capitolo dedicato). In questa fase non si ha quindi alcuna conoscenza del cammino reale che sarà necessario intraprendere per eseguire correttamente l'azione proposta (ad esempio "l'agente A raccoglie lo scaffale s1" si svolgerà praticamente tramite una sequenza di azioni del tipo "muoviti da 1 a 2, muoviti da 2 a 3 ... muoviti da x a y, raccogli s1") e conseguentemente degli eventuali incroci tra agenti che potrebbero verificarsi durante gli spostamenti. Questo permette di snellire il codice del pianificatore evitando di inserire aspetti del mondo non strettamente necessari. Il piano calcolato in questo modo è altresì ottimale nel senso che minimizza il numero di celle attraversate (ovvero la distanza percorsa) dagli agenti.
A questo punto entra in gioco il secondo livello, il quale ricevuta la stringa contenente le azioni an1,an2,an3 provvede a ricercare una sequenza di movimenti che permetta di raggiungere lo stato Sn+1, vale a dire una sequenza simile a quella presentata sopra (muoviti da ... a ... etc). Per ogni esecuzione successiva alla prima è aggiornato lo stato del mondo, che passa dalla situazione Sn a quella Sn+1, ed alle macro-azioni che di volta in volta sarà necessario eseguire per passare dallo stato corrente al successivo.
Il cammino trovato è ottimale nel senso che minimizza la distanza percorsa evitando collisioni tra agenti, cosa che ricordiamo il pianificatore di alto livello non poteva fare, data la conoscenza incompleta del mondo (ricordiamo che a più alto livello sono infatti note le sole distanze tra punti interessanti come buffer, goal etc). Anche in questo caso la suddivisione in livelli permette una gestione più snella ed efficiente della pianificazione, che si riduce al calcolo dei sottopiani necessari al completamento delle singole macro-azioni presentate di volta in volta dal pianificatore di alto livello.
move(a,g1),move(b,g2),move(c,g3) sarà allora tradotta in una stringa della forma
(Forward(a),5),(Forward(b),5),(Forward(c),5)se tutti gli agenti sono rivolti verso i rispettivi goal g1, g2 e g3 e debbano quindi spostarsi semplicemente in avanti.Il vettore totale assumerà un aspetto simile a
[... (Wait(a),0),(Turn 90(b),8),(Forward(c),5) ... (Forward(a),5),(Forward(b),5),(Forward(c),5)]Il valore di tempo massimo è calcolato in base all'azione più lunga tra quelle in esecuzione (ovvero presenti nella stringa) secondo questa tabella dei tempi
Per la pianificazione ci siamo affidati a DLV, il pianificatore presentato durante il corso. Come accennato nell'intreduzione, essendo il problema piuttosto complesso, se non suddiviso tende a diventare troppo pesante da gestire e la pianificazione risultante sarà di conseguenza troppo lenta. Abbiamo quindi adottato una politica di tipo divide et impera, in cui ad ogni livello di pianificazione sono affidati compiti specifici:
DLV è un sistema di programmazione basato sulla programmazione logica disgiuntiva che implementa la semantica a modelli stabili.
È nato al fine di facilitare lo sviluppo di applicazioni knowledge-based. Supporta sia la negazione come fallimento che la negazione classica, i vincoli di integrità e include un buon numero di funzioni aritmetiche.
In particolare abbiamo utilizzato DLV-K, che implementa un frontend per il linguaggio di pianificazione K nel sistema DLV, che ben si presta alla rappresentazione di "conoscenza incompleta". Si rimanda al sito ufficiale per maggiori informazioni.
La pianificazione ad alto livello si basa sulla conoscenza del mondo fornita nei file alto_livello.bk (statica) e alto_livello.plan (dinamica). In questi file vengono definiti gli agenti, gli scaffali e i luoghi interessanti del mondo fisico in cui si muovono i robot.
Il pianificatore non conosce la topografia completa del mondo, ma semplicemente un elenco di luoghi particolari, tra i quali è possibile eseguire particolari mosse, insieme alle rispettive distanze. Queste sono calcolate dinamicamente (cfr. la specifica delle distanze nel file sorgente) a seconda dello stato corrente del mondo.
La pianificazione si limita a questo livello a decidere quali scaffali debbano essere spostati, dove e quali agenti siano più indicati a farlo. Le regole generali seguite durante la pianificazione sono le seguenti e sono state pensate affinchè i cammini seguiti dagli agenti siano i più corti possibile, compatibilmente con l'obiettivo finale (si vedano i commenti all'interno dei file sorgenti per maggiori dettagli):
actions:
% l'agente A attende senza eseguire alcuna azione. Necessaria per
% evitare l'esecuzione di azioni inutilmente costose.
wait(A) requires agent(A) costs 0.
% l'agente in L1 raggiunge lo scaffale in L2 e lo carica
pick_up(A,S) requires agent(A), shelf(S) costs 2.
% l'agente A si muove in posizione L posto L
move(A,L) requires agent(A), place(L) costs 1.
wait(A): l'agente A rimane fermo.pick_up(A,S): l'agente A raccoglie lo scaffale S.move(A,L): l'agente A si muove nella posizione L.
fluents:
% fluenti che indicano la direzione in cui uno scaffale è bloccato
% es. BN(A,B) indica che A blocca B a nord. Solo gli scaffali possono
% essere bloccati
BN(O,S) requires object(O), shelf(S).
BS(O,S) requires object(O), shelf(S).
BE(O,S) requires object(O), shelf(S).
BO(O,S) requires object(O), shelf(S).
% La distanza è definita come fluente in quanto può cambiare a seconda
% dei blocchi presenti sugli scaffali (si ricordi che un agente non
% può attraversare posizioni nelle quali sia presente uno scaffale)
dist(L1,L2,D) requires place(L1), place(L2), #int(D).
% l'agente A ha caricato lo scaffale S
has_s(A,S) requires agent(A), shelf(S).
% lo scaffale S è in L
shelf_at(S,L) requires shelf(S), place(L).
% l'agente A è in L
agent_at(A,L) requires agent(A), place(L).
% lo scaffale S è bloccato
blocked(S) requires shelf(S).
% lo scaffale S va portato nel goal G
to_goal(S,G) requires shelf(S), is_goal(G).
% fluente di supporto, utilizzato per concisione, necessario nella
% definizione dei vincoli di eseguibilità per alcune azioni
free(B) requires is_buffer(B).
Diamo una breve spiegazione dei fluenti meno espliciti.
BN(O,S): l'oggetto O blocca da nord lo scaffale S.to_goal(S,G): lo scaffale S va portato nel goal G.blocked(S): lo scaffale S è bloccato.free(B): il buffer B è libero.% spostamento degli agenti caused agent_at(A,L) after move(A,L). caused -agent_at(A,L) after move(A,_), agent_at(A,L). caused agent_at(A,L) after pick_up(A,S), shelf_at(S,L). caused -agent_at(A,L) after pick_up(A,_), agent_at(A,L).In questo caso si può notare come la posizione di un agente sia aggiornata ogniqualvolta esso si muova nel mondo.
% lo scaffale non si può prelevare se è bloccato nonexecutable pick_up(_,S) if blocked(S).L'azione di pick_up è proibita qualora il fluente blocked non sussista nell'istante di esecuzione della mossa.
goal: shelf_at(a,g1), shelf_at(b,g2) ?Il piano ricavato è il seguente (eventuali piani equivalenti sono come detto scartati)
PLAN: pick_up(a,s4):2, pick_up(b,s5):2, wait(c); move(a,b1):1, move(b,b3):1, wait(c); pick_up(a,s1):2, pick_up(b,s2):2, wait(c); move(a,g1):1, move(b,g2):1, wait(c) COST: 12con un costo molto basso, sia per la parte relativa all'istanziazione sia per quanto concerne i tempi di calcolo della soluzione, come si può notare dalle statistiche d'esecuzione.
Residual Instantiation Rules : 29610 Constraints : 21912 Weak Constraints : 190 Structural Size : 353260 Maximum recursion level : 4 Choice Points : 27 Answer sets printed : 1 Time for first answer set : n/a (including instantiation) Time for all answer sets : n/a (including instantiation) Instantiation time : 0.891266 Model Generator time : 0.458150 Model Checker time : 0.000004 Total Model Check time : 0.000004 Partial Model Check time : 0.000000Si noti come grazie all'assegnazione di costi maggiori alle azioni di pick_up e move l'agente c rimanga fermo durante tutta l'esecuzione del piano.
Residual Instantiation Rules : 29610 Constraints : 21912 Weak Constraints : 190 Structural Size : 353260 Maximum recursion level : 4 Choice Points : 71 Answer sets printed : 6 Time for first answer set : 1.779602 (including instantiation) Time for all answer sets : 2.587071 (including instantiation) Instantiation time : 0.876516 Model Generator time : 1.099534 Model Checker time : 0.000009 Total Model Check time : 0.000009 Partial Model Check time : 0.000000con una perdita di prestazioni praticamente nulla. Questi livelli sono stati raggiunti soprattutto istanziando ogni variabile il più possibile a livello di regole, risparmiando in questo modo al pianificatore una lunga ricerca all'interno di tutte le istanziazioni possibili ma non valide e aggiungendo quanti più vincoli possibili all'eseguibilità delle mosse ed all'aggiornamento dei fluenti, in quest'ultimo caso evitando la computazione di piani non validi o senza sbocco.
La pianificazione a basso livello si basa sulla conoscenza del mondo fornita dal file basso_livello.bk . In questo file vengono infatti definiti gli agenti, gli scaffali e soprattutto le adiacenze tra i nodi che compongono il mondo fisico dei robot. Il seguente schema illustra lo stato iniziale del modello.
mm s1 - s2 - s3 mm Dove:
|| || || ° mm sono nodi non raggiungibili, muri
mm s4 - s5 - s6 mm ° sX sono i 6 Scaffali
|| || || ° bX sono i 4 Buffer
b9 - 10 - 11 - 12 - b13 ° a b c sono i 3 agenti
|| || || ° || rappresenta adj verticale
b4 - 05 - 06 - 07 - b8 ° - rappresenta adj orizzontale
|| || ||
mm a b c mm
Come possiamo vedere a basso livello abbiamo conoscenza completa del mondo. Possiamo permettercelo senza appesantire la pianificazione in quanto il pianificatore di basso livello cerca il path migliore per raggiungere i subgoal che altro non sono che le macroazioni dall'alto livello. La ricerca del path avviene tramite le azioni, i fluenti e le clausole definite in basso_livello.plan.actions: wait(A) requires agente(A) costs 0. move(A,P1,P2) requires agente(A), punto(P1), punto(P2) costs 1. pick_up(A,P,P1) requires agente(A),punto(P),punto(P1) costs 2.
move(A,P1,P2): muove l'agente A da P1 a P2. Move ha costo 1 wait(A): l'agente A sta fermo. Wait ha costo 0 pick_up(A,P,P1): l'agente A, che si trova in P, prende lo scaffale che è nel punto P1 se P è adiacente a P1. La presenza dello scaffale ci è assicurata dall'alto livello. Pick up ha costo 2
fluents:
at(O,P) requires object(O), punto(P).
picked(A,P) requires agente(A), punto(P).
always:
executable wait(A).
executable move(A,P,P1) if adiacente(P,P1), at(A,P).
executable pick_up(A,P,P1) if at(A,P), adiacente(P,P1), at(S,P1), scaffale(S).
%Non ci si puo' spostare in un punto occupato
nonexecutable move(A,P,P1) if at(O,P1), object(O).
at(O,P): l'oggetto O si trova nella posizione P. picked(A,P): l'agente A ha preso lo scaffale in posizione P. move sia possible solo tra due punti adiacenti e se il punto di arrivo è libero, ovvero non occupato da altri agenti o scaffali.pick_up è attuabile solo se l'agente si trova in una casella adiacente a quella nella quale si trova lo scaffale da prendere.goal: picked(a,18), at(b,13) ?generato da un subgoal dell'alto livello del tipo
wait(c) move(b,b3),pick_up(a,s2) ,
e una condizione iniziale così definita
initially: at(a,1). at(c,3). at(s1,17). at(s2,18). at(s3,19). at(s4,14). at(s6,16). at(b,15) .che rappresenta la posizioni degli agenti e degli scaffali, il piano restituito è il seguente:
wait(c), move(a,1,2):1, move(b,15,11):1; wait(c), move(a,2,6):1, move(b,11,12):1; wait(c), move(a,6,11):1, move(b,12,13):1; wait(b), wait(c), move(a,11,15):1; wait(b), wait(c), pick_up(a,15,18):2 COST: 9come si puo' notare il percorso trovato è il più breve e dal costo più basso. In questo caso le azioni compiute per eseguire il piano sono cinque, che è tipicamente il numero medio di azioni necessarie. Il costo del piano è 9, anche questo un valore vicino alla media.
Residual Instantiation Rules : 6567 Constraints : 130 Weak Constraints : 728 Structural Size : 16235 Maximum recursion level : 7 Choice Points : 25 Answer sets printed : 1 Time for first answer set : n/a (including instantiation) Time for all answer sets : n/a (including instantiation) Instantiation time : 0.424334 Model Generator time : 1.149978 Model Checker time : 0.000007 Total Model Check time : 0.000007 Partial Model Check time : 0.000000si può notare che la ricerca è piuttosto veloce e lo spazio di dimensioni accettabili, considerando l'ottimalità del cammino calcolato. Va inoltre ricordato che i tempi sono comunque dipendenti dalla configurazione della macchina utilizzata.
La flotta è composta da numero tre Lego Mindstorm NXT ® 2. Tutti i componenti hanno identiche caratteristiche tecniche. Il compito di queste unità è quello di eseguire il piano calcolato dal pianificatore; per rendere più comoda la programmazione dei robot abbiamo installato su ognuno di essi il firmware LejOS 3 che permette di utilizzare un linguaggio Java-like in sostituzione del simil C fornito dalla Lego. Le principali azioni svolte dal singolo agente sono cinque:
È il modello di robot utilizzato, in particolare si tratta di Lego Mindstorm NXT ®. Sono dotati di un firmware che permette la stesura del codice in un linguaggio proprietario simile al C, ma esiste la possibilità di cambiare il firmware abbastanza agilmente per adottarne uno dei molti OpenSource disponibili.
Oltre al processore, sono Lego anche gli altri pezzi utilizzati nella costruzione dei tre agenti.
È un linguaggio OpenSource Java-like, che ha permesso di estendere le capacità dei robot rispetto al linguaggio nativo. La versione utilizzata è la distribuzione 0.5 Beta, non la più recente (è da poco disponibile la versione 0.6) ma senza dubbio la più stabile. Piccola pecca di questa versione è l'assenza di switch statement e di molte funzioni di gestione file e stringhe che sono invece supportate nella versione più recente.
Tutti i robot hanno le stesse caratteristiche. Ogni agente sfrutta:
Il codice eseguito dagli agenti è diviso in due file: Lifter.java e Plan.java.
Quest'ultimo consiste di una classe di supporto contenente un vettore ordinato di azioni che l'agente dovrà eseguire per portare a termine il suo compito. Contiene inoltre il metodo getPlan() che restituisce il suddetto vettore.
Lifter.plan è invece il programma che gestisce effettivamente l'agente. Il corpo del programma è composto da un sistema di controllo "comportamentale" basato su oggetti di tipo behavior. I comportamenti disponibili includono:
Drive Forward e Offline è intuitivo e di supporto, mentre in Lift si svolge realmente l'esecuzione del piano. Lift richiama il metodo getAct(act), il quale comunica al robot la prossima esecuzione da eseguire. L'unica nota stonata del codice è che LeJOS ad oggi non supporta ancora gli switch statement, conseguentemente per la scelta delle azioni ci si deve affidare ad una serie poco elegante di costrutti if-else in cascata. Fortunatamente nel nostro caso le combinazioni possibili non sono molte e quindi la leggibilità del codice non ne ha risentito particolarmente.subString o stringTokenizer. Le scarse possibilità ci hanno quindi costretto a scrivere codice un po' criptico in alcuni punti. I miglioramenti da apportare riguardano sia l'aspetto implementativo
che la pianificazione.
Dal punto di vista della pianificazione si potrebbe migliorare la
scalabilità: la dimensione della griglia e il numero di scaffali
incidono notevolmente sulle prestazioni e talvolta rendono impossibile
la soluzione del problema. Il numero di agenti concorrenti gestito attualmente è inoltre limitato ad un massimo di tre.
Un altro aspetto da migliorare è la parte che fa da collante tra i livelli di pianificazione, ovvero il file machine_code.py: la riscrittura del goal e delle condizioni iniziali non è infatti del tutto robusta, con una gestione della procedura effettuata ad un livello molto basso. Sarebbe opportuno inserire una verifica dell'input prima di procedere alla riscrittura.
Dal punto di vista implementativo, sarebbe da valutare l'uso di bluetooth fra i vari agenti come strumento di sincronizzazione in sostituzione dei ritardi utilizzati dall'implementazione corrente. La comunicazione via bluetooth comporta tuttavia latenze significative, e sarebbe perciò opportuno stabilire una connessione persistente all'avvio mantenendola sino al termine dell'esecuzione.In questa appendice riportiamo il codice completo dei file di pianificazione.
%
% Pianificatore ad alto livello che stabilisce unicamente i ruoli dei vari
% agenti (chi prende cosa e dove lo porta); la pianificazione delle azioni
% vere e proprie viene delegata ad un pianificatore di livello più basso.
% Gestisce concorrentemente tre agenti.
%
actions:
% l'agente A attende senza eseguire alcuna azione. Necessaria per
% evitare l'esecuzione di azioni inutilmente costose.
wait(A) requires agent(A) costs 0.
% l'agente in L1 raggiunge lo scaffale in L2 e lo carica
pick_up(A,S) requires agent(A), shelf(S) costs 2.
% l'agente A si muove in posizione L posto L
move(A,L) requires agent(A), place(L) costs 1.
fluents:
% fluenti che indicano la direzione in cui uno scaffale è bloccato
% es. BN(A,B) indica che A blocca B a nord. Solo gli scaffali possono
% essere bloccati
BN(O,S) requires object(O), shelf(S).
BS(O,S) requires object(O), shelf(S).
BE(O,S) requires object(O), shelf(S).
BO(O,S) requires object(O), shelf(S).
% La distanza è definita come fluente in quanto può cambiare a seconda
% dei blocchi presenti sugli scaffali (si ricordi che un agente non
% può attraversare posizioni nelle quali sia presente uno scaffale)
dist(L1,L2,D) requires place(L1), place(L2), #int(D).
% l'agente A ha caricato lo scaffale S
has_s(A,S) requires agent(A), shelf(S).
% lo scaffale S è in L
shelf_at(S,L) requires shelf(S), place(L).
% l'agente A è in L
agent_at(A,L) requires agent(A), place(L).
% lo scaffale S è bloccato
blocked(S) requires shelf(S).
% lo scaffale S va portato nel goal G
to_goal(S,G) requires shelf(S), is_goal(G).
% fluente di supporto, utilizzato per concisione, necessario nella
% definizione dei vincoli di eseguibilità per alcune azioni
free(B) requires is_buffer(B).
always:
% buffer libero
caused free(B) if not shelf_at(s1,B), not shelf_at(s2,B), not shelf_at(s3,B),
not shelf_at(s4,B), not shelf_at(s5,B), not shelf_at(s6,B).
%%%%% EFFETTI DELLE AZIONI %%%%%
% fluente di supporto utilizzato per concisione
% gli scaffali risultano bloccati sino a che non sono liberi lato sud.
% Questo obbliga gli agenti a raccoglierli solo frontalmente.
caused blocked(S) if BS(_,S).
% spostamento degli scaffali
caused shelf_at(S,L) after move(A,L), has_s(A,S).
caused -shelf_at(S,L) after move(A,_), has_s(A,S), shelf_at(S,L).
% spostamento degli agenti
caused agent_at(A,L) after move(A,L).
caused -agent_at(A,L) after move(A,_), agent_at(A,L).
caused agent_at(A,L) after pick_up(A,S), shelf_at(S,L).
caused -agent_at(A,L) after pick_up(A,_), agent_at(A,L).
% trasporto degli scaffali
caused has_s(A,S) after pick_up(A,S).
caused -has_s(A,S) after move(A,L), has_s(A,S).
% quando un agente sposta nel buffer uno scaffale che ne blocca
% un altro, questo è libero (dal lato precedentemente bloccato). Al
% contempo anche quello spostato si libera (si veda la regola di
% simmetria sottostante)
caused -BN(S1,S2) after pick_up(_,S1), BN(S1,S2).
caused -BS(S1,S2) after pick_up(_,S1), BS(S1,S2).
caused -BO(S1,S2) after pick_up(_,S1), BO(S1,S2).
caused -BE(S1,S2) after pick_up(_,S1), BE(S1,S2).
% regola di simmetria
caused -BN(S1,S2) if -BS(S2,S1).
caused -BE(S1,S2) if -BO(S2,S1).
% il muro non blocca più gli scaffali spostati
caused -BN(m,S) after pick_up(_,S), BN(m,S).
caused -BS(m,S) after pick_up(_,S), BS(m,S).
caused -BO(m,S) after pick_up(_,S), BO(m,S).
caused -BE(m,S) after pick_up(_,S), BE(m,S).
% simmetria della distanza
caused dist(X,Y,D) if dist(Y,X,D).
% definizione delle distanze.
% Notare come le distanze verso le posizioni iniziali degli scaffali
% siano definite unicamente se uno di essi si trovi effettivamente in
% una di tali posizioni, eliminando molte distanze che risulterebbero
% altrimenti inutili
% da g1 a...
dist(g1,b1,3).
dist(g1,b2,2).
dist(g1,b3,5).
dist(g1,b4,4).
caused dist(g1,ini4,3) if shelf_at(_,ini4).
caused dist(g1,ini5,4) if shelf_at(_,ini5).
caused dist(g1,ini6,5) if shelf_at(_,ini6).
% da g2 a...
dist(g2,b1,4).
dist(g2,b2,3).
dist(g2,b3,4).
dist(g2,b4,3).
caused dist(g2,ini4,4) if shelf_at(_,ini4).
caused dist(g2,ini5,3) if shelf_at(_,ini5).
caused dist(g2,ini6,4) if shelf_at(_,ini6).
% da g3 a...
dist(g3,b1,5).
dist(g3,b2,4).
dist(g3,b3,3).
dist(g3,b4,2).
caused dist(g3,ini4,5) if shelf_at(_,ini4).
caused dist(g3,ini5,4) if shelf_at(_,ini5).
caused dist(g3,ini6,3) if shelf_at(_,ini6).
% da b1 a...
caused dist(b1,ini4,2) if shelf_at(_,ini4).
caused dist(b1,ini5,3) if shelf_at(_,ini5).
caused dist(b1,ini6,4) if shelf_at(_,ini6).
% da b3 a...
caused dist(b3,ini4,4) if shelf_at(_,ini4).
caused dist(b3,ini5,3) if shelf_at(_,ini5).
caused dist(b3,ini6,2) if shelf_at(_,ini6).
% definizione delle distanze per la fila superiore di scaffali
% (le definizioni commentate sono situazioni che non si verificheranno
% mai ma sono state lasciate per completezza)
caused dist(g1,ini1,4) if shelf_at(S,ini1), not blocked(S).%BS(s4,S).
%caused dist(g1,ini1,6) if shelf_at(S,ini1), BS(s4,S), not BE(s2,S), not shelf_at(s5,ini5).
%caused dist(g1,ini1,8) if shelf_at(S,ini1), BS(s4,S), not BE(s2,S), shelf_at(s5,ini5).
caused dist(g1,ini2,5) if shelf_at(S,ini2), not blocked(S).%BS(s5,S).
%caused dist(g1,ini2,5) if shelf_at(S,ini2), BS(s5,S), not BO(s1,S).
%caused dist(g1,ini2,7) if shelf_at(S,ini2), BS(s5,S), BO(s1,S), not BE(s3,S).
caused dist(g1,ini3,6) if shelf_at(S,ini3), not blocked(S).
caused dist(g2,ini1,5) if shelf_at(S,ini1), not blocked(S).%BS(s4,S).
%caused dist(g2,ini1,5) if shelf_at(S,ini1), BS(s4,S), not BE(s2,S), not shelf_at(s5,ini5).
%caused dist(g2,ini1,7) if shelf_at(S,ini1), BS(s4,S), not BE(s2,S), shelf_at(s5,ini5).
caused dist(g2,ini2,4) if shelf_at(S,ini2), not blocked(S).%BS(s5,S).
%caused dist(g2,ini2,6) if shelf_at(S,ini2), BS(s5,S), not BE(s3,S).
%caused dist(g2,ini2,6) if shelf_at(S,ini2), BS(s5,S), not BO(s1,S).
caused dist(g2,ini3,5) if shelf_at(S,ini3), not blocked(S).%BS(s6,S).
%caused dist(g2,ini3,5) if shelf_at(S,ini3), BS(s6,S), not BO(s2,S), not shelf_at(s5,ini5).
%caused dist(g2,ini3,7) if shelf_at(S,ini3), BS(s6,S), not BO(s2,S), shelf_at(s5,ini5).
caused dist(g3,ini1,6) if shelf_at(S,ini1), not blocked(S).
caused dist(g3,ini2,5) if shelf_at(S,ini2), not blocked(S).%BS(s5,S).
%caused dist(g3,ini2,5) if shelf_at(S,ini2), BS(s5,S), not BE(s3,S).
%caused dist(g3,ini2,7) if shelf_at(S,ini3), BS(s5,S), BE(s3,S), not BO(s1,S).
caused dist(g3,ini3,4) if shelf_at(S,ini3), not blocked(S).%BS(s6,S).
%caused dist(g3,ini3,6) if shelf_at(S,ini3), BS(s6,S), not BO(s2,S), not shelf_at(s5,ini5).
%caused dist(g3,ini3,8) if shelf_at(S,ini3), BS(s6,S), not BO(s2,S), shelf_at(s5,ini5).
%caused dist(b1,ini1,3) if shelf_at(S,ini1), not shelf_at(s4,ini4).
caused dist(b1,ini1,3) if shelf_at(S,ini1), not blocked(S).%BS(s4,S).
%caused dist(b1,ini1,5) if shelf_at(S,ini1), BS(s4,S), not BE(s2,S), not shelf_at(s5,ini5).
%caused dist(b1,ini1,7) if shelf_at(S,ini1), BS(s4,S), not BE(s2,S), shelf_at(s5,ini5).
caused dist(b1,ini2,4) if shelf_at(S,ini2), not blocked(S).%BS(s5,S).
%caused dist(b1,ini2,4) if shelf_at(S,ini2), BS(s5,S), not BO(s1,S).
%caused dist(b1,ini2,6) if shelf_at(S,ini2), BS(s5,S), BO(s1,S), not BE(s3,S).
caused dist(b1,ini3,5) if shelf_at(S,ini3), not blocked(S).
% la distanza da b2 alle posizioni iniziali è automaticamente definita
% in un passo in più rispetto a b1
caused dist(b2,L,D2) if is_initial(L), dist(b1,L,D1), D2=D1+1.
caused dist(b3,ini3,3) if shelf_at(S,ini3), not blocked(S).%BS(s6,S).
%caused dist(b3,ini3,5) if shelf_at(S,ini3), BS(s6,S), not BO(s2,S), not shelf_at(s5,ini5).
%caused dist(b3,ini3,7) if shelf_at(S,ini3), BS(s6,S), not BO(s2,S), shelf_at(s5,ini5).
caused dist(b3,ini2,4) if shelf_at(S,ini2), not blocked(S).%BS(s5,S).
%caused dist(b3,ini2,4) if shelf_at(S,ini2), BS(s5,S), not BE(s3,S).
%caused dist(b3,ini2,6) if shelf_at(S,ini2), BS(s5,S), BE(s3,S), not BO(s1,S).
caused dist(b3,ini1,5) if shelf_at(S,ini1), not blocked(S).
% la distanza da b4 alle posizioni iniziali è automaticamente definita
% in un passo in più rispetto a b3
caused dist(b4,L,D2) if is_initial(L), dist(b3,L,D1), D2=D1+1.
%%%%% PRECONDIZIONI %%%%%
% un agente può sempre aspettare
executable wait(A).
% si veda la sezione vincoli per informazioni riguardanti la non
% eseguibilità dell'azione pick_up
executable pick_up(A,S).
% un agente si muove solo quando trasporta uno scaffale a meno che non
% occupi una posizione di goal nella quale un'altro scaffale debba
% trovarsi (in questo caso si muoverà nel buffer più vicino)
executable move(A,L) if has_s(A,_).
executable move(A,L2) if is_buffer(L2), agent_at(A,L1), is_goal(L1), to_goal(S,L1),
dist(L1,L2,D1), is_buffer(L3), dist(L1,L3,D2), D1<D2, is_buffer(L4), dist(L1,L4,D3),
D1L3, L2<>L4, L2<>L5, L3<>L4, L3<>L5, L4<>L5.
%%%%% VINCOLI SULL'ESEGUIBILITÀ DELLE AZIONI %%%%%
%%%%% MOVE %%%%%
% non si può spostare uno scaffale dove è presente un altro scaffale
nonexecutable move(_,L) if shelf_at(_,L).
% non è possibile spostare uno scaffale nel goal se non deve essere
% `consegnato`
nonexecutable move(A,L) if has_s(A,S), is_goal(L), not to_goal(S,L).
% non si possono spostare gli scaffali nella zona di partenza
nonexecutable move(A,L) if is_initial(L).
%%%%% PICK_UP %%%%%
% lo scaffale non si può prelevare se è bloccato
nonexecutable pick_up(_,S) if blocked(S).
% non si possono caricare due scaffali contemporaneamente
nonexecutable pick_up(A,_) if has_s(A,_).
% due agenti non possono caricare lo stesso scaffale (necessario in
% quanto la pick_up non aggiorna la posizione dello scaffale)
nonexecutable pick_up(A1,S) if has_s(A2,S), A1<>A2.
% lo scaffale non si può prelevare se è nel goal
nonexecutable pick_up(_,S) if shelf_at(S,L), is_goal(L).
% truccone per costringere un agente che ha raccolto uno scaffale a
% spostarlo
nonexecutable wait(A) if has_s(A,_).
%%%%% CONTEMPORANEITÀ DELLE AZIONI %%%%%
% un'agente non può eseguire due mosse contemporaneamente
nonexecutable move(A,_) if pick_up(A,_).
nonexecutable move(A,_) if wait(A).
nonexecutable move(A,L1) if move(A,L2), L1<>L2.
nonexecutable pick_up(A,_) if move(A,_).
nonexecutable pick_up(A,_) if wait(A).
nonexecutable wait(A) if pick_up(A,_).
nonexecutable wait(A) if move(A,_).
%%%%% VINCOLI %%%%%
% la pick_up non può essere eseguita quando:
% l'agente A1 ha raccolto uno scaffale al quale non era il più vicino,
% e l'agente più vicino, all'istante successivo, si trova in una
% posizione che non sia un buffer (necessario per le pick_up di
% liberamento degli scaffali della fila posteriore)
caused false if agent_at(A2,L), not is_buffer(L) after pick_up(A1,S), agent_at(A1,L1),
is_goal(L1), agent_at(A2,L2), is_goal(L2), shelf_at(S,L3), is_initial(L3), dist(L1,L3,D1),
dist(L2,L3,D2), D1>D2, A1<>A2, L<>L1, L<>L3, L1<>L2, L1<>L3, L2<>L3.
% l'agente A1 ha raccolto uno scaffale al quale non era il più vicino,
% e l'agente più vicino si trovava nello stesso buffer prima e dopo
% l'esecuzione della mossa (necessario per le pick_up successive al
% liberamento della fila posteriore di scaffali)
caused false if agent_at(A2,L2), is_buffer(L2) after pick_up(A1,S), agent_at(A1,L1),
agent_at(A2,L2), shelf_at(S,L3), dist(L1,L3,D1), dist(L2,L3,D2), D1>D2, A1<>A2, L1<>L2,
L1<>L3, L2<>L3.
% l'agente A1 ha raccolto uno scaffale al quale non era il più vicino,
% e l'agente più vicino di lui non era il più vicino in assoluto, se
% tutti gli agenti partono da un buffer (necessario per evitare che
% dopo i primi pick_up agenti raccolgano scaffali a loro non vicini
% senza motivo)
caused false after pick_up(A1,S), agent_at(A1,L1), is_buffer(L1), agent_at(A2,L2),
is_buffer(L2), agent_at(A3,L3), is_buffer(L3), shelf_at(S,L4), is_initial(L4),
dist(L1,L4,D1), dist(L2,L4,D2), D1>D2, dist(L3,L4,D3), D2<D3, A1<>A2, A1<>A3, L1<>L2,
L1<>L3, L1<>L4, L2<>L4, L3<>L4, L2<>L3, A2<>A3.
% l'agente A1 ha raccolto uno scaffale al quale non era il più vicino,
% e l'agente più vicino di lui non era il più vicino in assoluto, se
% il secondo ed il terzo agente partono da un buffer e il primo da un
% goal (necessario per evitare che nel caso di soli due scaffali da
% portare nel goal il terzo agente raccolga scaffali non vicini a lui
% senza motivo)
caused false after pick_up(A1,S), agent_at(A1,L1), is_goal(L1), agent_at(A2,L2),
is_buffer(L2), agent_at(A3,L3), is_buffer(L3), shelf_at(S,L4), is_initial(L4),
dist(L1,L4,D1), dist(L2,L4,D2), D1>D2, dist(L3,L4,D3), D2<=D3, A1<>A2, A1<>A3, L1<>L2,
L1<>L3, L1<>L4, L2<>L4, L3<>L4.
% la move non può essere eseguita quando:
% l'agente A1 si è spostato in un buffer che non è il più vicino e il
% buffer che sarebbe più vicino è ancora libero dopo l'esecuzione della
% mossa
caused false if free(B2) after move(A1,B1), is_buffer(B1), agent_at(A1,L1), is_initial(L1),
dist(L1,B2,D1), dist(L1,B1,D2), D1<D2, B1<>B2.
% l'agente A1 si è spostato in un buffer che non è il più vicino e
% l'agente che ha occupato il buffer che sarebbe più vicino non ha
% occupato il buffer a lui più vicino
caused false if free(B3) after move(A1,B1), is_buffer(B1), agent_at(A1,L1), is_initial(L1),
dist(L1,B1,D2), dist(L1,B2,D1), D1<D2, agent_at(A2,L2), is_initial(L2), is_buffer(B3),
dist(L2,B2,D4), dist(L2,B3,D3), D3==D4, B1<>B2, B1<>B3, B2<>B3, A1<>A2.
% un'agente non può trasportare due scaffali contemporaneamente
caused false if has_s(A,S1), has_s(A,S2), S1<>S2.
% due agenti non possono caricare lo stesso scaffale
caused false if has_s(A1,S), has_s(A2,S), A1<>A2.
% due agenti non possono trovarsi nella medesima posizione
caused false if agent_at(A1,L), agent_at(A2,L), A1<>A2.
%%%%% INERZIALI %%%%%
inertial has_s(A,S).
inertial shelf_at(S,L).
inertial agent_at(A,L).
inertial to_goal(S,L).
inertial BN(O,S).
inertial BS(O,S).
inertial BO(O,S).
inertial BE(O,S).
% L'oggetto "mm" è il muro, non può essere spostato.
%
% mm mm mm mm mm
% mm s1 s2 s3 mm
% mm s4 s5 s6 mm
% b1 __ __ __ b3
% b2 __ __ __ b4
% mm a b c mm
initially:
% blocchi
BN(m,s1).
BN(m,s2).
BN(m,s3).
BO(m,s1).
BO(m,s4).
BE(m,s3).
BE(m,s6).
BS(s4,s1).
BS(s5,s2).
BS(s6,s3).
BO(s1,s2).
BO(s4,s5).
BO(s2,s3).
BO(s5,s6).
% simmetria dei blocchi
caused BN(S1,S2) if BS(S2,S1).
caused BE(S1,S2) if BO(S2,S1).
% posizionamento degli scaffali
shelf_at(s1,ini1).
shelf_at(s2,ini2).
shelf_at(s3,ini3).
shelf_at(s4,ini4).
shelf_at(s5,ini5).
shelf_at(s6,ini6).
% posizionamento degli agenti
agent_at(a,g1).
agent_at(b,g2).
agent_at(c,g3).
% scaffali che possono essere portati in un goal
to_goal(s1,g1).
to_goal(s2,g2).
%to_goal(s3,g1).
goal:
shelf_at(s1,g1) , shelf_at(s2,g2) ?%, shelf_at(s3,g1) ?
% L'oggetto "m" è il muro, non può essere spostato. % % mm mm mm mm mm % mm s1 s2 s3 mm % mm s4 s5 s6 mm % b1 __ __ __ b2 % b3 __ __ __ b4 % mm a b c mm wall(m). agent(a). agent(b). agent(c). shelf(s1). shelf(s2). shelf(s3). shelf(s4). shelf(s5). shelf(s6). object(O) :- wall(O). object(O) :- shelf(O). object(O) :- agent(O). is_goal(g1). is_goal(g2). is_goal(g3). is_buffer(b1). is_buffer(b2). is_buffer(b3). is_buffer(b4). place(L) :- is_buffer(L). place(L) :- is_goal(L). place(L) :- is_initial(L). % posizioni iniziali degli scaffali is_initial(ini1). is_initial(ini2). is_initial(ini3). is_initial(ini4). is_initial(ini5). is_initial(ini6).
actions:
wait(A) requires agente(A) costs 0.
move(A,P1,P2) requires agente(A), punto(P1), punto(P2) costs 1.
pick_up(A,P,P1) requires agente(A),punto(P),punto(P1) costs 2.
fluents:
at(O,P) requires object(O), punto(P).
picked(A,P) requires agente(A), punto(P).
always:
executable wait(A).
executable move(A,P,P1) if adiacente(P,P1), at(A,P).
executable pick_up(A,P,P1) if at(A,P), adiacente(P,P1), at(S,P1), scaffale(S).
%Non ci si puo' spostare in un punto occupato
nonexecutable move(A,P,P1) if at(O,P1), object(O).
nonexecutable pick_up(A,_,_) if picked(A,_).
%Evitiamo doppie azioni da parte di un agente
nonexecutable wait(A) if move(A,_,_).
nonexecutable wait(A) if pick_up(A,_,_).
nonexecutable pick_up(A,_,_) if move(A,_,_).
nonexecutable pick_up(A,_,_) if wait(A).
nonexecutable move(A,_,_) if pick_up(A,_,_).
nonexecutable move(A,_,_) if wait(A).
caused at(A1,P1) after move(A1,_,P1).
caused at(A1,P1) after pick_up(A1,_,P1).
caused -at(A1,P) after move(A1,P,_).
caused -at(A1,P) after pick_up(A1,P,_).
caused picked(A,P1) after pick_up(A,_,P1).
caused false if at(A,P1), at(A,P2), P1<>P2.
caused false if at(A1,P), at(A2,P), agente(A1), agente(A2), A1<>A2.
caused false if at(S1,P), at(S2,P), scaffale(S1), scaffale(S2), S1<>S2.
% un agente non può muoversi in due nodi differenti contemporaneamente
caused false after move(A1,P1,P), move(A1,P1,P2), P<>P2.
inertial at(O,P).
inertial picked(A,P).
% i nodi del grafo sono semplici interi, adiacenti secondo % la definizione più sotto. punto(D) :- #int(D). adiacente(X,Y) :- adiacente(Y,X). object(O) :- agente(O). object(O) :- scaffale(O). % istanza a titolo di esempio % % mm s1 - s2 - s3 mm Dove: % || || || ° mm sono nodi non raggiungibili, muri % mm s4 - s5 - s6 mm ° sX sono i 6 Scaffali % || || || ° bX sono i 4 Buffer % b19- 10 - 11 - 12 - b313 ° a b c sono i 3 agenti % || || || || || ° || rappresenta adj verticale % b24- 05 - 06 - 07 - b48 ° - rappresenta adj orizzontale % || || || % mm a b c mm agente(a). agente(b). agente(c). scaffale(s1). scaffale(s2). scaffale(s3). scaffale(s4). scaffale(s5). scaffale(s6). adiacente(1,5). adiacente(1,2). adiacente(2,6). adiacente(2,3). adiacente(3,7). adiacente(4,5). adiacente(5,6). adiacente(5,10). adiacente(6,7). adiacente(6,11). adiacente(7,8). adiacente(7,12). adiacente(9,10). adiacente(10,11). adiacente(10,14). adiacente(11,12). adiacente(11,15). adiacente(12,13). adiacente(12,16). adiacente(14,15). adiacente(14,17). adiacente(15,16). adiacente(15,18). adiacente(16,19). adiacente(17,18). adiacente(18,19).
#!/usr/bin/python
import sys,re,commands
turn_rates = {'front': {'front': '0', 'back': '180 right', 'left': '90 left', 'right': '90 right'},
'back': {'front': '180 right', 'back': '0', 'left': '90 right', 'right': '90 left'},
'left': {'front': '90 right', 'back': '90 left', 'left': '0', 'right': '180 right'},
'right': {'front': '90 left', 'back': '90 right', 'left': '180 right', 'right': '0'}
}
graph_directions = { '1': {'2': 'right', '5': 'front'},
'2': {'1': 'left', '3': 'right', '6': 'front'},
'3': {'2': 'left', '7': 'front'},
'4': {'5': 'right' , '9': 'front'},
'5': {'4': 'left', '1': 'back', '6': 'right', '10': 'front'},
'6': {'5': 'left', '2': 'back', '7': 'right', '11': 'front'},
'7': {'6': 'left', '3': 'back', '8': 'right', '12': 'front'},
'8': {'7': 'left', '13': 'front'},
'9': {'10': 'right' , '4': 'back'},
'10': {'9': 'left', '5': 'back', '11': 'right', '14': 'front'},
'11': {'10': 'left', '6': 'back', '12': 'right', '15': 'front'},
'12': {'11': 'left', '7': 'back', '13': 'right', '16': 'front'},
'13': {'8': 'back', '12': 'left'},
'14': {'10': 'back', '15': 'right', '17':'front'},
'15': {'14': 'left', '11': 'back', '16':'right', '18':'front'},
'16': {'12': 'back', '15': 'left', '19': 'front'},
'17': {'14': 'back', '18': 'right'},
'18': {'17': 'left', '15': 'back', '19':'right'},
'19': {'18': 'left', '16': 'back'}
}
action_costs = { '90 left': 8, '90 right': 8, 'wait': 0, 'pick_up': 2, '180 right': 9, '0': 5}
static_positions = { 'g1':'1', 'g2':'2', 'g3':'3', 'b1':'9', 'b2':'4', 'b3':'13','b4':'8'}
last_dir = {}
agent_wait={ 'a':False, 'b': False, 'c':False }
old_init = ""
# guarda nell'initially dove si trova l'elemento che vogliamo recuperare
def element_position(agent):
f=open('TMP_low_level.plan', 'r')
line=f.readline()
while not (re.search(r"initially:", line)):
line = f.readline()
matcher_string = f.readline()
re_at = "at\(%s,(\w+)\)" % (agent)
reobj = re.compile(re_at)
match = reobj.search(matcher_string)
if match:
result = match.group(1)
else:
result = ""
f.close
return result
# prende il modello di piano e modifica le condizioni iniziali e il goal
def rewrite_plan(initially, goal, involved_agents):
global old_init
f = open('basso_livello.plan', 'r')
g = open('TMP_low_level.plan', 'w')
# fondamentalmente e' una copia linea a linea, modificando solo le due righe
# che ci interessano
if initially != "":
line = f.readline()
while not (re.search(r"initially:", line)):
g.write(line)
line = f.readline()
#Scrive "initially :"
g.write(line)
if old_init == "" :
cur_init = f.readline().replace('\n','')
else:
#old_init=old_init.strip('.')
cur_init = old_init
new_init = cur_init.strip()
print "Old init: " + new_init
for ag in involved_agents:
if agent_wait[ag] == False:
repl_str = "at\(%s,\w+\)\." % (ag)
new_init = re.sub(repl_str, "", new_init)
else:
agent_wait[ag] = False
new_init = new_init + " " + initially
for moo in initially.split("."):
io = moo.strip(" t\(\)abcs.,")
repl_str = "at\(s\w+,%s\).\s*" % (io)
new_init = re.sub(repl_str, "", new_init)
print "Init: " + new_init
old_init = new_init
g.write(new_init)
else:
line = f.readline()
while not (re.search(r"goal:", line)):
g.write(line)
line = f.readline()
#g.write(line)
g.write("\ngoal: " + goal + "\n")
f.close()
g.close()
# pulisce i vecchi piani, permette alla funzione machine_code di operare in append mode
def blank_files():
file_a = open('../Jessica/Plan.java' , 'w')
file_b = open('../Roger/Plan.java' , 'w')
file_c = open('../Cippalippa/Plan.java' , 'w')
header="import java.util.Vector;\npublic class Plan {\npublic static Vector getPlan(){\nVector
vi= new Vector();\n"
file_a.write(header);
file_b.write(header);
file_c.write(header);
file_a.close()
file_b.close()
file_c.close()
def files_footer():
file_a = open('../Jessica/Plan.java' , 'a')
file_b = open('../Roger/Plan.java' , 'a')
file_c = open('../Cippalippa/Plan.java' , 'a')
footer="return vi;\n}\n}\n"
file_a.write(footer);
file_b.write(footer);
file_c.write(footer);
file_a.close()
file_b.close()
file_c.close()
# genera il codice che indica le operazioni da compiere: quando e di quanto girare, quanto aspettare, ecc.
def machine_code(low_plan, involved_agents):
max_time = 0
opposite = { 'front':'back', 'back':'front', 'left':'right', 'right':'left'}
turn_90_right = { 'front':'right', 'back':'left', 'left':'front', 'right':'back'}
turn_90_left = {'front':'left', 'back':'right', 'left':'back', 'right':'front'}
# ATTENZIONE: gestisce tre agenti - hardcoded
# i file vengono aperti ad ogni invocazione della funzione, sarebbe meglio spostarli in una
# funzione che li apre e restituisce la reference
file_a = open('../Jessica/Plan.java' , 'a')
file_b = open('../Roger/Plan.java' , 'a')
file_c = open('../Cippalippa/Plan.java' , 'a')
acta=""
actb=""
actc=""
agent=""
# inizializzazione, tutti gli agenti guardano verso nord
if len(last_dir) == 0:
for ag in involved_agents:
last_dir[ag] = 'front'
# divide l'output del pianificatore di basso livello in tuple di 3 azioni
tuples = low_plan.split(';')
for action_set in tuples:
reobj = re.compile(r"(?Pwait|move|pick_up)\((?P\w+,\w+,\w+|\w+,\w+|\w+)\)")
for match in reobj.finditer(action_set):
action = match.group('action')
values = match.group('values')
all_val = values.split(',')
agent = all_val[0]
if action != "wait":
if agent == "a":
acta=action
elif agent == "b":
actb=action
else:
actc=action
# se l'azione ha piu' di un argomento
if action == "move":
# se il secondo argo
node_from = all_val[1]
node_to = all_val[2]
turnrate = turn_rates[last_dir[agent]][graph_directions[node_from][node_to]]
# se la turnrate e' 0, la direzione e' la stessa
if turnrate != "0":
direction = turnrate.split(' ')[1]
# se la turnrate e' 180 la direzione viene invertita
if turnrate.split(' ')[0] == "180":
last_dir[agent] = opposite[last_dir[agent]]
else:
# se la turnrate e' 90, valuta come modificare la direzione
if direction == "right":
last_dir[agent] = turn_90_right[last_dir[agent]]
else:
last_dir[agent] = turn_90_left[last_dir[agent]]
message = "vi.addElement(\"%s\");" % (turnrate)
if action_costs[turnrate] > max_time:
max_time = action_costs[turnrate]
elif action == "pick_up":
cost=0
node_from = all_val[1]
node_to = all_val[2]
turnrate = turn_rates[last_dir[agent]][graph_directions[node_from][node_to]]
# se la turnrate e' 0, la direzione e' la stessa
if turnrate != "0":
direction = turnrate.split(' ')[1]
# se la turnrate e' 180 la direzione viene invertita
if turnrate.split(' ')[0] == "180":
last_dir[agent] = opposite[last_dir[agent]]
else:
cost=10
# se la turnrate e' 90, valuta come modificare la direzione
if direction == "right":
last_dir[agent] = turn_90_right[last_dir[agent]]
else:
last_dir[agent] = turn_90_left[last_dir[agent]]
else:
cost=7
message = "vi.addElement(\"%s\"); \nvi.addElement(\"pick_up\");" % (turnrate)
if cost > max_time:
max_time = cost
#message = "vi.addElement(\"pick_up\");"
else:
message = "vi.addElement(\"wait\");"
if action_costs['wait'] > max_time:
max_time = action_costs['wait']
if agent == "a":
file_a.write(message + "\n")
elif agent == "b":
file_b.write(message + "\n")
else:
file_c.write(message + "\n")
file_a.write("vi.addElement(\""+ str(max_time) +"\");\n")
file_b.write("vi.addElement(\""+ str(max_time) +"\");\n")
file_c.write("vi.addElement(\""+ str(max_time) +"\");\n")
max_time = 0
#print agent + " " + message
if acta == "move":
file_a.write("vi.addElement(\"leave\");\n")
if actb == "move":
file_b.write("vi.addElement(\"leave\");\n")
if actc == "move":
file_c.write("vi.addElement(\"leave\");\n")
file_a.close()
file_b.close()
file_c.close()
# cerca di generare piani di dimensione sempre maggiore, fino a quando ne viene generato uno
def low_level_planner():
length = 1
low_plan = ""
while low_plan == "":
dlv_invocation = 'dlv -FPsec -silent -planlength=%d -planminactions=3 -planmaxactions=3 -n=1
-N=20 basso_livello.bk TMP_low_level.plan' % (length)
low_plan = commands.getoutput(dlv_invocation)
print "Low Level --> Lunghezza %d" % (length)
length += 1
print low_plan
return low_plan
def call_low_level(goal,initially,involved_agents):
form_goal = goal[0:-2] + " ?"
print "chiamo pianificatore con:"
print "GOAL: " + form_goal
if initially == "":
print "INITIALLY: iniziale"
else:
print "INITIALLY: " + initially
rewrite_plan(initially, form_goal, involved_agents)
low_level = low_level_planner()
machine_code(low_level, involved_agents)
# il goal del passaggio precedente diventa l'initially del passaggio successivo
if goal != "":
initially = form_goal.replace('),',').').replace(' ?','').replace('picked','at') + "."
print "\n------------------------------------------\n"
return initially
lplan = 2
plan = ""
while plan == "":
print "High Level --> Lunghezza %d" %(lplan)
dlv_invocation ='dlv -FPsec -silent -planminactions=3 -planmaxactions=3 -planlength=%d -n=1 -N=6
alto_livello.bk alto_livello.plan' %(lplan)
plan = commands.getoutput(dlv_invocation)
lplan += 1
blank_files()
print plan + "\n"
reobj = re.compile(r"(?Ppick_up|move|wait)\((?P\w+,\w+|\w+)\)")
goal = ""
initially = ""
i = 0
involved_agents = []
rewrite_plan(goal, initially, involved_agents)
aw={ 'a':False, 'b': False, 'c':False }
for match in reobj.finditer(plan):
if i == 3:
print agent_wait
initially = call_low_level(goal, initially, involved_agents)
involved_agents = []
agent_wait=aw
aw={ 'a':False, 'b': False, 'c':False }
goal = ""
i = 0
i+=1
action = match.group('action')
values = match.group('values')
print "%d %s %s" % (i, action, values)
if len(values) > 1:
all_val = values.split(',')
involved_agents.append(all_val[0])
else:
involved_agents.append(values)
if action == "pick_up":
s_pos = element_position(all_val[1])
goal += "picked(%s,%s), " % (all_val[0], s_pos)
elif action == "move" :
goal += "at(%s,%s), " % (all_val[0], static_positions[all_val[1]])
elif action == "wait":
aw[values] = True
call_low_level(goal, initially, involved_agents)
files_footer()
In questa appendice riportiamo il codice completo dei file utilizzati della flotta.
import lejos.nxt.*;
import lejos.subsumption.*;
import lejos.navigation.*;
import java.util.*;
public class Lifter {
final static Pilot pilot = new Pilot(5.6f,16.0f,Motor.A, Motor.C, false);
final static LightSensor light = new LightSensor(SensorPort.S1);
static Vector vi = new Vector();
static int act=0;
static int times[]=null;
public static void main(String [] args)
throws Exception {
vi=Plan.getPlan();
times=new int[vi.size()];
// ATTENZIONE: I valori di luce sono restituiti in modo diverso da sensore a sensore ed in base
// all'illuminazione della stanza,quindi i valori utilizzati in questo codice sono
// da considerarsi solamente un esempio.
// Se viene riconosciuta la linea nera l'agente va avanti.La linea nera è riconosciuta in base
// al valore restituito dal sensore di luce.In questo caso se viene restituito un valore al di
// sotto di 500 allora l'agente va avanti.
Behavior DriveForward = new Behavior()
{
public boolean takeControl() {
return (light.readNormalizedValue() <= 500 );}
public void suppress() {
pilot.stop();}
public void action() {
int color=light.readNormalizedValue();
String mex="Colore : " + color;
LCD.drawString(mex,1,2);
pilot.forward();}
};
// Se l'agente esce dalla linea nera effettua delle rotazioni fino a ritrovarla.Se il sensore
// restituisce un valore di luce compreso tra 500 e 600 allora si è fuori dalla linea,
// quindi viene invocata la procedura di rotazione.
Behavior OffLine = new Behavior()
{
private boolean suppress = false;
public boolean takeControl() {
return ( light.readNormalizedValue() > 500 && light.readNormalizedValue() <= 600); }
public void suppress() {
suppress = true;
while (suppress) Thread.yield();
}
public void action() {
int sweep = 10;
int color=light.readNormalizedValue();
String mex="Colore : " + color;
LCD.drawString(mex,1,2);
while (!suppress) {
pilot.rotate(sweep,true);
while (!suppress && pilot.isMoving()) Thread.yield();
sweep *= -2;
}
pilot.stop();
suppress = false;
}
};
// Se viene riconosciuta una stazione vuol dire che l'agente deve richiedere quale sarà
// la prossima azione che deve eseguire, quindi si estrae l'azione corrispondente dal
// vettore delle azioni e la si esegue.Una stazione è riconosciuta dall'agente se il sensore
// restituisce un valore maggiore di 600.
Behavior Lift = new Behavior()
{
public boolean takeControl() {
return (light.readNormalizedValue() > 600 );
}
public void suppress() {
pilot.stop();
}
public void action() {
int color=light.readValue();
String mex="Colore : " + color;
LCD.drawString(mex,1,2);
pilot.stop();
if(act < vi.size())
{
getAct();
act++;
}
if (act >= vi.size())
{
try{
Thread.sleep(50000);
}catch (Exception e){}
}
pilot.forward();
}
};
Behavior[] bArray = {OffLine, DriveForward,Lift};
(new Arbitrator(bArray)).start();
}
// La funzione getAct() scorre il vettore delle azioni e le esegue una alla volta.Questa funzione
// viene invocata quando viene rilevata una stazione di modo che venga eseguita l'azione corrispondente
// a quella stazione appunto.
private static boolean getAct(){
// La sincronizzazione tra gli agenti viene fatta calcolando il tempo di esecuzione della azione.
// Terminata l'esezuzione dell'azione corrente l'agente rimane in attesa di x secondi, dove x
// è la differenza tra il tempo utilizzato per l'esecuzione ed il tempo di attesa estratto dal
// vettore in base alle azioni degli altri agenti.
times[act]=(int)System.currentTimeMillis();
String yep="Act : " + vi.elementAt(act);
LCD.drawString(yep,2,4);
int t=0;
if(act >= vi.size()){
try{
Thread.sleep(50000);
}catch (Exception e){}return false;}
if (vi.elementAt(act).equals("wait")){
try{
act++;
Thread.sleep(getT((String)vi.elementAt(act)));
times[act]=(int)System.currentTimeMillis();
act++;
getAct();
}catch (Exception e){}
}
else if (vi.elementAt(act).equals("90 left")){
pilot.travel(10);
pilot.rotate(-80); }
else if (vi.elementAt(act).equals("90 right")){
pilot.travel(10);
pilot.rotate(80);
}
else if (vi.elementAt(act).equals("180 right")){
pilot.travel(10);
pilot.rotate(140);
}
else if (vi.elementAt(act).equals("leave")){
Motor.B.setSpeed(600);
Motor.B.rotateTo(0);
act++;
if(act < vi.size()){
getAct();
}
}
else if (vi.elementAt(act).equals("0")){
pilot.travel(10);
}
else if (vi.elementAt(act).equals("pick_up")){
// L'azione pick_up sovrascrive il tempo di arrivo alla stazione poichè in questo caso
// il tempo non deve essere calcolato all'arrivo della stazione ma quando la pick_up
// è conlcusa, quindi quando l'agente ha terminato il sollevamento.
Motor.B.setSpeed(600);
Motor.B.rotateTo(925);
times[act]=(int)System.currentTimeMillis();
try{
t=times[act]-times[act-2];
act++;
t=((getT((String)vi.elementAt(act)))-t);
Thread.sleep(t);
}catch (Exception e){}
times[act]=(int)System.currentTimeMillis();
act++;
if(act < vi.size()){
getAct();}
}
else {
try{
t=times[act]-times[act-1];
t=((getT((String)vi.elementAt(act)))-t);
Thread.sleep(t);
} catch (Exception e){}
times[act]=(int)System.currentTimeMillis();
act++;
if(act < vi.size()){
getAct();
}
}
return true;
}
// Purtroppo Lejos non implementa le classi java per l'estrazione di interi da un vettore,ne per la conversione
// di stringhe in interi e per questo è stata realizzata questa funzione che, se pur non molto elegante,
// in base alla stringa letta restituisce l'intero corrispondente.La funzione è necessaria per estrarre dal
// vettore le attese che gli agenti devono fare per mantenersi sincronizzati tra di loro.
private static int getT(String s){
if (s.equals("5")){
return 5000;
}
else if (s.equals("7")){
return 7000;
}
else if (s.equals("8")){
return 8000;
}
else if (s.equals("9")){
return 9000;
}
else if (s.equals("10")){
return 10000;
}
return 0;
}
}
import java.util.Vector;
public class Plan {
// E' la funzione richiamata in Lifter.java per richiedere il vettore delle azioni e delle attese per l'agente
public static Vector getPlan(){
// Ogni azione nel vettore è seguita da un intero che indica un tempo in secondi.
// L'agente utilizza questo valore per effettuare l'attesa alla fine di un azione.
// Il valore in secondi indica il tempo di esecuzione dell'azioni più lunga tra quelle
// eseguite dagli agenti a quel passo del piano.
Vector vi= new Vector();
// ESEMPIO:
// Nel caso dell'azione wait il tempo di attesa successivo indica la lunghezza dell'attesa.
vi.addElement("wait");
vi.addElement("7");
vi.addElement("wait");
vi.addElement("9");
// 0 indica l'azione forward
vi.addElement("0");
vi.addElement("9");
vi.addElement("0");
vi.addElement("5");
// Nel caso dell'azione forward seguita da pick_up il tempo di attesa è inserito una sola volta
// in quanto le azioni forward + pick_up devono essere eseguite come un azione singola.
vi.addElement("0");
vi.addElement("pick_up");
vi.addElement("8");
vi.addElement("wait");
vi.addElement("7");
vi.addElement("180 right");
vi.addElement("9");
vi.addElement("0");
vi.addElement("5");
vi.addElement("leave");
return vi;
}
}