PAIPr in Portuguese


My series of PAIPr (Paradigms of AI Programming in Ruby) are being translated into Portuguese by Hugo Lima Borges. You can read the result on his blog here: http://www.agaelebe.com.br/2008/10/10/traducao-paradigmas-da-programao-para-inteligencia-artificial.



Tools and searching


This post in the PAIPr series will be a little bit different. In fact it won’t contain any “real” AI code of any sort. Instead the chapter it’s based on (Chapter 6, Building Software Tools) is more about generalizing some of the code written before and adding a few needed searching tools to the tool box.

This is also the one chapter that provide quite difficult to port. In many cases the solutions is based on the Common Lisp functions in such a way that the resulting Ruby code ended up a bit clunky in some places. You specifically see this where a piece of code need to take more than one code argument. This is where the Common Lisp sharp-quote is really useful, and the Ruby symbol is not at all as useful. I’ll point out some examples of this when we touch on that code.

A generic REPL

But first let’s get started on the Eliza command line we created in the last post. This part of the chapter starts out with a lock at the interactive prompt for Lisp, and the main equivalent for Ruby would be IRb. But it’s quite easy to do something small that works more or less correctly. Basically it would read a string of text, call eval on that and then inspect the result and print it. The first stab at something generic that would do the same could look like this (lib/ch06/inter.rb):

def interactive_interpreter(prompt)
  while true
    print prompt
    puts(yield(gets))
  end
end

Nothing much happening. We expect a prompt of some kind, and a transformer. In the Lisp code the transformer is another lambda, but in the Ruby code it makes sense to send in a block.

Now that we have it, it’s a snap to use it to create a Ruby interpreter from it (lib/ch06/inter.rb):

def ruby
  interactive_interpreter '> ' do |str|
    eval(str)
  end
end

In the same manner the Eliza interpreter can be written like this (lib/ch06/inter.rb):

$:.unshift '../ch05'
require 'eliza2'

def eliza
  interactive_interpreter 'eliza> ' do |str|
    Eliza.eliza_rule(str.downcase.split,
                     Rule::ELIZA_RULES2)
  end
end

It would be a simple thing to add history and other convenient parts to this generic REPL framework.

In the Lisp code there is a need to flatten input after the Eliza rules have been used – due to some differences in the way Eliza was implemented, this is not necessary for our code. For posterity I’ll still display two versions of the compose-function Norvig gives. These are sufficiently different in Ruby to be interesting (lib/ch06/inter.rb):

def compose(first, second = nil, &block)
  second ||= block
  lambda do |*args|
    first[second[*args]]
  end
end

class Proc
  def +(other)
    lambda do |*args|
      self[other[*args]]
    end
  end
end

In the first example the composition looks a bit like the Lisp one, except that I allow the possibility to use either two procs or one proc and one block. The second example is maybe more idiomatic, adding a plus operator to Proc. This more or less matches the semantics of addition (or maybe composition is more like multiplication? hmm…)

A second version of the interpreter, with some more advanced features, look like this (lib/ch06/inter2.rb):

def interactive_interpreter(prompt,
                            transformer = nil,
                            &block)
  transformer ||= (block || proc { |arg| arg })
  while true
    begin
      case prompt
      when String
        print prompt
      when Proc
        prompt.call
      end
      puts(transformer[gets])
    rescue Interrupt
      return
    rescue Exception => e
      puts ";; Error #{e.inspect} ignored, back to top level"
    end
  end
end

def prompt_generator(num = 0, ctl_string = "[%d] ")
  lambda do
    print ctl_string%[num+=1]
  end
end

interactive_interpreter(prompt_generator)

This code does some funky things. First of all, it really tries HARD to give you a default transformer. You can use either proc as an argument, or give it a block. If you don’t do any of those it will use an identity proc instead. This is what that first line full of line noise does.

After that it tries to decide what to do with the prompt. If the prompt is a proc it calls it each loop, if it’s a string it just uses it. Finally it calls the transformer on the result of gets and then puts it. Notice the rescue blocks. I wanted to rescue any error condition, so I choose to use Exception. Otherwise you could crash the interpreter by calling a non-existing method for example. But it was a bit funny to be reminded the hard way that Ctrl+C actually generates an exception of type Interrupt. Since I was ignoring all exceptions I didn’t have any way of shutting down the ruby process. Only kill -9 worked. So that’s why the rescue of Interrupt needs to be there.

What about prompt_generator? This is a higher order method that makes it possible to give a prompt with ascending numbers each time a new prompt is created. It does this in a classic closure way, by incrementing the num argument every time it’s called. Notice the use of sprintf style formatting here. It’s generally much more capable than doing dynamic string interpolation.

Pattern matching revisited

It’s time to get back to the pattern matching tools we developed for Eliza and see if we can make them a bit more general. This turned out to be a bit complicated for some of the matching operations that is provided in the book, specifically since the Lisp reader makes reading patterns very easy compared to Ruby. Before we can get into the code ported from the book though, a small piece of the puzzle need to be fixed. Remember that we used ?x and *x as ways to represent variables in the matching pattern? The problem is that these aren’t general enough. So the first code to write is to be able to parse a Ruby string like “I think that (?* ?x) flurg” into the array [“I”, “think”, “that”, [“?*”, “?x”], “flurg”]. The code in lib/ch06/pat_read.rb accomplishes this:

class Pattern
  def initialize(pattern)
    @pattern = pattern
  end

  class << self
    def from_string(str)
      result = []
      str.scan(/(\(\?.*?\))|([^[:space:]]+)/) do |f|
        if f[1]
          result << f[1]
        else
          result << f[0][1..-2].split
        end
      end
      Pattern.new result
    end
  end
end

This makes use of a small regular expression that either matches stuff between parenthesis or chunks of non-space. This regular expression will not handle nested lists correctly, but except for that it will work quite all right for our current needs.

OK, back to the chapter. The code we need to write is all about adding more powerful matching operations to the language, and also making it extensible. As a typical example of the kind of patterns we might want to match is “?x (?or < = >) ?y” against “3 < 4”.

I’m not reusing any of the pattern matching code from Eliza. I’ve copied and modified pieces from that code though, but the differences are larger than the similarities in such a way that inheritance is not really practical.

The first part of the code for Pattern matching looks like this (lib/ch06/pat_match.rb):

class Pattern
  def initialize(pattern)
    @pattern = pattern
  end

  def match(input, bindings = {}, pattern = @pattern)
    case
    when !bindings
      nil
    when variable?(pattern)
      match_variable(pattern, input, bindings)
    when pattern == input
      bindings
    when segment_pattern?(pattern)
      segment_matcher(pattern, input, bindings)
    when single_pattern?(pattern)
      single_matcher(pattern, input, bindings)
    when pattern.is_a?(Array) && input.is_a?(Array)
      match(input[1..-1],
            match(input[0], bindings, pattern[0]),
            pattern[1..-1])
    else
      nil
    end
  end
end

This code follows the same pattern as earlier, checking for different types of entries in the pattern and matching based on that.

The simple variable matching is first, and looks like this (lib/ch06/pat_match.rb):

  def variable?(pattern)
    pattern.is_a?(String) && pattern[0] == ??
  end

  def match_variable(px, i, bindings)
    (!bindings[px] && bindings.merge(px => i)) ||
      (bindings[px] == i && bindings)
  end

Nothing much have changed here.

The main difference in the structure of this code is that we won’t hard code which method to use for matching a specific type. Instead we’ll add a Hash of available matchers, and have them describe what to call to actually do the matching. In Common Lisp Norvig uses the fact that you can set properties on symbols for this. Although you can do the same thing in Ruby it doesn’t feel right at all, and I opted for a dictionary approach instead (lib/ch06/pat_match.rb):

  SINGLE_MATCH = {
    "?is"  => :match_is,
    "?or"  => :match_or,
    "?and" => :match_and,
    "?not" => :match_not
  }

  SEGMENT_MATCH = {
    "?*"  => :segment_match,
    "?+"  => :segment_match_plus,
    "??"  => :segment_match_?,
    "?if" => :match_if
  }

Here you see that there are two types of matchers. Things that only can match one element of something, and matchers that can eat zero or more tokens. These need to be handled differently and are thus defined in different places.

The glue for getting all of this working looks like this (lib/ch06/pat_match.rb):

  def segment_pattern?(pattern)
    pattern.is_a?(Array) &&
      pattern.first.is_a?(Array) &&
      SEGMENT_MATCH[pattern.first.first]
  end

  def single_pattern?(pattern)
    pattern.is_a?(Array) &&
      SINGLE_MATCH[pattern.first]
  end

  def segment_matcher(pattern, input, bindings)
    self.send(SEGMENT_MATCH[pattern.first.first],
              pattern,
              input,
              bindings)
  end

  def single_matcher(pattern, input, bindings)
    self.send(SINGLE_MATCH[pattern.first],
              pattern[1..-1],
              input,
              bindings)
  end

Nothing surprising – we just get the symbol name from the hash and then send it to ourselves. This implies that these methods need to be instance methods on Pattern for it to work. That’s the only constraint on adding new kinds of matching operators.

First up, the single token matchers. They look like this (lib/ch06/pat_match.rb):

  def match_is(var_and_pred, input, bindings)
    var, pred = var_and_pred
    new_bindings = match(var, input, bindings)
    if !new_bindings || !self.send(pred, input)
      nil
    else
      new_bindings
    end
  end

  def match_and(patterns, input, bindings)
    case
    when !bindings
      nil
    when patterns.empty?
      bindings
    else
      match_and(patterns[1..-1],
                input,
                match(patterns[0],
                      input,
                      bindings))
    end
  end

  def match_or(patterns, input, bindings)
    if patterns.empty?
      nil
    else
      new_bindings = match(patterns[0], input, bindings)
      if !new_bindings
        match_or(patterns[1..-1], input, bindings)
      else
        new_bindings
      end
    end
  end

  def match_not(patterns, input, bindings)
    if match_or(patterns,input,bindings)
      nil
    else
      bindings
    end
  end

All of them follow the same pattern. All except for match_is are interestingly recursive, defining themselves in terms of one another.

The segment matching is quite a lot more complicated, and we even need to add a new helper method to find the right place. This is because we need to have general back tracking (lib/ch06/pat_match.rb):

  def segment_match(pattern, input, bindings, start = 0)
    var = pattern[0][1]
    pat = pattern[1..-1]
    if !pat || pat.empty?
      match_variable(var, input, bindings)
    else
      pos = first_match_pos(pat[0], input, start)
      return nil unless pos

      b2 = match(input[pos..-1],
                 match_variable(var, input[0...pos], bindings),
                 pat)
      return b2 if b2
      segment_match(pattern, input, bindings, pos+1)
    end
  end

  def first_match_pos(pat1, input, start)
    input = [] unless input
    case
    when !pat1.is_a?(Array) && !variable?(pat1)
      (vv = input[start..-1].index(pat1)) && vv + start
    when start < input.length
      start
    else
      nil
    end
  end

Having first_match_pos makes it possible to write patterns that are not separated by literal tokens.

This test code from lib/ch06/pat_match.rb makes it obvious what kind of complicated segment matchings can be handle by this code:

  require 'pat_read'
  p Pattern.from_string("a (?* ?x) d").
    match(%w(a b c d))
  p Pattern.from_string("a (?* ?x) (?* ?y) d").
    match(%w(a b c d))
  p Pattern.from_string("a (?* ?x) (?* ?y) ?x ?y").
    match(['a', 'b', 'c', 'd', ['b', 'c'], ['d']])

