% Greedy (Best First) Search
% COMP3411/9414/9814 Artificial Intelligence, UNSW, Alan Blair
% solve(Start, Solution, G, N)
% Solution is a path (in reverse order) from start node to a goal state.
% G is the length of the path, N is the number of nodes expanded.
solve(Start, Solution, D, N) :‐
consult(pathsearch), % insert_legs(), head_member(), build_path()
h(Start,H),
greedy([[Start,Start,H]], [], Solution, 1, N),
5. length(Solution, D1),
D is D1 ‐ 1.
% greedy(Generated, Expanded, Solution, L, N)
%
% The algorithm builds a list of generated “legs” in the form
% Generated = [[Node1,Prev1,H1],[Node2,Prev2,H2],…,[Start,Start,H]]
5. % The heuristic H is stored with each leg,
% and the legs are listed in increasing order of H.
% The expanded nodes are moved to another list (H is discarded)
% Expanded = [[Node1,Prev1],[Node2,Prev2],…,[Start,Start]]
% If the next leg to be expanded reaches a goal node,
% stop searching, build the path and return it.
greedy([[Node,Pred,_H]|_Generated], Expanded, Path, N, N) :‐
goal(Node),
5. build_path([[Node,Pred]|Expanded], Path).
% Extend the leg at the head of the queue by generating the
% successors of its destination node.
% Insert these newly created legs into the list of generated nodes,
% keeping it sorted in increasing order of H; and continue searching.
5. greedy([[Node,Pred,_H]|Generated], Expanded, Solution, L, N) :‐
extend(Node, Generated, Expanded, NewLegs),
M is L + 1,
insert_legs(Generated, NewLegs, Generated1),
greedy(Generated1, [[Node,Pred]|Expanded], Solution, M, N).
% Find all successor nodes to this node, and check in each case
% that the new node has not previously been generated or expanded.
extend(Node, Generated, Expanded, NewLegs) :‐
% write(Node),nl, % print nodes as they are expanded
5. findall([NewNode, Node, H], (s(Node, NewNode, _C)
, not(head_member(NewNode, Generated))
, not(head_member(NewNode, Expanded))
, h(NewNode, H)
), NewLegs).
% base case: insert one leg into an empty list.
insert_one_leg([], Leg, [Leg]).
% Insert the new leg in its correct place in the list (ordered by H).
insert_one_leg([Leg1|Generated], Leg, [Leg,Leg1|Generated]) :‐
Leg = [_Node, _Pred, H],
0
(/progress/?
Your Progress
0
javascript:;
https://www.openlearning.com/progress/?course=unswcourses/courses/comp93414&student=linhan94
Leg = [_Node, _Pred, H],
Leg1 = [_Node1,_Pred1,H1],
5. H < H1, ! . % Search recursively for the correct place to insert. insert_one_leg([Leg1|Generated], Leg, [Leg1|Generated1]) :‐ insert_one_leg(Generated, Leg, Generated1). 0 (/progress/? Your Progress 0 javascript:; https://www.openlearning.com/progress/?course=unswcourses/courses/comp93414&student=linhan94 % A‐Star Search % COMP3411/9414/9814 Artificial Intelligence, UNSW, Alan Blair % solve(Start, Solution, G, N) % Solution is a path (in reverse order) from the start node to a goal state. % G is the length of the path, N is the number of nodes expanded. solve(Start, Solution, G, N) :‐ consult(pathsearch), % insert_legs(), head_member(), build_path() h(Start,H), astar([[Start,Start,0,H]], [], Solution, G, 1, N). % astar(Generated, Expanded, Solution, L, N) % % Generated = [[Node1,Prev1,G1,H1],[Node2,Prev2,G2,H2],...,[Start,Start,0,H0]] % Expanded = [[Node1,Prev1],[Node2,Prev2],...,[Start,Start]] 5. % Store the steps generated but not yet expanded in a queue % sorted in increasing order of G+H. % If the next leg to be expanded begins with a goal node, % stop searching, build the path and return it. astar([[Node,Pred,G,_H]|_Generated], Expanded, Path, G, N, N) :‐ goal(Node), 5. build_path([[Node,Pred]|Expanded], Path). % Extend the leg at the head of the queue by adding the % successors of its head node. % Add these newly created legs to the end of the queue astar([[Node,Pred,G,_H]| Generated], Expanded, Solution, G1, L, N) :‐ 5. extend(Node, G, Expanded, NewLegs), M is L + 1, insert_legs(Generated, NewLegs, Generated1), astar(Generated1, [[Node,Pred]|Expanded], Solution, G1, M, N). % find all successor nodes to this node, and check in each case % that the new node has not previously been expanded extend(Node, G, Expanded, NewLegs) :‐ % write(Node),nl, % print nodes as they are expanded 5. findall([NewNode, Node, G1, H], (s(Node, NewNode, C) , not(head_member(NewNode, Expanded)) , G1 is G + C , h(NewNode, H) ), NewLegs). % base case: insert one leg into an empty list. insert_one_leg([], Leg, [Leg]). % If we already knew a shorter path to the same node, discard the new one. insert_one_leg([Leg1|Generated], Leg, [Leg1|Generated]) :‐ Leg = [Node,_Pred, G, _H], Leg1 = [Node,_Pred1,G1,_H1], 5. G >= G1, ! .
% Insert the new leg in its correct place in the list (ordered by G+H).
insert_one_leg([Leg1|Generated], Leg, [Leg,Leg1|Generated]) :‐
0
(/progress/?
Your Progress
0
javascript:;
https://www.openlearning.com/progress/?course=unswcourses/courses/comp93414&student=linhan94
insert_one_leg([Leg1|Generated], Leg, [Leg,Leg1|Generated]) :‐
Leg = [_Node, _Pred, G, H ],
Leg1 = [_Node1,_Pred1,G1,H1],
5. F1 is G1 + H1,
F is G + H,
F < F1, ! . % Search recursively for the correct place to insert. insert_one_leg([Leg1|Generated], Leg, [Leg1|Generated1]) :‐ insert_one_leg(Generated, Leg, Generated1). 0 (/progress/? Your Progress 0 javascript:; https://www.openlearning.com/progress/?course=unswcourses/courses/comp93414&student=linhan94 % Iterative Deepening A‐Star Search % COMP3411/9414/9814 Artificial Intelligence, UNSW, Alan Blair % solve(Start, Solution, G, N) % Solution is a path (in reverse order) from Node to a goal state. % G is the length of the path, N is the number of nodes expanded. solve(Start, Solution, G, N) :‐ 5. nb_setval(counter,0), idastar(Start, 0, Solution, G), nb_getval(counter,N). % Perform a series of depth‐limited searches with increasing F_limit. idastar(Start, F_limit, Solution, G) :‐ depthlim([], Start, 0, F_limit, Solution, G). idastar(Start, F_limit, Solution, G) :‐ write(F_limit),nl, F_limit1 is F_limit + 2, % suitable for puzzles with parity idastar(Start, F_limit1, Solution, G). % depthlim(Path, Node, Solution) % Use depth first search (restricted to nodes with F <= F_limit) % to find a solution which extends Path, through Node. % If the next node to be expanded is a goal node, add it to % the current path and return this path, as well as G. depthlim(Path, Node, G, _F_limit, [Node|Path], G) :‐ goal(Node). % Otherwise, use Prolog backtracking to explore all successors % of the current node, in the order returned by s. % Keep searching until goal is found, or F_limit is exceeded. depthlim(Path, Node, G, F_limit, Sol, G2) :‐ 5. nb_getval(counter, N), N1 is N + 1, nb_setval(counter, N1), % write(Node),nl, % print nodes as they are expanded s(Node, Node1, C), 10. not(member(Node1, Path)), % Prevent a cycle G1 is G + C, h(Node1, H1), F1 is G1 + H1, F1 =< F_limit, 15. depthlim([Node|Path], Node1, G1, F_limit, Sol, G2). 0 (/progress/? Your Progress 0 javascript:; https://www.openlearning.com/progress/?course=unswcourses/courses/comp93414&student=linhan94 No tags yet Activity: Running the Code 1. Download the code by following the instructions in Week 3 Prolog Code: Path Search (the same zip �le includes code for Informed as well as Uninformed Search algorithms). 2. Launch prolog by typing prolog (or swipl ) 4. Load the information for the Romania map: ?‐ [romania]. true. 5. Load the instructions for the Greedy Search algorithm: ?‐ [greedy]. true. 6. Search for a path from Timisoara to Bucharest: ?‐ solve(timisoara,Sol,G,N). Sol = [bucharest, pitesti, craiova, dobreta, mehadia, lugoj, timisoara], G = 6, N = 10 7. Now try A*Search by re-launching Prolog and typing [astar] instead of [greedy] . Run searches with di�erent starting points. You can change the goal by commenting out goal(bucharest) and replacing it with, for example, goal(lugoj) . 8. If you have time, try searching the 15-Puzzle instead of the Romania map, by typing: ?‐ [puzzle15]. true. ?‐ [breadthfirst]. true. 5. ?‐ start10(Pos), solve(Pos, Sol, G, N), showsol(Sol). Challenge Activity: Implement Another Path Search Problem in Prolog Choose another path search problem and implement it in Prolog, so that it can interface with the path search algorithms we have provided. You will need to de�ne goal() as well as the successor function s() and (for Informed search) the heuristic function h() . Post your code (and any other observations) below. Alan Blair (/u/alanblair) – 19 days ago (Apr 11 2017, 5:52 p.m.) Be the �rst to like this Like(/u/alanblair) Comments Collapse All Sorted by: New Threads Write a comment... Robert Newey (https://www.openlearning.com/u/robert.newey) · about a month ago 0 (/progress/? Your Progress 0 https://www.openlearning.com/u/alanblair https://www.openlearning.com/u/alanblair https://www.openlearning.com/u/robert.newey javascript:; https://www.openlearning.com/progress/?course=unswcourses/courses/comp93414&student=linhan94