STRIP Planner RoboCaffè
Si tratta di un progettino per il corso di inteligenza artificiale, in sostanza è un pianificatore STRIPS scritto in prolog (algoritmo usato A*).
Il problema che modella è quello di un robot che deve portare il caffè a varie persone disponendo di due macchinette del caffè.
File gjko.pl
/******************************************************************************* ALL Gjko - Abstract Language Layer Gjko Questo file contiene la definizione del linguaggio che permette di manipolare il linguaggio Gjko. ------------------------------------------------------------------------------ INTRODUZIONE ------------------------------------------------------------------------------ L'idea di base che sta dietro a questa porzione di prolog e' quella di mappare delle frasi a dei predicati prolog, i quali vengono usati da A* per compiere il suo lavoro. Gjko permette di lavorare su due tipi di fatti quelli dinamici e quelli statici. I fatti dinamici necessitano di essere dichiarati anche nelle direttive come tali (tramite :- dynamic(Functor/Arrity)). Questo permette di mutare il loro stato durante il corso del calcolo. Ogni istruzione deve terminare con un punto ".". ------------------------------------------------------------------------------ DIRETTIVE ------------------------------------------------------------------------------ Le direttive sono formate dalla seguente sintassi ":- direttiva" Sono importanti definire che vanno inserite come :- dynamic nomefattodinamico/arieta. :- retractall(nomefattodinamico(...)). Il primo rende dinamico il fatto ed il secondo pulisce l'ambiente da possibili fatti dinamici ancora prsenti nel DB del sistema. ------------------------------------------------------------------------------ DATI ------------------------------------------------------------------------------ I dati che il sistema dispone sono definiti in prolog come nomefatto(argomenti). ------------------------------------------------------------------------------ DEFINIZIONE NODI POSSIBILI ------------------------------------------------------------------------------ La definizione di un nodo avviene nella definizione di can X if L. Il nodo X esiste se sono verificate le condizioni L. L e' definito come (1) L = fatto. L = fatto and L1 L1 e' definito come L, quindi puo essere una congiunzioni di fatti dinamici o statici Esempio: can move(Ag, Pos1, Pos2) if adjacent(Pos1, Pos2) and at(Ag, Pos1) and at(Ag, Pos1) X = move(Ag, Pos1, Pos2) L = adjacent(Pos1, Pos2) and at(Ag, Pos1) and at(Ag, Pos1) ------------------------------------------------------------------------------ DEFINIZIONE DI COME LO STATO DI UN NODO CAMBIA ------------------------------------------------------------------------------ Lo stato di un nodo e' l'insieme dei fatti statici e dinamici con il loro valore mutare il valore di questi fatti significa mutare lo stato del nodo. Lo stato influnza principalmente la determinazione dei prossimi nodi. Per ogni possibile nodo bisogna definire come esso muta se il nodo se A* decide di attraversare questo nodo e bisogna indicare come A* deve tornare indietro. Per mutare lo stato per andare al nuovo stato bisogna definire change X then L. X e' il nodo ed L ha la medesima definizione (1). Nota: Per modificare lo stato di un fatto dinamico si usano assert e retract. Per mutare lo stato per tornare allo stato precedente bisogna definire back X then L X e' il nodo ed L ha la medesima definizione (1). ------------------------------------------------------------------------------ DEFINIZIONE DEL COSTO ------------------------------------------------------------------------------ La definizione del costo e' definita come segue: cost X to Y total N X e Y sono i nodi da cui si vuole partire (X) a dove si vuole andare Y, il costo e' N. ------------------------------------------------------------------------------ DEFINIZIONE DEI GOAL ------------------------------------------------------------------------------ La definizione dei goal e' formata da : goal X. X e' il nodo che si vuole raggiungere Note: Il sistema e' progettato per lavorare meglio su piu' nodi ------------------------------------------------------------------------------ DEFINIZIONE DEL NODO DI PARTENZA ------------------------------------------------------------------------------ NOTA: Le chiamate call sono superficiali ma sono inserite per chiarezza. *******************************************************************************/ :- op(100, fx, 'statico'). :- op(300, yfx, 'if'). :- op(300, yfx, 'then'). :- op(200, fx, 'can'). :- op(100, yfx, 'and'). :- op(200, fx, 'change'). :- op(200, fx, 'back'). :- op(200, fx, 'root'). :- op(200, fx, 'cost'). :- op(200, fx, 'goal'). :- op(200, yfy, 'to'). :- op(200, yfx, 'total'). /******************************************************************************* and(A, B) *******************************************************************************/ and(A, B) :- call(A), call(B). /******************************************************************************* Interfaccia con A* del predicato can. *******************************************************************************/ can(X) :- call(can X if R), call(R). /******************************************************************************* Interfaccia con A* del predicato change *******************************************************************************/ change(X) :- call(change X then R), call(R). /******************************************************************************* Interfaccia con A* del predicato bchange *******************************************************************************/ bchange(X) :- call(back X then R), call(R). /******************************************************************************* Interfaccia con A* del predicato goalnum *******************************************************************************/ goalnum(N) :- findall(A, goal(A), R), length(R, N). /******************************************************************************* Interfaccia con A* del predicato cpstp *******************************************************************************/ costo(X, Y, N) :- (cost X to Y total N), !. /******************************************************************************* Interfaccia con main. del predicato iroot *******************************************************************************/ iroot(nodo(L, [], 0 )) :- (root L).
File astar.pl
/*******************************************************************************
A*
L'implementazione dell'algoritmo A* e' lievemente cambiato rispetto al
originale. E' stato aggiunto il conteggio delle iterazioni e il sistema di
gestione dello stato.
--------------------------------------------------------------------------------
Sistema di gestione dello STATO corrente:
--------------------------------------------------------------------------------
Il calcolo dei neighbors usa un predicato definito dal problema e lo stato
corrente del sistema per dare una risposta.
Questo stato viene calcolato prima di chiamare neighbors. Dopo aver calcolato
neighbors viene rigenerato lo stato iniziale.
Guardare per maggiori informazioni: trek, btrek in questo file o
change e bchange in strips.pl.
--------------------------------------------------------------------------------
Definizione di nodo
--------------------------------------------------------------------------------
nodo(Nodo, ListaPercorso, CostoTotale).
Nodo e' definito dal problema.
*******************************************************************************/
% MOTORE
select(N, [N|F1], F1).
search(F0, nodo(N,P,C), Ip, I) :-
select(nodo(N, P, C), F0, _),
I is Ip + 1, % Variante
is_goal([ N | P]).
search(F0, G, Ip, I) :-
select(nodo(N, P, C), F0, F1),
trek([N | P]), % Variante
neighbors(NL),
btrek([N | P]), % Variante
add_paths(NL, nodo(N, P, C), NL1),
inserts(NL1, F1, F2),
Ip2 is Ip + 1, % Variante
search(F2, G, Ip2, I).
add_paths([], _, []).
add_paths([M|R], nodo(N,P,C),[nodo(M, [N|P], NC)|RF]) :-
costo(N,M,CN),
NC is C + CN,
add_paths(R,nodo(N,P,C),RF).
/*******************************************************************************
neighbors(out:Nodi)
Questo predicato restituisce nodi vicini al nodo corrente. Il nodo corrente
e' implicito nello stato del sistema.
*******************************************************************************/
neighbors(Res) :-
setof(ACT, can(ACT), Res).
/*******************************************************************************
treck(in:Lista)
Questo predicato applica le modifiche allo stato del sistema che ogni nodo
della lista implica.
Nota: Applica dal fondo della lista.
*******************************************************************************/
trek([]).
trek([H | L]) :-
trek(L),
change(H).
/*******************************************************************************
btreck(in:Lista)
Questo predicato applica le modifiche allo stato del sistema che ogni nodo
della lista implica.
Nota: Applica dal inizio della lista.
*******************************************************************************/
btrek([]).
btrek([H | L]) :-
bchange(H),
btrek(L).
/*******************************************************************************
confronto(Test, A, B)
Questo predicato e' utilizato per confrontare due nodi A e B in base
al loro costo attuale piu' il costo stimato dall'euristica h. Questo costo
totale viene calcolato da f.
NOTA: Si e' preferito che quando si trova un elemento uguale venga messo
in fondo a quelli uguali.
*******************************************************************************/
confronto(<, A, B) :- f(A, C1), f(B, C2), C1 < C2, !.
confronto(>, A, B) :- f(A, C1), f(B, C2), C1 >= C2.
/*******************************************************************************
inserts(in:Lista1, in:Lista2, out:Risultato)
Inserizione ordinata della Lista1 nella Lista2 usando il predicato confronto.
*******************************************************************************/
inserts([], Lista, Lista).
inserts([H | R], Lista, Ris) :-
insert(H, Lista, Result),
inserts(R, Result, Ris).
/*******************************************************************************
insert(in:Elemento, in:Lista, out:Risultato)
Inserizione ordinata del Elemento nella Lista usando il predicato confronto.
Non conserva gli elementi identici.
*******************************************************************************/
insert(Ele, [], [Ele]).
insert(Ele, [H | R], [Ele | L]) :-
(Ele \= H),
confronto(<, Ele, H),
L = [ H | R ].
insert(Ele, [H | R], [ H | Ri]) :-
(Ele \= H),
confronto(>, Ele, H),
insert(Ele, R, Ri).
/*******************************************************************************
GOAL
Il goal e' considerato come una lista di sottogoal. is_goal e' vera quando
tutti i goal si trovano nella lista controllata
is_goal(in:Lista)
Controlla che tutti i goal sono verificati nella lista.
*******************************************************************************/
is_goal(X) :-
forall(goal(G), member(G, X)).
/*******************************************************************************
EURISTCA
Il concetto su cui si basa l'euristica di questa implementazione e' quello di
sapere quanti goal devo ancora attraversare.
Quindi assumo che il goal e' espresso da una lista di sottogoal.
Questi sottogoal vengono contatti nella lista dei nodi gia attraversati e ne
viene fatta la differenza con quelli totali. Per stimare quanti ne devo
attraversare nei prossimi passaggi.
Questa differenza e' moltiplicata per un valore rapprsentativo di quanto mi
costa passare da un nodo ad un altro.
AGGIUNTA
- E' stata aggiunta la capacita di scoprire se nei neighbors del nodo
corrente e' presente un goal.
- E' stata aggiunto un limitatore di calcolo i base all'espressione
Soglia = Fattore * Numero_Goal + Fattore_Iniziale
- Fattore e' un numero che dovrebbe indicare quanti nodi intercorrono
tra un goal e l'altro.
- Fattore_Iniziale �� un numero che indica quanti nodi intercorrono tra
l'inizio e il primo goal.
Nota: Queste modifiche portano ad un valore di iterazione migliore ma una
pesantezza di calcolo maggiore.
f(in:Nodo, out:CostoF)
Calcola con l'euristica sopra spiegata il costo f di un nodo.
*******************************************************************************/
f(nodo(Azione, Lista, Costo), CostoH) :-
goalnum(L),
trek([Azione | Lista]),
neighbors(NL),
btrek([Azione | Lista]),
(findgoal(NL) ->
CountStart = 1;
CountStart = 0
),
countgoal([Azione | Lista], CountStart, C) -> (
Tau is L-C,
Tau >= 0,
costof(Tau, Costo, CostoH)
);
(goalnum(L), costof(L, Costo, CostoH)).
costof(N, Costo, CostoF) :-
CostoF is (Costo+N*15).
/*******************************************************************************
countgoal(in:Lista, in:Num, out:Count)
Restituisce il numero di goal trovati piu il numero Num.
*******************************************************************************/
countgoal([], Count, Count).
countgoal([ H | R], Count, Res) :-
goalnum(L),
Count =< L,
(goal(H) -> (
C is (Count+1),
countgoal(R, C, Res)
);
countgoal(R, Count, Res)).
/*******************************************************************************
findgoal(in:Lista)
Vero quando nella lista passata come argomente e' presente almeno un goal.
*******************************************************************************/
findgoal([]) :- fail.
findgoal([ H | R]) :- (goal(H), !) ; findgoal(R).
File l.pl
% Direttive :- dynamic(at/2). :- dynamic(numcoffe/2). :- retractall(at(_, _)). :- retractall(numcoffe(_, _)). % dati adjacent(o109,o103). adjacent(o103,o109). adjacent(o109,coffe2). adjacent(coffe2,o109). adjacent(o109,o111). adjacent(o111,o109). adjacent(o103,coffe1). adjacent(coffe1,o103). adjacent(o109,lab1). adjacent(lab1,o109). adjacent(o103,s103). adjacent(s103,o103). adjacent(o103,s109). adjacent(s109,o103). robot(rob). mcoffe(coffe1). mcoffe(coffe2). coffecapability(rob, 3). at(rob, o109). numcoffe(rob, 0). % definizioni can move(Ag, Pos1, Pos2) if adjacent(Pos1, Pos2) and at(Ag, Pos1) and at(Ag, Pos1). can load(Ag, N) if (N = 1) and at(Ag, Pos) and mcoffe(Pos) and numcoffe(Ag, L) and coffecapability(rob, CC) and ((N+L)==0). change move(Ag, Pos1, Pos2) then retract(at(Ag, Pos1)) and assert(at(Ag, Pos2)). change load(Ag, N) then retract(numcoffe(Ag, L)) and (R is (L + N)) and assert(numcoffe(Ag, R)). change serve(Ag, N, _) then retract(numcoffe(Ag, L)) and (R is (L - N)) and assert(numcoffe(Ag, R)). back move(Ag, Pos2, Pos1) then retract(at(Ag, Pos1)) and assert(at(Ag, Pos2)). back load(Ag, N) then retract(numcoffe(Ag, L)) and (R is (L - N)) and assert(numcoffe(Ag, R)). back serve(Ag, N, _) then retract(numcoffe(Ag, L)) and (R is (L + N)) and assert(numcoffe(Ag, R)). % goal goal serve(rob, 1, o109). goal serve(rob, 1, o111). goal serve(rob, 1, o103). cost move(_, _, _) to move(_, _, _) total 7. cost move(_, _, _) to load(_, _, _) total 7. cost load(_, _, _) to move(_, _, _) total 6. cost move(_, _, _) to serve(_, _, _) total 7. cost serve(_, _, _) to move(_, _, _) total 7. cost _ to _ total 10. root move(rob, o109, o103).
File progetto.pl
/******************************************************************************* Progetto RRS Robot del Caffe (qualita Java) Autore: Matteo Valdina Versione: 4 Documentazione di sviluppo Il progetto e' distribuito su due file principali che sono strips.pl e astar.pl e dal file progetto.pl. Il caricamento corretto del progetto avviene eseguendo il consult del file progetto.pl. Il calcolo inizia richiamando il predicato main/0. *******************************************************************************/ /******************************************************************************* Project Foundation File su cui il progetto e' fondato. *******************************************************************************/ :- consult(gjko). :- consult(l). :- consult(astar). /******************************************************************************* Main e' il predicato da cui il progetto inizia i suoi calcoli per stamparli sul terminale *******************************************************************************/ main :- iroot(X), search([X], nodo(N, P, C), 0, I), writeln('============================================================'), writesol([N | P]), write('Iterazioni: '), writeln(I), write('Costo: '), writeln(C), writeln('============================================================'). /******************************************************************************* Stampa a terminale una lista. *******************************************************************************/ writesol([]). writesol([Az | R]) :- writesol(R), writeln(Az).
File strips.pl
/******************************************************************************* Sistema di rappresentazione dello stato e Linguaggio Basato su STRIPS rappresentation Version: 4 dev LINGUAGGIO Il linguaggio usato per la rappresentazione dello stato si basa sulla definizione di tre predicati che permettono ad A* di modificare e determinare lo stato corrente. Predicati che modificano lo stato sono: - change - bchange Predicati che indagano lo stato sono: - can Lo stato e' a sua volta definito da fluenti e fatti. - predicato(Arg) static % fatti - predicato(Arg) % Fluenti Il sistema si basa su STRIPS ma con un diverso approccio. Infatti sostituisce il sistema delle liste con un sistema retract assert, quindi non si trova piu' una ripartizione in precondition, add, e delete ma can e change. - can e' in pratica precondition. - change e' lo stesso sistema di add e delete ma unito in un unico predicato. bchange compie l'opposto di change, ritornando allo stato precedente. NOTE: guardare trek e btrek nel file astar.pl *******************************************************************************/ /******************************************************************************* change(in:oNodo) Compie le modifiche dello stato del sistema in base all'argomento.. *******************************************************************************/ change(move(Ag, Pos1, Pos2)) :- retract(at(Ag, Pos1)), assert(at(Ag, Pos2)). change(load(Ag, N)) :- retract(numcoffe(Ag, L)), R is (L + N), assert(numcoffe(Ag, R)). change(serve(Ag, N, _)) :- retract(numcoffe(Ag, L)), R is (L - N), assert(numcoffe(Ag, R)). /******************************************************************************* bchange(in:Nodo) Torna in base allo stato attuale e l'argomento allo stato precedente. *******************************************************************************/ bchange(move(Ag, Pos2, Pos1)) :- retract(at(Ag, Pos1)), assert(at(Ag, Pos2)). bchange(load(Ag, N)) :- retract(numcoffe(Ag, L)), R is (L - N), assert(numcoffe(Ag, R)). bchange(serve(Ag, N, _)) :- retract(numcoffe(Ag, L)), R is (L + N), assert(numcoffe(Ag, R)). /******************************************************************************* can(in:Nodo) Indica quale deve essere lo stato del sistema attuale per dire se il nodo e' valido. IMPORTANTE lo stato corrente e' gestito da A* con un sistema di retract e assert. *******************************************************************************/ can(move(Ag, Pos1, Pos2)) :- (robot(Ag)static), (adjacent(Pos1, Pos2)static), at(Ag, Pos1). can(load(Ag, N)) :- N = 1, (robot(Ag)static), at(Ag, Pos), (mcoffe(Pos)static), numcoffe(Ag, L), (coffecapability(rob, CC)static), ((N+L)==0). can(serve(Ag, N, Pos)) :- N = 2, (robot(Ag)static), at(Ag, Pos), numcoffe(Ag, L), ((L-N)>=0). /******************************************************************************* Dati sullo stato del sistema *******************************************************************************/ % Rappresentazione della cartina adjacent(o109,o103)static. adjacent(o103,o109)static. adjacent(o109,coffe2)static. adjacent(coffe2,o109)static. adjacent(o109,o111)static. adjacent(o111,o109)static. adjacent(o103,coffe1)static. adjacent(coffe1,o103)static. adjacent(o109,lab1)static. adjacent(lab1,o109)static. adjacent(o103,s103)static. adjacent(s103,o103)static. adjacent(o103,s109)static. adjacent(s109,o103)static. % Robot (in questo caso l'agente). robot(rob)static. % Macchine del caffe mcoffe(coffe1)static. mcoffe(coffe2)static. % Capacita del Robot coffecapability(rob, 3)static. /******************************************************************************* Stato iniziale del sistema. NOTA: I predicati che vengono mutati durante l'esecuzione devono essere dichiarati dinamici *******************************************************************************/ at(rob, o109). numcoffe(rob, 0).
Tags: IA