Tinkering with simple AI stuff

Building Problem Solvers by Kenneth D. Forbus and Johan de Kleer inspired me to tinkering a bit with AI stuff again. This time, instead of writing routines for solving specific problems, I wanted to tackle writing more generic code that could be adapted to solve various kinds of problems. The result: stilpo, simple AI library that doesn’t do much yet (but hopefully will be doing bunch of stuff in the future).

Currently it supports solving problems where problem space is neatly defined and not overly large. User needs to specify how state of problem is represented, how to transition it to different states and how to recognize both identical states and goal state. After that they just choose a suitable search strategy (depth first and breadth first only currently) and hope for the best.

For example, if we wanted to solve a common problem that we all encounter daily:

Your task is to measure exactly 2 liters of water. You have two jugs at your disposal: one with 4 liters of capacity and another with 5 liters of capacity

A high level example of typical solver initialization and execution:

(require stilpo.cps)
(require hy.contrib.anaphoric)
(import [stilpo.cps [depth-first-solver breadth-first-solver
                     valid-operators]])

(def d-solve (depth-first-solver :is-goal goal?
                                 :operators operators
                                 :is-identical identical?))
(-> (d-solve initial-state)
    (print-solution))

This will create a depth first solver and configure it to this particular problem. Then it’s executed and resulting path is printed out. Path is just a list of dictionaries with current state and optionally the action to get there. The very first element of path only has the initial state and no action at all associated with it.

depth-first-solver is a function that will create a solver that uses depth first search when called. This solver can then be used to solve one or more problems (it doesn’t retain state between calls).

We represent state of our problem as a dictionary (any other data structure would work too, stilpo isn’t that particular about it). At the beginning, there are two jugs, both empty:

(def initial-state {:jug-4 0
                    :jug-5 0})

Detecting goal in our case is simple. When ever one of the jugs holds exactly two liters of water, we’re done:

(defn goal? [state]
  (or (= (:jug-4 state) 2)
      (= (:jug-5 state) 2)))

CPS needs to know which operators it can perform to any given state. Operator is just a function that when applied to a state, will return a new state. You are free to structure your code in the way you prefer, but stilpo has an utility functions for building operators and detecting when they can be applied.

operator macro is used to define special function that represents an operation that can be done to a state (I have omitted most of the operators for the sake of brevity as they aren’t particularly interesting):

(operator empty-jug-4 "pour 4 liter jug empty"
                      (> (:jug-4 state) 0)
                      {:jug-4 0
                       :jug-5 (:jug-5 state)})

First parameter is name of the function being defined, second one is textual description that can be printed out to specify solution to the problem. Third parameter is a form that returns true if operator is legal for given state. Rest of the code is used to create a new state that has been modified (4 liter jug poured empty in this example).

Each discrete action is defined as an operator like above and then packed into a function that can check which operators are valid for given state and return their application:

(defn operators [state]
  "all valid operators for given state and their descriptions"
  (valid-operators state empty-jug-4 empty-jug-5
                   fill-jug-4 fill-jug-5
                   pour-4-to-5 pour-5-to-4))

Final tool we need to define is detection of identical states. This is used by search algorithm to prune possible loops from the solution:

(defn identical? [state1 state2]
  (and (= (:jug-4 state1) (:jug-4 state2))
       (= (:jug-5 state1) (:jug-5 state2))))

We of course would like to print out our solution, so we define pretty-print to do that task for us:

(defn pretty-print [path]
  (when path
    (ap-each path
             (cond [(in :action it)
                    (print (.format "{0} (jugs: {1} and {2})"
                                         (:desc (:action it))
                                         (:jug-4 (:state it))
                                         (:jug-5 (:state it))))]
                   [true (print "starting")]))))

Function simple walks the path and prints out textual info of action taken and amount of water held by each jug:

starting
fill 5 liter jug with water (jugs: 0 and 5)
fill 4 liter jug with water (jugs: 4 and 5)
pour 5 liter jug empty (jugs: 4 and 0)
pour water from 4 liter jug to 5 liter jug (jugs: 0 and 4)
fill 4 liter jug with water (jugs: 4 and 4)
pour water from 4 liter jug to 5 liter jug (jugs: 3 and 5)
pour 5 liter jug empty (jugs: 3 and 0)
pour water from 4 liter jug to 5 liter jug (jugs: 0 and 3)
fill 4 liter jug with water (jugs: 4 and 3)
pour water from 4 liter jug to 5 liter jug (jugs: 2 and 5)

Looks correct to me. Notice how in the beginning there’s some pouring actions that aren’t really necessary for the solution. What if we wanted to try different search strategy? That’s simple, lets just try following:

(def b-solve (breadth-first-solver :is-goal goal?
                                   :operators operators
                                   :is-identical identical?))
(-> (b-solve initial-state)
    (print-solution))

By simply switching to different search strategy we get different path to solution:

starting
fill 4 liter jug with water (jugs: 4 and 0)
pour water from 4 liter jug to 5 liter jug (jugs: 0 and 4)
fill 4 liter jug with water (jugs: 4 and 4)
pour water from 4 liter jug to 5 liter jug (jugs: 3 and 5)
pour 5 liter jug empty (jugs: 3 and 0)
pour water from 4 liter jug to 5 liter jug (jugs: 0 and 3)
fill 4 liter jug with water (jugs: 4 and 3)
pour water from 4 liter jug to 5 liter jug (jugs: 2 and 5)

Under the hood the system builds up a tree representation of problem space. Initially the tree only contains one node, the initial state. All legal operators are applied to that state and the resulting states are applied in the tree and linked to first node. After that, next node is picked up based on the search algorithm and process is repeated until goal state has been found or search space exhausted. Breadth first search will find the optimal solution, while depth first usually finds a sub-optimal solution faster.

The same idea can be applied to other problems where problem space is relatively limited. As the problem space grows, so grows the time and memory these routines need to solve it. I’m currently working on getting A* implementation to work fast enough to be included in the library. It’s pretty fascinating to tinker with different kinds of search routines and compare them on simple problems like this or path finding.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s