A* Search

This is a framework for an A* search inspired by the other similar search frameworks given in Sterling and Shapiro's "The Art of Prolog".

domains
  /* move, posn and value must be defined by the caller */
  asmoves  = move*
  asposns  = posn*
  asstate  = s(posn,asmoves,value)
  asstates = asstate*
predicates
/* The following must be defined by the caller:
  initial_posn(posn)
  final_posn(posn)
  nondeterm move(posn,move) 
  update(posn,move,posn) 
  legal(posn)
  value(posn,value) /* Underestimate of "cost" from current to final */ 
*/
  astar(asmoves)
  astar_1(asstates,asposns,asmoves)
  filter(asmoves,asstate,asposns,asstates,asstates)
  insert(asstates,asstate,asstates)
  reverse(asmoves,asmoves,asmoves)
  nondeterm member(posn,asposns)
  length(asmoves,value,value)
clauses

astar(Moves):-
  initial_posn(Position),
  astar_1([s(Position, [], 0)], [], Moves).

/* astar_1(States, History, Moves) is true if Moves is a sequence of       */
/*   moves to reach a desired final state from the initial state, where    */
/*   States contains the current states under consideration, and History   */
/*   contains the positions visited previously.                            */
astar_1([s(Posn, Path, _)|_], _, Moves):-
  final_posn(Posn),
  reverse(Path, [], Moves).
astar_1([s(Posn, Path, Value)|States], History, FinalMoves):-
  findall(Move, move(Posn, Move), Moves),
  filter(Moves, s(Posn, Path, Value), History, States, States1),
  astar_1(States1, [Posn|History], FinalMoves).

filter([], _, _, States, States).
filter([Move|Moves], s(Posn, Path, Value0), History,
             States, States1):-
  update(Posn, Move, Posn1),
  legal(Posn1),
  not(member(Posn1, History)),
  !,
  value(Posn1, Value),
  length(Path, Value, Value1),
  insert(States, s(Posn1, [Move|Path], Value1), States0),
  filter(Moves, s(Posn, Path, Value0), History, States0, States1).
filter([_|Moves], State, History, States, States1):-
  filter(Moves, State, History, States, States1).

insert([s(P2, M2, V2)|States0], s(P1, M1, V1), States):-
  V1 > V2, !,
  insert(States0, s(P1, M1, V1), States1),
  States = [s(P2, M2, V2)|States1].
insert(States, State, [State|States]).

/* member(X, Xs) is true if X is a member of the list Xs.                  */
member(X, [X|_]).
member(X, [_|Ys]):-member(X, Ys).

/* reverse(Xs, Ys, Zs) is true if Zs is the result of concatenating the    */
/*   reverse of the list Xs to the front of the list Ys.                   */
reverse([], Ys, Ys).
reverse([X|Xs], Ys, Zs):-reverse(Xs, [X|Ys], Zs).

/* length(Xs, L0, L) is true if L is equal to L0 plus the number of        */
/*   elements in the list Xs.                                              */
length([], L, L).
length([_|Xs], L0, L):-L1 = L0 + 1, length(Xs, L1, L).

Turbo Prolog Index     Home Page