Introduction

• Farmer, Wolf, Goat, Cabbage (Production System)
• Stack
• Queue
• Priority Queue
• Best First Search

Search in PROLOG

Setting up the Search

The main predicate for all three types of searches will initialize the data structures and invoke the path/3 predicate, which will recursively search from the start to the goal state.

The main predicate for depth-first search looks as follows:

    go(Start,Goal) :-
        empty_stack(Empty_open),
        stack([Start,nil], Empty_open, Open_list),
        empty_set(Closed_set),
        path(Open_list, Closed_set, Goal).

The main predicate for breadth-first search looks as follows:

    go(Start,Goal) :-
        empty_queue(Empty_open),
        enqueue([Start,nil], Empty_open, Open_list),
        empty_set(Closed_set),
        path(Open_list, Closed_set, Goal).

Note that for depth first and breadth first searches the current state is represented as the list [State,Parent]. For the initial state this gives [Start,nil] because the initial state has no parent. This representation of the current state allows the solution path to be recursively reconstructed from the goal state and the closed list as follows:

    printsolution([State,nil],_) :- write(State),nl.
    printsolution([State,Parent), Closed_set) :-
        member_set([Parent,GrandParent], Closed_set),
        printsolution([Parent,GrandParent], Closed_set),
        write(State), nl. 

The main predicate for best-first search looks as follows. Note the addition of the heuristic/3 predicate:

    go(Start,Goal) :-
        empty_set(Closed_set),
        empty_pq(Empty_open),
        heuristic(Start, Goal, H),
        insert_pq([Start,nil,0,H,H], Empty_open, Open_list),
        path(Open_list, Closed_set, Goal).

Note that for best first search the state is represented as the five-tuple:

     [State,Parent,Depth,Heuristic,Sum]

   f(n) = g(n) + h(n)

Recursive Search: path/3

   path(Open_list,_,) :-
      empty_stack(Open_list),                        %% Or empty_queue or empty_pq
      write("No solution found with these rules.").

   path(Open_list, Closed_set, Goal) :-
      stack([State,Parent],_,Open_list), State=Goal,        %% Or dequeue or dequeue_pq
      write("The solution path is:"), nl,
      printsolution([State,Parent], Closed_set).      

   path(Open_list, Closed_set, Goal) :-
      stack([State,Parent],Rest_open, Open_list),           %% Or dequeue or dequeue_pq
      get_children(State, Rest_open, Closed_set, Children),
      add_list_to_stack(Children, Rest_open, New_open),       %% Or add_list_to_queue or insert_list_pq
      union([[State,Parent]],Closed_set,New_closed_set),
      path(New_open, New_closed_set, Goal), !.

The comments indicate where the differences occur among these three algorithms. Note how the recursive path/3 predicate manages the updating the open and closed lists for the search. Each level of recursion uses a different open and closed lists. If the open list becomes empty before the goal is reached, that constitutes failure. If the first element on the open list is a Goal state, that constitutes success.

The cut operator is used here to cut off PROLOG's automatic backtracking. This prevents PROLOG from storing the old values of open and closed. When search fails at any given point, the algorithm does not go back to the preceding values of open and closed. Instead, it updates open and closed

In-class Exercise