-
Notifications
You must be signed in to change notification settings - Fork 0
/
astarCC.pl
200 lines (160 loc) · 8.22 KB
/
astarCC.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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
/* -----------------------------------------------------------------------
(SWI Prolog Version)
A* search algorithm + Cycle Checking
Identical to A* except must past an equality test for states
so that duplicate states can be detected.
astarCC(Start, NbFn, GoalFn, HvalFn, Answer, StateEqFn).
"Answer" is the path found using an A* search with transition costs
and neighbours of a state returned by Successors, and the heuristic
value of a state returned by Hvalfn.
More specifically.
More specifically.
Start---a node in the state space. This is passed in using whatever
representation the user designs. The design of the state space
representation will of course influence how the other functions
like GoalTest, Successors, HvalFn operate. Note that the state
represenation could include other information besides the
raw state, e.g., the move that was used to generate this
state. It can have whatever is convenient. All you have to
do is ensure that the other functions "GoalTest",
"Succesors" etc. operate properly with your state your data
structure, perhaps ignoring parts of the structure not
relevant to them.
Successors---A function of the form
Successors(State, ListOfNeighboursWithCosts)
Returns a list of neighbours of a state, the elements of
this list must be in the form of pairs
(Cost, Newstate). Where Cost is the cost of getting to the
neighbour and Newstate is the neighbour.
GoalTest-A predicate of the form
GoalTest(State1)
which is true iff State1 is a goal state.
HvalFn-A function of the form
HvalFn(State, Hval)
which sets Hval to be the heuristic value of the state
(estimated distance to a goal)
Answer this is a list of states from the initial state to the final
goal satisfying state. This is the path to the goal.
StateEqFn(State1, State2)
this predicate is true of two states that are equal. Note
that if one is including extra information in the state
representation, e.g., the action that yielded the state,
then the equality function will have to ignore the
irrelevant parts of the state representation.
NOTE the signature of these functions is important. The routine
generates particular types of function calls assuming these
signatures.
NOTE you must also consult "basics" prior to using.
How Cycle checking works. There are different ways of getting CC to
work. Here we use a technique that will ensure that CC works even if
the heuristic is not monotone. The price we pay is that we might
repeat parts of the search. In particular, we store the old states
expanded as well as the g-value (the cost of the path we found to that
state). If later on we find the same state again we only reject it if
its g-value (the cost of the new path we have found) is higher than
or equal to the cost of the old path found.
Now to the mechanics. Again there are different ways. The technique we
use is that when a state is to be expanded we first check to see if it
was expanded before with a lower cost path. If so, we reject it and move
on to the next state. When we expand a state we reject all of its
successors to which we have already expanded with cheaper
paths. Then we place all of the rest on the frontier. This
technique allows the possiblity of having duplicate paths on the
frontier: we might not have seen node n, we expand two nodes n1 and
n2 both have n as a successor, since n has never been expanded
before, the two copies of n both end up on the frontier since we
never check the states on the frontier for duplicates, only the set
of states already expanded are checked. It is more effort to
check the frontier and is not worth while unless space is very
tight---but then we would probably use IDA* instead. Because we don't
check the frontier, and might place duplicates on it, we need to
recheck a node prior to expanding it.
Finally to implementation. Here we use a trick of utilizing the prolog
database to store the previously visited states and the cost of the
path to them---we use "assert".
----------------------------------------------------------------------- */
:- ensure_loaded('astarcommon.pl').
astarCC(Start, Successors, GoalFn, HvalFn, Answer, StateEqFn) :-
%% call an internal start point with Start initialized as a
%% path. Each path also contains a pair (g-val, h-val)
%% stored at the front of the path. This cost information is
%% used internally by astar, the user need not worry about the
%% this data.
%%
%% Get heuristic value of start state, initialize the
%% predicate used to store duplicate state then recursively search
%% for a solution.
callHvalFn(HvalFn, Start, Val), !,
astarRecursiveCC([[(0,Val), Start]], Successors, GoalFn, HvalFn,
StateEqFn, [], Answer, 0).
/* ----------------------------------------------------------
astarRecursiveCC (internal A*)
(3 clauses)
---------------------------------------------------------- */
%1 We found a goal.
astarRecursiveCC([ [_, FinalState | Path ] | _], _, GoalFn, _,
_, _, Answer, NumExpanded) :-
callGoalFn(GoalFn, FinalState), !,
reverse([FinalState | Path], Answer),
N is NumExpanded +1,
writeln(['Search Successful, states expanded =', N]).
%2. We expand a previously unseen or more expensively seen node.
astarRecursiveCC([ [(Gval,_), FinalState | Path ]| OtherPaths], Successors,
GoalFn, HvalFn, StateEqFn, OldStates, Answer, NumExpanded) :-
%% Before expanding we check to see if we have visited the
%% node with a cheaper path.
ccOk(FinalState, Gval, OldStates, StateEqFn),
%% Expand and search.
%%writeln(['Expanding node: ', NumExpanded, FinalState]),
%%nl,
ccRemember(FinalState, Gval, OldStates, NewOldStates),
callSuccessors(Successors,FinalState,Neighbours),
expand_astarCC(Gval, FinalState , Path, Neighbours, HvalFn, NewPaths),
ccPrune(NewPaths,PrunedPaths, OldStates, StateEqFn),
ourmerge(PrunedPaths, OtherPaths, NewFrontier),
N is NumExpanded +1,!,
(N =< 10000 ->
astarRecursiveCC(NewFrontier, Successors, GoalFn,
HvalFn, StateEqFn, NewOldStates, Answer,N) ;
writeln(['Node Expansion Limit Reached', N]), nl, !, fail).
%3 The front of the frontier was seen before via an equally cheap path.
astarRecursiveCC([ _ | OtherPaths], Successors, GoalFn, HvalFn,
StateEqFn, OldStates, Answer,NumExpanded) :-
!,
astarRecursiveCC(OtherPaths, Successors, GoalFn, HvalFn,
StateEqFn, OldStates, Answer,NumExpanded).
expand_astarCC(_, _, _, [], _, []).
expand_astarCC(Gval, State, Path,
[(Cost,NewState) | RestNeigh], HvalFn,
[ [(NGval, NHval), NewState, State | Path] | RestNewPaths]) :-
%%This function massages the successor states into the proper
%%representation of paths that are on A*'s frontier.
%%The form of the new paths is the G and H vals in a pair followed by
%%the new state followed by the old states. Newstate is a
%%legit extension of the old path if the pair
%%(Cost,NewState) is in neighbours and the new Gval is the old
%%one plus the cost. And the new Hvalue is the hvalue of NewState.
NGval is Gval + Cost,
callHvalFn(HvalFn, NewState, NHval),
expand_astarCC(Gval, State, Path, RestNeigh, HvalFn, RestNewPaths).
/* ----------------------------------------------------------
Cycle checking
---------------------------------------------------------- */
ccOk(_, _, [], _).
%%New path must be cheaper than ALL other paths to the same state.
ccOk(State, Gval, [(OldState,OldGval) | Rest], StateEqFn) :-
callEqFn(StateEqFn, State, OldState), Gval < OldGval, !,
ccOk(State, Gval, Rest, StateEqFn).
%% clause for nonmatching state.
ccOk(State, Gval, [(OldState, _) | Rest], StateEqFn) :-
not(callEqFn(StateEqFn, State, OldState)), !,
ccOk(State, Gval, Rest, StateEqFn).
ccRemember(State, Gval, OldStates, [(State,Gval)|OldStates]).
ccPrune([ NewPath | RestNPaths], PrunedPaths, OldStates, StateEqFn) :-
NewPath = [(Gval, _), FinalState | _],
ccOk(FinalState, Gval, OldStates, StateEqFn), !,
ccPrune(RestNPaths, RestPruned, OldStates, StateEqFn),
PrunedPaths = [NewPath | RestPruned].
ccPrune([ _ | RestNPaths], PrunedPaths, OldStates, StateEqFn) :-
ccPrune(RestNPaths, PrunedPaths, OldStates, StateEqFn).
ccPrune([], [], _, _).