SEARCHING

Introduction

· Suppose we have a graph defined by two predicates:

start(StartingPlace) This predicate identifies a starting point in the graph. Usually it will identify a unique node in the graph, one which has no predecessors, but that isn’t strictly necessary.

child((ParentPlace,ChildPlace)This predicate is true whenever ParentPlace and ChildPlace are nodes of the graph and there is an arc leading directly from ParentPlace to ChildPlace.

and we want to locate nodes which can be reached from a starting place by following “child” arcs which satisfy a third given predicate:

solution(InterstingPlace)which is true of those nodes in the graph which we are interested in finding

· In Prolog we can search using different techniques: simple depth-first, depth-first with explicit open set, breadth-first, breadth-first with queues, etc.

Sample tree

start(a).

child(a,b).

child(a,c).

child(b,d).

child(b,e).

child(c,f).

child(c,g).

solution(b).

solution(f).

Simple Depth-First Search

answer(Y):-

start(X),

child_star(X,Y),

solution(Y).

child_start(X,X).

child_star(X,Z):-

child(X,Y),

child_star(Y,Z).

· This program has two readings: a declarative reading and a procedural reading.

- Declarative reading: it is a description of what we mean by Y being an answer.

- Procedural reading: it is a program that can be executed to find answers. It is a depth-first program (it searches each node’s children before it explores its brothers).

· Prolog has depth-first as its default specification. Depth-first has many virtues, but it is not always the best way of searching a graph.

· We can write programs which specify a different search order.

Depth-First Search with explicit Open set

• It is more convenient to pick up all the children of a node at once:

children(ParentNode,ChildrenNodes):-

findall(ChildNode,child(ParentNode,ChildNode),ChildrenNodes).

• The new program is:

depth_first(Answer):-

start(Start),

depth_star(/*Open*/[Start],Answer),

solution(Answer).

depth_star([X|_],X).

depth_star([X|Open1],Y):-

children(X,Children),

append(Children,Open1,Open2),

depth_star(Open2,Y).

Compare with simple Depth-First:

• The collection of unexplored nodes is visible as an explicit list (rather than being implicit in the stack frames of the child_star/2 predicate).
• depth_start/2 is popping nodes off the front of the list, and pushing the children back onto the front, so the Open set is being maintained as a stack.

The Importance of Queues (FIFO)

[A queue is a first-in first-out (FIFO) store of information; i.e. we add elements at one end and remove them from the other]

For example,

Given a difference list [a,b,c|Tail]/Tail,

[a,b,c|Tail] is an open list,

the beginning of the queue is [a,b,c] ( the head of the open list), and

the end of the queue is Tail, and

the members of the queue are the members of the open list.

Why bother?

Lists are good for implementing the stacks, but with a queue we add elements at one end and remove them from the other.

A simple approach would be to use lists:

empty_queue_1([]).

queue_head_1(Head,Queue1,[Head|Queue1]).

queue_last_1(Last,Queue1,Queue0):-

append(Queue1,[Last],Queue0).

Problems:

Making an empty queue/adding/removing an element at the left of a queue costs unit time, but adding/removing an element at the right of a queue having N elements costs O(N) time and space.

Batching updates:

queue_head_list_1(Heads,Queue1,Queue0):-

append(Heads,Queue1,Queue0).

queue_last_list_1(Lasts,Queue1,Queue0):-

append(Queue1,Lasts,Queue0).

[Adding M elements at the right of a queue having N elements with these definitions costs O(N) time, rather than the O(MN) time that adding the elements one at a time would cost.].

Another option:

Keep a back-to-back pair of lists L+R, where L+R is the sequence represented by the list append(L,reverse(R)).

empty_queue_2([]+[]).

queue_head_2(Head,L+R,[Head|L]+R).

queue_head_2(Head,L+[],[]+R):-

reverse(R,[Head|L]).

queue_last_2(Last,L+R,L+[Last|R]).

queue_last_2(Last,[]+R,L+[]):-

reverse(L,[Last|R]).

reverse([],[]).

reverse([Head|Tail],Result):-

reverse(Tail,ReversedTail),

append(ReversedTail,[Head],Result).

We can rewrite it as follows, to make it faster:

empty_queue_2([]+[]).

queue_head_2(Head,L1+R1,L2+R2):-

queue_head_2(L2,R2,L1,R1,Head).

queue_head_2([],R,L,[],Head):-

reverse(R,[Head|L]).

queue_head_2([Head|L],R,L,R,Head).

queue_last_2(Last,L1+R1,L2+R2):-

queue_head_2(R2,L2,R1,L1,Last).

Another option (Difference Lists):

empty_queue_3(Queue-Queue).

queue_head_3(Head, Front-Back, [Head|Front]-Back).

queue_last_3(Last, Front-[Last|Back], Front-Back).

Disadvantage:

It is possible to remove more elements from such a queue than were inserted into it. So, we need to specify the length of the queue.

The technique used in the book:

Use a difference list to hold the elements of a queue, but augment it with the current length of the queue, represented in unary notation, i.e. the queue representation looks like:

q(s(…s(0)..), [X1,…,Xn,Y1,…],[Y1,…])

n 1 1 n

where the term 0 represents the integer 0, and s(X) represents the successor of X.

Final Version :

% queue(Queue)
% is true when Queue is a queue with no elements.
 
queue(q(0,B,B)).
 
%  queue(X,Queue)
%  is true when Queue is a queue with one element.
 
queue(X,q(s(0),[X|B],B)).
 
% queue_head(X,Queue1,Queue0)
%  is true when Queue0 and Queue1 have the same elements except
%  that Queue0 has in addition X at the front.
% Use it for enqueuing and dequeuing both.
 
 
queue_head(X,q(N,F,B),q(s(N),[X|F],B)).
 
% queue_head_list(List,Queue1,Queue0)
% is true when append(List,Queue1,Queue0) would be true
%  if only Queue1 and Queue0 were lists instead of queues.
 
 
queue_head_list([],Queue,Queue).
queue_head_list([X|Xs],Queue,Queue0):-
 queue_head(X,Queue1,Queue0),
 queue_head_list(Xs,Queue,Queue1).
 
% queue_last(X,Queue0,Queue1)
% is true when Queue0 and Queue1 have the same elements except
% that Queue0 has in addition X at the end.
 
queue_last(X,q(N,F,[X|B]),q(s(N),F,B)).
 
 
% queue_last_list(List,Queue1,Queue0)
% is true when append(Queue1,List,Queue0) would be true
% if only Queue1 and Queue0 were lists instead of queues.
 
queue_last_list([],Queue,Queue).
queue_last_list([X|Xs],Queue1,Queue):-
 queue_last(X,Queue1,Queue2),
 queue_last_list(Xs,Queue2,Queue).
 
 
 
 
% list_queue(List,Queue)
% is true when List is a list and Queue is a queue and they
% represent the same sequence
 
list_queue(List,q(Count,Front,Back)):-
 list_queue(List,Count,Front,Back).
 
list_queue([],0,B,B).
list_queue([X|Xs],s(N),[X|F],B):-
 list_queue(Xs,N,F,B).
 
 
% queue_length(Queue,Length)
% is true when Length is (a binary integer representing) the number
% of elements in (the queue represented by) Queue. This version cannot
% be used to generate a Queue, only to determine the Length.
 
 
queue_length(q(Count,Front,Back),Length):-
 queue_length(Count,Front,Back,0,Length).
 
queue_length(0,Back,Back,Length,Length).
queue_length(s(N),[_|Front],Back,L0,Length):-
 L1 is L0+1,
 queue_length(N,Front,Back,L1,Length).
 
 

Breadth-First Search

[All the nodes that are N steps away from the starting point will be explored before any of the nodes that are N+1 steps away from the starting point]

Changes:

• Add the children at the other end of the Open list.

[With this change we maintain the Open collection as a queue rather than a stack!]

Compare with Depth-First Search with explicit Open set:

· A very small change in the code causes such a crucial difference in behavior:

We swapped the first two arguments of append/3

breadth_first_1(Answer):-

start(Start),

breadth_star_1(/*Open*/[Start],Answer),

solution(Answer).

breadth_star_1([X|_],X).

breadth_star_1([X|Open1],Y):-

children(X,Children),

append(Open1,Children,Open2),

breadth_star_1(Open2,Y).

Breadth-First Search with Simple Lists

· This program has an open set. The children of a given node are looked at immediately one after the other (breadth_first), and, when looking at each of them their respective children are inserted at the end of the open list . The result is not a stack but a queue (first in first out).

breadth_first_1(Answer):-

start(Start),

breadth_star_1(/*Open*/[Start],Answer),

solution(Answer).

breadth_star_1([X|_],X).

breadth_star_1([X|Open1],Y):-

children(X,Children),

append(Open1,Children,Open2),

breadth_star_1(Open2,Y).

Breadth-First Search with Difference Lists

· A faster version of breadth_first_1 is breadth_first_2:

breadth_first_2(Answer):-

start(Start),

breadth_star_2([Start|Rest],Rest,Y),

solution(Y),

!,

Answer=Y.

breadth_star_2([X|Open],Rest,Y):-

(Y=X

; children(X,Children),

append(Children,Rest1,Rest),

breadth_star_2(Open,Rest1,Y)).

/* The difference between this program and the previous one is just that breadth_star_2 is defined not a relation between a simple list and an element, but as a relation between a difference list and an element */

Breadth-first-1(with simple lists) vs. breadth-first-2 (with difference lists):

· Breadth_first_2 is faster than Breadth_first_1 since it appends the children of each new node to the end of the rest of the difference list, instead of appending them to the end of the whole open list.

· Breadth_first_2 works only provided there is at least one answer in the tree, and it finds only one answer (the highest one in the tree). (Note that Breadth_first_1 did not have these restrictions).

- The restrictions on Breadth_first_2 procede from the fact that a cut is needed after one solution is found in order to stop the program from hallucinating infinite nodes (and never terminating).

Breadth-First Search with Queues

· We can code breadth-first search more efficiently with the aid of the queue package.

breadth_first(Answer):-

start(Start),

queue(Start,Open),

breadth_star(Open,Answer),

solution(Answer).

breadth_star(Open,Y):-

queue_head(X,Open1,Open),

( Y=X

; children(X,Children),

queue_last_list(Children,Open1,Open2),

breadth_star(Open2,Y)

).

/* breadth_star is defined here as the relation between a queue whose head is the starting node and an element; breadth_star calls the predicate queue_head, which decomposes the queue (Open) into e head and a queue without the head. If the head = Answer the program jumps back to “breadth_first, otherwise it appends the children of the head to the queue without the head thus getting a new queue. Then it goes to breadth_star again (recursion) */

Breadth-first-2 (with difference lists) vs. Breadth-first with Queues:

· Breadth_first uses queues and is slower than breadth_first_2.

· Breadth_first does not have the restrictions stated above for Breadth_first_2. Thus, breadth_first can check a graph with no answers, or a graph with several answers, and it always terminates-. The queue does not hallucinate new nodes when a node has no children.

· Fragment of a trace of breadth_first (with queues) (it terminates):

Query: breadth_first(X):

Fragment of the trace showing that the program does not hallucinate new nodes after the last node of the tree has been looked at:

Exit: (14) children(g, []) ? creep

Call: (14) queue_last_list([], q(0, _G625, _G625), _G667) ? creep

Exit: (14) queue_last_list([], q(0, _G625, _G625), q(0, _G625, _G625)) ? creep

Call: (14) breadth_star(q(0, _G625, _G625), _G420) ? creep

Call: (15) queue_head(_G665, _G666, q(0, _G625, _G625)) ? creep

Fail: (15) queue_head(_G665, _G666, q(0, _G625, _G625)) ? creep

Fail: (14) breadth_star(q(0, _G625, _G625), _G420) ? creep

Fail: (14) queue_last_list([], q(0, _G625, _G625), _G667) ? creep

^ Fail: (15) findall(_G659, child(g, _G659), _G670) ? creep

Fail: (14) children(g, _G663) ? creep

/* Call 15 fails because the third argument of queue_head has to be a queue with one element, not an empty queue (the program keeps track of how many nodes it still has available)*/

Improved Versions of Breadth-First with Queues

· Second version of Breadth-First with Queues:

breadth_first(Answer):-

start(Start),

breadth_star(s(0),[Start|B0],B0,Answer),

solution(Answer).

breadth_star(s(N1),[Node|F1],B1,Answer):-

( Answer=Node

; children(Node,Children),

queue_last_list(Children,N1,F1,B1,N2,F2,B2),

breadth_star(N2,F2,B2,Answer)

).

queue_last_list([],N,F,B,N,F,B).

queue_last_list([X|Xs],N0,F1,[X|B1],N,F,B):-

queue_last_list(Xs,s(N0),F1,B1,N,F,B).

/* The predicates “queue” and “breadth_star” from the first version have been merged; All the queues have been unpacked (see predicates “breadth_star” and “queue_last_list”. Unpacking the arguments of a compound term speeds up a Prolog procedure. */

· Third version of Breadth-First with Queues:

breadth_first(Answer):-

start(Start),

breadth_one(s(0),[Start|B],B,Answer).

breadth_one(s(N1),[Node|F1],B1,Answer):-

( solution(Node),

Answer=Node

; children(Node,Children),

breadth_two(Children,N1,F1,B1,Answer)

).

breadth_two([],N,F,B,Answer):-

breadth_one(N,F,B,Answer).

breadth_two([X|Xs],N,F,[X|B],Answer):-

breadth_two(Xs,s(N),F,B,Answer).

/* The maximum arity of predicates in this program is 5, whereas the previous version contained predicates with 7 arguments (“queue_last_list”). The main change in the program refers to the predicates which construct longer queues by adding new children to the old queue. Before, we had the predicate “queue_last_list”, formulated as follows:

queue_last_list([],N,F,B,N,F,B).

queue_last_list([X|Xs],N0,F1,[X|B1],N,F,B]:-

queue_last_list(Xs,s(N0),F1,B1,N,F,B).

Now, we have the predicate “breadth_two”:

breadth_two([],N,F,B,Answer):-

breadth_one(N,F,B,Answer).

breadth_two([X|Xs],N,F,[X|B],Answer):-

breadth_two(Xs,s(N),F,B,Answer).

Breadth_two/5 says that when the list of children is empty the predicate “breadth_one” has to hold between the old list (with no changes) and the Answer. When the list of children is not empty, the predicate “breadth_two” has to hold between a new queue with one more element (the head of the children) and the Answer (recursive clause). */

· Fourth version of Breadth-First with Queues:

breadth_first(Answer):-

start(Start),

breadth_star([],s(0),[Start|B],B,Answer).

breadth_star([],s(N),[Node|F],B,Answer):-

( solution(Node),

Answer=Node

; children(Node,Children),

breadth_star(Children,N,F,B,Answer)

).

breadth_star([X|Xs],N,F,[X|B],Answer):-

breadth_star(Xs,s(N),F,B,Answer).

/* This program is the result of doing the following changes in the previous one: the first clause of “breadth_two” has been merged with the clause “breadth_one”. The only difference between both predicates was that “breadth_two” had one more argument, the first one, an empty list. The predicate “breadth_one” has been changed, a new argument has been added (the empty list is now its first argument). This has no effect in the way “breadth_one” works, since this empty list is a constant that does not play a role in the conditions for the satisfaction of the clause. */

Search with Closed Sets

· It can be useful to keep track at every moment of the nodes that we don’t want to look at in the process of searching. Sometimes these will be nodes that have already been looked at (for instance, in case of cyclic graphs, if we want to avoid infinite loops, we will need to

prevent the program from looking at the same node more than once), sometimes these will be nodes with certain characteristics that we are not interested in. In order to keep track of these nodes the predicate “ord_union” can be used.

Ord_union(+OldSet, +NewSet, ?Union, ?ReallyNew): Given an OldSet and a NewSet, this returns their Union, and the ReadllyNew elements, namely the elements of the NewSet which were not already in OldSet.

depth_first(Answer):-

start(Start),

depth_star(/*Open*/[Start],/*Closed*/[Start],Answer),

solution(Answer).

depth_star([X|_],_,X).

depth_star([X|Open1],Closed,Y):-

children(X,Children),

ord_union(Closed,Children,Closed1,Children1),

append(Children1,Open1,Open2),

depth_star(Open2,Closed1,Y).

children(ParentNode,ChildrenSet):-

findall(ChildNode,

child(ParentNode,ChildNode),

ChildrenNodes),

sort(ChildrenNodes,ChildrenSet).

breadth_first(Answer):-

start(Start),

queue(Start,Open),

breadth_star(Open,/*Closed*/[Start],Answer),

solution(Answer).

breadth_star(Open,Closed,Y):-

queue_head(X,Open1,Open),

( Y=X

; children(X,Children),

ord_union(Closed,Children,Closed1,Children1),

queue_last_list(Children1,Open1,Open2),

breadth_star(Open2,Closed1,Y)

).

Local Heuristic Ordering

:-['/home/dm/lehre/01/autumn/795E/sics_library/ordsets'].

h_depth_first(Answer):-

start(Start),

h_depth_star(/*Open*/[Start],/*Closed*/[Start],Answer),

solution(Answer).

h_depth_star([X|_],_,X).

h_depth_star([X|Open1],Closed,Y):-

children(X,Closed,Closed1,Children1),

append(Children1,Open1,Open2),

h_depth_star(Open2,Closed1,Y).

children(ParentNode,Closed,Closed1,RankedChildren):-

ordered_children(ParentNode,Closed,Closed1,OrdPairs),

strip_ranks(OrdPairs,RankedChildren).

ordered_children(ParentNode,Closed,Closed1,OrdPairs):-

children(ParentNode,ChildrenSet),

ord_union(Closed,ChildrenSet,Closed1,NewChildren),

compute_ranks(NewChildren,RawPairs),

keysort(RawPairs,OrdPairs).

compute_ranks([],[]).

compute_ranks([Child|Children],[Estimate-Child|Pairs]):-

estimated_distance_to_goal(Child,Estimate),

compute_ranks(Children,Pairs).

strip_ranks([],[]).

strip_ranks([_-Child|Pairs],[Child|Children]):-

strip_ranks(Pairs,Children).

h_breadth_first(Answer):-

start(Start),

queue(Start,Open),

h_breadth_star(Open,/*Closed*/[Start],Answer),

solution(Answer).

h_breadth_star(Open,Closed,Y):-

queue_head(X,Open1,Open),

( Y=X

; children(X,Closed,Closed1,Children1),

queue_last_list(Children1,Open1,Open2),

h_breadth_star(Open2,Closed1,Y) /* Typo in the book */

).

Global Heuristic Ordering

Local Ordering: We ordered the children of a node by their distance to the closest solution.

Global Ordering: We can keep the entire Open set in such an order.

We need a data structure which represents a collection of nodes and cost estimates from which we can cheaply select the node with lowest associated cost estimate.

Here are the operations that we need:

empty_heap(-Heap) make an empty heap.

add_to_heap(+Heap0,+Cost,+Node,-Heap) add a Node and its associated cost to a given Heap0, yielding a new Heap containing that Node and the contents of the old Heap0.

get_from_heap(+Heap0,-Cost,-Node,-Heap) remove from a given Heap0 the Node with the lowest associated Cost, and return the updated Heap.

Example:

?- empty_heap(H0),add_to_heap(H0,4,a,H1),

add_to_heap(H1,0,b,H2),add_to_heap(H2,5,c,H3),

get_from_heap(H3,X,Y,H4),get_from_heap(H4,A,B,H5).

A = 4,

B = a,

X = 0,

Y = b,

H0 = t(0,[],t),

H1 = t(1,[],t(4,a,t,t)),

H2 = t(2,[],t(0,b,t(4,a,t,t),t)),

H3 = t(3,[],t(0,b,t(4,a,t,t),t(5,c,t,t))),

H4 = t(2,[2],t(4,a,t,t(5,c,t,t))),

H5 = t(1,[3,2],t(5,c,t,t)) ? ;

no

best_first(Answer):-

start(Start),

initial_heap(Start,Heap),

best_star(/*Open*/Heap,/*Closed*/[Start],Answer),

solution(Answer).

initial_heap(Start,Heap):-

estimated_distance_to_goal(Start,Estimate),

empty_heap(Empty),

add_to_heap(Empty,Estimate,Start,Heap).

best_star(Heap,Closed,Answer):-

get_from_heap(Heap,_,Node,Heap1),

( Answer=Node

; children_4(Node,Closed,Closed1,Heap1,Heap2),

best_star(Heap2,Closed1,Answer)

).

children_4(ParentNode,Closed,Closed1,Heap,Heap1):- ordered_children(ParentNode,Closed,Closed1,OrdPairs),

add_children(OrdPairs,Heap,Heap1).

add_children([],Heap,Heap).

add_children([Estimate-Child|Children],Heap0,Heap):-

add_to_heap(Heap0,Estimate,Child,Heap1),

add_children(Children,Heap1,Heap).

children(ParentNode,Closed,Closed1,RankedChildren):-

ordered_children(ParentNode,Closed,Closed1,OrdPairs),

strip_ranks(OrdPairs,RankedChildren).

ordered_children(ParentNode,Closed,Closed1,OrdPairs):-

children(ParentNode,ChildrenSet),

ord_union(Closed,ChildrenSet,Closed1,NewChildren),

compute_ranks(NewChildren,RawPairs),

keysort(RawPairs,OrdPairs).

compute_ranks([],[]).

compute_ranks([Child|Children],[Estimate-Child|Pairs]):-

estimated_distance_to_goal(Child,Estimate),

compute_ranks(Children,Pairs).

An Example:”The 8-puzzle”

The goal is to rearrange the puzzle by sliding the squares one at a time to some prespecified final configuration. [The graph nodes represent puzzle configurations, and the arcs represent legal transitions between them.]

%The 8-Puzzle

start([1,2,3,7,8,4,6,5,hole]).

solution([A1,B1,C1,D1,E1,F1,G1,H1,I2]).

child([A,B,C,D,E,F,G,H,I],[A1,B1,C1,D1,E1,F1,G1,H1,I1]) :-

slide([[A,D,G],[B,E,H],[C,F,I]],[[A1,D1,G1],[B1,E1,H1],[C1,F1,I1]]).

child([A,B,C,D,E,F,G,H,I],[A1,B1,C1,D1,E1,F1,G1,H1,I1]) :-

slide([[A,B,C],[D,E,F],[G,H,I]],[[A1,B1,C1],[D1,E1,F1],[G1,H1,I1]]).

/* deal with each column or row. X, Y and Z are bound to either whole rows or whole columns. */

slide([X,Y,Z],[X1,Y,Z]) :- move_tile(X,X1).

slide([X,Y,Z],[X,Y1,Z]) :- move_tile(Y,Y1).

slide([X,Y,Z],[X,Y,Z1]) :- move_tile(Z,Z1).

/* deal with a column or row, downs and rights before ups and

lefts. C1 and C2 are bound to either a whole row or a whole column. */

move_tile(C1,C2) :- down(C1,C2).

move_tile(C1,C2) :- up(C1,C2).

/* move tile down or to the right. X and Y are bound to individual tiles. */

down([X,Y,hole],[X,hole,Y]).

down([X,hole,Y],[hole,X,Y]).

/* move tile up or to the left. X and Y are bound to individual tiles.*/

up([hole,X,Y],[X,hole,Y]).

up([X,hole,Y],[X,Y,hole]).

Summary

• Heuristic information can be used to estimate how far a node is from a nearest goal node in the state space.
• The best_first heuristic principle guides the search process so as to always expand the node that is currently the most promising, according to the heuristic estimates.

The Rest of the Chapter:

Iterative Deepening (won’t be discussed in this presentation)

Iterative deepening is a simple modification of depth-first search. It sets a limit on the length of the paths being searched, and exhaustively searches all paths whose length is within the limit. If no solution is found, the limit on path length is increased and the process is repeated.