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.


One Comment, Comment or Ping

  1. So if we have a really cool tool in LISP (the sharp-quote) and a not-so-cool one in Ruby, why not write that really cool tool in Ruby? It MUST be possible, right? :) And it would make programming easier, too, right? :)

    October 12th, 2009

Reply to “Tools and searching”