Finally, matching one or more expressions, or matching zero or one expression is easily achieved using segment_match (lib/ch06/pat_match.rb):

  def segment_match_plus(pattern, input, bindings)
    segment_match(pattern, input, bindings, 1)
  end

  def segment_match_?(pattern, input, bindings)
    var = pattern[0][1]
    pat = pattern[1..-1]
    match(input, bindings, [var] + pat) ||
      match(input, bindings, pat)
  end

The main difference between the Common Lisp implementation of matching and the Ruby version is that there is no obvious way of embedding Ruby code there. If any Ruby code is added that has parenthesis in them the regexp reader will bail out. That’s why I decided to not actually implement match_if for now. We’ll have to live without it. Obviously it can be done using Ruby code, but a different representation might have to be chosen. I leave this as an exercise to the reader. =)

Another small nitpick is that it might be a good thing to be able to provide an abbreviation facility. Especially for patterns like “foo (?* ?x) bar” it would be nice to say “foo ?x* bar” instead. The final version of lib/ch06/pat_read.rb provides for this:

class Pattern
  def initialize(pattern)
    @pattern = pattern
  end

  class << self
    def from_string(str)
      result = []
      str.scan(/(\(\?.*?\))|([^[:space:]]+)/) do |f|
        if f[1]
          result << f[1]
        else
          result << f[0][1..-2].split
        end
      end
      Pattern.new expand(result)
    end

    attr_accessor :expansions

    def match_abbrev(symbol, expansion)
      self.expansions[symbol.to_sym] = expand(expansion)
    end

    def expand(pat)
      if !pat.is_a?(Array)
        if self.expansions[pat.to_sym]
          self.expansions[pat.to_sym]
        else
          pat
        end
      elsif pat.empty?
        pat
      else
        [expand(pat[0])] + expand(pat[1..-1])
      end
    end
  end

  self.expansions = { }
end

The final look at Eliza in Norvig’s book looks at how to generalize the rule based Eliza tool into a more general version. If I would do this I would probably go a totally different route than the one shown in PAIP, and provide something flexible based on mixins or inheritance. I couldn’t figure out a clean way of implementing the code in this part based on the current work we’ve done, so I decided to leave that out too.

Searching tools

In this section Norvig talks a bit about different tools for implementing search. Search can be characterized by four features. The start state, the goal state/states, the successor states and the ordering strategy. The four pieces will be part of all the search implementations presented here, in some way.

A simple way to do search is tree-searching. The algorithm can be used to implement several search tools with different characteristics. In lib/ch06/search.rb you can find tree_search:

    def tree_search(states, successors, combiner, &goal_p)
      dbg :search, ";; Search %p", states
      return nil if !states || states.empty?
      if goal_p[states.first]
        states.first
      else
        tree_search(combiner[successors[states.first], states[1..-1]],
                    successors,
                    combiner,
                    &goal_p)
      end
    end

Here we see the inconvenient way Common Lisp translates to Ruby. The arguments successor, combiner and goal_p are all blocks of code, but one of them can be sent as a block while the other has the be regular parameters. I’ve tried to be consistent and always put the goal predicate as the block parameter. The actual code does surprisingly little. It returns nil on failure (when the current states are empty or nil). It then checks if the first element of states matches the goal criteria, and then returns that element. On failure it calls itself recursively after finding the successors for the first element and combining them with the rest of the available states. To see how this works in practice, consider simple depth first (lib/ch06/search.rb):

    def depth_first(start, successors, &goal_p)
      tree_search([start],
                  successors,
                  proc{ |x, y| x+y },
                  &goal_p)
    end

The combining function uses simple addition of arrays. Before testing the code we need some simple helper methods to make the invocations look better (lib/ch06/search.rb):

module Trees
  class << self
    def binary(x)
      [2*x, 2*x + 1]
    end

    def finite_binary(n)
      proc do |x|
        binary(x).select { |child| child<=n }
      end
    end
  end
end

def is(value)
  lambda { |x| x == value }
end

With the help of these we can define the first test of depth first search (lib/ch06/eternal_search.rb):

require 'search'

debug :search
Search.depth_first(1,
                   proc{|v| Trees.binary(v)},
                   &is(12))

This code will run until you abort it, and it shows one of the problems with depth first search.

The alternative to depth first is breadth first search (lib/ch06/search.rb):

    def breadth_first(start, successors, &goal_p)
      tree_search([start],
                  successors,
                  proc{ |x, y| y + x },
                  &goal_p)
    end

The main difference here is that the combiner proc will actually focus on the rest of the states before looking at the successors of the current state. Using this version (lib/ch06/noneternal_search.rb):

require 'search'

debug :search
Search.breadth_first(1,
                     proc{|v| Trees.binary(v)},
                     &is(12))

will find the correct element quite quickly. Another way of getting around the problem above is to make sure to not generate an infinite successor function. If you try this (lib/ch06/noneternal_depth.rb):

require 'search'

debug :search
Search.depth_first(1,
                   Trees.finite_binary(15),
                   &is(12))

everything will work out right with the depth first search, since the finite_binary method will only generate a binary tree up to a specific N.

A problem with these algorithms is that they currently can’t take advantage of any specific knowledge about the problem space. They will trod along happily, either depth first or breadth first without any specific exceptions. One way of avoiding this behavior is to provide a cost function and some way of sorting based on cost. Once you have this you can implement best first search. If the problem space has any specific cost that means you’re getting closer to the value you’re looking for, this is a really good way of guiding a search (lib/ch06/guiding.rb).

require 'search'

module Search
  class << self
    def diff(num)
      lambda do |x|
        (x - num).abs
      end
    end

    def sorter(&cost_fn)
      lambda do |new, old|
        (new + old).sort_by do |n|
          cost_fn[n]
        end
      end
    end

    def best_first(start, successors, cost_fn, &goal_p)
      tree_search([start], successors, sorter(&cost_fn), &goal_p)
    end
  end
end

This code contains three different methods. The diff method will return a closure that in turn will return the distance to a specific number. The sorter method will return a closure that will sort the combination of it’s two arguments based on the cost of elements in the arrays. Finally, the implementation of best_first takes advantage of the sorter, takes a new cost function and generates a combiner based on the sorting and the cost function and promptly sends it along to the tree_search. All in all, best first basically just sorts the problem space based on cost before every iteration of a new search loop. If you look at the debug out put from code like this (lib/ch06/guiding.rb):

  debug :search
  Search.best_first(1,
                    proc{|v| Trees.binary(v)},
                    Search.diff(12),
                    &is(12))

you will see that it at every stage has the states closest to 12 at the front:

;; Search [1]
;; Search [3, 2]
;; Search [7, 6, 2]
;; Search [14, 15, 6, 2]
;; Search [15, 6, 2, 28, 29]
;; Search [6, 2, 28, 29, 30, 31]
;; Search [12, 13, 2, 28, 29, 30, 31]

If we know something about the successors, for example that all successors are greater than the current state, we can use that to give a cost function that provides an extremely high cost for numbers above the goal (lib/ch06/guiding.rb):

def price_is_right(price)
  lambda do |x|
    if x > price
      100000000
    else
      price - x
    end
  end
end

Using this code you will see that the debug output is quite different, even with the same parameters for the search (lib/ch06/guiding.rb):

  Search.best_first(1,
                    proc{|v| Trees.binary(v)},
                    price_is_right(12),
                    &is(12))

The debug looks like this:

;; Search [1]
;; Search [3, 2]
;; Search [7, 6, 2]
;; Search [6, 2, 15, 14]
;; Search [12, 2, 13, 15, 14]

Another variation on tree search is beam search. Beam search is based on best first search, but works on a limited “beam” of states at one time, by looking ahead and choosing a few best ways to proceed. Depending on the beam width you get different characteristics.

require 'guiding'

module Search
  class << self
    def beam(start, successors, cost_fn, beam_width, &goal_p)
      tree_search([start], successors, proc do |old, new|
                    sorted = sorter(&cost_fn)[old,new]
                    if beam_width > sorted.length
                      sorted
                    else
                      sorted[0...beam_width]
                    end
                  end,
                  &goal_p)
    end
  end
end

if __FILE__ == $0
  debug :search
  Search.beam(1,
              proc{|v| Trees.binary(v)},
              price_is_right(12),
              2,
              &is(12))

  # Search.beam(1,
  #             proc{|v| Trees.binary(v)},
  #             Search.diff(12),
  #             2,
  #             &is(12))
end

This code is a bit more complicated because the combiner proc is inlined in the call to tree_search. The commented code shows that different ways of working with beam search doesn’t necessarily yield perfect results. In the case of the second invocation it throws away the correct way of getting to the final state. If the beam width were set to 3 instead of 2 it would work fine.

OK, it’s time for a concrete search example. It concerns planning the flight of a small airplane where the longest distance it can fly is a 1000km. Based on this we want to be able to found routes for it between different American cities. First let’s look at the definition of some cities (lib/ch06/plan_flight.rb):

require 'beam_search'

City = Struct.new(:name, :long, :lat)

class City
  CITIES =
    [
     ['Atlanta',        84.23, 33.45],
     ['Boston',         71.05, 42.21],
     ['Chicago',        87.37, 41.50],
     ['Denver',        105.00, 39.45],
     ['Eugene',        123.05, 44.03],
     ['Flagstaff',     111.41, 35.13],
     ['Grand Junction',108.37, 39.05],
     ['Houston',       105.00, 34.00],
     ['Indianapolis',   86.10, 39.46],
     ['Jacksonville',   81.40, 30.22],
     ['Kansas City',    94.35, 39.06],
     ['Los Angeles',   118.15, 34.03],
     ['Memphis',        90.03, 35.09],
     ['New York',       73.58, 40.47],
     ['Oklahoma City',  97.28, 35.26],
     ['Pittsburgh',     79.57, 40.27],
     ['Quebec',         71.11, 46.49],
     ['Reno',          119.49, 39.30],
     ['San Francisco', 122.26, 37.47],
     ['Tampa',          82.27, 27.57],
     ['Victoria',      123.21, 48.25],
     ['Wilmington',     77.57, 34.14]
    ].map do |name, long, lat|
    new(name, long, lat)
  end
end

This code first defines a struct representing a City, then adds all American cities to a constant inside the class.

To be able to plan a trip, we really need to be able to find all the neighbors that are within a 1000km. This is an instance method on City (lib/ch06/plan_flight.rb):

  def neighbors
    CITIES.select do |c|
      c != self &&
        self.air_distance_to(c) < 1000.0
    end
  end

I’ll get back to air_distance_to in a while. Notice how nice select is to use like this. Another simple method needed is a way to find a city based on name. I decided to make that the indexing method for City (lib/ch06/plan_flight.rb):

  class << self
    def [](name)
      CITIES.find { |c| c.name == name }
    end
  end

Finally, the definition of the trip method, that gives back a routes, is also a class method on City (lib/ch06/plan_flight.rb):

  class << self
    def trip(start, dest)
      Search.beam(start,
                  proc { |c| c.neighbors },
                  proc { |c| c.air_distance_to(dest) },
                  1,
                  &is(dest))
    end
  end

As you can see it’s a beam search where the successors are all the neighbors of the city, and the cost for a city is the distance to the final destination.

Invoking trip with San Francisco and Boston looks like this (lib/ch06/plan_flights.rb):

if __FILE__ == $0
  debug :search
  City.trip(City['San Francisco'], City['Boston'])
  p "---"
  City.trip(City['Boston'], City['San Francisco'])
end

The trip from San Francisco to Boston looks like this:

