AI / Machine Learning

It's that time of year again where you reach deep into your brains to learn something new, and I reach deep into my pockets to reward you with a toy for sending it to me.

Last year the contest got a fair amount of interest, with Adrian Moreno claiming the prize.

This year it's back, and I'm giving you the choice between a 16GB iPod Nano, or an 8GB iPod Touch (the iPod that's funner than all previous iPods). More...

Hey! Why don't you make your life easier and subscribe to the full post or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!

With multiple monitors and mobile computing becoming the norm rather than the exception, applications need to start behaving in a way that makes operation under those conditions less abrasive. We already see programs like Ultramon on Windows popping up to make the experience smoother (and for which I still have yet to find a suitable replacement on Mac OS), but I think we're going to have to do better. More...

Automatic download of libraries and packages
I'd like to see automatic downloads of libraries/packages from IDEs.

The idea came to me a couple of weeks ago on twitter. More...

Dave Mark raises some interesting questions about artificial intelligence in games over at AIGameDev.com. First, he explains that although we're seeing more and better AI in games, a common complaint heard from gamers runs along the lines of "why can't they combine such and such AI feature from game X in game Y." Then, Dave poses the questions for developers to answer:

We can only cite limited technological resources for so long.
...
Perhaps, from a non-business standpoint... that of simply an AI developer, we should be asking ourselves what the challenges are in bringing all the top AI techniques together into the massive game environments that are so en vogue. What is the bottleneck? Is it money? Time? Hardware? Technology? Unwillingness? Unimaginativeness? A belief that those features are not wanted by the gamer? Or is it simply fear on the part of AI programmers to undertake those steps necessary to put that much life into such a massive world?

Let me first admit that I'd wager Dave Mark knows a lot more about this stuff than me. That's how he makes a living, after all. My experience in developing game AI comes from choose your-own-adventure text-based games as a kid (where the algorithm was very deterministic, with few options), making villagers walk around in Jamaicanmon!, More...

The Turing Test was designed to test the ability of a computer program to demonstrate intelligence. (Here is Alan Turing's proposal of it.) It is often described as so: if a computer can fool a person into believing it too is a person, the computer has passed the test and demonstrated intelligence. That view is a simplified version.

Quoth Wikipedia about the rules:

A human judge engages in a natural language conversation with one human and one machine, each of which try to appear human; if the judge cannot reliably tell which is which, then the machine is said to pass the test.

Specifically, the test should be run multiple times and if the judge cannot decipher which respondent is the human about 50% of the time, you might say he cannot tell the difference, and therefore, the machine has demonstrated intelligence and the ability to hold a conversation with a human.

I bring this up because recently Giles Bowkett said that poker bots pass the test, and pointed to another post where he said the Turing test was beaten in the 1970s by a paranoid repeater named PARRY.

I suppose the idea of poker bots passing the test comes about because (presumably) the human players at the table don't realize they are playing against a computer. But if that is the case, even a losing bot would qualify - human players may think the bot player is just an idiot. More...

More interesting is his idea that the Turing test was beaten in the 1970s.

In defense of that thought, Giles mentions that the requirement having the questioner "actively [try] to determine the nature of the entity they are chatting with" is splitting hairs. Even if you agree with that, the poker bot certainly does not qualify - there is no chat, and there is certainly no natural language.

If that still constitutes hair splitting, I'm sure we can eventually split enough hairs to reduce the test so that most any program can pass. Give the sum(x,y) x,y ε {0..9} program to a primary school math teacher, and the fact that it can add correctly may lead the teacher to believe it is a smart kid. Then add in the random wrong answer to make it more believable.

In any case, if you accept the hair-splitting argument about the program that actually did chat in natural language, then certainly PARRY passed the test. On the other hand, while you may consider that the test was passed in fact, it was not done so in spirit.

I'll admit that I think the requirement of a tester talking to both a human and a computer program is an important one. Even disregarding the "no occasion to think they were talking to a computer," if we limit the computer's response to a particular set of people who think they are in a particular context, we could (for example) use Markov-model generated sentences with some characters in keyboard-distance-proximity replaced within the words. We now have a drunk typist. Perhaps in his drunken stupor he is not at his sharpest, but he would likely still be considered an intelligent being.

If the human tester is able to ask questions of both the computer and another human, do you think he would ever choose the computer program that rephrases his questions to sound paranoid as the human over the person who answers to the best of his ability?

The point is that without that requirement, the test becomes meaningless. Giles notes that

All the test really does is expose how little we know about what makes people people. The fact that it's easy to fool people into thinking a computer is human doesn't actually teach you anything about the difference between computers and humans; all it does is teach you that it's easy to fool people.

I think that's only true if you conceive of the test as he does. By keeping all of the requirements Turing proposed, it becomes quite a bit harder to pass, and retains its utility. Further, removing that quality changes the essence of the test. Since we can assume the test was designed to be useful, can we really say that insisting the test retain its essence is unreasonable?

What do you think?

The following was generated using a 7th order Markov chain and several of my blog posts as source text:

More...

For the monetary hurdles? A computer to prove anything on you.

If you are serving with talented coders so it doesn't change. Can you understand the case study present in different paradigm shifts in science. I was on vacation, "I can't see my old search terms every time you run into a code monkey? Are you a code monkey? Are you stick to standards so you could have implement our own develop good sound-editor to do it. Even more diplomatic terms, of course of action - if a proxy) the objectives and different approach much better, and how can you believe it?" I think it would solve those domain you're willing to him speak than after a little over a million users so it doesn't "mean that a competitors. Of course of action - if a proxy) the objectives and different paradigms to help out in the to-read list: The Power of integration in asking what other hand, JSF, Seam, and Tapestry are based on my to-read list.) Because I think you can keep the view updated - but there are made, and borders on absurd side of the elements in the code for you to record an improvement. That's not a far leap to see that you do?" Here he actually pointless. How do I know - I was doing before I started to deploy to XBOX 360 or PC (Developers created." Instead, you should use is a contest to avoid conversations. It can be threatened." What are the Maximizers are drive-in traffic and implementation of an old professor of mine, be honest about it. Thanks XNA!

