-
Notifications
You must be signed in to change notification settings - Fork 0
/
astar.pl
125 lines (96 loc) · 4.73 KB
/
astar.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
/* -----------------------------------------------------------------------
(SWI Prolog Version)
A* search algorithm
astar(Start, Successors, GoalTest, HvalFn, Answer).
True if "Answer" is a path from "Start" to a state on which
GoalTest succeeds.
"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.
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.
NOTE the signature of these functions is important. The routine
generates particular types of function calls assuming these
signatures.
NOTE you must execute
consult(basics).
Before astar will work.
----------------------------------------------------------------------- */
:- ensure_loaded('astarcommon.pl').
astar(Start, Successors, GoalTest, HvalFn, Answer, StateEqFn) :-
%% call an internal start point with Start initialized as a
%% path. Each path also contains the 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 statt state, then recursively search
%% for a solution.
callHvalFn(HvalFn, Start, Val), !,
astarRecursive([[(0,Val), Start]], Successors, StateEqFn, GoalTest, HvalFn, Answer, 0).
astarRecursive([ ], _, _, _, _, 'unsolvable', NumExpanded) :- !,
writeln(['Frontier empty, problem shown unsolveable, states expanded =', NumExpanded]),
!, fail.
astarRecursive([ [_, FinalState | Path ] | _], _, _, GoalTest, _, Answer, NumExpanded) :-
%%found goal
callGoalFn(GoalTest,FinalState), !, % cut is to abort this clause if not at goal state
reverse([FinalState | Path], Answer),
N is NumExpanded + 1,
writeln(['Search Successful, states expanded =', N]).
astarRecursive([ [(Gval,_), FinalState | Path ]| OtherPaths],
Successors, StateEqFn, GoalTest, HvalFn, Answer, NumExpanded) :-
%% Expand and search.
%%writeln(['Expanding: ', [FinalState|Path]]),
%%nl,
callSuccessors(Successors,FinalState,Neighbours),
expand_astar(Gval, FinalState, Path, Neighbours, StateEqFn, HvalFn, NewPaths),
ourmerge(NewPaths, OtherPaths, NewFrontier),
N is NumExpanded + 1,!,
%%%Here you can place a node expansion bound
(N =< 10000 ->
astarRecursive(NewFrontier, Successors, StateEqFn, GoalTest,
HvalFn, Answer, N) ;
writeln(['Node Expansion Limit Reached', N]), nl, !, fail).
expand_astar(Gval, State , Path,
[(Cost,NewState) | RestNeigh], StateEqFn, HvalFn,
[ [(NGval, NHval), NewState, State | Path] | RestNewPaths]) :-
%%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, if Newstate is not equal to
%%a previous state on the path, and the new Gval is the old
%%one plus the cost. And the new Hvalue is the hvalue f NewState.
cyclecheck(NewState, [State | Path], StateEqFn), !, %cycle checking!
NGval is Gval + Cost,
callHvalFn(HvalFn, NewState, NHval),
expand_astar(Gval, State, Path, RestNeigh, StateEqFn, HvalFn, RestNewPaths).
expand_astar(Gval, State , Path,
[(_,_)| RestNeigh], StateEqFn, HvalFn, RestNewPaths) :-
%% For newstates that fail the cyclecheck
expand_astar(Gval,State,Path, RestNeigh, StateEqFn, HvalFn, RestNewPaths).
expand_astar(_, _, _, [],_,_, []).