An implementation of IDA star

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % IDA* implemented using assert and % % retract. % % An implementation without assert or % % retract requires an agenda and some % % way of keeping track of the paths. % % Thus losing the space advantage of % % depth first search. % % % % Author. J.P.E. Hodgson % % Date Started 11/30/1994 % % Last Changed 1/4/95 % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % This code runs under standard prolog. The minor % modifications required for ALS, Quintus, BIM % and LPA prolog are indicated as necessary. % :- dynamic(next_bound/1). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % The user must supply the heuristic relation % value(+Node, -Value), and the successor relation % successor(+Node, -ChildNode, -TransitionCost). % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ida_star(+Start, % Node to start from % -Soln) % Solution % ida_star(Start, Soln) :- abolish(next_bound/1), % in ALS prolog abolish(next_bound,1) value(Start, H), asserta(next_bound(infinity)), % set bound for next search. ida_star(parent,[], Start/0,H,Start, Soln). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5 % % ida_star(+master_slave, % is this a master or a slave % +Path, % Path to node before current node % +Node/Cost, % Pairing of current node and cost to reach it % +CurrentBound, % Bound for current search % +Start, % Start, needed for next search. % -NewPath % New path. % Goal reached. ida_star(_,Path, Node/G, _,Start, [Node|Path]) :- goalreached(Node). % Normal search. Depth first with cutoff if bound is exceeded. % Checks to see if next bound needs to be reset lower. ida_star(_,Path, Node/G, Bound, Start,Soln) :- successor(Node, Node1, C), not member(Node1, Path), % no looping. G1 is G + C, value(Node1, H1), F1 is G1 + H1, revise_next_bound(F1, Bound), lesseq(F1,Bound), % acceptable node ida_star(slave,[Node|Path], Node1/G1, Bound,Start, Soln). % Normal search failed, try to go deeper. This clause % is only available to the master search. ida_star(master,_, _, Bound, Start, Soln) :- next_bound(Next), Next = Bound -> (write('Search has failed'),nl ) ; ( % Do deeper search reset_next_bound, ida_star(master,[], Start/0, Next, Start, Soln) ). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % revise_next_bound(+Val, +CurrentBound) % % update the asserted value of next_bound. % This must always succeed. % revise_next_bound(Val, Current) :- lesseq(Val, Current), !. revise_next_bound(Val,Current ) :- next_bound(Next), (better(Val, Next) -> retract(next_bound(Next)), asserta(next_bound(Val)); true). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % reset_next_bound/0 if a new search is started % next bound needs to be set to infinity. % reset_next_bound :- retract(next_bound(Val)), asserta(next_bound(infinity)). %%%%%%%%%%%%%%%%%%%%% % % better(+V1,+V2) true if V1 is less than V2, V2 may be infinity % better(Val, infinity) :- !. better(Val, V1) :- Val < V1, !. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % lesseq(+V1, +V2) true if V1 is V1 is less than or equal to V2, % V2 may be infinity. % lesseq(F, infinity) :- !. lesseq(F, Bd) :- F =< Bd.
Jonathan Hodgson
Last Changed: 30/11/1994