Spoiler: You might have guessed it already… you won’t see any real goat in here[1].
This is about a planning problem and how we can solve it using Prolog.
A planning ploblem could be for example a game or a more or less complex task. You know the starting and goal state and the rules to go from one state to another, but not if and how many states are between[2].
I will describe the problem, break it down to Prolog and describe how the Search-Algorithm works.

Where are the Goats now?

Okay, first things first: There is only one goat. And this goat can only survive under specific circumstances.

Imagine you are a ferryman, going from one riverside to the other. Next to some rickety grandmas (which are taking the ferry almost every day to keep themselves busy) and a bunch of heavily interested tourists (not interested at all), you were commissioned to transport three things from riverside A to riverside B:

  • A Goat
  • Some Cabbage
  • A Wolf

And there are some “Rules” you have to follow:

  • Only one thing at a time transportable
  • Goat eats Cabbage
  • Wolf eats Goat

How can the ferryman transport all three things from riverside A to B without any damage?

Breakdown of the Problem

Imagine playing a game which you never played before. The rules are clear but it might not be clear which strategy is key. So the best strategy in the first place might be guessing or do things in a specific order to gain experience. To make the things more formal: When I have situation X, which action/move/… leads me to the goal situation?

Same thing in Prolog. We can implement the rules but we need an algorithm which tries to find a solution. In order to find something, you have to search. While we have no heuristic (or in our game example: we have no experience) which tells us how we can get to the solution very quickly, we need brute force or in AI terms an uninformed search algorithm.
The most effective one is the Iterative Depth Search algorithm (IDS). This search combines the positive aspects of the breadth-first- and the depth-first search and is therefore optimal (=finds always the shortest path).

The search algorithm can walk through a graph where the nodes are states and the edges are the action/move/.. you have to do in order to go from one state to an other.

In our example, ervery state contains the location of four things: Goat, Cabbage, Wolf and Ferryman. Every thing can be either on riverside A or B. As a result every state  is a combination of the location of all four things. The Rules are telling us which actions are allowed and which not.

Let’s imagine how a search graph would look alike (cmp. Figure 1). Each node is a state and each edge is an action.

But this graph has some faulty edges which are not following our rules. Guess which!

Search Graph
Figure 1 – Snippet of the Search Graph

 

Hint

Only one edge is actually right.

[collapse]
Solution

The following edges are wrong:

Edge 1: The Ferryman is allowed to go alone, but either the Goat is eating the Cabbage or the Wolf is eating the Goat (or both).

Edge 3: The Wolf is eating the Goat.

Edge 4: The Goat is eating the Cabbage.

[collapse]

The Prolog Program

In order to make use of the search algorithm, we need to put every state into a List. Every index has it’s fixed meaning. For example is the first element the location of the goat, the second the one of the cabbage and so on.

start([a,a,a,a]).
goal([b,b,b,b]).

The previous line shows as an example the starting and goal state of our problem in Prolog.

Now we describe a transition.

transition0([G,C,W,a],[G,C,W,b]).

This transition allows the ferryman to go alone from riverside A to riverside B. This is accomplished by only allowing the ferryman variable to change the location, all other variables have to stay where they are.

Let’s add all other transitions.

transition0([a,C,W,a],[b,C,W,b]).
transition0([G,a,W,a],[G,b,W,b]).
transition0([G,C,a,a],[G,C,b,b]).

This Transition goes only in one direction. Let’s make it symmetric by adding a new transition predicate.

transition(X,Y) :- transition0(X,Y);transition0(Y,X).

The reason why I called the predicate transition and not rule is that the most rules are missing. We actually can move from A to B with only on thing at a time, but it is allowed to keep for example the wolf and the goat alone.
We need to validate each state in order to tell if the transition is allowed or not. Let’s make a new predicate for the validation and add it later to our symmetric transition.

valid([F,_,_,F]).
valid([G,C,W,_]) :- G \== C, G \==W.

This predicate takes a single state and checks if:

  1. The Goat is with the ferryman -> Everything is okay because the wolf doesn’t harm the cabbage
  2. The Goat doesn’t share its location with either wolf or cabbage. We can exclude the ferryman here while we took care of him in the rule above

Now we can add the valid predicate to our transition.

transition(X,Y) :- (transition0(X,Y);transition0(Y,X)), valid(X),valid(Y).
Summary

The transition0  Predicate describes which move is allowed from a to b.

The valid  Predicate checks if a single state is legal based on our rules.

The transition  Predicate uses our transition0  in both directions in order to go from a to b and from b to a. This is possible while Prolog doesn’t have fixed Input and Output Variables.

The Search Algorithm (IDS)