;; Search [#<struct City name="San Francisco", long=122.26, lat=37.47>]
;; Search [#<struct City name="Reno", long=119.49, lat=39.3>]
;; Search [#<struct City name="Grand Junction", long=108.37, lat=39.05>]
;; Search [#<struct City name="Denver", long=105.0, lat=39.45>]
;; Search [#<struct City name="Kansas City", long=94.35, lat=39.06>]
;; Search [#<struct City name="Indianapolis", long=86.1, lat=39.46>]
;; Search [#<struct City name="Pittsburgh", long=79.57, lat=40.27>]
;; Search [#<struct City name="Boston", long=71.05, lat=42.21>]

While the equivalent one backwards look like this:

;; Search [#<struct City name="Boston", long=71.05, lat=42.21>]
;; Search [#<struct City name="Pittsburgh", long=79.57, lat=40.27>]
;; Search [#<struct City name="Chicago", long=87.37, lat=41.5>]
;; Search [#<struct City name="Kansas City", long=94.35, lat=39.06>]
;; Search [#<struct City name="Denver", long=105.0, lat=39.45>]
;; Search [#<struct City name="Flagstaff", long=111.41, lat=35.13>]
;; Search [#<struct City name="Reno", long=119.49, lat=39.3>]
;; Search [#<struct City name="San Francisco", long=122.26, lat=37.47>]

There is a different route in this code, based on the fact that the cost function is subtly wrong. The cost should not minimize the distance from the next city to the destination, but minimize the whole path.

Before fixing this problem though, let’s just quickly take a look at the tools needed for air distance (lib/ch06/plan_flight.rb):

  EARTH_DIAMETER = 12765.0

  def air_distance_to(city)
    d = distance(self.xyz_coords, city.xyz_coords)
    EARTH_DIAMETER * Math.asin(d/2)
  end

  def xyz_coords
    psi = deg_to_radians(self.lat)
    phi = deg_to_radians(self.long)
    [
     Math.cos(psi) * Math.cos(phi),
     Math.cos(psi) * Math.sin(phi),
     Math.sin(psi)
    ]
  end

  def distance(point1, point2)
    Math.sqrt(point1.
              zip(point2).
              map { |a, b| (a-b)**2 }.
              inject(0) { |sum, e| sum+e })
  end

  def deg_to_radians(deg)
    (deg.truncate + ((deg%1) * (100.0/60.0))) *
      Math::PI *
      1.0/180.0
  end

There is nothing really strange here. With this in place we can start taking a look at the second implementation of planning a trip, using the concept of paths (lib/ch06/plan_flight2.rb):

class Path
  attr_accessor :state, :previous, :cost_so_far, :total_cost

  def initialize(state = nil,
                 previous = nil,
                 cost_so_far = 0,
                 total_cost = 0)
    self.state = state
    self.previous = previous
    self.cost_so_far = cost_so_far
    self.total_cost = total_cost
  end

  def map(&block)
    res = [block[state]]
    if previous
      res + previous.map(&block)
    else
      res
    end
  end

  def to_s
    "#<Path to %s cost %.1f>" % [self.state, self.total_cost]
  end
end

class City
  class << self
    def trip(start, dest, beam_width = 1)
      Search.beam(Path.new(start),
                  path_saver(proc { |c| c.neighbors },
                             proc { |c, c2| c.air_distance_to(c2) },
                             proc { |c| c.air_distance_to(dest) }),
                  proc { |p| p.total_cost },
                  beam_width,
                  &is(dest, :state))
    end
  end
end

This code really does a lot. There is no point to have Path be a struct, since we need to give it default arguments. The Path.map method is needed later on, and we also provide a nice to_s implementation for it. The new trip implementation makes everything by Path’s instead of plain Cities. That makes the successor function slightly complicated. We also need a way of saying which key should be used by the is-method to decide if something is equal or not. path_saver and the new is looks like this (lib/ch06/plan_flight2.rb):

def is(value, key = nil)
  if key
    lambda { |path| path.send(key) == value }
  else
    lambda { |path| path == value }
  end
end

def path_saver(successors, cost_fn, cost_left_fn)
  lambda do |old_path|
    old_state = old_path.state
    successors[old_state].map do |new_state|
      old_cost = old_path.cost_so_far +
        cost_fn[old_state, new_state]
      Path.new(new_state,
               old_path,
               old_cost,
               old_cost + cost_left_fn[new_state])
    end
  end
end

def show_city_path(path)
  puts "#<Path %.1f km: %s>" % [path.total_cost, 
    path.map { |s| s.name }.reverse.join(' - ')]
end

With all this machinery in place, we can finally get back to planning those trips (lib/ch06/plan_flight2.rb):

if __FILE__ == $0
  show_city_path(City.trip(City['San Francisco'], City['Boston'], 1))
  show_city_path(City.trip(City['Boston'], City['San Francisco'], 1))
  show_city_path(City.trip(City['Boston'], City['San Francisco'], 3))
end

This gives these outputs:

#<Path 4514.8 km: San Francisco - Reno - Grand Junction - 
  Denver - Kansas City - Indianapolis - 
  Pittsburgh - Boston>
#<Path 4577.3 km: Boston - Pittsburgh - Chicago - 
  Kansas City - Denver - Grand Junction - 
  Reno - San Francisco>
#<Path 4514.8 km: Boston - Pittsburgh - Indianapolis - 
  Kansas City - Denver - Grand Junction - 
  Reno - San Francisco>

as expected.

A problem you might have noticed with the beam width in beam search is that it can fail to find something because of having the wrong width. Norvig calls the solution to this an iterative widening search, which does exactly what it sounds like – if it fails with one beam width it tries another, until it reaches a cutoff point. The code for this is in lib/ch06/iter_widening.rb:

require 'plan_flight2'

module Search
  class << self
    def iter_wide(start, successors, cost_fn,
                  width = 1, max = 100, &goal_p)
      dbg :search, "; Width: %d", width
      unless width > max
        beam(start, successors, cost_fn,
             width,
             &goal_p) ||
          iter_wide(start, successors, cost_fn,
                    width + 1, max, &goal_p)
      end
    end
  end
end

if __FILE__ == $0
  debug :search
  p Search.iter_wide(1,
                     Trees.finite_binary(15),
                     Search.diff(12),
                     &is(12))
end

This code will retry several times until it finds it’s goal or reaches the maximum width. Interestingly, the repeated work isn’t as large as you’d expect. This algorithm only wastes 10% of it’s time doing repetitive generations.

The two final search implementations we are going to look at all searches graphs instead of trees. The former implementations have actually also searched graphs, but in disguise. Tree searching can be applied to many kinds of graph searching too, albeit not as efficient in some cases.

A simple implementation of a graph search is a bit more complicated than the tree search (lib/ch06/graph_search.rb):

require 'iter_widening'

module Search
  class << self
    def graph(states,
              successors,
              combiner,
              state_eq = proc{ |a, b| a == b},
              old_states = [],
              &goal_p)
      dbg :search, ";; Search: %p", states
      return nil if states.empty?
      return states.first if goal_p[states.first]
      graph(combiner[new_states(states,
                                successors,
                                state_eq,
                                old_states),
                    states[1..-1]],
            successors,
            combiner,
            state_eq,
            old_states.find { |os| state_eq[os, states.first] } ?
              old_states :
              [states.first] + old_states,
            &goal_p)
    end

    def new_states(states, successors, state_eq, old_states)
      successors[states.first].select do |state|
        !(states.find { |s|
            state_eq[state,s]
          } || old_states.find { |s|
            state_eq[state,s]
          })
      end
    end
  end
end

The new_states method generates all the new states from the successors method, finding those that aren’t cyclic. The actual graph_search method is recursive in the same way the tree_search method.

The exercise it, we need a small method that generates two new nodes in a graph of numbers, and then we can see it in action (lib/ch06/graph_search.rb):

def next2(x)
  [x+1, x+2]
end

if __FILE__ == $0
  debug :search
  p Search.graph([1],
                 proc { |n| next2(n) },
                 proc { |x,y| y+x },
                 &is(6))
end

The final search algorithm to look at is A*. This code is substantially more complicated, but it’s also much more efficient. It uses paths to be able to find the best solution quickly. A* can be characterized as a general best-first graph search. The code looks like this (lib/ch06/a_star.rb):

require 'graph_search'

module Search
  class << self
    def a_star(paths,
               successors,
               cost_fn,
               cost_left_fn,
               state_eq = proc { |a, b| a == b},
               old_paths = [],
               &goal_p)
      dbg :search, ";; Search: %s", paths

      return [] if paths.empty?
      return [paths.first, paths] if goal_p[paths.first.state]

      path = paths.shift
      state = path.state
      old_paths = insert_path(path, old_paths)

      successors[state].each do |state2|
        cost = path.cost_so_far + cost_fn[state, state2]
        cost2 = cost_left_fn[state2]
        path2 = Path.new(state2, path, cost, cost+cost2)

        old = find_path(state2, paths, state_eq)
        if old
          if better_path(path2, old)
            paths = insert_path(path2, paths - [old])
          end
        else
          old = find_path(state2, old_paths, state_eq)
          if old
            if better_path(path2, old)
              paths = insert_path(path2, paths)
              old_paths = old_paths - [old]
            end
          else
            paths = insert_path(path2, paths)
          end
        end
      end
      a_star(paths,
             successors,
             cost_fn,
             cost_left_fn,
             state_eq,
             old_paths,
             &goal_p)
    end

    def find_path(state, paths, state_eq)
      paths.find do |p|
        state_eq[p.state, state]
      end
    end

    def better_path(path1, path2)
      path1.total_cost < path2.total_cost
    end

    def insert_path(path, paths)
      (paths + [path]).sort_by { |p| p.total_cost }
    end

    def path_states(path)
      return [] if !path
      [path.state] + path_states(path.previous)
    end
  end
end

if __FILE__ == $0
  debug :search
  p Search.path_states(Search.a_star([Path.new(1)],
                                     proc { |n| next2(n) },
                                     proc { |x,y| 1 },
                                     Search.diff(6),
                                     &is(6)).first)
end

In this case the algorithm is complicated enough that it might help to just look up a mathematical definition of it instead. It disappears a bit in the noise of Ruby.

As a small variation on the searches shown here, you can also quite easy make a search that returns every possible solution for a problem, provided that the problem space is finite. If it’s not… well, you’re on your own there. You can see code for search out all solutions in lib/ch06/search_all.rb:

require 'beam_search'

module Search
  class << self
    def all(start,
            successors,
            cost_fn,
            beam_width,
            &goal_p)
      solutions = []
      beam(start,
           successors,
           cost_fn,
           beam_width,
           &(proc do |x|
               solutions << x if goal_p[x]
               nil
             end)
           )
      solutions
    end
  end
end

The final pages of the section on search shows how to apply search to the GPS. Since GPS actually is search in disguise, using some of these algorithms might turn out to work well. The following code, from lib/ch06/search_gps.rb, successfully uses beam search to solve the Sussman anomaly:

$:.unshift '../ch04'
require 'gps3'
require 'blocks'
require 'beam_search'

class GPS2
  def successors(state)
    applicable_ops(state).map do |op|
      state.select do |x|
        !op.del_list.include?(x)
      end + op.add_list
    end
  end

  def applicable_ops(state)
    @ops.select do |op|
      op.preconds.subset_of?(state)
    end
  end

  def search(goal, beam_width = 10)
    Search.beam([[:start]] + @state,
                proc { |n| successors(n) },
                proc { |state|
                  state.select { |s| action?(s) }.size +
                  goal.select  { |con| !state.include?(con) }.size
                },
                beam_width
                ) do |state|
      goal.subset_of?(state)
    end.select do |s|
      action?(s)
    end
  end
end

if __FILE__ == $0
  gps = GPS2.new([[:c, :on, :a],
                  [:a, :on, :table],
                  [:b, :on, :table],
                  [:space, :on, :c],
                  [:space, :on, :b],
                  [:space, :on, :table]],
                 Blocks.make_ops([:a, :b, :c]))
  require 'pp'
  pp gps.search([[:a, :on, :b], [:b, :on, :c]])
end

Wow. That turned out to be a meatier chapter than I’d expected. It’s over now, at least, and we have some general tools to bring forward into the next chapters. Both searching and pattern matching will turn out to be really important for the coming approaches.

Next post it will be time to look at solving algebra problems. Interesting stuff.



Eliza


Eliza is probably one of the most famous AI programs ever made; it was first described in 1966. It’s interesting to note that after we have looked at the implementation it’s obvious that there isn’t much intelligence in this program at all, even though it does feel a bit spooky sometimes when having conversations with it.

The understanding Eliza displays is a result of quite simple pattern matching rules and have nothing to do with understanding. It’s also pattern matching that will take up most of this blog post. The algorithm implemented here is quite basic and something more advanced will be prepared for later chapters.

The Ruby code will have some differences compared to the original Lisp code, and I’ll note these as we go along. The most important one is that I’ll represent patterns and input strings as arrays of strings that are separated using split. Norvig uses (READ) so the Lisp code works on Lisp lists and atoms. This Ruby code will be a bit more complex in some cases due to this.

The file lib/ch05/pat.rb contains a first stab at simple pattern matching:

require 'enumerator'

class Pattern
  def initialize(pattern)
    @pattern = pattern
  end

  # Does pattern match input? Any variable can match anything
  def match(input, pattern = @pattern)
    pattern.enum_for(:zip, input).all? do |p, i|
      (p.is_a?(Array) && i.is_a?(Array) && match(i, p)) ||
        variable?(p) ||
        p == i
    end
  end

  def variable?(pattern)
    pattern.is_a?(String) && pattern[0] == ??
  end
end

Also note the cute trick combining zip and all?. The Enumerable#zip method will allow you to combine two or more arrays, and getting an enumerator for it makes it possible to first combine the array and then call all? on it. This should be quite efficient too. This will match simple patterns against input, using variables that begins with a question mark. This version really only returns true or false. To use it, do something like this:

p Pattern.new(%w(I need a ?X)).match(%w(I need a vacation))

At this stage, really simple matching works, but anything complicated will fail. We also need a way of getting hold of the variables captured in the matching, so that we can replace them in answers from Eliza.

The second version (in lib/ch05/pat2.rb) uses the same algorithm, but captures variables:

require 'enumerator'

class Pattern
  def initialize(pattern)
    @pattern = pattern
  end

  # Does pattern match input? Any variable can match anything
  def match(input, variables = [], pattern = @pattern)
    pattern.enum_for(:zip, input).all? do |p, i|
      (p.is_a?(Array) && i.is_a?(Array) && match(i, variables, p)) ||
        (variable?(p) && (variables << [p, i])) ||
        p == i
    end && variables
  end

  def variable?(pattern)
    pattern.is_a?(String) && pattern[0] == ??
  end
end

As you can see, the main difference is that match takes an optional array for variables. If the match succeeds it returns all variables, otherwise false. So something like this:

p Pattern.new(%w(I need a ?Y)).match(%w(I need a vacation))

would return [[“?Y”, “vacation”]].

The next version will also include a primitive form of unificiation, which makes it possible to match the same variable twice (lib/ch05/pat3.rb):

require 'pat2'

class Pattern
  # Match pattern against input in the context of the bindings
  def match(input, variables = {}, pattern = @pattern)
    pattern.enum_for(:zip, input).all? do |p, i|
      match_recurse(p, i, variables) ||
        match_variable(p, i, variables) ||
        p == i
    end && variables
  end

  def match_recurse(p, i, bindings)
    p.is_a?(Array) && i.is_a?(Array) && match(i, bindings, p)
  end

  def match_variable(p, i, bindings)
    variable?(p) &&
      ((bindings[p].nil? && (bindings[p] = i)) ||
       bindings[p] == i)
  end
end

This version is different mainly in that it returns a Hash instead of an Array. Norvig uses Lisp lists for this, but it doesn’t really make sense to define lots of extra functions for working with it when we already have a nice Hash in Ruby. Using a Hash also makes it really easy to check for previous examples of the same variable. Try it with a pattern such as %w(?Y should be ?Y).

The algorithm is slightly tricky, specifically since it actually modifies the hash as it recurses. This could easily bite you, but it’s still a step in the right direction.

Now, for making Eliza work out well enough for us, we actually need to have segment matching. This will allow matching of none or several atoms in a sweep. Adding this functionality actually transforms the code quite a lot, so let’s take a look at a first stab for this (lib/ch05/pat4.rb):

require 'pat3'

class Pattern
  # Match pattern against input in the context of the bindings
  def match(input, variables = {}, pattern = @pattern)
    case
    when variables.nil?
      nil
    when variable?(pattern)
      match_variable(pattern, input, variables)
    when pattern == input
      variables
    when segment_pattern?(pattern)
      match_segment(pattern, input, variables)
    when pattern.is_a?(Array) && input.is_a?(Array)
      match(input[1..-1],
            match(input[0], variables, pattern[0]),
            pattern[1..-1])
    else
      nil
    end
  end

  def match_variable(p, i, bindings)
    (bindings[p].nil? && bindings.merge(p => i)) ||
      (bindings[p] == i && bindings)
  end

  def segment_pattern?(p)
    p.is_a?(Array) && p[0][0] == ?*
  end

  def match_segment(pattern, input, bindings, start = 0)
    var = "?#{pattern[0][1..-1]}"
    pat = pattern[1..-1]
    if pat.nil? || pat.empty?
      match_variable(var, input, bindings)
    else
      pos = input[start..-1].index(pat[0])
      return nil unless pos
      b2 = match(input[(start+pos)..-1], bindings, pat)
      if b2.nil?
        match_segment(pattern, input, bindings, start+1)
      else
        match_variable(var, input[0...(start+pos)], b2)
      end
    end
  end
end

Here we aren’t modifying the Hash anymore, instead using a recursive version with match_variable merging a new array. Note how functional in style match_variable is. No modifications at all are happening there.

There are now several different cases to keep in mind. The first decision I made was to mirror Norvigs original algorithm that walks through the head of each array, instead of zipping everything up. Since we’re working with stuff that will be able to match even though the length of arrays are different, zip is really not the way to go anymore.

Another difference is the addition of the segment_pattern? and match_segment. Norvig uses a representation that includes a nested list such as (?* ?Y) to denote a segment. Since I don’t want to parse text, I decided to make a much easier choice, such that *Y denotes a segment, that will save into the ?Y variable. In my opinion, it makes both the code and the specifications easier to read.

Since we’re doing a recursive algorithm, the variables parameter is used for the base case of failure – if anything returns false or nil for variables, we fail match immediately.

So what is match_segment doing, really? This is the most tricky bit. Basically it needs to check what the next part of the pattern is to match (you can’t have two segments after each other without anything in between). Once that’s been found, match_segment tries to run the rest of a full match on the rest of the text. If that fails it tries to eat one more atom and recurses, otherwise it associates the current stretch of atoms with the variable.

You can try it out like this:

p Pattern.new(%w(*p need *x)).
  match(%w(Mr Hulot and I need a vacation))
p Pattern.new(%w(*x is a *y)).
  match(%w(what he is is a fool))

The first example shows the simple case, while the second one needs to do some backtracking. But the current version is not totally correct. Specifically, a case such as this would fail:

p Pattern.new(%w(*x a b *x)).
  match(%w(1 2 a b a b 1 2 a b))

The problem is that the algorithm successfully matches the first part of the string but can’t do anything with the rest, since ?X has different values unless the segment matching proceeds further. The fix is to first call match_variable so we can try to match the segment again in the worst case. It looks like this (lib/ch05/pat5.rb):

require 'pat4'

class Pattern
  def match_segment(pattern, input, bindings, start = 0)
    var = "?#{pattern[0][1..-1]}"
    pat = pattern[1..-1]
    if pat.nil? || pat.empty?
      match_variable(var, input, bindings)
    else
      pos = input[start..-1].index(pat[0])
      return nil unless pos

      b2 = match(input[(start+pos)..-1],
                 match_variable(var, input[0...(start+pos)], bindings),
                 pat)

      if !b2
        match_segment(pattern, input, bindings, start+1)
      else
        b2
      end
    end
  end
end

With this code the previous example works fine.

That is all the code there is to the pattern matching for our version of Eliza. Now for the actual implementation. Remember that this version is slightly less complicated compared with the original version. The list of rules in this code is not a full set either. (lib/ch05/eliza1.rb):

require 'pat5'

module Enumerable
  def some?
    self.each do |v|
      result = yield v
      return result if result
    end
    nil
  end
end

class Array
  def random_elt
    self[rand(self.length)]
  end
end

class Rule
  attr_reader :pattern, :responses

  def initialize(pattern, *responses)
    @pattern, @responses = pattern, responses
  end

  ELIZA_RULES =
    [
     Rule.new(Pattern.new(%w(*x hello *y)),
              "How do you do. Please state your problem"),
     Rule.new(Pattern.new(%w(*x I want *y)),
              "What would it mean if you got ?y?",
              "Why do you want ?y?",
              "Suppose you got ?y soon"),
     Rule.new(Pattern.new(%w(*x if *y)),
              "Do you really think it's likely that ?y? ",
              "Do you wish that ?y?",
              "What do you think about ?y?",
              "Really-- if ?y?"),
     Rule.new(Pattern.new(%w(*x no *y)),
              "Why not?",
              "You are being a bit negative",
              "Are you saying \"NO\" just to be negative?"),
     Rule.new(Pattern.new(%w(*x I was *y)),
              "Were you really?",
              "Perhaps I already knew you were ?y?",
              "Why do you tell me you were ?y now?"),
     Rule.new(Pattern.new(%w(*x I feel *y)),
              "Do you often feel ?y?"),
     Rule.new(Pattern.new(%w(*x I felt *y)),
              "What other feelings do you have?")
    ]
end

module Eliza
  class << self
    def run(rules = Rule::ELIZA_RULES)
      while true
        print "eliza> "
        puts eliza_rule(gets.downcase.split, rules)
      end
    end

    def eliza_rule(input, rules)
      rules.some? do |rule|
        result = rule.pattern.match(input)
        if result
          switch_viewpoint(result).
            inject(rule.responses.random_elt) do |sum, repl|
            sum.gsub(repl[0], repl[1].join(" "))
          end
        end
      end
    end

    def switch_viewpoint(words)
      replacements = [%w(I you),
                      %w(you I),
                      %w(me you),
                      %w(am are)]
      hash = {}
      words.each do |key, val|
        hash[key] = replacements.inject(val) do |sum, repl|
          sum.map { |val| val == repl[0] ? repl[1] : val}
        end
      end
      hash
    end
  end
end

if __FILE__ == $0
  Eliza.run
end

This is quite a lot of code, so let’s take it in chunks. First off I need some methods we defined in earlier chapters, namely Enumerable#some? and Array#random_elt. I’ve re-added them here for ease. Then we have the definition of a Rule, which is a pattern and a list of possible responses. It’s a very simple class definition, that takes all the arguments as parameters. Finally, there is the definition of a choice of rules from the original Eliza program. As you can see there are several variations in most cases, so the program can vary in its output.

The Eliza module has three different methods. The run-method takes the rules to use and goes into an infinite loop where it first prints a prompt, then reads a line of input, downcases this and finally splits it, sends it into the eliza_rule method and prints the result.

The eliza_rule method tries to match against at least one rule. If it succeeds in matching it first calls switch_viewpoint on the result (remember that the result here is a Hash of extracted segments from the input). It then replaces all instances of variables in one of the rules replacement text with the variable information.

The switch_viewpoint method just makes sure that the extracted strings from variables is turned into the other viewpoint, replacing “I” with “you”, “me” with “you”, etc.

The last lines of code just runs the Eliza program if this is the main program file that’s running. Try it out!

Now, wasn’t that quite easy? The magic really disappear once you’ve looked at this tiny implementation. And it’s obvious that there are many things that don’t work as well as it should. Pattern matching solves many problems, but you need a quite comprehensive suite of rules to make it really believable.

Eliza was one of the first programs to try to look like it understood English. But really understanding English is a much harder problem that is still at the core of AI.

For some more fun, I’ve encoded the full set of Eliza rules in lib/ch05/eliza2.rb.



Taste of Eliza


This is a typical conversation from the Ruby version of Eliza with full rule set I’ve just pushed to github. I’ll describe it in another blog post soon:

eliza> Hello there
How do you do. Please state your problem
eliza> I want to see if you work
Really-- if I work?
eliza> Yeah. You're a computer program that I need to check.
What do you think machines have to do with your problem?
eliza> Well, you're a machine, right?
Go on
eliza> And since you're a machine and I need to check you, you are quite relevant to this discussion.
What makes you think I am quite relevant to this discussion.?
eliza> That you are a computer program
What do you think about machines?
eliza> They are evil. They want to kill me
Possibly they are evil. they want to kill you
eliza> Yeah.
Please continue
eliza> No
You are being a bit negative
eliza> Yes
I understand
eliza> I don't think you do
Do you feel strongly about discussing such things?
eliza> Yes, I really feel strongly about it
What does that suggest to you?
eliza> That you are a fake
What makes you think I am a fake?
eliza> Just intuition
Please continue
eliza> What's your name?
Do you feel strongly about discussing such things?
eliza> What is your name?
What do you think?

Quite funny indeed, although there are some obvious glitches.



The General Problem Solver, part 2


In the last post I described a simple version of the General Problem Solver. This post will take a look at a more complete version that fixes some of the problems I discussed earlier. The first problem to solve is that it can sometimes be a bit hard to debug the output from our solver. If it fails we only know that it failed, not how far it got, and so on. So lets begin by creating a custom debug framework for us (lib/ch04/dbg.rb):

$dbg_ids = []

def dbg(id, format, *args)
  if $dbg_ids.include?(id)
    $stderr.puts(format%args)
  end
end

def debug(*ids)
  $dbg_ids = ($dbg_ids + ids).uniq
end

def undebug(*ids)
  $dbg_ids -= ids
end

def dbg_indent(id, indent, format, *args)
  if $dbg_ids.include?(id)
    $stderr.print "  "*indent
    $stderr.puts(format%args)
  end
end

This code uses a global variable to decide which debug statements should be used. We can turn on and off specific ids using the debug and undebug methods, while we can use dbg and dbg_indent to actually write something out.

Notice that I’ve used the sprintf operator (%) to make formatting of strings built into the system itself.

At this point it’s time to look at GPS2, which provide solutions for the “running around the block”, “prerequisite clobbers sibling”, “leaping before you look” and “recursive subgoal” problems.

One of the more interesting changes is that this version will not print anything, but instead return a status list that describes the actions taken. This will allow some more flexibility in how the code is used, later on.

Before starting out there are some things we need to add to make the output reasonable. We do that by representing operations a little bit differently, by including in the add-list a composite action that will include the symbol executing, and the name of the action. We also need an equivalent of the some-function. Finally, we need to have something that can create new operations including the execution part in the add list.

This code can be seen in lib/ch04/gps2.rb:

require 'gps'
require 'gps_no_clobber'
require 'dbg'

module Enumerable
  def some?
    self.each do |v|
      result = yield v
      return result if result
    end
  end
end

class GPS::Op
  def convert!
    unless self.add_list.any? do |l|
        l.is_a?(Array) && l.first == :executing
      end
      self.add_list << [:executing, self.action]
    end
    self
  end
end

GPS::SCHOOL_OPS.each do |op|
  op.convert!
end

class GPS2 < GPS
  class << self
    def op(action, parts = {})
      GPS::Op.new(action,
             parts[:preconds],
             parts[:add_list],
             parts[:del_list]).convert!
    end
  end
end

In this case I’ve chosen to make a subclass of GPS2, and use the existing helpers in gps and gps_no_clobber, although at the end most methods will be overridden.

I define the method some? on Enumerable; it’s actually really similar to a Ruby version of find/detect. The only difference is that we need to save the result of the block and actually return that instead of the value we sent in to the block.

I open up the GPS::Op class and add convert!. Notice that I’ve named it with a bang, since it will possibly modify the current instance. I’ve also decided to not follow convention by returning nil from a bang method. Instead I return self because it makes some of my code a bit simpler later on. The convert! method will check if the add-list already contains an array where the first element is :executing, otherwise it will add one of these. This will be more interesting later.

The gps2 file also converts all the available school operations.

Finally we provide a new method called GPS2::op, that will create a new converted operation for us. Notice that I’m using the convention of opening up the self class with class << self. I almost always prefer this way.

The next step is to take a look at the new solve-method. This will become slightly different since now all methods will take a state argument to keep track of where in the evaluation we are. The only place that doesn’t take a state is the solve-method, since it uses the initial state given to the initialize method. All methods except solve will also take a parameter for the current goal stack, that will help us keep track of which goals we have achieved so far.

The method solve looks like this (lib/ch04/gps2.rb):

  def solve(*goals)
    achieve_all([[:start]] + @state, goals, []).grep(Array)
  end

The original Lisp code uses remove-if #’atom to filter out all noise from the state, but the Ruby is much simplified by just using grep and sending in an Array. You did know that grep can take as argument anything that implements ===, right?

To keep track of the fact that we have started, we add the list [:start] to the front of the current state.

There are three more methods that need to be updated to make this implementation run. The first two are achieve_all and achieve (lib/ch04/gps2.rb):

  def achieve_all(state, goals, goal_stack)
    current_state = goals.inject(state) do |current_state, g|
      return [] if current_state.empty?
      achieve(current_state, g, goal_stack)
    end
    if goals.subset_of?(current_state)
      current_state
    else
      []
    end
  end

  def achieve(state, goal, goal_stack)
    dbg_indent(:gps, goal_stack.length, "Goal: %p", goal)

    if state.include?(goal)
      state
    elsif goal_stack.include?(goal)
      []
    else
      @ops.find_all do |op|
        appropriate?(goal, op)
      end.some? do |op|
        apply(state, goal, op, goal_stack)
      end || []
    end
  end

These are a fair bit more complicated than the first implementation. This is because we need to handle some things that the first implementation really didn’t handle well at all.

The achieve_all method is definitely a bit more messy. That’s because we need to update the current state for each call to achieve. In Norvig’s book, the implementation actually used a state variable that was updated after each iteration, but I felt that explicit modification didn’t feel right here, especially not in the presence of inject, which is really a perfect tool for this kind of updating. The only complication is that we want to halt everything if any call to achieve returns an empty state (this means that it couldn’t continue). If a goal couldn’t be achieved, it’s obvious we can just jump out directly.

The use here of inject is a bit different since it doesn’t explicitly build up something, but instead creates a new variable each time that is a modified version of the original. This is a refactoring that I would like to see in more code bases, since it’s a very nice way of getting rid of explicit mutation.

After building up the current state by calling achieve on all goals, we also need to make sure that all goals are still part of the current state. We do this using the subset? method defined in the code for the first GPS version.

The achieve method is the first place we use our debugging system. The length of the goal stack gives us an obvious indentation parameter, since it will get longer and longer the deeper we recurse. I use %p instead of %s since I really want to get the inspected output here.

There are three ways achieve can go. The first is if the goal is already in the current state. That means we have already achieved that goal, and all is fine.

If the goal is in the goal stack, that means we are in the second iteration of a recursive goal search – not good. That means we have failed that goal, so we return an empty array.

Finally, if none of the above situations are true, we need to find all appropriate operations for the current goal – using the same appropriate? method as the first GPS. We then use some? on all appropriate operations. The difference between find/detect and some? is obvious here – if we’d used find, the result would be an instance of Op, while some? will return the current state returned from the apply-method called inside the block.

At the end of the evaluation, if some? doesn’t find anything, it’s necessary to return an empty array instead of nil, since I’m using the empty array to represent failure every. (I will discuss this in more detail in a comparison post between Common Lisp and Ruby).

The missing method in GPS2 is now apply. It looks like this (lib/ch04/gps2.rb):

  def apply(state, goal, op, goal_stack)
    dbg_indent(:gps, goal_stack.length, "Consider: %p", op.action)

    state2 = achieve_all(state, op.preconds, [goal] + goal_stack)

    unless state2.empty?
      dbg_indent(:gps, goal_stack.length, "Action: %p", op.action)
      (state2 - op.del_list) + op.add_list
    end
  end

As you can see, we use dbg_indent in two different places here to make it obvious what’s happening while actually applying an operation. This is also the place where we first recurse to make sure all the operations preconditions have been satisfied. If we get back a state that is not empty, we can return a new state that is modified by the delete-list and then the add-list.

Wow, that was a bit more complicated, but not too bad. Let’s take a look at how this version works with the problems we established for GPS earlier (lib/ch04/gps2_problem1.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money,
                :have_phone_book],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school)

If you run it, you’ll see that the result matches more or less the steps we got from the first GPS. I use pp to display the result of the operation. The main difference is that the start condition is in there too.

Something very simple, like lib/ch04/gps2_problem2.rb also works fine:

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_works],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school)

The problem the last version used to get wrong now works correctly (lib/ch04/gps2_problem3.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money,
                :have_phone_book],
              GPS::SCHOOL_OPS)
pp gps.solve(:have_money, :son_at_school)

and lib/ch04/gps2_problem4.rb:

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money,
                :have_phone_book],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school, :have_money)

Leaping before you look also fails as it should (lib/ch04/gps2_problem5.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school)

Really simple problems that require no action also works fine (lib/ch04/gps2_problem6.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_home)

Monkey and bananas

So that we can see that the G in GPS is there for a reason, let’s see if we can apply the new version of GPS to a new domain. This problem is a classic AI problem – monkey and bananas. The basic idea is that a monkey is standing at the doorway to a room, there are bananas hanging from a rope in the middle of the room – out of the monkeys reach – and there is a chair near the door that the monkey can push into the room and stand upon to reach the bananas. The first thing we need to do is define the operators for this domain (lib/ch04/gps2_monkey1.rb):

require 'gps2'
require 'pp'

$banana_ops = [
              GPS2::op(:climb_on_chair,
                       :preconds => [:chair_at_middle_room,
                                     :at_middle_room,
                                     :on_floor],
                       :add_list => [:at_bananas, :on_chair],
                       :del_list => [:at_middle_room, :on_floor]),
              GPS2::op(:push_chair_from_door_to_middle_room,
                       :preconds => [:chair_at_door,
                                     :at_door],
                       :add_list => [:chair_at_middle_room,
                                     :at_middle_room],
                       :del_list => [:chair_at_door, :at_door]),
              GPS2::op(:walk_from_door_to_middle_room,
                       :preconds => [:at_door, :on_floor],
                       :add_list => [:at_middle_room],
                       :del_list => [:at_door]),
              GPS2::op(:grasp_bananas,
                       :preconds => [:at_bananas, :empty_handed],
                       :add_list => [:has_bananas],
                       :del_list => [:empty_handed]),
              GPS2::op(:drop_ball,
                       :preconds => [:has_ball],
                       :add_list => [:empty_handed],
                       :del_list => [:has_ball]),
              GPS2::op(:eat_bananas,
                       :preconds => [:has_bananas],
                       :add_list => [:empty_handed, :not_hungry],
                       :del_list => [:has_bananas, :hungry])
             ]

Nothing really strange here, really. So let’s use it and see if GPS works for it (lib/ch04/gps2_monkey1.rb):

gps = GPS2.new([:at_door,
                :on_floor,
                :has_ball,
                :hungry,
                :chair_at_door],
               $banana_ops)
pp gps.solve(:not_hungry)

This will generate the expected output:

[[:start],
 [:executing, :push_chair_from_door_to_middle_room],
 [:executing, :climb_on_chair],
 [:executing, :drop_ball],
 [:executing, :grasp_bananas],
 [:executing, :eat_bananas]]

And since we didn’t make any changes to the GPS problem, the claims of being generic does have some validity.

Maze searching

Another classic AI problem is maze searching. We can easily define a maze as numbered squares where one numbered square can lead to zero or more other squares. To make definitions really easy, we define a few simple methods that make it simple to define the operations for us (lib/ch04/maze.rb):

require 'gps2'
require 'pp'

module Maze
  class << self
    def make_ops(pair)
      [make_op(pair[0], pair[1]),
       make_op(pair[1], pair[0])]
    end

    def make_op(here, there)
      GPS2::op([:move, :from, here, :to, there],
               :preconds => [[:at, here]],
               :add_list => [[:at, there]],
               :del_list => [[:at, here]])
    end
  end

  Ops = [[1,2], [2,3], [3,4], [4,9], [9,14], [9,8],
         [8,7], [7,12], [12,13], [12,11], [11,6],
         [11,16], [16,17], [17,22], [21,22], [22,23],
         [23,18], [23,24], [24,19], [19,20], [20, 15],
         [15,10], [10,5], [20,25]].inject([]) do |sum, obj|
    sum + make_ops(obj)
  end
end

Here we first have make_ops, that just make all passages from one square to another symmetric – meaning we won’t have to define the passage from 1 to 2 AND the one from 2 to 1. The make_op method make use of some interesting properties of our code that was there without any real thought given to it. Namely that goals can be represented as arrays instead of symbols. In fact it doesn’t matter how you represent the goals, as long as you always use the same representation for the same goal. You can mix and match strings, symbols, regexps and arrays if you would like too. In this case the only goals we have are of the form [:at, 1], but it gives us a bit more representation power to do it like this.

Finally, a large array of pairs of numbers is transformed into operations using inject and calls to make_ops. The end result is all the operations we need to define this particular maze.

So, a first problem for this maze would probably look at how to get out of it, so lets see it (lib/ch04/maze_problem1.rb):

require 'maze'

gps = GPS2.new([[:at, 1]],
               Maze::Ops)
pp gps.solve([:at, 25])

The initial state is simple, we are at the first square, and want to get to the last (which is number 25). The output from running this problem gives us this output:

[[:start],
 [:executing, [:move, :from, 1, :to, 2]],
 [:executing, [:move, :from, 2, :to, 3]],
 [:executing, [:move, :from, 3, :to, 4]],
 [:executing, [:move, :from, 4, :to, 9]],
 [:executing, [:move, :from, 9, :to, 8]],
 [:executing, [:move, :from, 8, :to, 7]],
 [:executing, [:move, :from, 7, :to, 12]],
 [:executing, [:move, :from, 12, :to, 11]],
 [:executing, [:move, :from, 11, :to, 16]],
 [:executing, [:move, :from, 16, :to, 17]],
 [:executing, [:move, :from, 17, :to, 22]],
 [:executing, [:move, :from, 22, :to, 23]],
 [:executing, [:move, :from, 23, :to, 24]],
 [:executing, [:move, :from, 24, :to, 19]],
 [:executing, [:move, :from, 19, :to, 20]],
 [:at, 25],
 [:executing, [:move, :from, 20, :to, 25]]]

Except for that spurious [:at, 25], everything looks like we would expect here. We have a start move and then moving from square to square until we get to the last square.

The problem with the extra element is that the way we defined solve leaves everything that is an Array in there. What we really want to do is to leave everything that denotes an action in there. As you can see in lib/ch04/gps3.rb:

require 'gps2'

class GPS2
  def action?(x)
    x == [:start] || (x.is_a?(Array) && x.first == :executing)
  end

  def solve(*goals)
    achieve_all([[:start]] + @state, goals, []).find_all do |state|
      action?(state)
    end
  end
end

We first define what an action is and then find everything that satisfies that criteria.

What’s interesting with the current representation of the GPS, and also the way our maze domain looks like is that we can use the output for several different things. Say for example that we want to get a list of the path to the exit. Then we can use the code in lib/ch04/find_path.rb:

require 'maze'
require 'gps3'

module Maze
  class << self
    def find_path(start, finish)
      results = GPS2.new([[:at, start]], Maze::Ops).
        solve([:at, finish])
      unless results.empty?
        [start] + ((results - [[:start]]).map do |action|
          destination(action)
        end)
      end
    end

    def destination(action)
      action[1][4]
    end
  end
end

pp Maze.find_path(1, 25)
pp Maze.find_path(1, 1)
pp(Maze.find_path(1, 25) == Maze.find_path(25,1).reverse)

Running this first gives us the paths from 1 to 25, then from 1 to 1, and finally shows that our expectations of reversing the path is correct:

[1, 2, 3, 4, 9, 8, 7, 12, 11, 16, 17, 22, 23, 24, 19, 20, 25]
[1]
true

The blocks world

A final domain that probably has gotten more attention than any other in AI circles is the blocks world. The basic point of it is that you have a child’s set of building blocks on a table. The problems usually involve moving them in different ways, putting them on top of each other in different order, and so on. The assumption for our current modeling of it will be that you can only have one block on top of another. The only action you can take in this world is to move a block that has nothing on top of itself on top of either the table or on top of a block that has nothing on top of it.

First of, creating the operators for this domain (lib/ch04/blocks.rb):

require 'gps3'

module Blocks
  class << self
    def make_ops(blocks)
      ops = []
      blocks.each do |a|
        blocks.each do |b|
          unless a == b
            blocks.each do |c|
              unless [a, b].include?(c)
                ops << move_op(a, b, c)
              end
            end
            ops << move_op(a, :table, b)
            ops << move_op(a, b, :table)
          end
        end
      end
      ops
    end

    # Make an operator to move A from B to C
    def move_op(a, b, c)
      GPS2.op([:move, a, :from, b, :to, c],
              :preconds => [[:space, :on, a], [:space, :on, c], [a, :on, b]],
              :add_list => move_ons(a, b, c),
              :del_list => move_ons(a, c, b))
    end

    def move_ons(a, b, c)
      b == :table ? [[a, :on, c]] :
        [[a, :on, c], [:space, :on, b]]
    end
  end
end

This implementation is trickier than the others. The style of operations we want is something along the lines of “Move block A from TABLE to B”. This code accomplishes all available variations, while checking that there are spaces on top of A and B, and that A is on top of TABLE. The guards in make_ops need to make sure that we don’t create operations from a block to itself.

Now that we can make operators, lets see a simple problem. We have two blocks a and b, that lie on a table, and we want to put a on top of b. That would look like this (lib/ch04/blocks_problem1.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:a, :on, :table],
                [:b, :on, :table],
                [:space, :on, :a],
                [:space, :on, :b],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b]))

pp gps.solve([:a, :on, :b], [:b, :on, :table])

This gives us the expected output:

[[:start], [:executing, [:move, :a, :from, :table, :to, :b]]]

Lets consider the case where we have a on top of b, and want to move it so b is on top of a. This time with debug output (lib/ch04/blocks_problem2.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:a, :on, :b],
                [:b, :on, :table],
                [:space, :on, :a],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b]))

pp gps.solve([:b, :on, :a])

This also gives us what we expect:

Goal: [:b, :on, :a]
Consider: [:move, :b, :from, :table, :to, :a]
  Goal: [:space, :on, :b]
  Consider: [:move, :a, :from, :b, :to, :table]
    Goal: [:space, :on, :a]
    Goal: [:space, :on, :table]
    Goal: [:a, :on, :b]
  Action: [:move, :a, :from, :b, :to, :table]
  Goal: [:space, :on, :a]
  Goal: [:b, :on, :table]
Action: [:move, :b, :from, :table, :to, :a]
[[:start],
 [:executing, [:move, :a, :from, :b, :to, :table]],
 [:executing, [:move, :b, :from, :table, :to, :a]]]

One of the more interesting features of my implementation compared to Norvigs is that he has some ordering problems that needs extra code in achieve_all to handle. I haven’t figured out why, but my code doesn’t have that problem, so I’ll not show the fixed code (since there was no need to fix it). An example that caused these problems for Norvig looks like this with the Ruby code (lib/ch04/blocks_problem3.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:a, :on, :b],
                [:b, :on, :c],
                [:c, :on, :table],
                [:space, :on, :a],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b, :c]))

pp gps.solve([:c, :on, :b], [:b, :on, :a])

This problem represent a block world where a is on top of b, b is on top of c and c is on top of table, and you want to reverse the ordering of them.

Another problem Norvig has that doesn’t show up in this code is a few examples that do to many operations to achieve something. The file lib/ch04/blocks_problem4.rb is one of those:

require 'blocks'
require 'pp'

gps = GPS2.new([[:c, :on, :a],
                [:a, :on, :table],
                [:b, :on, :table],
                [:space, :on, :b],
                [:space, :on, :c],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b, :c]))

