Policy Analytics Generation using Action Probabilistic Logic Programs

GERARDO I. SIMARI; JOHN P. DICKERSON; V.S. SUBRAHMANIAN

Handbook of Computational Approaches to Counterterrorism

SPRINGER

Lugar: New York - USA; Año: 2012; p. 515 - 542

During the last few years, action-probabilistic logic programs (ap-programs) have been extensively used 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". In this work, we are interested in the problem of given an ap-program, 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. We call this the Basic Abductive Query Answering Problem (BAQA). We first formally define BAQA, and then go on to study specific subclasses of the problem; we also develop heuristics to solve BAQA efficiently. The second problem, called the Cost-based Query Answering (CBQA) problem, checks to see if there is some way of achieving a desired action (or set of actions) with a probability exceeding a threshold, given certain costs. We formally define CBQA, and then go on to propose an efficient algorithm for a specific subclass of ap-programs that builds on the work for BAQA. Finally, we also present algorithms for parallel solutions for CBQA. We conclude with a report on experimental evaluations performed over prototype implementations of the algorithms developed for CBQA.