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.

By Ola Bini | In: paipr | tags: AI, artificial intelligence, general problem solver, gps, paipr, ruby. | #