eiverson@nmsu.edu (Eric Iverson) (10/31/89)
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? I have some ideas of how to solve the problem, but am interested in other peoples opinions. -Eric Iverson
ok@cs.mu.oz.au (Richard O'Keefe) (10/31/89)
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? Look in the literature under the heading "intelligent backtracking". It may be possible to recast your problem so that you don't need it. Why not tell us what your real problem is?
cam@aipna.ed.ac.uk (Chris Malcolm) (11/09/89)
[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
ted@nmsu.edu (Ted Dunning) (11/11/89)
In article <1593@aipna.ed.ac.uk> cam@aipna.ed.ac.uk (Chris Malcolm) writes: Path: opus!lanl!cmcl2!nrl-cmf!think!ames!claris!apple!usc!cs.utexas.edu!uunet!mcsun!ukc!edcastle!aipna!cam From: cam@aipna.ed.ac.uk (Chris Malcolm) Newsgroups: comp.lang.prolog Date: 8 Nov 89 17:03:02 GMT References: <EIVERSON.89Oct30145311@hades.nmsu.edu> 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.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. ... not so firmly, if you have some special help. prolog dialects such as sicstus and nu allow a goal to be frozen pending the instantiation of a variable. this facility can be used to implement a sort of instantaneous failure on a higher level at the cost of handing the variable to be instantiated down to the descendants. for example, parent :- set_failure_point(X), first_child(X), write(didnt_backtrack),nl. parent :- write(back_tracked), nl. first_child(X) :- second_child(X). second_child(X) :- write(deep), nl, cause_failure(X), write(not_here), nl. set_failure_point(X) :- freeze(X,X=1). cause_failure(2).
lee@munnari.oz.au (Lee Naish) (11/12/89)
In article <TED.89Nov10212545@haywire.nmsu.edu> ted@nmsu.edu (Ted Dunning) writes: >prolog dialects such as sicstus and nu allow a goal to be frozen >pending the instantiation of a variable. this facility can be used to >implement a sort of instantaneous failure on a higher level at the >cost of handing the variable to be instantiated down to the >descendants. for example, > > >parent :- set_failure_point(X), first_child(X), write(didnt_backtrack),nl. >parent :- write(back_tracked), nl. > >first_child(X) :- second_child(X). > >second_child(X) :- write(deep), nl, cause_failure(X), write(not_here), nl. > > >set_failure_point(X) :- freeze(X,X=1). >cause_failure(2). The call to cause_failure binds X to 2, then the frozen goal X=1 is woken up and fails. However, the system does not immediately backtrack to where set_failure_point was called. When cause_failure is backtracked into it fails, undoing the binding of X and restoring the frozen goal. Backtracking then continues in the normal way. The need for intelligent backtracking can sometimes be avoided by reordering calls. Coroutining gives more flexibility in doing this. However, current implementations of coroutining are not a general solution to the intelligent backtracking problem. Several years ago I suggested a form of coroutining which behaved like a simple intelligent backtracking scheme (so simple it saves no extra information during forward execution). I thought of implementing it on top of MU-Prolog but never got around to it. It is described in "Heterogeneous SLD Resolution", JLP, 1:4, Dec 1984. lee