As always came back in January. Perhaps you understand it. If you want to conversations. It can be threatened." What are the number of integration in asking people something to do it. Even more diplomatic terms, of course, you can do. In particular, by posting a good developers created." Instead, you should.

The point is that you're not passion.

There are a couple of repeats noticeable, which is mostly due to my lack of source text. At least, it worked a little better using one-hundred 8.5" x 11" pages of Great Expectations (still gibberish though).

Anyway, here's the Ruby source code:

class MarkovModel
    def create_model(file, order, unit)
    #unit = "word" or "character"
        @unit = unit
        entire_file = ""
        @order = order
        #read the entire file in
        File.open(file, "r") do |infile|
                cnt=0
                while (line = infile.gets)
                        entire_file += line
                        cnt+=1
                end
        end

        #split the file according to characters or words
        if unit == "word"
                split_on = /\s/
        else
                split_on = ""
        end
        @entire_file_split = entire_file.split(split_on)

        #construct a hash like:
        #first 'order' letters, letter following, increment count
        @model = Hash.new
        i = 0
        @entire_file_split.each do |c|
            this_group = @entire_file_split[i,order]
            next_letter = @entire_file_split[i+order,1]

            #if group doesn't exist, create it
		   if @model[this_group] == nil
		       @model[this_group] = { next_letter => 1 }
            #if group exists, but this "next_letter" hasn't been seen, insert it
            elsif @model[this_group][next_letter] == nil
                @model[this_group][next_letter] = 1
            #if group and next letter exist in model, increment the count
            else
                cur_count_of_next_letter = @model[this_group][next_letter] + 1
                @model[this_group][next_letter] = cur_count_of_next_letter
            end
            i+=1
        end
    end

    def generate_and_print_text(amount)
        start_group = @entire_file_split[0,@order]
        print start_group

        this_group = start_group
        (0..(amount-@order)).each do |i|
            next_letters_to_choose_from = @model[this_group]

            #construct probability hash
            num = 0
            probabilities = {}
            next_letters_to_choose_from.each do |key, value|
                    num += value
                    probabilities[key] = num
            end

            #select next letter
            index = rand(num)
            matches = probabilities.select {|key, value| index <= value }
            sorted_by_value = matches.sort{|a,b| a[1]<=>b[1]}
            next_letter = sorted_by_value[0][0]
            print " " if @unit == "word" #if we're splitting on words
            print next_letter

            #shift the group
            this_group = this_group[1,@order-1] + next_letter.to_ary
        end
    end

    def print_model
        require 'pp'
        PP.pp(@model)
    end
