Answer Set Programming (ASP) is a declarative way to solve search and planning problems: you write rules, and a solver returns the "answer sets," the consistent sets of facts the rules support. Much of its power comes from negation-as-failure, the ability to conclude something because a fact is absent ("the robot may move to cell c unless another robot is known to occupy it"). Fifteen years ago, Bauters and colleagues proved something surprising. Negation-as-failure need not live inside any program. Several definite programs, which contain no negation and can each be evaluated in polynomial time, can recover all of it by querying one another. In that setup, a failed query to another program plays the role of "not." With added "focus" and leader-follower protocols, such systems climb the polynomial hierarchy up to PSPACE. Nobody has ever built one. The two founding papers are explicitly theoretical, and whether the construction runs at practical speed is unknown.
This proposal builds the first working solver for communicating definite programs and tests it on standard multi-agent ASP benchmarks. The key design choice uses a structural fact the theory exposes but never exploits. Each component's local reasoning is monotone and cheap, so all of the hard, non-monotone behaviour sits in the messages between components. That lets us make the messaging inexact on purpose: stale, cached, or budget-limited answers to queries. We then repair the result with an exact, polynomial-time check of every candidate model. The outcome is a solver with a tunable trade-off between convergence speed and completeness that never returns a wrong answer. This is the discrete counterpart of the step-size trade-off familiar from distributed optimization.
Core Claim
Communication-as-negation turns ASP solving into an iterative message-passing process. The only source of error is message inexactness, and every output can be certified cheaply. As a result, the speed–accuracy trade-off that numerical consensus methods face as an "error floor" becomes, in this setting, a trade-off between time and recall, the fraction of true answer sets found. Precision stays exact. We claim that a fixed staleness bound gives fast time-to-first-verified-model but plateaus below full recall, and that a decaying staleness schedule recovers completeness at a sublinear cost. This mirrors constant versus diminishing step sizes. We further claim that on loosely coupled multi-agent problems, which are the ones where monolithic grounding blows up, this decomposition can match or beat a monolithic solver on time-to-first-solution and on peak memory. The second claim may well be false, and testing it honestly is half the point.
What the Prior Work Supplies and Where It Stops
The formal object comes from Communicating Answer Set Programs. That paper defines components that query each other's literals, shows that communicating simple programs simulate normal programs through auxiliary "world" components, and shows that focusing on one component reaches Σ₂ᴾ-hardness. Expressiveness of communication in answer set programming adds multi-focused leader-follower chains that reach PSPACE, covering problems such as STRIPS planning. Both papers treat a query as an abstract oracle. They specify no protocol and no convergence criterion, and they never discuss what happens when queries form cycles. We reuse their semantics and their normal-to-simple translation unchanged. Our contribution is operational and empirical.
The closest system is Distributed Evaluation of Nonmonotonic Multi-context Systems. Its DMCS family evaluates networks of non-monotonic knowledge bases, exchanging belief sets and breaking cycles by guessing. It reports that ring topologies degrade badly because performance hinges on those guesses. This result both motivates and constrains our design. It shows that exact cycle-breaking is the bottleneck, which is why we move inexactness into the message layer. It also warns that a naive implementation of Bauters' scheme will reproduce the same blow-up. DMCS keeps full non-monotonic local solvers and has no mechanism to trade correctness of intermediate states for speed. We do the opposite on both counts.
The trade-off lens comes from distributed optimization. There, fixed penalties or step sizes give fast convergence to a neighbourhood of the solution, while tighter accuracy costs conditioning or iterations. Wei's asynchronous Newton work (A Fast Distributed Asynchronous Newton-Based Optimization Algorithm) shows this for fixed penalties. Fast ADMM Algorithm for Distributed Optimization with Adaptive Penalty adapts per-edge penalties from local residuals. A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications ties rates to oracle inexactness and delay. Each of these assumes continuous and often strongly convex objectives; IDEAL states this restriction explicitly. We do not borrow their algorithms. We borrow their two design ideas, delay-bounded inexact oracles and residual-driven adaptive schedules, and transplant them to a discrete fixpoint process where convexity is meaningless.
Answer Set Networks shows that message passing over a compiled rule graph can beat CPU solvers dramatically at scale. It is centralized on one GPU, and it relies on an exact final model-reduction step. We share the "propagate, then verify" shape but distribute it across semantically separate programs.
Research Program
The solver has three layers. In the local layer, each component is a definite program. Given its current belief about the situated literals it imports, it computes its least model by forward chaining. This step is polynomial, and grounding happens per component. In the message layer, components exchange the literals other components have asked about. A component's unanswered or failed query is read as negation, exactly as in the Bauters semantics. In the verification layer, a candidate global state is accepted only if every component's least model, recomputed under the final messages, reproduces the beliefs it was assumed to hold. This is a polynomial check, so no unverified state is ever returned.
Synchronous message rounds without guessing behave like an alternating fixpoint. They quickly settle a sound partial assignment and leave a residue of undecided situated literals on cycles. Resolving that residue needs search, and search is where the cost explodes. Our inexactness controls act only on this residue. The staleness bound τ says how many rounds a component may act on cached answers before re-querying. The guess budget sets how many undecided literals are branched on per round. An adaptive rule, in the spirit of residual-driven penalties, tightens τ on edges whose messages keep flipping.
We build two front ends. The first automatically translates normal programs into communicating simple programs using the published construction. This tests the theory directly and lets us measure the size blow-up from auxiliary world components. The second takes a hand-structured per-agent decomposition, with one component per robot plus a coordination component. This tests practical usefulness. Focused communication is implemented as leader-side filtering of candidate models. Multi-focused chains are a stretch goal, targeted at planning instances.
Baselines
The naive reference point is a faithful, exact, synchronous implementation of the Bauters semantics: no caching, with full sub-search on each query. This shows what the theory costs when run literally. We expect it to be the cheapest to beat, and its failure modes show where effort goes.
The strongest competitor is the monolithic clingo solver run on the original normal-program encoding. It is the engine behind the strongest results in this file. On the MAPF warehouse benchmark, Solving Sum-of-Costs Multi-Agent Pathfinding with Answer-Set Programming reports that its ASP-USC variant held a 100% success rate with up to 14 agents, where EPEA* and other baselines failed beyond 10. Its cost-to-go pruning cut solving time by a factor of 1.74. On asprilo, Experimenting with robotic intra-logistics domains reports frequent 1800 s timeouts on the larger domains, but gives no tabular numbers. We will run clingo with those authors' best published encodings, including CG pruning for MAPF and the direct encoding for domain M. It gets the same wall-clock limit, the same total CPU cores (one solving thread per core, versus one core per component for us), and the same memory cap. Beating it means one of two things on a declared instance family: higher success rate within the cutoff at agent counts beyond 14 on the warehouse layout, or lower median time-to-first-verified-model with peak memory below its grounding footprint. Losing on small instances is expected and will be reported.
The distributed competitor is DMCSOPT from Distributed Evaluation of Nonmonotonic Multi-context Systems. It runs on that paper's synthetic tree and ring topologies, with the same component contents encoded as contexts. No numbers for those benchmarks are reported on Lacuna, so we will rerun it ourselves. Beating it means a lower runtime on rings, which is its documented weak case, without losing on trees.
Three ablations isolate our ingredients. Exact messaging with verification separates the effect of inexactness from the effect of decomposition. Components that keep local negation-as-failure, each solved by clingo, isolate whether restricting components to definite programs helps, through cheap local fixpoints, or hurts, through extra communication. A continuous variant replaces boolean messages with damped truth values in [0,1]. It is run with constant and diminishing damping, then rounded and verified, to test whether a numerical relaxation beats discrete staleness.
Why not just…?
Why not just run clingo on the original program? This is the real threat. On compact encodings, conflict-driven learning will likely dominate any message-passing scheme, and we expect to lose there. The case for decomposition rests on documented monolithic pain points: grounding becoming prohibitive at 512×512 grids in the MAPF paper, and frequent timeouts on asprilo's combined domains. The head-to-head experiment below decides whether those pain points are where communication helps. If it never helps, we publish the negative result together with the measured cost of the translation. That still closes the validation gap the founding papers left open.
Why not just use DMCS, which already does distributed non-monotonic reasoning? DMCS answers a different question. Its contexts keep full non-monotonic solvers, and its cycle handling is exact guessing, which its own evaluation identifies as the bottleneck on rings. Our ring-topology comparison with matched contents tests directly whether moving all non-monotonicity into an inexact, verified message layer removes that bottleneck.
Why not just relax truth values to continuous variables and run ADMM-style consensus? The convergence guarantees of ADMM and IDEAL rest on convexity, which logic constraints violate. Rounding a non-convex relaxation offers no soundness or completeness. We still include a damped continuous variant as an ablation arm rather than dismissing it. If it matches discrete staleness in recall-versus-time, the simpler numerical story wins and we will say so.
Why not just compile to Answer Set Networks on a GPU? ASN reports its own memory bottleneck when choices proliferate, and it requires the whole ground program on one device. Where the instance fits, ASN is a fair speed reference. We will report it on the shared-memory instances to show whether the gains come from distribution or simply from message passing.
Proposed Experiments and Decisive Checks
We use four benchmark families. The first is the Bauters translation applied to normal-program encodings of MAPF on 20×20 grids with 10% obstacles and on the warehouse layout, measuring translation size and solve time. The second is per-robot decompositions of the same MAPF instances and of asprilo domains M, A, B and C. The third is the DMCS synthetic tree and ring topologies. The fourth is randomly generated communicating programs with controlled cycle density, which let us vary the size of the undecided residue directly.
We report four metrics. Time-to-first-verified-model and success rate within the cutoff measure speed. Recall at time t, against answer sets enumerated offline by clingo on instances small enough to enumerate, measures completeness. Peak memory and total messages measure resource cost.
The first decisive check is whether the speed–recall curve has the predicted shape. Fixed τ should give a fast rise and a recall plateau that grows with τ. Decaying τ should reach full recall more slowly. If recall does not depend on τ, the trade-off framing is wrong and inexactness is merely noise. The second check is whether an instance family exists, which we expect to be loosely coupled and large-grounding warehouse MAPF, where the decomposed solver beats clingo past the 14-agent mark on success rate or memory. The third check is whether the automatic translation's world-component blow-up is small enough to be usable. If it is not, the expressiveness result is practically inert, and only hand decompositions matter. That would be the most important empirical correction to the theory.
References
- Communicating Answer Set Programs
- Expressiveness of communication in answer set programming
- Distributed Evaluation of Nonmonotonic Multi-context Systems
- A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
- Fast ADMM Algorithm for Distributed Optimization with Adaptive Penalty
- A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
- IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
- Answer Set Networks: Casting Answer Set Programming into Deep Learning
- Solving Sum-of-Costs Multi-Agent Pathfinding with Answer-Set Programming
- Experimenting with robotic intra-logistics domains