pp gps.solve([:c, :on, :table])

Where the optimal solution takes one action, the lisp code does two actions (moving c from a to b, and then from b to table). This is because of ordering problems. Topological sort might solve it, for example. There is another example that takes four operations instead of two (lib/ch04/blocks_problem5.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:c, :on, :a],
                [:a, :on, :table],
                [:b, :on, :table],
                [:space, :on, :b],
                [:space, :on, :c],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b, :c]))

pp gps.solve([:c, :on, :table], [:a, :on, :b])

But as mentioned before, it doesn’t seem like the Ruby code exhibit this problem, so I decided to not implement Norvigs fixes for them.

Interestingly, there are problems that can’t be solved no matter which order you put the goals. Take the example where b and a is on the table, and c is on top of a. You want to have c on the table, b on top of c and a on top of b. The current GPS implementation can’t handle this no matter which order you try (lib/ch04/blocks_problem6.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:c, :on, :a],
                [:a, :on, :table],
                [:b, :on, :table],
                [:space, :on, :c],
                [:space, :on, :b],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b, :c]))

pp gps.solve([:a, :on, :b], [:b, :on, :c])
pp gps.solve([:b, :on, :c], [:a, :on, :b])

This is called the Sussman anomaly, and solutions will be covered later in the book.

Conclusion

