Implementazione in Prolog
Il programma di simulazione ricostruisce la struttura del grafo rappresentante le strade e gli incroci con annesse macchine,semafori,limiti stradali e stop mediante una loro rappresentazione sotto forma di base di conoscenza che viene dinamicamente interrogata per ricostruire lo stato e per aggiornarlo in circostanze come gli scambi di conoscenza. Di seguito ne è rappresentata la struttura e le funzioni.
:-dynamic(strada_corrente/2).
:-dynamic(prossima_strada/2).
:-dynamic(partenza/2).
:-dynamic(destinazione/2).
:-dynamic(mitrovo/3).
:-dynamic(rosso/1).
:-dynamic(peso/2).
:-dynamic(contamacchine/2).
:-dynamic(velocita/3).
:-dynamic(somma/2).
:-dynamic(conta/2).
Definizione di tutti i predicati come dynamic per consentire di effettuare nuove asserzioni, aggiornando la conoscenza mediante comando assert(), durante l’esecuzione del programma di simulazione e del relativo interprete. La porzione commentata fa riferimento ad eventuali predicati da inserire come espansione della base di conoscenza.
partenza(partenza,partenza1).
destinazione(destinazione,destinazione1).
angolo(angolo,angolo1).
collega(incrocio1,strada,incrocio2).
coordinata(strada33,x,y).
prossima_strada(macchina4,strada6).
strada_corrente(macchina5,strada7).
lunghezza(lunghezza1,lunghezza2).
velocitamax(strada3,numero1).
semaforo(strada5).
stop(strada4).
temporosso(strada5,9).
velocita(macchina3,velocitas,stradas).
strada(strada6).
incrocio(incrocio3).
macchina(macchinas).
velocitamedia(strada3,qualcosa).
Elenco di asserzioni di esempio,una per ogni predicato.
strada(X):- lunghezza(X,_Y).
strada(X):- angolo(X,_Z).
strada(D):- collega(_C,D,_E).
strada(X):- peso(X,_Y).
strada(L):- coordinata(L,_X,_Y).
strada(L):- strada_corrente(_K,L).
strada(L):- velocita(_S,_E,L).
incrocio(C):- collega(C,_D,_E).
incrocio(E):- collega(_C,_D,E).
macchina(K):- strada_corrente(K,_L).
macchina(S):- velocita(S,_E,_L).
Definizione delle conseguenze logiche di ogni predicato,ovvero viene specificato per ogni argomento quale predicato ne consegue. Le parti commentate fungono da eventuali miglioramenti futuri.
somma([],0).
somma([X|Y],D):- somma(Y,G),velocita(X,F,_L),D is F + G.
Il predicato somma calcola ricorsivamente la somma(argomento D) delle velocità delle macchine contenute nella lista (argomento [X|Y]).
conta([],0).
conta([_H|Coda], N) :- conta(Coda, N1),N is N1 + 1.
Il predicato conta calcola ricorsivamente il numero di elementi di una lista.
contamacchine(L,N):- findall(X,strada_corrente(X,L),Y),conta(Y,N).
Il predicato contamacchine trova mediante findall la lista di macchine nella strada considerata e ne conta il numero
velocitamedia(L,D):- findall(X,strada_corrente(X,L),Y),
contamacchine(L,N),somma(Y,C),D is /(C,N).
Il predicato velocitamedia calcola la media aritmetica delle velocita delle macchine nella strada considerata.
peso(L,X):-
lunghezza(L,K),
contamacchine(L,N),
(semaforo(L) -> temporosso(L,J); J is 0),
(N is 0 -> D is 1,W is 0 ; velocitamedia(L,D), W is 1),
(stop(L) -> Costante is 3 ; Costante is 0),
velocitamax(L,F),
X is +(+(+(/(K,F),/(J,2)),Costante),*(/(K,D),W)).
Il predicato peso effettua il calcolo del peso associato alla strada secondo la formula:
peso=(lunghezza/velocita_massima)+
(lunghezza/velocita_media)+
costante_stop+
attesa_rosso
Ogni singolo fattore viene considerato solo se c’è relativo riscontro nella rappresentazione del grafo mediante il costrutto if then else.
Nell’incrocio rappresentato,ogni vettura deve domandarsi se occorre dare la precedenza ad ognuna delle altre, considerando sia la sua posizione corrente che la strada verso cui intende dirigersi. Tale criterio è rappresentato dalle porzioni evidenziate in giallo alla destra di ogni automobile. Il programma di simulazione,nel dover gestire un incrocio dunque domanderà alla base di conoscenza se la macchina A abbia la precedenza verificando che non debba darla a nessun’altra macchina dell’incrocio e verificando che la macchina considerata non si trovi ad un semaforo rosso.In base alle risposte ricevute determinerà l’ordine di precedenza che gestisce l’incrocio.
precedenza(A) :- \+(precedenza(A,_B)),strada_corrente(A,L),\+(rosso(L)).
Per determinare se la macchina A debba dare precedenza alla macchina B occorrerà dunque considerare la prossima strada di A e la strada corrente di entrambe,così da poterne confrontare gli angoli associati per determinare quella che nella figura è la destra,evidenziata in giallo, della macchina A. Ulteriori controlli sono necessari nel caso in cui la strada dI B abbia un semaforo rosso o ci sia uno stop poichè in quel caso A non deve dare precedenza. Infine è necessario verificare se A stesso si trovi ad uno stop o ad un semaforo rosso per determinare,a seconda dello stato di B, se occorre dare precedenza o meno.
precedenza(A,B) :-
prossima_strada(A,Rn),
strada_corrente(A,Ra),
strada_corrente(B,Rb),
((stop(Ra), \+(stop(Rb))-> true;fail) ;
(rosso(Ra), \+(rosso(Rb))-> true;fail) ;
(\+(stop(Ra)),\+(rosso(Ra))->true;fail)),
\+(A=B),
(rosso(Rb)-> fail;true),
(stop(Rb)-> fail;true),
angolo(Rn, An),
angolo(Ra, Aa),
angolo(Rb, Ab),
(1 is -(Aa,An) -> fail;
( (0 is -(Aa,An), -1 is -(An,Ab)) -> true;
(-1 is -(Aa,An),(0 is -(An,Ab) ; -1 is - (An,Ab))) -> true ;
((-2 is -(Aa,An),
(1 is -(An,Ab) ; 0 is -(An,Ab) ; -1 is -(An,Ab)))
-> true ; fail))).
Calcolo del percorso minimo Il calcolo del percorso minimo viene effettuato innanzitutto realizzando un predicato in grado di garantire la costruzione di un percorso sotto forma di lista
percorso(A,B,Path,Len) :-
spostamento(A,B,[A],Q,Len),
reverse(Q,Path).
Il predicato percorso dunque costruisce una lista Path di lunghezza complessiva Len ottenuta facendo la lista inversa di quella ottenuta dal predicato applicato ricorsivamente spostamento che:
spostamento(A,B,P,[B|P],L) :-
collega(A,C,B),
peso(C,L).
Nel caso semplice o passo base verifica che A e B,incroci, siano collegati mediante una strada C di peso L. Tale incrocio B viene così aggiunto in testa alla lista dei nodi P già considerati.
spostamento(A,B,Visitato,Path,L) :-
collega(A,D,C),
peso(D,F),
C \== B,
\+member(C,Visitato),
spostamento(C,B,[C|Visitato],Path,L1),
L is F+L1.
Nel passo ricorsivo,invece viene verificato che B sia differente da C,nodo collegato ad A, e che C non sia già stato visitato (eseguendo dunque una potatura dei cicli) , e si procede dunque ad aggiungerne il valore F del peso al peso complessivo L e ha ricalcolare lo spostamento da C a B aggiungendo C alla lista dei Visitati. Una volta giunti al passo base la lista dei Visitato sarà ripresa da Path che ci aggiungerà l’ultimo elemento e verrà restituita come lista finale del percorso.
piubreve(A,B,Path,Length) :-
setof([P,L],percorso(A,B,P,L),Set),
Set = [_|_],
minimo(Set,[Path,Length]).
Il predicato piubreve crea un insieme di liste formate da ogni percorso P con relativa lunghezza L e di questi stabilisce il percorso con lunghezza minima.
minimo([F|R],M) :- min(R,F,M).
Il predicato minimo prende il primo elemento F di Set e mediante il predicato min lo confronta ricorsivamente con il resto di Set R per stabilire quale il termine minimo M.
min([],M,M).
Passo base che restituisce M se il resto della lista di Set è vuota.
min([[P,L]|R],[_,M],Min) :- L < M, !, min(R,[P,L],Min).
min([_|R],M,Min) :- min(R,M,Min).
Passo ricorsivo: se L è minore di M allora calcolo min tra il [P,L] e il resto della lista R altrimenti esegue la seconda regole sottostante e non considero l’elemento di che precede R e continua calcolare min direttamente da R risparmiando in termini di computazione.