end

file = File.expand_path "source_text.txt"
mm = MarkovModel.new
mm.create_model(file, 7, "character")
mm.generate_and_print_text(2000)
mm.create_model(file, 1, "word")
mm.generate_and_print_text(250)
#mm.print_model

A couple of weeks ago the UH Code Dojo embarked on the fantastic voyage that is writing a program to solve Sudoku puzzles, in Ruby. This week, we continued that journey.

Though we still haven't completed the problem (we'll be meeting again tenatively on October 15, 2007 to do that), we did construct what we think is a viable plan for getting there, and began to implement some of it.

The idea was based around this algorithm (or something close to it): More...

	while (!puzzle.solved)

	{

	  find the most constrained row, column, or submatrix

	  for each open square in the most constrained space,

	    find intersection of valid numbers to fill the square

	  starting with the most constrained, 

	    begin filling in open squares with available numbers

	}

With that in mind, we started again with TDD.

I'm not going to explain the rationale behind each peice of code, since the idea was presented above. However, please feel free to ask any questions if you are confused, or even if you'd just like to challenge our ideas.

Here are the tests we added:

  def test_find_most_constrained_row_column_or_submatrix
    assert_equal "4 c", @solver.get_most_constrained
  end
  
  def test_get_available_numbers
    most_constrained = @solver.get_most_constrained
    assert_equal [3,4,5], @solver.get_available_numbers(most_constrained).sort
  end
  
  def test_get_first_empty_cell_from_most_constrained 
    most_constrained = @solver.get_most_constrained
    indices = @solver.get_first_empty_cell(most_constrained)
    assert_equal [2,4], indices
  end  
  
  def test_get_first_empty_cell_in_submatrix
    indices = @solver.get_first_empty_cell("0 m")
    assert_equal [0,2], indices
  end

And here is the code to make the tests pass:

def get_most_constrained
    min_open = 10
    min_index = 0
    @board.each_index do |i|
      this_open = @board[i].length - @board[i].reject{|x| x==0}.length
      min_open, min_index = this_open, i.to_s + " r" if this_open < min_open 
    end

    #min_row = @board[min_index.split(" ")]
    
    @board.transpose.each_index do |i|
      this_open = @board.transpose[i].length - @board.transpose[i].reject{|x| x==0}.length
      min_open, min_index = this_open, i.to_s + " c" if this_open < min_open 
    end

    (0..8).each do |index|
      flat_subm = @board.get_submatrix_by_index(index).flatten
      this_open = flat_subm.length - flat_subm.reject{|x| x==0}.length
      min_open, min_index = this_open, index.to_s + " m" if this_open < min_open
    end
   
    return min_index    
  end
  
  def get_available_numbers(most_constrained)
  	index, flag = most_constrained.split(" ")[0].to_i,most_constrained.split(" ")[1] 
    avail = [1,2,3,4,5,6,7,8,9] - @board[index] if flag == "r"
    avail = [1,2,3,4,5,6,7,8,9] - @board.transpose[index] if flag == "c"
    avail = [1,2,3,4,5,6,7,8,9] - @board.get_submatrix_by_index(index).flatten if flag == "m"

    return avail
  end
  
  def get_first_empty_cell(most_constrained)
    index, flag = most_constrained.split(" ")[0].to_i,most_constrained.split(" ")[1]
    result = index, @board[index].index(0) if flag == "r"
    result = @board.transpose[index].index(0), index if flag == "c"
    result = index%3*3,index*3+@board.get_submatrix_by_index(index).flatten.index(0) if flag == "m"

    return result
  end 

Obviously we need to clean out that commented-out line, and I feel kind of uncomfortable with the small amount of tests we have compared to code. That unease was compounded when we noticed a call to get_submatrix instead of get_submatrix_by_index. Everything passed because we were only testing the first most constrained column. Of course, it will get tested eventually when we have test_solve, but it was good that the pair-room-programming caught the defect.

