Skip to content

AI Planning: Logistics Puzzles in Cartesian World

In this post we discuss simple breadth-first forward state-space solver for puzzles that can be called “logistics puzzles”.  The puzzle about farmer crossing river with cabbage, goat and wolf is probably the most well known example of such puzzles.

 Logistics Puzzles

We start with couple examples. In both of them the goal is to present a plan of crossing a river.

Puzzle 1. [1] A Wolf, A Goat and A Cabbage. A farmer needs to cross a river and to transport a wolf, a goat and a cabbage to the other side in a boat. The boat can carry the farmer and only one item. The following pairs of items can’t be left unattended by the farmer: wolf-goat and goat-cabbage for obvious reasons.

Puzzle 49. [1] Cannibals and Missionaries. Three missionaries and three cannibals must cross a river. Their boat can hold only two people, and it can’t cross the river by itself. If present missionaries can not be outnumbered by cannibals.

The common components of such puzzles are: a list of locations (river sides in the examples above), a list of items to move in between the initial and the goal location and a list of conditions to satisfy while moving. The objective is to plan moves so that the goal state is reached from the initial state while each intermediate step satisfies the conditions.

World States

We can represent a state of the world in such puzzles by specifying the number of items at each location. If there are n_i items of kind i total then the number of items of kind i at any location belongs to the set N(i)=\{0,\dots,n_i\}. If there are m locations, then the distribution of item i across them is described by a point in the set \nu(i) = N(i)^m, which is Cartesian product of m instances of N(i). Combining all \nu(i) together for all item types we get a complete space S=\prod_i \nu(i). Any world state for such kind of puzzles is a point in S.

Such formalization helps to easily enumerate all eligible neighbors of a current state for the purpose of searching a path
p=(s,\dots,g) in S from initial state s to the goal state g.

Search Strategy

We will adopt the simplest possible strategy for state-space search. Namely, the algorithm we are going to use is a specialization of Graph-Search algorithm (Figure 3.19 in [2]) with breadth first forward search strategy. Next we will explore Python implementation of this approach and apply it to the two puzzles above.

 Implementation Notes

Nested Dictionary

Programmatically we can represent a point S using, say, nested dictionary. Each item type present in the puzzle will correspond to a key at some level of hierarchy. The dictionary will give a complete world state description, e.g. dct[‘left’][‘goat’] will contain number of goats on left side of the river. Locations and items correspond to different levels of nesting in such dictionary. For the kind of puzzles we are exploring depth 2 of nesting is sufficient (locations and items) but the nested dictionary class can easily describe more complex situations by deeper nesting.

'''Defines class for symmetric nested dictionary
treated like a complete tree with methods following
depth first traversal. For some additional implementation notes see post
http://stackoverflow.com/questions/14692690/access-python-nested-dictionary-items-via-a-list-of-keys
'''
import pprint

class NestedDict:
    '''Nested dictionary with the main
    assumption that it has same keys for all
    nodes at the same level.'''

    def __init__(self, dictn=None):
        '''Initialized empty dictionary and empty list of labels.'''
        self.dictn = {} if dictn is None else dictn
        self.labels = []
        self.detph = 0

    def expand(self, labels, func=lambda: None):
        '''Given nested list of labels of the form
        [[L1a, L1b, ...][L2a, ...][L3a, ...]...]
        creates the tree with leaves created
        using passed in function. By default
        leaves values are None.

        :param labels: nested list of labels.

        :params func: function to create
            default leaves.
        '''
        self.dictn = self._expand(labels, func)
        self.depth = len(labels)
        self.labels = labels

    def _expand(self, labels, func):
        '''Expands dictionary recursively to the next
        level in the tree depth.

        :params labels: remaining labels to expand;

        :params func: function for creating leaves.'''
        dictn = {}

        is_leaf = len(labels) == 1

        if is_leaf:
            for label in labels[0]:
                dictn[label] = func()
        else:
            for label in labels[0]:
                dictn[label] = self._expand(labels[1:], func)
        return dictn

    def get_at(self, dpath):
        '''Returns value given a path as list of labels.

        :param dpath: list in the form [L1, L2, ...]
            where Li are labels to follow on corresponding
            level.'''
        return reduce(lambda d, k: d[k], dpath, self.dictn)

    def set_at(self, dpath, value):
        '''Uses get_at to set value at the path in the tree.
        Assumes that the tree is already fully expanded.

        :params dpath: data path in the tree, a list of
            labels to visit on corresponding level.

        :params value: value to set on the path.'''
        self.get_at(dpath[:-1])[dpath[-1]] = value

    def get_as_str(self):
        return pprint.pformat(self.dictn, indent=1, width=800)

