  In Probabilistic Logic Programming (PLP) the most commonly studied inference
task is to compute the marginal probability of a query given a program. In this
paper, we consider two other important tasks in the PLP setting: the
Maximum-A-Posteriori (MAP) inference task, which determines the most likely
values for a subset of the random variables given evidence on other variables,
and the Most Probable Explanation (MPE) task, the instance of MAP where the
query variables are the complement of the evidence variables. We present a
novel algorithm, included in the PITA reasoner, which tackles these tasks by
representing each problem as a Binary Decision Diagram and applying a dynamic
programming procedure on it. We compare our algorithm with the version of
ProbLog that admits annotated disjunctions and can perform MAP and MPE
inference. Experiments on several synthetic datasets show that PITA outperforms
ProbLog in many cases.
