< up >
2022-07-23 18:54:31 +0200 CEST

Saving Goats with Prolog

Preface

This post was originally posted in my old blog raphaelpour.de on 09.02.2018. Retrospectively this post is a pretty good insight of my artifical intelligence studies back then.

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 solve it with an Iterative Depth Search (IDS).

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:

Rules:

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

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. 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) to rank all current possible actions by shortest distance to the goal, we need an uninformed search algorithm.

The most effective one is the Iterative Depth Search (IDS). It combines the positive aspects of the breadth-first- such as 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 (see graphic below). 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!

The following edges are wrong:

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:

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 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 transitions are left[3].

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 uninformed depth-first-search but the i is still missing. Let’s add a loop ids_loop that increases the depth until the goal has been reached. The loop is solved via recursive call of ids_loop where ids_start is initializes the loop with the initial depth. Our ds has been extended with a depth parameter which gets decremented on every recursive call. A depth of zero will cause the search to return with false.

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 the graph below.

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

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