🚀 go-pugleaf

[Apologies if you've seen this before -- I suffer from whimsical network
connections.]

In article <EIVERSON.89Oct30145311@hades.nmsu.edu> eiverson@nmsu.edu (Eric Iverson) writes:
>This may be a baby problem, but here goes:  Is there any possible way
>to skip levels while backtracking?  By this I mean that if I run into
>a problem at level 4 and realize that level 2 is causing the problem,
>is there anyway that I can go directly to level 2 without having level
>3 exhaustively fail first?

A very interesting question. There are lots of different ways of doing
it. When I was faced with this problem (in a robot assembly planner) a
crucial requirement of the implementation was that it be FAST, which
unfortunately ruled out - so I concluded - any elegant solutions. 

The solution I adopted is based on carrying two items of info down the
recursion stack: the recursion level number, and a simple identification
of the item processed (the part being assembled) at that level. When a
failure occurs (damn I can't fit this part in) the problem is analysed
(it's this other part which is in the way of my fingers, which was put
there at level N).  The part identity, the level number I wish to
backtrack to, and the fact that there is smart backtracking going on,
are all separately asserted.  The clause then fails. All relevant
clauses first check whether there is smart backtracking in progress (a
simple check for fact existence).  If not, normal processing. If so, and
this is not the right level, fail.  This unravels recursion back to the
right level in little more fails than levels to jump. Once at the right
level, the clauses then start looking for the right item identity (i.e.,
failing until it is found).  As soon as this is found, all the
backtracking switches are reset to normal, and processing continues as
normal, just as though normal backtracking had wound its pedestrian way
back to this point.  The overhead on normal processing is a little extra
luggage in the parameters passed down the recursion, plus the special
backtracking smartness disjoined behind a fact existence test at the
start of the relevant clauses; in practice a negligible overhead in this
application.

It's fast, and disgusting. I would be very pleased if someone could
suggest a neater way of doing this, which carried at worst a minor time
penalty. I would also be very pleased if someone could suggest a much
faster way of solving this problem, regardless of how disgusting it was!

The assembly planner consists of about 2,000 active (non-comment) lines
of POPLOG PROLOG, and can plan the assembly of a soma cube in all
possible ways (1440 - 240x6 - remember the asymmetry of gravity), in a
few weeks on a Sun3. Hence the great interest in speed.

-- 
Chris Malcolm    cam@uk.ac.ed.aipna   031 667 1011 x2550
Department of Artificial Intelligence, Edinburgh University
5 Forrest Hill, Edinburgh, EH1 2QL, UK