It’s obvious that this version of GPS is much more powerful than the original one. But there is also some things that still show up as problems. Even though we introduced several measures there are still cases where a correct solution can’t be found. For example, we can take a look at the getting a child to school problem again, adding a new operator for taking a taxi there. Say that we want to get the son to school without using any money and define it like this (lib/ch04/gps2_problem7.rb):

require 'gps3'
require 'pp'

gps = GPS2.new([:son_at_home,
                :have_money,
                :have_works],
              GPS::SCHOOL_OPS +
               [
                GPS2::op(:taxi_son_to_school,
                         :preconds => [:son_at_home,
                                       :have_money],
                         :add_list => [:son_at_school],
                         :del_list => [:son_at_home,
                                       :have_money])
               ])
debug :gps
pp gps.solve(:son_at_school, :have_money)

Here something funny happens. If you look at the debug output:

Goal: :son_at_school
Consider: :drive_son_to_school
  Goal: :son_at_home
  Goal: :car_works
  Consider: :shop_installs_battery
    Goal: :car_needs_battery
Consider: :taxi_son_to_school
  Goal: :son_at_home
  Goal: :have_money
Action: :taxi_son_to_school
Goal: :have_money
[]

There are two ways of solving this: first solve the have_money goal and then the get son to school. In that case the have_money goal is solved trivially, and then the money is spent on a taxi. If the other ordering is tried the child is taxied to school and then the have_money goal fails. There is a valid solution (driving the son to school) but it’s never tried.

