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".

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),
  \+ member(Posn1, History), !,
  value(Posn1, I),
  length(Path, J),
  Value1 is I + J,
  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, !,
  States = [s(P2, M2, V2)|States1],
  insert(States0, s(P1, M1, V1), States1).
insert(States, State, [State|States]).

/*
 * Test Data - This is Exercise 18.1 (ii) from "The Art of Prolog"
 *             by Sterling and Shapiro
 */

/* p(WhereTheBoatIs, MissionariesOnLeft, CannibalsOnLeft)                  */
/* m(MissionariesInBoat, CannibalsInBoat)                                  */
 
initial_posn(p(left, 3, 3)).

final_posn(p(right, 0, 0)).

move(p(left,  M, _), m(1, 0)):-M >= 1.
move(p(left,  _, C), m(0, 1)):-C >= 1.
move(p(left,  M, C), m(1, 1)):-M >= 1, C >= 1.
move(p(left,  M, _), m(2, 0)):-M >= 2.
move(p(left,  _, C), m(0, 2)):-C >= 2.
move(p(right, M, _), m(1, 0)):-(3 - M) >= 1.
move(p(right, _, C), m(0, 1)):-(3 - C) >= 1.
move(p(right, M, C), m(1, 1)):-(3 - M) >= 1, (3 - C) >= 1.
move(p(right, M, _), m(2, 0)):-(3 - M) >= 2.
move(p(right, _, C), m(0, 2)):-(3 - C) >= 2.

update(p(left, M0, C0), m(MB, CB), p(right, M, C)):-
  M is M0 - MB, C is C0 - CB.
update(p(right, M0, C0), m(MB, CB), p(left, M, C)):-
  M is M0 + MB, C is C0 + CB.

/* This uses an (under)estimation of the number of remaining voyages as    */
/*   the evaluation function.                                              */
value(p(_,     M, C), 1):-M + C =:= 1, !.
value(p(left,  M, C), L):-L is (M + C - 2) * 2 + 1.
value(p(right, M, C), L):-L is (M + C) * 2.

/* Ensures that, on each bank, the cannibals are not outnumbered */
legal(p(_, _, 3)):-!.
legal(p(_, _, 0)):-!.
legal(p(_, M, M)).

LPA Index     Home Page

Valid HTML 4.01 Strict