TY - GEN

T1 - Abductive inference in probabilistic logic programs

AU - Simari, Gerardo I.

AU - Subrahmanian, V. S.

PY - 2010

Y1 - 2010

N2 - Action-probabilistic logic programs (ap-programs) are a class of probabilistic logic programs that have been extensively used during the last few years for modeling behaviors of entities. Rules in ap-programs have the form "If the environment in which entity E operates satisfies certain conditions, then the probability that E will take some action A is between L and U". Given an ap-program, we are interested in trying to change the environment, subject to some constraints, so that the probability that entity E takes some action (or combination of actions) is maximized. This is called the Basic Probabilistic Logic Abduction Problem (Basic PLAP). We first formally define and study the complexity of Basic PLAP and then provide an exact (exponential) algorithm to solve it, followed by more efficient algorithms for specific subclasses of the problem. We also develop appropriate heuristics to solve Basic PLAP efficiently.

AB - Action-probabilistic logic programs (ap-programs) are a class of probabilistic logic programs that have been extensively used during the last few years for modeling behaviors of entities. Rules in ap-programs have the form "If the environment in which entity E operates satisfies certain conditions, then the probability that E will take some action A is between L and U". Given an ap-program, we are interested in trying to change the environment, subject to some constraints, so that the probability that entity E takes some action (or combination of actions) is maximized. This is called the Basic Probabilistic Logic Abduction Problem (Basic PLAP). We first formally define and study the complexity of Basic PLAP and then provide an exact (exponential) algorithm to solve it, followed by more efficient algorithms for specific subclasses of the problem. We also develop appropriate heuristics to solve Basic PLAP efficiently.

UR - http://www.scopus.com/inward/record.url?scp=84880233664&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880233664&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICLP.2010.192

DO - 10.4230/LIPIcs.ICLP.2010.192

M3 - Conference contribution

AN - SCOPUS:84880233664

SN - 9783939897170

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 192

EP - 201

BT - Technical Communications of the 26th International Conference on Logic Programming, ICLP 2010

T2 - 26th International Conference on Logic Programming, ICLP 2010

Y2 - 16 July 2010 through 19 July 2010

ER -