I’ll try to make clearer what kind of s/w I’m trying to develop.

While it’s presently in the "messy" phase, it has been pleasing to actually get some useful work out of it, in what’s been my first real-world testing.

(As ash has indicdated elsewhere, there’s a world of diff between getting a robot to putter around a virtual world and getting it to putter around a table-top in actual solid real reality .

First, some outline of the simple planner I’m using.

 Originally culled from some conference proceeding when I was in love with theorem proving and (later) Prolog, the David Warren "Warplan" system was never documented anywhere I could find. Even recent Googles don’t seem to turn up anything. Ah well, it was back in the 70s, so what can I expect?

The basic idea is the planner keeps a set of facts in an internal database. In the case of Warplan, the facts are just Prolog clauses (i.e. may be Prolog facts or Prolog clauses).

Each of these database facts essentially represent the state of some possibly partially-completed operation or something else that is beleived about the world.

The planning is specified by describing what database actions occur whenever certain operations are executed (i.e. "added to the end of or somewhere in the middle of the plan"). The database actions are things like add (when an operation is executed, what facts are added to the database) and del (when an operation is executed, what facts are deleted from the database) but also include "permanent" database items like always (i.e. things that are always presumed true in the world and, hence, present in the database) and imposs (things that are presumed  can never become true in the world and should never end up being added to the database).

You describe any particular state of the world (e.g. the start state or the goal state) with given items.

But perhaps more important than those kinds of descriptions are the can rules  that describe pre-conditions for issuing certain operations. E.g. if a robot can not lift more than 1 block at a time, there should be a can rule indicating that the pickup operation can not execute on a block X unless there is a fact in the database like clear(X).

Don’t worry — I’m going to start blogging examples,  and will eventually add in the Prolog source code for the planner and compiler tools as well.

Now what "operations" are, how many and what kinds of parameters they take, and what they actually do if (e.g.) executed as a Prolog or MBasic program is purely upto the programmer.

Everything is very flexible, which is why (I guess) this is all so vague.

Example 1: An old 3-block puzzle.

Anyway, here’s my first example.

—————————————–

add( on(U,W), move(U,V,W) ).

add( clear(V), move(U,V,W) ).

del( on(U,Z), move(U,V,W) ).

del( clear(W), move(U,V,W) ).

can( move(U,V,floor),on(U,V) & not_equal(V,floor) & clear(U) ).

can( move(U,V,W), clear(W) & on(U,V) & not_equal(V,W) & clear(U) ).

imposs( on(X,Y) & clear(Y) ).

imposs( on(X,Y) & on(X,Z) & not_equal(Y,Z) ).

imposs( on(X,X) ).

given( start, on(a,floor) ).

given( start, on(b,floor) ).

given( start, on(c,a) ).

given( start, clear(b) ).

given( start, clear(c) ).

 —————————————-

(Don’t worry about the odd oder of params — this was designed for Prolog efficiency and not human-readability :) . 

The example describes an old puzzle where you have a 2-block stack but want to change one of the blocks in the stack. In some planners this is know to cause runtime loops.

To see whether we’re on the same page, try to translate some of the imposs or can rules. E.g. one rule describes it’s not possible to add on(X,X) to the runtime database (in Prolog things starting with capital letters are variables — things starting with lower-case letters are "constants" or what the logic folks might call "individuals"). Another rule says "you can’t have 2 blocks on top of another block", and there’s also "a block can’t both have something on it and also be marked clear". 

Given the above, the planner can find and execute the set of operations that begin in one state (e.g. the start state, described above) and reach another goal state.

———————————————

:- plans( on(a,b) & on(b,c), start ).

———————————

(To execute something in Prolog you usually need to put the magic :- "turnstyle" symbol at the start of the line; otherwise it’s just a description that sits there taking up memory :) . 

The above says we want to start at start and end up in a state where the runtime database ("the world") has at least the facts on(a,b) and on(b,c).  Tell me what sequence of operations can do that.

Normally the planner will just print out the list of operations needed to reach the goal, but various options allow operations or plans to be executed as Prolog programs, or otherwise post-processed (e.g. translated into MBasic statements and uploaded over a serial line .

And also note — if there is more than one set of operations ("plan") to obtain a goal, it’s possible to cause a backtrack and either list all such plans or post-process them and ensure they have a particular property before they’re subsequently listed/executed.

In the simplest Warplan setup, the system will just print out the "solution" to the above as:

———————————

start;

move(c, a, floor);

move(a, floor, b);

move(b, floor, c).

———————————

Meaning "take c from off the top of a and put it on the floor then move a from the floor and put it on b, then take b and put it on c".

I have a whole heap of problems solved in this style, so I’ll try to type them up neatly and blog them.

I’ll eventually get to the point of spitting out some MBasic or what-not to show a planner can be a compiler, partial evaluator and source-to-source translator — or anything else a robot might need to self-program.