Another problem with the approach is that the descriptive power is not general and powerful enough. The conditions we use for operators in GPS is not really abstract enough.

GPS also assumes that you know everything about the world (“perfect information”), and that everything is either true or false. Probability is nowadays one of the better approaches available for AI, and the GPS doesn’t take fuzzy knowledge into account.

Finally, interacting goals, where you have several active goals at the same time is something most people have, but GPS takes one goal at a time.

All of these problems made it problematic to continue to use the GPS approach. Another thing that had a large impact was the realization how NP-hard problems affected problem solvers like GPS. At the end of the day, GPS was an interesting early approach to solve the problem, and it’s definitely been part of AI heritage available today.



The General Problem Solver, part 1


One of the earlier attempts to create a system capable of problem solving was given the grandiose name General Problem Solver. It was first developed in 1957 by Alan Newell and Herbert Simon. When GPS was first introduced it caused quite some excitement in the AI community. GPS never did live up to the expectations, but it’s still important from a historical perspective. The original GPS implementation was written in IPL and had some subtle differences to the program developed in PAIP. I’ll follow PAIP while developing the Ruby version. If you have an interest in the original version I suggest first finding a book explaining IPL (which is not a funny language at all).

GPS implements a version of something called means-ends analysis. The kind of thinking embodied by this analysis is quite common sense. In short, you have some goals, you then figure out what conditions need to be true for you to achieve that goal. If those conditions aren’t true, you need to figure out how to achieve those, and so on.

