Discussion about Abductive logic programming vs Answer Set Programming

Question

I am looking to clarify the some things about abductive logic programming vs. Answer set programming.

I with some classmates are creating a game. In this game there are "heroes" (special npcs). The heroes have goals and behaviors.

(All of this is story driven) What I would like the heroes to react to a player's or another hero's action then decide what to do from there.

A teacher told us about a paper called "RoleModel: Towards a Formal Model of Dramatic Roles for Story Generation" it explains abductive logic programming. Through my research I found Answer Set Programming.

Question: Is there a difference between the ALP paradigm and the ASP paradigm? Is one better then other for my purposes? Is there another option?

Answer 1

You're really asking three questions. I'm not qualified to answer any of them, but I'm going to take a crack at it anyway.

1. Is there a difference between the ALP paradigm and the ASP paradigm?

Yes. ASP is a paradigm in which your search problem is made into a model that can be handed over to different solvers. The paper you reference says in section 4.1 that they follow the ASP paradigm and use deductive and abductive reasoning concurrently. So you can see that abductive and deductive are acting as tactical solvers inside a larger ASP process.

Based on what I read on Wikipedia, this is a good approach because abductive reasoning is about providing explanations rather than logical consequences. I could see how you would like that in story generation; "Mary hates Sue, therefore Mary killed Sue" is a deduction but "Mary hates Sue, because Sue ran over her dog" seems more like an abduction, based on my cursory reading. You would want both to flesh out a story, or it's going to get pretty dull.

2. Is one better then other for my purposes?

All you've said about your purposes is that you're making a game. I am not a game developer but I feel fairly confident is assuring you that nothing like this is used in a typical game. Game AI is its own whole field. I would be shocked if any of this stuff was used in a major game.

That said, RoleModel shows you can do it, and it uses both, with ASP controlling a combined ALP/DLP process. It seems likely to me that the two are pretty separable and since one can use the other, I would guess they are not in strict opposition to each other. If it worked for RoleModel game, the real question isn't can it be done, is it a good idea, but is it a good fit for what you're trying to accomplish? If you're trying to build an action-shooter, I would wager that other, simpler approaches will work out better; if you're trying to build a rich RPG, maybe it will be OK.

3. Is there another option?

Probably. I would investigate AI for games. The priorities are different enough that I would expect their literature starts in completely different places and goes in radically different directions, but I could be mistaken.

Answer 2

Any logic programming that supports hypothetical reasoning, can support ALP. Since ASP supports hypothetical reasoning, it can also support ALP. Hypothetical reasoning is a search where temporarily facts are assumed.

With standard ISO core Prolog we can simulate assuming a fact by the following code. The code leaves a choice point and doesn't work correctly if there is a cut involved, this is why specialized systems are nevertheless needed:

assumez(P) :- assertz(P).
assumez(P) :- retract(P), fail.

We can now solve the following abductive problem:

abducible :- (assumez(amount(glucose,low));assumez(amount(glucose,medium))),
         (assumez(amount(lactose,medium));assumez(amount(lactose,hi))).

feed(lactose) :- amount(glucose,low), amount(lactose,hi).
feed(lactose) :- amount(glucose,medium), amount(lactose,medium).

A possible query runs as follows:

?- abducible, feed(lactose), listing(amount/2).

amount(glucose, low).
amount(lactose, hi).
Yes;

amount(glucose, medium).
amount(lactose, medium).
Yes ;

No

The above solution uses backward chaining. A forward chaining solution, and something that is closer to ASP choice operators, can be provided as well. The choice operator in ASP will do the hypothetical variants, we only use (;)/2 as a choice operator:

:- use_module(library(minimal/delta)).

:- multifile abducible/0.
:- dynamic abducible/0, amount/2, feed/1.
:- forward feed/2.

post(amount(glucose,low));post(aamount(glucose,medium)) <= posted(abducible).
post(amount(lactose,medium));post(amount(lactose,hi)) <= posted(abducible).

post(feed(lactose)) <= posted(amount(glucose,low)), posted(amount(lactose,hi)).
post(feed(lactose)) <= posted(amount(glucose,medium)), posted(amount(lactose,medium)).

A possible query runs as follows:

?- post(abducible), feed(lactose), listing(amount/2).

amount(glucose, low).
amount(lactose, hi).
Yes ;

amount(glucose, medium).
amount(lactose, medium).
Yes ;

No

Answer 3

FYI: As has been mentioned, some systems for performing inductive and abductive logic programming use ASP systems. A free open source example is XHAIL https://github.com/stefano-bragaglia/XHAIL

There is also a paper describing this version:

Bragaglia S., Ray O. (2015) Nonmonotonic Learning in Large Biological Networks. In: Davis J., Ramon J. (eds) Inductive Logic Programming. Lecture Notes in Computer Science, vol 9046. Springer, Cham

It could be argued that Sherlock Holmes is actually famous for abductive reasoning not deductive reasoning... so I think there is some interesting scope for a detective game using ALP. :).