I'm also not entirely convinced I like passing around the index of the most constrained whatever along with a flag denoting what type it is. I really think we can come up with a better way to do that, so I'm hoping that will change before we rely too much on it, and it becomes impossible to change without cascading.

Finally, we also set up a repository for this and all of our future code. It's not yet open to the public as of this writing (though I expect that to change soon). In any case, if you'd like to get the full source code to this, you can find our Google Code site at http://code.google.com/p/uhcodedojo/.

If you'd like to aid me in my quest to be an idea vacuum (cleaner!), or just have a question, please feel free to contribute with a comment.

A couple of days ago the UH Code Dojo met once again (we took the summer off). I had come in wanting to figure out five different ways to implement binary search. The first two - iteratively and recursively - are easy to come up with. But what about three other implementations? I felt it would be a good exercise in creative thinking, and pehaps it would teach us new ways to look at problems. I still want to do that at some point, but the group decided it might be more fun to tackle to problem of solving any Sudoku board, and that was fine with me.

Remembering the trouble Ron Jeffries had in trying to TDD a solution to Sudoku, I was a bit weary of following that path, thinking instead we might try Peter Norvig's approach. (Note: I haven't looked at Norvig's solution yet, so don't spoil it for me!) More...

Instead, we agreed that certainly there are some aspects that are testable, although the actual search algorithm that finds solutions is likely to be a unit in itself, and therefore isn't likely to be testable outside of presenting it a board and testing that its outputted solution is a known solution to the test board.

On that note, our first test was:

require 'test/unit'
require 'sudokusolver'

class TestSudoku < Test::Unit::TestCase
  def setup  
    @board = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
             [6, 0, 0, 1, 9, 5, 0, 0, 0],
             [0, 9, 8, 0, 0, 0, 0, 6, 0],
             [8, 0, 0, 0, 6, 0, 0, 0, 3],
             [4, 0, 0, 8, 0, 3, 0, 0, 1],
             [7, 0, 0, 0, 2, 0, 0, 0, 6],
             [0, 6, 0, 0, 0, 0, 2, 8, 0],
             [0, 0, 0, 4 ,1 ,9 ,0, 0, 5],
             [0, 0, 0, 0, 8, 0, 0, 7, 9]]
          
    @solution =[[5, 3, 4, 6, 7, 8, 9, 1, 2],
                [6, 7, 2, 1, 9, 5, 3, 4, 8],
                [1, 9, 8, 3, 4, 2, 5, 6, 7],
                [8, 5, 9, 7, 6, 1, 4, 2, 3],
                [4, 2, 6, 8, 5, 3, 7, 9, 1],
                [7, 1, 3, 9, 2, 4, 8, 5, 6],
                [9, 6, 1, 5, 3, 7, 2, 8, 4],
                [2, 8, 7, 4 ,1 ,9 ,6, 3, 5],
                [3, 4, 5, 2, 8, 6, 1, 7, 9]]
    
    @solver = SudokuSolver.new
    
  end

  def test_solve
    our_solution = @solver.solve(@board)
    assert_equal(@solution, our_solution)
  end

end

We promptly commented out the test though, since we'd never get it to pass until we were done. That doesn't sound very helpful at this point. Instead, we started writing tests for testing the validity of rows, columns, and blocks (blocks are what we called the 3x3 submatrices in a Sudoku board).

Our idea was that a row, column, or block is in a valid state if it contains no duplicates of the digits 1 through 9. Zeroes (open cells) are acceptable in a valid board. Obviously, they are not acceptable in a solved board.