World State

To describe world state we subclass nested dictionary and end up with a more specialized class:

'''Logistics puzzle state.'''
import copy
import nested_dict

class State(nested_dict.NestedDict):
    '''A 'template' state of a logistics puzzle world.
    The only assumption is that any state is a subset
    of Cartesian product of state components (which is
    always true but is highly redundant if the valid
     subset is small).'''

    def __init__(self, labels, state_values):
        '''World state described by nested dictionary.

        :params labels: labels, a list of lists; e.g. the
            first one is locations e.g. ['left', 'right']
            second one is item label e.g. ['goat', 'wolf', etc].

        :params values: list of pairs, e.g. [['left', 'goat'], 1]
            which corresponds to one goat on left bank of river.
        '''
        nested_dict.NestedDict.__init__(self)
        self.expand(labels, func=lambda: 0)
        for item, item_value in state_values:
            self.set_at(item, item_value)
        self.prev_state = None

    def get_neighbor(self):
        '''Returns deep copy of self, sets self as predecessor.'''
        state_candidate = copy.deepcopy(self)
        state_candidate.prev_state = self
        return state_candidate

    def enumerate_neighbors(self):
        return []

    def is_valid(self):
        return True

    def equals(self, other):
        '''The danger of strings comparison is that order
        used for formatting string representation may vary.'''
        return self.get_as_str() == other.get_as_str()

    def get_path(self, prefix=[]):
        ''' Returns list of the states visited on the way
        to the current. Used to print out solution.'''
        prefix.append(self.get_as_str())
        if not self.prev_state is None:
            self.prev_state.get_path(prefix) 

As an example of specialization of world state, consider PuzzleState class for cannibals and missionaries.

import state

class PuzzleState(state.State):
    '''Defines state in the search graph for
    missionaries and cannibals puzzle.'''

    locations = ['left', 'right']
    items = ['boat', 'missionaries', 'cannibals']
    labels = [locations, items]
    boat_capacity = 2

    def __init__(self, state_values):
        state.State.__init__(self, PuzzleState.labels, state_values)

    def side_is_valid(self, side):
        '''Returns true is on the given side of the river
        the number of cannibals does not exceed number of
        missionaries.'''
        return self.dictn[side]['missionaries'] >= self.dictn[side]['cannibals'] \
            or self.dictn[side]['missionaries'] == 0

    def is_valid(self):
        '''True of the state is valid, i.e. missionaries
        can't be eaten.'''
        return self.side_is_valid('left') and self.side_is_valid('right')

    def boat_location_and_destinations(self):
        '''Returns current location of boat and possible destinations for it.'''
        destinations = []
        location = None
        for loc in PuzzleState.locations:
            if self.dictn[loc]['boat'] == 1:
                location = loc
            else:
                destinations.append(loc)
        return location, destinations

    def enumerate_neighbors(self):
        '''Returns list of admissible states directly
        reachable from the current state (self).'''
        neighbors = []
        location, destinations = self.boat_location_and_destinations()
        neighbors = []
        location, destinations = self.boat_location_and_destinations()
        for dest in destinations:
            for mm in range(self.dictn[location]['missionaries'] + 1):
                for cc in range(self.dictn[location]['cannibals'] + 1):
                    n_moved = cc + mm
                    if n_moved > PuzzleState.boat_capacity or n_moved == 0:
                        continue
                    state_candidate = self.get_neighbor()
                    state_candidate.move(location, dest, "cannibals", cc)
                    state_candidate.move(location, dest, "missionaries", mm)
                    state_candidate.move(location, dest, "boat", 1)
                    if state_candidate.is_valid():
                        neighbors.append(state_candidate)
        return neighbors

    def move(self, from_location, to_location, item, n_items):
        '''Moves n_items of kind item between two locations.'''
        self.dictn[from_location][item] -= n_items
        self.dictn[to_location][item] += n_items

We may consider introduction of another intermediate class for river crossing puzzles. Then functions move and boat_location_and_destinations will be factored out to that new class.

Solver

The solver below uses string representation of a state to keep track of the visited states and assumes that states implement an appropriate get_as_str() method.

class BreadthFirstForward:
    def __init__(self, initial, goal):
        ''' Saves the initial state and the goal state
        as an instance variables. Initializes the internal
        bookkeeping: lists of visited and fringe states.'''
        self.initial = initial
        self.goal = goal
        self.visited = [initial.get_as_str()]
        self.fringe = [self.initial]

    def run(self):
        '''Implements the simplest version of breadth first
        search using FIFO queue for the fringe states.'''
        while self.fringe:
            state = self.fringe[0]
            if state.equals(self.goal):
                return state
            self.fringe = self.fringe[1:]
            new_states = state.enumerate_neighbors()
            for new_state in new_states:
                state_hash = new_state.get_as_str()
                if state_hash in self.visited:
                    continue
                self.visited.append(state_hash)
                self.fringe.append(new_state)