As already mentioned, the Iterative Deepening Search Algorithm fits perfect for our needs. In order to understand how this search works, I will build it up step by step.

At first we need the depth-first-search on which the IDS is based on.

ds(Node, Goal) :-
    Node == Goal;
    transition(Node,Neighbour), ds(Neighbour, Goal).

The Depth-First search works with the Back-Tracking feature of Prolog. It goes into depth until either a Goal is reached or transition  returns false. If the transition is false, it will go to the previous call of transition and will try all possible transition s until a goal has been reached or no transitionsare left.

This implementation doesn’t has a kind of a history in order to avoid infinite loops when the graph has a circle.

ds(Node, Goal, Path) :- 
    Node == Goal; 
    transition(Node,Neighbour), not(member(Neighbour,Path)),
    ds(Neighbour, Goal, [Neighbour|Path]).

Now out Search keeps track of the previous passed nodes and passes no node twice.
Until now, our Search only returns a true or false whenever the goal can be reached or not. What’s with the path itself? Unfortunately, the path will be deleted when the search comes back from the recursion. This can be added by using an additional output variable. This will be filled with a reserved version of our path while the head of the path is the last move and the last element of the tail our start node.

ds(Node, Goal, Path, ReturnPath) :- 
    Node == Goal, reverse(Path, ReturnPath);
    transition(Node,Neighbour), not(member(Neighbour,Path)), 
    ds(Neighbour, Goal, [Neighbour|Path]).

Now we have and informative Depth-First-Search but the I is still missing.

ids_core(Node, Path, Goal, DepthLimit, ReturnPath) :-
    Node == Goal,reverse(Path,ReturnPath);
    DepthLimit>0,
    transition(Node,Neighbour),not(member(Neighbour,Path)),
    ids_core(Neighbour,[Neighbour|Path],Goal,DepthLimit-1,ReturnPath).

ids_loop(Start,Goal,DepthLimit,ReturnPath) :-
    ids_core(Start,[Start],Goal,DepthLimit,ReturnPath);
    ids_loop(Start,Goal,DepthLimit+1,ReturnPath).

ids_start(Start,Goal,ReturnPath) :-
    ids_loop(Start,Goal,ReturnPath,1).

This implementation is very generic and can be used not only for rescuing our goat.
For example think about looking for a path from 1 to 5 in Figure 2.

Figure 2 – Simple Graph

 

This Graph can be modeld in Prolog in the following way[3].

transition(A,B) :- member((A,B),[(1,2),(2,3),(2,4),(4,5),(3,5)]

Together with the IDS-Code follows:

-? ids_start(1,5,R)
R = [(1,2),(2,3),(3,5)].

Save the Goat (finally)

Let’s mix all together and save the goat before it starves or get eaten by the bad wolf.

start([a,a,a,a]). 
goal([b,b,b,b]).

transition0([G,C,W,F1],[G,C,W,F2]). 
transition0([F1,C,W,F1],[F2,C,W,F2]). 
transition0([G,F1,W,F1],[G,F2,W,F2]). 
transition0([G,C,F1,F1],[G,C,F2,F2]).

transition(X,Y) :- (transition0(X,Y);transition0(Y,X)), valid(X),valid(Y).

valid([F,_,_,F]). 
valid([G,C,W,_]) :- G \== C, G \==W.

% Iterative Depth-Search Algorithm
ids_core(Node, Path, Goal, DepthLimit, ReturnPath) :- 
    Node == Goal,reverse(Path,ReturnPath); 
    transition0(Node,Neighbour),not(member(Neighbour,Path)), 
    ids_core(Neighbour,[Node|Path],Goal,DepthLimit-1,ReturnPath). 

ids_loop(Start,Goal,DepthLimit,ReturnPath) :- 
    ids_core(Start,[Start],Goal,DepthLimit,ReturnPath); 
    ids_loop(Start,Goal,DepthLimit+1,ReturnPath). 

ids_start(Start,Goal,ReturnPath) :- ids_loop(Start,Goal,ReturnPath,1).

save_the_goat() :- 
    start(S),
    goal(G),
    ids_start(S,G,R),
    write(R).

UPDATE [10.02.1018]

I wrote reflexible transition and ment symmetric. Reflexible would mean transition(X,Y) :- transition0(X,X);transition0(Y,Y).  which would be pretty meaningless…

[1] Except in the featured image but I adoptet her from Pixabay
[2] And if there are multiple ways to reach the goal. But this is not important for us. While our approach with the Iterative Deepening Search finds always the shortest way to the goal.
[3] For simplicity, I didn’t made transition  symmetric. This means that the search algorithm can go in both directions. In our example the search can only go from top to down. To be more correct I should’ve added arrows to all edges in Figure 2 to make the graph directional.

Hits: 499