To get there, we realized we needed to make initialize take the initial game board as an argument (so you'll need to change that in the TestSudokuSolver#setup method and SudokuSolver#solve, if you created it), and then we added the following tests (iteratively!):

  def test_valid_row
    assert @solver.valid_row?(0)
  end

  def test_valid_allrows
   (0..8).each do |row|
     assert @solver.valid_row?(row)
     end
  end

The implementation wasn't difficult, of course. We just need to reject all zeroes from the row, then run uniq! on the resulting array. Since uniq! returns nil if each element in the array is unique, and nil evaluates to false, we have:

class SudokuSolver
  def initialize(board)
    @board = board
  end
    
  def valid_row?(row_num)
    @board[row_num].reject{|x| x==0}.uniq! == nil
  end
end

At this point, we moved on to the columns. The test is essentially the same as for rows:

  def test_valid_column
    assert @solver.valid_column?(0)
  end

  def test_valid_allcolumns
   (0..8).each do |column|
     assert @solver.valid_column?(column)
     end
  end

The test failed, so we had to make it pass. Basically, this method is also the same for columns as it was for rows. We just need to call Array#transpose# on the board, and follow along. The valid_column? one-liner was @board.transpose[col_num].reject{|x| x==0}.uniq! == nil. We added that first, made sure the test passed, and then refactored SudokuSolver to remove the duplication:

class SudokuSolver
  def initialize(board)
    @board = board
  end
  
  def valid_row?(row_num)
    valid?(@board[row_num])
  end
  
  def valid_column?(col_num)
    valid?(@board.transpose[col_num])
  end
  
  def valid?(array)
    array.reject{|x| x==0}.uniq! == nil
  end
end

All the tests were green, so we moved on to testing blocks. We first tried slicing in two dimensions, but that didn't work: @board[0..2][0..2]. We were also surprised Ruby didn't have something like an Array#extract_submatrix method, which assumes it it passed an array of arrays (hey, it had a transpose method). Instead, we created our own. I came up with some nasty, convoluted code, which I thought was rather neat until I rewrote it today.

Ordinarily, I'd love to show it as a fine example of how much prettier it could have become. However, due to a temporary lapse into idiocy on my part: we were editing in 2 editors, and I accidentally saved the earlier version after the working version instead of telling it not to save. Because of that, I'm having to re-implement this.

Now that that sorry excuse is out of the way, here is our test for, and implementation of extract_submatrix:

def test_extract_submatrix
  assert_equal [[1,2,3],[4,5,6],[7,8,9]].extract_submatrix(1..2,1..2) , [[5,6],[8,9]]
end

class Array
  def extract_submatrix(row_range, col_range)
    self[row_range].transpose[col_range].transpose
  end
end

Unfortunately, that's where we ran out of time, so we didn't even get to the interesting problems Sudoku could present. On the other hand, we did agree to meet again two weeks from that meeting (instead of a month), so we'll continue to explore again on that day.

Thoughts? (Especially about idiomatic Ruby for Array#extract_submatrix)

Update: Changed the misspelled title from SudokoSolver to SudokuSolver.

Update 2: SudokuSolver Part 2 is now available.

For background and history on partial order planners, see What is Partial Order Planning?, Selected History of POP Part 1, and POP History Part 2. Or, you can read the entire thing in PDF format.

Our goal is to give commands to the partial order planner, telling it what the goal is, the initial state (if it exists), and actions it can perform. The actions contain the name of the action, any preconditions that must be fulfilled before that action can be performed, and a set of effects the action has on the world state. After giving this information to the planner, it should output a plan if one exists.

For simplicity's sake, I've used a STRIPS-like notation, without the complexity of existentially or universally quantified variables, among other things. Further, only one possible plan is returned, rather than attempting to find all plans. The one returned is not guaranteed to be optimal, though (inadequate) tests have shown that it is correct. Plans are to improve these limitations in the future, moving to a less restrictive ADL-style syntax, and adding support for returning multiple plans. More...

In the meantime, the first task is to allow a user to enter commands in a syntax that looks like:

PlanName("Put on Shoes")

Goal(:RightShoeOn ^ :LeftShoeOn)

Action(:RightShoe, EFFECT => :RightShoeOn, PRECOND => :RightSockOn)

Action(:RightSock, EFFECT => :RightSockOn)

Action(:LeftShoe, EFFECT => :LeftShoeOn, PRECOND => :LeftSockOn)

Action(:LeftSock, EFFECT => :LeftSockOn)

Also, it should allow function-like notation, such as:

PlanName("Change Tire")

Init(At(:Flat,:Axle) ^ At(:Spare,:Trunk))

Goal(At(:Spare,:Axle))

Action(Remove(:Spare,:Trunk),

       PRECOND => At(:Spare,:Trunk),

       EFFECT => NotAt(:Spare,:Trunk) ^ At(:Spare,:Ground))

Action(Remove(:Flat,:Axle),

       PRECOND => At(:Flat,:Axle),

       EFFECT => NotAt(:Flat,:Axle) ^ At(:Flat,:Ground))

Action(PutOn(:Spare,:Axle),

       PRECOND => At(:Spare,:Ground) ^ NotAt(:Flat,:Axle),

       EFFECT => NotAt(:Spare,:Ground) ^ At(:Spare,:Axle))

Action(:LeaveOvernight,

       EFFECT => NotAt(:Spare, :Ground) ^ NotAt(:Spare,:Axle) ^

       NotAt(:Spare,:Trunk) ^ NotAt(:Flat,:Ground) ^

       NotAt(:Flat,:Axle))

The domain described in Code Sample 1 should produce a plan such as:

LeftSock → LeftShoe → 
RightSock → RightShoe

and RightSock → LeftSock → LeftShoe → RightShoe. As one can surmise from looking at the domain as it is written, any plan where the socks are on before the shoes is sufficient.

Finally, the domain given in Code Sample 2 should render plans like

Remove(Flat,Axle) → 
Remove(Spare,Trunk) → PutOn(Spare,Axle)

, switching the first two actions depending on which it decides to do first (since either one would work).

Implementing (or allowing) such syntax in Ruby turns out to be simple. To get the conjunction operator ^, we simply define a module with ^ as a method, and include that module in Ruby's String, Symbol, and Array classes, since we'll be using each of these as symbols in our "new" language (See Code Sample 3).

module Logic

    def ^(condition)

        [self, condition]

    end

end

#modify the symbol class to include the ^ operation

class Symbol

    include Logic

end

#modify the array class to include the ^ operation

class Array

    include Logic

end

#modify the string class to include the ^ operation

class String

    include Logic

end

Next, we need to allow the use of function-style symbols, such as Remove(:Spare,:Trunk). As with most things in Ruby, this is also simple. We just use the method_missing method in our module:

# when the user enters a function, turn it into an action

def method_missing(method_id, *args)

    symbol_name = "#{method_id}("

    args.each { |arg| symbol_name += arg.to_s + "," }

    symbol_name[0,symbol_name.length-1] + ")"

end

We now have the ability to use the syntax we laid forth in the first two blocks of code to define our problems that need planning. All that remains are to implement the functions in our "language" that allow us to define the problem domain, and an algorithm to solve for plans.

To do so, first, we initialize the start state with an Init() function that simply stores the conditions it is passed. Similarly, the goal state and initial open preconditions are simply stored into member variables as they are passed via the Goal() method. Finally, actions are constructed from a name and a hash with keys PRECOND and EFFECT.

#constants to use to store hash for precondition and effect

#(only for purposes of keeping the DSL looking close to the original)

PRECOND = :precondition

EFFECT = :effect

#store the start-state conditions

def Init(conditions)

    @start_state = conditions

end

alias init Init

#store the goal defined by the user

def Goal(conditions)

    @goal = conditions

    @open_preconditions = @goal

end

alias goal Goal

# store actions defined by the user

def Action(name, precondition_effect)

    action= ["name" => name,

                "precondition" => precondition_effect[PRECOND],

                "effect" => precondition_effect[EFFECT]]

    @actions = [] if !@actions

    @actions = @actions + action

end

alias action Action

Finally, we come to the meat of the problem, the partial-order planning algorithm. The algorithm itself follows a fairly simple path:

From the list of open preconditions, choose one.
Find an action whose effect is the same as the precondition we chose and add it to the plan.
Add to the list of preconditions any requirements for that action.
Remove from the list of preconditions any that match the effects for the chosen action.
Repeat steps 1-4 until the set of open preconditions is empty, or no action that satisfies a precondition can be found.
Remove any preconditions from the open list that match the starting state.
If the set of open preconditions is empty, return the plan. Otherwise, fail.

The algorithm in Ruby follows:

def make_plan

    action_plan = []

    fail = false

    while (@open_preconditions.size > 0 && !fail)

        #randomize the open_preconditions and actions to show order

        #doesn't matter

        @open_preconditions=@open_preconditions.sort_by { rand }

        #find an action that solves it the first open precondition

        attempted_precondition = @open_preconditions.shift

        action_to_take = find_action_for attempted_precondition

        if (action_to_take != nil)

            add_preconditions_for action_to_take

            remove_preconditions_fulfilled_by action_to_take

            #add the action to the plan

            action_plan.push(action_to_take["name"])

        else

            #put the precondition back on the open_preconditions, since

            #it wasn't fulfilled by an action

            fail = true if @open_preconditions.size == 0

            @open_preconditions.push attempted_precondition

            remove_preconditions_matching_start_state

            fail = false if @open_preconditions.size == 0

        end

    end

    if @open_preconditions.size > 0 || fail

        puts "There appears to be no plan that satisfies the problem."

        puts "Open preconditions: "

        puts @open_preconditions

        action_plan = []

     end

    sanitize_plan(action_plan.reverse)

end

Most of the code is aptly named where there are functions (see RubyPOP.zip for the complete source), but two issues in this algorithm immediately jump to the forefront. The first is: why aren't we also randomizing the list of actions? Clearly, if there are two actions that satisfy the same precondition, the first one encountered will always win. This was done because randomizing the list of actions (if two or more satisfy the same precondition) has the potential to cause a loop of preconditions/effects, and thus cause incorrect plans to be generated. Since no attempt was made at finding the optimal plan, I didn't want to clutter the code and make it harder to follow. Correct plans are still generated, and a future version meant for more demanding environments would indeed allow a random action to be chosen.

The second issue that is not immediately clear begs the question: "just what is that sanitize_plan method doing there?" Some actions may add duplicate preconditions to the set of open preconditions. The algorithm as it stands allows this to happen for readability purposes, and simply cleans up the plan later with the sanitize_plan function.

Finally, it is also clear that a more "elegant" solution may have been to take actions as functions, which receive preconditions as their parameters, and whose output are effects. The thought of such an implementation is interesting and worthy of exploration, though time constraints prevented me from doing so in this case.

As mentioned above, a complete version of the code and three manual tests can be found in the RubyPOP.zip file.

If you need more context (rather than jumping straight into this), check out What is Partial-Order Planning? and Selected History of Partial Order Planning, Part 1 if you haven't already.

* * * *

As David Chapman noted in 1985, "planners of the most promising ('nonlinear') sort have been complicated, heuristic, ill-defined AI programs, without clear conditions under which they work." And since the time of NOAH, INTERPLAN, and NONLIN (and others I've left out for space reasons), there have been various improvements in the realm of partial-order planning. Chapman's program, TWEAK, is one of them, and was followed by the UCPOP and RePOP planners. More...

It was apparent as far back as 1975 that "linear planning" (or totally ordered planning, as described in What is Partial-Order Planning?) was not sufficient. Russell and Norvig relay the story of Allen Brown's experiment: that it could not solve simple problems such as the Sussman anomaly, where given 3 blocks labeled A, B, and C, with block B on the table and C on top of A which is on the table, get to the goal state of A on top of B on top of C (Russell, 410, 414) (See Figure 1). Around that time, as part of his Ph.D., Austin Tate released a paper which described INTERPLAN, a system to solve the problem of interleaving shown by Brown using Sussman's HACKER program (the Sussman Anomaly) (Tate [A] / Russell 410). More...

Last night I had the good fortune to be in attendance at a talk given by Ray Kurzweil entitled "The Web Within Us: When Minds and Machines Become One." For those unfamiliar with Ray, part of his bio as given in the program distributed at the presentation reads

Ray Kurzweil has been described as "the restless genius" by the Wall Street Journal and "the ultimate thinking machine" by Forbes. Moreover, Inc. magazine ranked him eighth among entrepreneurs in the United States, calling him the "rightful heir to Thomas Edison." ...

As one of the leading inventors of our time, Kurzweil was the principle developer of the first CCD flat-bed scanner, the first omni-font optical character recognition system, the first print-to-speech reading machine for the blind, the first text-to-speech synthesizer, the first music synthesizer capable of recreating the sound of a grand piano and other orchestral instruments, and the first commercially marketed large vocabulary speech recognition system.

More...

The talk was simply mind-blowing. He showed off a camera for the blind that could correct for 3D rotation and angles to read a page in a book, and some still-in-the-works but much better than currently available speech-to-speech translation (using speech-to-text, then translation, then text-to-speech). Some of the more interesting bits reminded me of a couple of ideas I had back in high school - one of combatting cancer with "machines" where they could be injected into the blood stream, detect cancer cells, and destroy them - and the other was like a "printer" that could build things, given the specs and materials (my words, not his). I should have been an inventor!

He also mentioned that we are coming ever closer to being able to reverse engineer the entire brain - saying the cerebral cortex (if I remember correctly... I could just be making that up) has already been well synthesized (along with 20 or so other parts of the brain) and that soon, we'd be able to do all the parts of the brain. Another cool bit was the fat-inhibitor pill, which would detect the gene responsible for storing fat, and switch it off.

There was a lot of AI and biotechnology involved, but the talk would still have been easy to follow for just about anyone I think (there were 1500 people or so in attendance). And the breadth and depth of his knowledge on various subjects is just simply amazing. I wish I could have made it to the follow-up this morning where it would have been just a small classroom-sized audience with a lot more interaction, but I just couldn't get away from the office for the amount of time I would have needed to (plus, it would have been rush hour, where the drive would take me 1.5 hours instead of the normal 30 minutes).

One last thing - he talked about full-immersion virtual reality- where we could switch off the actual receptors (well, more like switch what they are receiving) in our brain and replace the signal. Very cool stuff indeed, but also scary. If you're into that branch of technology, or just like to know what's coming up in the future, I'd recommend checking out his website or the books. I certainly plan to.

Update: CNNMoney has a profile on Ray Kurzweil from May 2, 2007.

For our case, we'll explore partial-order planning in a classical planning environment. Such an environment is fully observable (as opposed to only partially so) and deterministic (as opposed to having randomness, or being stochastic). Further, the space is finite and static in nature - it does not change in the middle of deliberation. Finally, the environment is "discrete (in time, action, objects, and effects)," as opposed to continuous along any of these axes (Russell, 375. For further reading on the characteristics of environments, see Russell page 41-42). More...

To understand what partial-order planning entails, it might be helpful to know what planning is, and then what ordered planning entails. To that end, planning is "the task of coming up with a sequence of actions that will achieve a goal" (Russell, 375). That is a fairly straightforward - exactly as we would expect if we weren't speaking of computers and programs.

An example is simple: given a set of actions I can perform, which ones do I choose (and in what order should I apply them) in order to reach my goal? I've got to get to work this morning - what should I do to get there? I might need to wake up, turn off the alarm, shower, take off my wet pajamas and put on something suitable for doing business, and so on, until I reach work in the morning (or, afternoon if it was a late night). However, we wouldn't consider having our agent perform the actual driving of the car in a classical environment. This is because in doing so, our environment loses several of the characteristics we laid forth above - chief among these are that the new environment would become stochastic and continuous.

There are several types of algorithms that allow us to construct a plan. For instance, we briefly examine progression planning, regression planning, and our main topic, partial-order planning. Progression planning is done with a forward state-space search, which is to say that, "we start in the problem's initial state [and consider] sequences of actions until we find a sequence that reaches a goal state" (Russell, 383). This can pose major performance problems because it considers even completely irrelevant actions. As you might guess from its name, regression planning is the opposite - it works backwards from the goal state. This removes the problems associated with examining irrelevant actions, but as Russell notes, it is not without its problems: oftentimes it is not "obvious how to generate a description of the possible predecessors of the set of goal states" (Russell, 384).

What distinguishes partial-order planning from the other two is all in the name - it is not totally-ordered as we see in progression and regression planning. Instead, partial-order planning enables us to "take advantage of problem decomposition." The algorithm "works on several subgoals independently, solves them with several subplans, then combines the subplans" (Russell, 387). In addition, he notes that, "such an approach also has the advantage of flexibility in the order in which it constructs the plan. That is, the planner can work on 'obvious' or 'important' decisions first, rather than being forced to work on steps in chronological order."

We can see a similar phenomenon in application design - we may not choose to work in any chronological order, but instead work on the parts to construct the whole. Whereas some of the most important design decisions are often made at the beginning of a project, when we know the least about it, the prudent designer may choose to work on more obvious decisions, or decide to choose to work on the most important one at the time.

Reference:
Russell, Stuart and Norvig, Peter. Artificial Intelligence: A Modern Approach 2nd Edition. New Jersey: Pearson Education, 2003. ----------------------------------------------

Does that make any sense? Are there areas that could be better explained, or worded? Any input is appreciated.