def solve_breadth_first(start, goal):
    '''A wrapper to create solver, run it and print result to console.'''
    slv = BreadthFirstForward(start, goal)
    solution = slv.run()
    if not solution is None:
        solution_str = []
        solution.get_path(solution_str)
        for line in solution_str:
            print line
    else:
        print "No solution."

An output for the missionaries and cannibals puzzle looks like this:

    import solver

    missionaries = [['left', 'missionaries'], 3]
    cannibals = [['left', 'cannibals'], 3]
    boat = [['left', 'boat'], 1]
    start = PuzzleState([missionaries, cannibals, boat])

    missionaries = [['right', 'missionaries'], 3]
    cannibals = [['right', 'cannibals'], 3]
    boat = [['right', 'boat'], 1]
    goal = PuzzleState([missionaries, cannibals, boat])

    solver.solve_breadth_first(start, goal)

{'left': {'boat': 0, 'cannibals': 0, 'missionaries': 0}, 'right': {'boat': 1, 'cannibals': 3, 'missionaries': 3}}
{'left': {'boat': 1, 'cannibals': 2, 'missionaries': 0}, 'right': {'boat': 0, 'cannibals': 1, 'missionaries': 3}}
{'left': {'boat': 0, 'cannibals': 1, 'missionaries': 0}, 'right': {'boat': 1, 'cannibals': 2, 'missionaries': 3}}
{'left': {'boat': 1, 'cannibals': 3, 'missionaries': 0}, 'right': {'boat': 0, 'cannibals': 0, 'missionaries': 3}}
{'left': {'boat': 0, 'cannibals': 2, 'missionaries': 0}, 'right': {'boat': 1, 'cannibals': 1, 'missionaries': 3}}
{'left': {'boat': 1, 'cannibals': 2, 'missionaries': 2}, 'right': {'boat': 0, 'cannibals': 1, 'missionaries': 1}}
{'left': {'boat': 0, 'cannibals': 1, 'missionaries': 1}, 'right': {'boat': 1, 'cannibals': 2, 'missionaries': 2}}
{'left': {'boat': 1, 'cannibals': 1, 'missionaries': 3}, 'right': {'boat': 0, 'cannibals': 2, 'missionaries': 0}}
{'left': {'boat': 0, 'cannibals': 0, 'missionaries': 3}, 'right': {'boat': 1, 'cannibals': 3, 'missionaries': 0}}
{'left': {'boat': 1, 'cannibals': 2, 'missionaries': 3}, 'right': {'boat': 0, 'cannibals': 1, 'missionaries': 0}}
{'left': {'boat': 0, 'cannibals': 1, 'missionaries': 3}, 'right': {'boat': 1, 'cannibals': 2, 'missionaries': 0}}
{'left': {'boat': 1, 'cannibals': 3, 'missionaries': 3}, 'right': {'boat': 0, 'cannibals': 0, 'missionaries': 0}}

There is a potential caveat with using string to represent state in keeping track of visited states. We need to make sure the nested dictionary is traversed in the same order each time by the pprint function pformat. Here we rely on the pprint module implementation and do not provide any additional guarantees. If the assumption fails, the search will not fail but will become more expensive as we will be visiting same state more than once. Eventually the search will return a solution if it exists but it may differ from the breadth first search solution.

Finally, it is obvious that reverting initial and goal state will turn the algorithm into a backward search.

Discussion

It might be an interesting exercise (for which we may have a separate post in the future) to build an automated puzzle generator. It is relatively easy to come up with a generator and parser of first order logic rules describing valid states. Automated class generation for such rules could be also not so difficult to implement. The main challenge would be conversion of abstract items, locations and transitions into human readable puzzle fiction. Even without going that far, the framework we outlined here allows to test simple variations to the existing puzzles, say adding more items and locations (e.g. an island where items can be “parked” temporarily). We can also add item conditions: a perishable item left on initial side of a river for longer than certain number of moves is a loss and leads to an invalid state of the world. That will increase depth of the nested dictionary to three (locations, items, item conditions).

References

[1] A. Levitin, M. Levitin, Algorithmic Puzzles, Oxford University Press, 2011, 257 pages.
[2] S. Russel, P. Norvig, Artificial Intelligence, Modern Approach, Second Edition, Prentice Hall, 2003, 1081 pages.
[3] More river crossing puzzles https://justpuzzles.wordpress.com/2011/02/16/river-crossing-1/