The way we’ll write the first version of GPS, there are several interesting properties. The most central ones are the starting state, the goals, and the available operations. At the moment I will represent the states and goals as symbols. An operation need to be a bit more complicated. First of all, it’s got a name so you can trace it. It has preconditions that details what needs to be true for this operation to be able to operate. And it has an add-list and a delete-list. The add-list tells which conditions are true after the operation has executed, and the delete-list details what is no longer true.

So lets take a look at the first version of the implementation. I have made some changes compared to Norvig’s Lisp-code. The most obvious one is that I’m not using global variables, instead opting to put everything into a class called GPS (this code can be found in lib/ch04/gps.rb):

class GPS
  Op = Struct.new(:action, :preconds, :add_list, :del_list)

  def initialize(state, ops)
    @state = state
    @ops = ops
  end

  # General Problem Solver main interface: achieve all goals using
  # defined operations
  def solve(*goals)
    goals.all? do |goal|
      achieve goal
    end
  end

  # A goal is achieved if it already holds, or if there is an
  # appropriate op for it that is applicable
  def achieve(goal)
    @state.include?(goal) ||
      (@ops.find_all do |op|
         appropriate?(goal, op)
       end.any? do |op|
         apply(op)
       end)
  end

  # An op is appropriate to a goal if it is in its add list
  def appropriate?(goal, op)
    op.add_list.include?(goal)
  end

  # Print a message and update state if op is applicable
  def apply(op)
    if op.preconds.all? { |cond| achieve(cond) }
      puts "Executing #{op.action}"
      @state -= op.del_list
      @state += op.add_list
      return true
    end
    false
  end
end

There are several components to this code so lets take them piece by piece. First of all, we create a class called GPS. Inside if it we immediately define a struct called Op. There is a symmetry between the Common Lisp defstruct operation and the Ruby Struct.new call that I like a lot. In this case it’s perfect since we don’t want Op to have any actual behavior right now. The Op consists of an action, the preconditions, the add-list and the delete-list.

The initialize method takes the current state and the available ops. The current state is an array of states, and the ops is an array of ops.

The actualy central piece of this code is the solve-method. This method corresponds to the GPS function in the original code. The main difference is that the GPS function takes the state, goals and ops as parameters, while we put these inside the object using the initialize method instead.

So what does it mean for us to solve goals? Basically we try to achieve all goals. If we can achieve all goals we have solved it, otherwise not. Norvig’s Lisp code handles this a bit differently, by returning the symbol ‘solved if it works. I decided to just return a boolean instead. This means that our usage of the solve method might be a bit more verbose.

The achieve-method tries to do two different things. First it checks if the current state already includes the goal. In that case we’re fine. Otherwise we first need to find all operations that are appropriate for this goal, and then check if any of those operations can be applied. Before taking a look at appropriate? and apply, it’s interesting to note that I’ve decided to use any? here, while Norvig uses the function called some. These two operations are actually a bit different, but right now that difference doesn’t matter. The difference is that while any? will always return true or false, some will actually return the non-nil value generated from the test method. Ruby doesn’t seem to have anything like that (Enumerable#detect/find returns the original value, not the value generated by the block). As you’ll see in the next post I’ll actually have to implement some at that point.

What is appropriate? then? First of all, it’s a method that might actually belong on the Op class instead of in the GPS class. At the moment it just checks that the operations add-list includes the goal – meaning that the operation can be used to achieve the goal.

Finally we have the apply method (this one is called apply-op in Norvig’s code). Apply is where the recursive elements of the algorithm come into play. Basically, for an operation to be applied, all of the preconditions of that operation need to be fulfilled. We use all? to try to achieve all of the preconditions and if it succeeds we print which action we executed, modify the state by removing the delete-list and adding the add-list, and finally return true.

And that’s really all there is to the general problem solver. Of course we should test it and see, right? The original domain used for GPS was about drvining to nursery school and we will use something similar to that for testing this implementation.

First of all we need to have some operations defined for this domain. You can find this code in lib/ch04/gps.rb too:

  SCHOOL_OPS = [
                Op.new(:drive_son_to_school,
                       [:son_at_home, :car_works],
                       [:son_at_school],
                       [:son_at_home]),
                Op.new(:shop_installs_battery,
                       [:car_needs_battery, :shop_knows_problem,
                        :shop_has_money],
                       [:car_works],
                       []),
                Op.new(:tell_shop_problem,
                       [:in_communication_with_shop],
                       [:shop_knows_problem],
                       []),
                Op.new(:telephone_shop,
                       [:know_phone_number],
                       [:in_communication_with_shop],
                       []),
                Op.new(:look_up_number,
                       [:have_phone_book],
                       [:know_phone_number],
                       []),
                Op.new(:give_shop_money,
                       [:have_money],
                       [:shop_has_money],
                       [:have_money])
               ]

As you can see, this domain gives a hint about what might play into the goals for this domain. So let’s begin by taking a look at a problem. The first one can be found in lib/ch04/problem1.rb:

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money,
               :have_phone_book],
              GPS::SCHOOL_OPS)
if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

The current state says that the son is at home, the car needs battery and we have money and a phone book. The goal to solve is to get the son to school. If we run this code it generates this output:

Executing look_up_number
Executing telephone_shop
Executing tell_shop_problem
Executing give_shop_money
Executing shop_installs_battery
Executing drive_son_to_school
Solved

Well, that seemed to work out fine, right? What about the case where we have no phone book (lib/ch04/problem2.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

This generates

Not solved

as we would expect. And if we take a simple example where the car already works (lib/ch04/problem3.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_works],
              GPS::SCHOOL_OPS)

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

We get:

Executing drive_son_to_school
Solved

Nice. It seems to be quite good. So what are the problems with the current approach? First of all, it doesn’t solve some very easy problems. The representation is generally wrong for continous activities. Norvig calls this “The Running around the block problem”. It’s easy to define a goal to drive from home to school, but it’s a bit more tricky to represent running around the block. There are ways around it, of course, but the GPS operator doesn’t necessarily make it as natural as it could be.

Another, more serious problem is the clobbered sibling goal problem. In something like lib/ch04/problem4.rb, this version of GPS handle everything correctly:

require 'gps'

gps = GPS.new([:son_at_home,
               :have_money,
               :car_works],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

But if we create a problem like this (lib/ch04/problem5.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_phone_book,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

This will incorrectly report the problem as solved – since GPS first solves the problem of having money, and then solves the problem of having the son at school. The way of handling this problem is to replace every instance that achieves every call with a call to a new method called achieve_all. That involves the solve and apply methods. You can see the code in lib/ch04/gps_no_clobber.rb:

require 'gps'

class Array
  def subset_of?(other)
    (self - other) == []
  end
end

class GPS
  def solve(*goals)
    achieve_all goals
  end

  def apply(op)
    if achieve_all(op.preconds)
      puts "Executing #{op.action}"
      @state -= op.del_list
      @state += op.add_list
      return true
    end
    false
  end

  def achieve_all(goals)
    goals.all? do |goal|
      achieve goal
    end && goals.subset_of?(@state)
  end
end

Here I’ve decided to just open up the GPS class to provide this functionality. Another choice would be to subclass, but since this doesn’t substantially change the functionality I’ve decided to just do it like this. There are several things going on here. First I’ve decided to add an operator to Array, which mirrors the Common Lisp function subsetp. Array.subset_of? returns true if the current array is a subset of the argument array, so [].subset_of?([1]) == true, while [1].subset_of?([]) == false. The solve method is updated to just call achieve_all, and apply also calls achieve_all. The definition of achieve_all first makes sure we can achieve all goals, and then make sure that all of the goals to achieve are still in the current state.

If you execute lib/ch04/problem6.rb:

require 'gps_no_clobber'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_phone_book,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

You will see that it executes several actions but then returns a not solved, since it’s not possible to achieve both goals.

Another problem with this implementation is based on the interleaving of planning and execution. Norvig calls it “The leaping before you look problem”. You can see it exemplified in the last execution – namely we do lots of things, but then realize that we haven’t solved the problem. At the end of the execution we have already fixed the car by giving the shop the money. That might not be that good. Since we only have one state variable, and this has already been changed, there is no way to go back.

There is one final problem, with recursive subgoals. That is, this version of GPS is not too good at handling the case where a goal depends on a goal that depends on the original goal. The file lib/ch04/problem7.rb exemplifies this:

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money],
              GPS::SCHOOL_OPS +
              [
               GPS::Op.new(:ask_phone_number,
                           [:in_communication_with_shop],
                           [:know_phone_number],
                           [])
              ])

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

We have removed :have_phone_book state from the initial state, and added a new operation to ask for phone number. This operation requires you to be in communication with the shop, and since you need the phone number to be in communication with the shop this will result in a SystemStackError in Ruby.

A final nuisance with the current implementation is that the result is just true or false. The only information we get is the printed output.

All of these are things that the final version of GPS will handle more correctly – at least in some cases. This post ended up long enough as it is, so GPS2 will have to wait until the next time.



Language generation


This post is the first in a series of posts about PAIPr. Read here for more info about the concept.

Today I would like to start with taking a look at Chapter 2. You can find the code in lib/ch02 in the repository.

Chapter 2 introduces Common Lisp through the creation of a series of ways of doing generation of language sentences in English, based on simple grammars. It’s an interesting chapter to start with since the code is simple and makes it easy to compare the Ruby and Common Lisp versions.

The first piece to take a look at is the file common.rb, which contains two methods we’ll need later on:

require 'pp'

def one_of(set)
  [set.random_elt]
