Combining uncertainty and optimization in logic-based AI

Logic-based reasoning systems often face two different questions: what might happen, and which solutions best satisfy a set of preferences? The preprint “Optimal Probabilistic Answer Set Programming: Complexity and Implementations” brings these questions together. Its authors introduce optimal Probabilistic Answer Set Programming, or optPASP, define its mathematical meaning, analyze its computational difficulty and test implementations. The arXiv listing states that the work has been accepted for publication in Theory and Practice of Logic Programming.

Answer Set Programming, or ASP, describes a problem through logical rules. Its solutions, called answer sets, represent combinations of statements consistent with the program’s semantics. Probabilistic ASP adds facts with associated probabilities. Each combination of included and excluded probabilistic facts defines a possible world, within which the logical program may still have several answer sets. World probabilities are calculated by multiplying the probabilities of included facts and the complementary probabilities of excluded facts.

The researchers use credal semantics, which does not prescribe how a world’s probability should be divided among its answer sets. Instead, a query receives lower and upper probability bounds. A world contributes to the lower bound when the query holds in every answer set, and to the upper bound when it holds in at least one. These bounds therefore describe uncertainty left unresolved by the model, rather than sampling error around an estimate.

The extension adds weak constraints: preferences that assign costs to solutions without simply prohibiting them. Costs can have priority levels, so one objective takes precedence over another. Within each world, optPASP retains only answer sets that are optimal under those preferences. It then calculates probability bounds using those optimal solutions. World probabilities remain unchanged. Restricting the solutions considered can raise the lower bound and lower the upper bound, although the bounds need not become equal.

This order of operations matters. The framework optimizes solutions separately within each uncertain world and then combines their probability contributions. It is not the same as choosing one decision that maximizes expected utility across all worlds. The paper also studies most probable explanation, or MPE: finding the highest-probability selection of uncertain facts whose optimal solutions support specified evidence. The “brave” version requires support in at least one optimal solution; the “cautious” version requires support in all of them.

For the propositional program fragment studied, the authors establish that both optimal MPE decision problems are Sigma-P-2-complete. Adding preferences raises the complexity classification of brave MPE from NP-complete, while cautious MPE retains its existing classification. Probability-threshold inference remains PP-with-an-NP-oracle complete, as in plain PASP. These are worst-case classifications, not assurances of practical speed.

The implementations take different computational routes. An enumeration baseline examines every selection of probabilistic facts and uses the clingo solver to obtain optimal answer sets. A knowledge-compilation implementation built on aspmc converts the program into an arithmetic circuit. Its two-level algebraic model-counting calculation identifies optimal solutions within worlds and combines their probability contributions across worlds. For MPE, the researchers also implement encodings in quantified ASP, evaluated using the casper system.

The evaluation uses generated, real-world-inspired problems involving reviewer assignment, patient scheduling with uncertain attendance, and viral marketing through social networks. Probabilities are randomly assigned, with fixed seeds for reproducibility. Experiments run on a 3.7 GHz machine with 32 GB of RAM and a one-hour limit per instance. Enumeration performs well on some small problems, but compilation generally handles larger inference instances. With ten papers, aspmc handles seven reviewers; enumeration solves none of the tested ten-paper instances. In viral-marketing inference, aspmc solves the ten-person instance in 338.1 seconds, while enumeration already fails at five people.

Quantified ASP handles larger MPE examples: the authors report brave MPE for 200 reviewers within 800 seconds, and scheduling examples with 100 people within 100 seconds for brave MPE and 40 seconds for cautious MPE. Nevertheless, scalability remains limited. Enumeration reaches timeouts, while aspmc encounters compilation errors that the authors suggest may reflect excessive memory requirements. The framework also assumes every world has an answer set and restricts the logical program fragment considered. Because the benchmarks are generated rather than operational deployments, they demonstrate computational feasibility in the tested settings, not improvements in actual clinical, reviewing or marketing outcomes.