Optimal planning with incrementally tabled abductive logic programming

Question

I'd like to use abductive logic programming to find optimal plans. Exhaustively searching the space of plans would be impractical but there are ordering heuristics that, in ordinary logic programming, would be used to represent facts (ground predicates) as sorted lists. Sorted lists can, of course, be recast in predicate form as facts (ground predicates) with an ordering predicate -- and it is in this form that I would prefer to work given that abducibles are predicates.

In this form, I'd like to search the ground predicates with priority accorded to the their (respective) ordering predicate(s), and terminate at the first solution as it is provable that any other solutions would be less optimal.

I understand that this would require, at the very least, tabled logic programming. Fortunately tabling is now widely supported. However, it may also require incremental tabling as abducibles are asserted and retracted during abduction -- which would limit it to XSB, AFAIK.

How can one tell the Prolog engine to use an ordering predicate to search ground terms?

Also, is incremental tabling necessary to make this practical?

Answer 1

I and my PhD student Ari Saptawijaya,ari.saptawijaya@gmail.com, have been publishing on tabled abduction, implemented in XSB, and you might like to see our publications, available for download at my home page (where you can find our latest paper, accepted at ICLP'14). At present we are combining tabled abduction with tabled incremental updating of fluents, where we abduce actions and incrementally propagate their effects on fluents. One general concept we use is contextual abduction, whereby abductive may be usable from one context to another, or reject worse attempted solutions. The issues there are quite technical and not susceptible to explaining here. I suggest you glance at our papers and come back to us, after seeing how you are attempting might benefit from our stance. I also advise you to look at the tabling chapters of the XSB user's manual, available at Sourceforge. Professor David Warren, the main architect of XSB Prolog may help you too. Best wishes Luis Moniz Pereira

Answer 2

Tabling, at least in XSB, follows (by default) a scheduling strategy known as local scheduling. This means that answers to a goal are not returned as they are derived (like in the usual Prolog, without tabling), but only when the table of that goal has been completed. For this reason, the use of tabling to help return (and terminate at) the first solution only (as in your case) may not be appropriate. One can nevertheless opt for batched scheduling of XSB tabling, so the answers are returned as soon as they are derived. But this option can be only be set during the XSB installation, and not in the level of predicate.

Alternatively, XSB provides tries data structure that can be used to store facts. It can be used to simulate batched scheduling (returning an answer as soon as it is derived) in the presence of the default local scheduling. This technique is used for example in computing dual rules by-need. The idea is to compute and store in a trie the solutions one by one according to the given ordering.

These strategies, and their (dis)advantages, along with tries are discussed in XSB first manual.

With respect to the use of incremental tabling, it can certainly be useful if the asserted or retracted abducibles affect other tabled predicates; the latter predicates should then be incrementally tabled and abducibles should be declared incrementally dynamic (not just simply dynamic predicates). So doing, the tabled predicates will correctly reflect such updates.