Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!usc!cs.utexas.edu!uunet!mcsun!ukc!edcastle!aipna!cam From: cam@aipna.ed.ac.uk (Chris Malcolm) Newsgroups: comp.lang.prolog Subject: Re: non-sequential recursion Message-ID: <1593@aipna.ed.ac.uk> Date: 8 Nov 89 17:03:02 GMT References: Reply-To: cam@aipna.ed.ac.uk (Chris Malcolm) Distribution: comp Organization: Dept of AI, Edinburgh University, UK. Lines: 51 [Apologies if you've seen this before -- I suffer from whimsical network connections.] In article 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