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.

6 Comments | By Ola Bini | In: paipr | tags: AI, artificial intelligence, eliza, paipr, ruby. | #

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.

No Comments | By Ola Bini | In: paipr | tags: AI, artificial intelligence, eliza, paipr, ruby. | #

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.

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

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.

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

It seems that the current trend in Internet services is all the rage about meta information; ways to find the information you want. These services come in various guises; some collecting pictures or movies, collecting and classifying links or finding out what other people are looking at. The quintessential application right now must be the search engine and Google is in the forefront with this, as well as with many other current meta information processing applications. But what is the next level? The next evolutionary step in information processing?

Is meta-meta-information enough?
The obvious answer would be that we need meta information about the meta services; a way to search, handle and collect this information. Which meta services are the people I admire using? But is that really enough? It places a big burden on the individual trying to keep up with the information flow. Tagging and such helps the situation a bit, but it’s still way to much for one person. I already feel slightly overwhelmed right now, trying to keep up with everything that happens in my current domains of interest at the moment. It seems to me that meta services for finding meta information wouldn’t be enough, since it doesn’t solve the underlying problem of actually helping to manage the information.

Are there any alternatives?
The development in services from this point on seems to revolve around two solutions; the semantic web, RDF and all those shenanigans, and intelligent agents.

The semantic web is a collection of technologies – some that exist and some that don’t, yet – that enables more collaboration and interaction through Internet. Typical examples include ontologies for classifying information, two-ended links, user annotations and other ways to include self-description in the data itself.

Intelligent agents are probably the easiest AI application to rationalize, since it doesn’t require strong AI, and it’s obvious how helpful they would be. Intelligent agents are typically cast in the same box as semantic web, but I feel that intelligent agents (IA from now on) could probably exist and be effective without semantic web metadata. What makes IA more or less necessary very soon, is that automating handling of information is the solution to the meta-meta-problem. Most of my current meta information handling is done with the help of programs that I have customized in various ways to make information easier for me to handle, but manually customizing handling of meta meta information suffers from the same problem as manually tagging spam; it is just too much information. IA could help, by first getting to know the habits and interests of it’s user, and then extrapolating what information would be useful and what could be thrown away.

Finalities
Is semantic web or IA enough in it’s own right? Could the one solve the problem without the other? I think not, or at least not solve it permanently. I believe semantic web tech will enter Internet before IA, but I don’t believe the information flow will be solved without them. At most, semantic web will buy us one or two years to catch our breath. IA is interesting technology, and we really need it now, especially if are a knowledge worker.

2 Comments | By Ola Bini | In: Uncategorized | tags: AI, information, intelligent agents, meta information, semantic web. | #