-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path_robot.pl
150 lines (125 loc) · 4.25 KB
/
_robot.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
% ---------------------
% ** ESERCIZIO Robot **
% ---------------------
% Un robot si muove sul piano X/Y fra ostacoli rettangolari allineati con gli assi cartesiani.
% Il robot si può assimilare ad un punto e si può muovere solo orizzontalmente o verticalmente.
% Supponiamo che il costo di cambiare direzione sia pari a quello di avanzare di "una mattonella".
:-dynamic destinazione/1.
:-dynamic partenza/1.
:-dynamic o/2.
percorso(Percorso) :-
retractall(destinazione(_)),retractall(partenza(_)),retractall(o(_,_)),
write('Da dove deve partire?'), nl,
read(XPartenza/YPartenza), assert(partenza(XPartenza/YPartenza)),
write('dove deve arrivare?'), nl,
read(XArrivo/YArrivo),
assert(destinazione(o(XArrivo/YArrivo))), % arrivo in orizzontale
assert(destinazione(v(XArrivo/YArrivo))), % arrivo in verticale
ucs([0-[XPartenza/YPartenza]],C-P), % ricerca UCS
reverse(P,PInv),
Percorso = C-PInv.
ostacolo(2/2, 3/3). % coordinate ostacolo rettangolare
ostacolo(0/3, 1/3). % coordinate ostacolo rettangolare
luogo(X/Y) :- % determina un luogo tale per cui ...
partenza(Xp/Yp), % ... con riferimento al punto di partenza ..
between(0,5,DistX), % .. ne disti al massimo 5 in orizzontale ..
between(0,5,DistY), % .. e 5 in verticale ..
( X is Xp + DistX, Y is Yp + DistY
; X is Xp - DistX, Y is Yp + DistY
; X is Xp + DistX, Y is Yp - DistY
; X is Xp - DistX, Y is Yp - DistY
),
X/Y \= Xp/Yp. % .. e non coincida con il punto di partenza
s(X/Y1,o(X/Y2),Costo) :- % primo passo in verticale
luogo(X/Y2), Y2 \= Y1,
\+ osta(X/Y1,X/Y2),
Costo is abs(Y2 - Y1).
s(X1/Y,v(X2/Y),Costo) :- % primo passo in orizzontale
luogo(X2/Y), X2 \= X1,
\+ osta(X1/Y,X2/Y),
Costo is abs(X2 - X1).
s(v(X/Y1),o(X/Y2),Costo) :- % generico passo in verticale
luogo(X/Y2), Y2 \= Y1,
\+ osta(X/Y1,X/Y2),
Costo is abs(Y2 - Y1).
s(o(X1/Y),v(X2/Y),Costo) :- % generico passo in orizzontale
luogo(X2/Y), X2 \= X1,
\+ osta(X1/Y,X2/Y),
Costo is abs(X2 - X1).
osta(X/Y1,X/Y2) :- % è presente un ostacolo su percorso orizzontale
ostacolo(Xbs/Ybs,Xad/Yad),
between(Xbs,Xad,X),
comprende_ostacolo(Y1,Y2,Ybs,Yad).
osta(X1/Y,X2/Y) :- % è presente un ostacolo su percorso verticale
ostacolo(Xbs/Ybs,Xad/Yad),
between(Ybs,Yad,Y),
comprende_ostacolo(X1,X2,Xbs,Xad).
comprende_ostacolo(_,Fine,_,Fine). % destinazione dentro fine ostacolo
comprende_ostacolo(_,Fine,Fine,_). % destinazione dentro inizio ostacolo
comprende_ostacolo(Partenza,Fine,Estremo_basso,Estremo_alto) :-
( Partenza < Estremo_basso, % partenza a sx dell'ostacolo
Fine > Estremo_alto
; Partenza > Estremo_alto, % partenza a dx dell'ostacolo
Fine < Estremo_basso).
% ucs([0-[Partenza]],C-Percorso) ricerca a costo uniforme derivata da
% quella in ampiezza; tiene meno percorsi in memoria perché elimina
% quelli che riespandono un nodo già espanso
ucs([C-[Nodo|Perc]|_],C-[Nodo|Perc]) :-
destinazione(Nodo).
ucs([C-[N|P]|Percorsi],Soluzione):-
ottimo(N,C),
espansione(C-[N|P],PercorsiEstesi),
fusioneOrdinata(PercorsiEstesi,Percorsi,NuoviPercorsi),
ucs(NuoviPercorsi,Soluzione).
espansione(C-[N|P],Percorsi):-
setof(CC-[NN,N|P],C1^(s(N,NN,C1),\+ o(NN,_),CC is C+C1),Percorsi),
!.
espansione(_-_,[]). % non fa fallire espansione
fusioneOrdinata([],L,L).
fusioneOrdinata(L,[],L).
fusioneOrdinata([C1-P1|CP1],[C2-P2|CP2],[C1-P1|Coda]) :-
C1 =< C2,
fusioneOrdinata(CP1,[C2-P2|CP2],Coda).
fusioneOrdinata([C1-P1|CP1],[C2-P2|CP2],[C2-P2|Coda]) :-
C1 > C2,
fusioneOrdinata([C1-P1|CP1],CP2,Coda).
% restituisce il costo ottimo se il nodo è stato già espanso
% altrimenti lo asserisce
ottimo(N,C) :-
o(N,C),
!.
ottimo(N,C) :-
assertz(o(N,C)).
/*
Qui di seguito un esempio di lanci del programma (notate che si possono inserire anche coordinate negative):
2 ?- percorso(P).
Da dove deve partire?
|: 1/1.
dove deve arrivare?
|: 4/4.
P = 6-[1/1, v(4/1), o(4/4)] .
3 ?- percorso(P).
Da dove deve partire?
|: 1/2.
dove deve arrivare?
|: 4/4.
P = 7-[1/2, o(1/1), v(4/1), o(4/4)] .
4 ?- percorso(P).
Da dove deve partire?
|: 0/2.
dove deve arrivare?
|: 4/4.
P = 8-[0/2, o(0/1), v(4/1), o(4/4)] .
5 ?- percorso(P).
Da dove deve partire?
|: -1/2.
dove deve arrivare?
|: 4/4.
P = 7-[-1/2, o(-1/4), v(4/4)] .
8 ?- percorso(P).
Da dove deve partire?
|: -1/(-1).
dove deve arrivare?
|: 4/4.
P = 10-[-1/ -1, o(-1/1), v(4/1), o(4/4)] .
*/