end

class Array
  def random_elt
    self[rand(self.length)]
  end
end

As you can see I’ve also required pp, to make it easier to print structures later on.

Both one_of and Array.random_elt are extremely simple methods, but it’s still nice to have the abstraction there. I’m retaining the naming from the book for these two methods.

The first real example defines a grammar by directly using methods. (From simple.rb):

require 'common'

def sentence; noun_phrase + verb_phrase; end
def noun_phrase; article + noun; end
def verb_phrase; verb + noun_phrase; end
def article; one_of %w(the a); end
def noun; one_of %w(man ball woman table); end
def verb; one_of %w(hit took saw liked); end

As you can see, all the methods just define their structure by combining the result of more basic methods. A noun phrase is an article, then a noun. An article is either ‘the’ or ‘a’, and a noun can be ‘man’, ‘ball’, ‘woman’ or ‘table’. If you run sentence a few times you will see that you sometimes get back quite sensible sentences, like [“a”, “ball”, “hit”, “the”, “table”]. But you will also get less interesting things, such as [“a”, “ball”, “hit”, “a”, “ball”]. At this stage the space for variation is quite limited, but you can still see a simplified structure of the English language in these methods.

To create an example that involves some more interesting structures, we can introduce adjectives and prepositions. Since these can be repeated zero times, or many times, we’ll use a production called PP* and Adj* (pp_star and adj_star in the code). This is from simple2.rb:

require 'simple'

def adj_star
  return [] if rand(2) == 0
  adj + adj_star
end

def pp_star
  return [] if rand(2) == 0
  pp + pp_star
end

def noun_phrase; article + adj_star + noun + pp_star; end
def pp; prep + noun_phrase; end
def adj; one_of %w(big little blue green adiabatic); end
def prep; one_of %w(to in by with on); end

Nothing really changes here, except that in both the optional productions we randomly return an empty array 50% of the time. They then call themselves recursively. The noun phrase production also changes a bit, and adj and prep gives us the two new terminals needed. If you try this one, you might get some more interesting results, such as: [“a”, “table”, “took”, “a”, “big”, “adiabatic”, “man”]. It’s still nonsensical of course. And it seems that this approach with randomness generates quite large output in some cases. To make it really nice there should probably be a diminishing bias in the adjectives and prepositions based on the length of the already generated string.

Another problem with this approach is that it’s kinda unwieldy. Using methods for the grammar is probably not the right choice long term. More specifically, we are tied to this implementation by having the grammar be represented as methods.

A viable alternative is to represent everything as a grammar definition – using a rule based solution. The first part of rule_based.rb looks like this:

require 'common'

# A grammar for a trivial subset of English
$simple_grammar = {
  :sentence => [[:noun_phrase, :verb_phrase]],
  :noun_phrase => [[:Article, :Noun]],
  :verb_phrase => [[:Verb, :noun_phrase]],
  :Article => %w(the a),
  :Noun => %w(man ball woman table),
  :Verb => %w(hit took saw liked)}

# The grammar used by generate. Initially this is $simple_grammar, but
# we can switch to other grammars
$grammar = $simple_grammar

Note that I’m using double arrays for the productions that aren’t terminal. There is a reason for this that will be more pronounced in the later grammars based on this. But right now it’s easy to see that a production is either a list of words, or a list of list of productions. Production names beginning with a capital is a terminal – this is a convention in most grammars. I didn’t use capital letters for the terminals when using methods because Ruby methods named like that causes additional trouble when calling them.

Now that we have the actual grammar we also need a helper method. PAIP defines rule-lhs, rule-rhs and rewrites, but the only one we actually need here is rewrites. (From rule_based.rb):

def rewrites(category)
  $grammar[category]
end

And actually, we could do away with it too, but it reads better than an index access.

The final thing we need is the method that actually creates a sentence from the grammar. It looks like this:

def generate(phrase)
  case phrase
  when Array
    phrase.inject([]) { |sum, elt|  sum + generate(elt) }
  when Symbol
    generate(rewrites(phrase).random_elt)
  else
    [phrase]
  end
end

If what we’re asked to generate is an array, we generate everything inside of that array, and combine them. If it’s a symbol we know it’s a production, so we get all the possible rewrites and take a random element from it. Currently every production have one rewrite, so the random_elt isn’t strictly necessary – but as you’ll see later it’s quite nice. And finally, if phrase is not an Array or Symbol, we just return the phrase as the generated element.

I especially like the use of inject as a more general version of (mappend #’generate phrase). Of course, for readability it would have been possible to implement mappend too:

def mappend(sym, list)
  list.inject([]) do |sum, elt|
    sum + self.send(sym, elt)
  end
end

But I choose to use inject directly instead, since it’s more idiomatic. Note that this version of mappend doesn’t work exactly the same as Common Lisp mappend, since it doesn’t allow a lambda.

Getting back to the generate method. If you were to run generate(:sentence), you would get the same kind of output as with the method based version – with the difference that changing the rules is much simpler now.

So for example, you can use this code from bigger_grammar.rb, which creates a larger grammar definition and then sets the default grammar to use it:

require 'rule_based'

$bigger_grammar = {
  :sentence => [[:noun_phrase, :verb_phrase]],
  :noun_phrase => [[:Article, :'Adj*', :Noun, :'PP*'], [:Name],
                   [:Pronoun]],
  :verb_phrase => [[:Verb, :noun_phrase, :'PP*']],
  :'PP*' => [[], [:PP, :'PP*']],
  :'Adj*' => [[], [:Adj, :'Adj*']],
  :PP => [[:Prep, :noun_phrase]],
  :Prep => %w(to in by with on),
  :Adj => %w(big little blue green adiabatic),
  :Article => %w(the a),
  :Name => %w(Pat Kim Lee Terry Robin),
  :Noun => %w(man ball woman table),
  :Verb => %w(hit took saw liked),
  :Pronoun => %w(he she it these those that)}

$grammar = $bigger_grammar

This grammar includes some more elements that make the output a bit better. For example, we have names here, and also pronouns. One of the reasons this grammar is easier to use is because we can define different versions of the productions. So for example, a noun phrase can be the same as we defined earlier, but it can also be a single name, or a single pronoun. We use this to handle the recursive PP* and Adj* productions. You can also see why the productions are defined with an array inside an array. This is to allow choices in this grammar.

A typical sentence from this grammar (calling generate(:sentence)) gives [“Terry”, “saw”, “that”], or [“Lee”, “took”, “the”, “blue”, “big”, “woman”].

So it’s easier to change these rules. Also believe that it’s easier to read, and understand the rules here. But one of the more important changes with the data driven approach is that you can use the same rules for different purposes. Say that we want to generate a sentence tree, which includes the name of the production used for that part of the tree. That’s as simple as defining a new generate method (in generate_tree.rb):

require 'bigger_grammar'

def generate_tree(phrase)
  case phrase
  when Array
    phrase.map { |elt| generate_tree(elt) }
  when Symbol
    [phrase] + generate_tree(rewrites(phrase).random_elt)
  else
    [phrase]
  end
end

This code follows the same pattern as generate, with a few small changes. You can see that instead of appending the results from the Array together, we instead just map every element. This is because we need more sub arrays to create a three. In the same manner when we get a symbol we prepend that to the array generated. And actually, at this point it’s kinda interesting to take a look at the Lisp version of this code:

(defun generate-tree (phrase)
  (cond ((listp phrase)
         (mapcar #'generate-tree phrase))
        ((rewrites phrase)
         (cons phrase
               (generate-tree (random-elt (rewrites phrase)))))
        t (list phrase)))

As you can see, the structure is mostly the same. I made a few different choices in representation, which means I’m checking if the phrase is a symbol instead of seeing if the rewrites for a symbol is non-nil. The call to mapcar is equivalent to the Ruby map call.

What does it generate then? Calling it with “pp generate_tree(:sentence)” I get something like this:

[:sentence,
 [:noun_phrase, [:Name, "Lee"]],
 [:verb_phrase,
  [:Verb, "saw"],
  [:noun_phrase,
   [:Article, "the"],
   [:"Adj*",
    [:Adj, "green"],
    [:"Adj*"]],
   [:Noun, "table"],
   [:"PP*"]],
  [:"PP*"]]]

which maps neatly back to our grammar. We can also generate all possible sentences for a grammar without recursion, using the same data driven approach.

The code for that can be found in generate_all.rb:

require 'rule_based'

def generate_all(phrase)
  case phrase
  when []
    [[]]
  when Array
    combine_all(generate_all(phrase[0]),
                generate_all(phrase[1..-1]))
  when Symbol
    rewrites(phrase).inject([]) { |sum, elt|  sum + generate_all(elt) }
  else
    [[phrase]]
  end
end

def combine_all(xlist, ylist)
  ylist.inject([]) do |sum, y|
    sum + xlist.map { |x| x+y }
  end
end

If you run generate(:sentence) you will get back a list of all 256 possible sentences from this simple grammar. In this case the algorithm is a bit more complicated. It’s also using the common Lisp idiom of working on the first element of a list and then recur on the rest of it. This makes it possible to combine everything together. I assume that it should be possible to devise something suitably clever based on the new Array#permutations or possible Enumerable#group_by or zip.

It’s interesting how well the usage of mappend and mapcar maps to uses of inject and map in this code.

Note that I’ve been using globals for the grammars in this implementation. An alternative that is probably better is to pass along an optional parameter to the methods. If no grammar is supplied, just use the default constant instead.

Anyway, the code for this chapter is in the repository. Play around with it and see if you can find anything interesting. This code is definitely an introduction to Lisp, more than a serious AI program – although it does show the kind of approaches that have been used for primitive code generation.

The next chapter will talk about the General Problem Solver. Until then.



Paradigms of Artificial Intelligence Programming (in Ruby)


Since I never can get enough projects, I’ve decided to start on something I’ve thought about doing for a long time. There are several reasons for doing it, but foremost among them is that I want to get back to playing with AI, and I want to have a project with many small pieces that I can do when I have some time over. If it ends up being educational or useful for others at the same time, well, I’m not complaining!

So what is it?

Well, first I’d like to introduce a book. It’s called Paradigms of Artificial Intelligence Programming or PAIP for short. It’s written by Peter Norvig, who’s also written several other books about AI. Currently he’s the Director of Research at Google. PAIP is probably both my favorite book about AI, and my favorite book about Common Lisp. It’s a really great book. Really. If you have any interest in one of those two subjects you should get hold of it. PAIP doesn’t cover cutting edge AI, but rather takes the historic view and looks at several examples from different eras, going from the first programs to some later, quite advanced things.

I’ve read it numerous times, went through the code and tweaked it and so on. It’s lots of fun. But that was a few years ago. So basically, what I want to do is to go through the book again. But this time I’m going to write all the programs in Ruby – converting them from Common Lisp and then maybe tweak them a bit to make them more idiomatic. And I’m planning to post it here. Or rather, I’m going to post the actual source code to http://github.com/olabini/paipr. I’m going to blog about all the code I write. You don’t necessarily have to have the book, since I’m going to surround the code with some descriptions and explanations.

Once again then, why should anyone care? Well, I don’t know. No one might care. But for me personally it’s going to be an interesting experience converting idiomatic Common Lisp into idiomatic Ruby. It’s going to be fun to revisit the old approaches to AI. And it might serve as a good, code heavy introduction to the subject for anyone interested in it.

I do have the permission from Peter Norvig to do this. The Ruby code I write is covered by the MIT license, while any Lisp code posted as part of this exercise is covered by the license here: http://norvig.com/license.html.

Also note that I sometimes won’t write the most obvious Ruby – it will be good to have a few links to the original Lisp code.