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.
1 Comment | By Ola Bini | In: paipr | tags: artificial intelligence, paipr, searching. | #