Counting Loops in the Scope Cover: When Locally Consistent Plans Glue Together

Large planners and temporal reasoners stay tractable by splitting a problem into overlapping pieces. One piece might be all the plumber's actions, another everything on the third floor, another one mission's subtasks. Each piece is solved on its own, and the solver then patches the pieces together where they share actions. The patching step is the weak point. In Lansky's GEMPLAN, a step called "completion" re-checks shared constraints across overlapping regions, and its cost grows until it eats the savings once regions overlap densely. No one has a criterion for which overlaps actually need re-checking. This note proposes a simple, testable criterion taken from algebraic topology. Build the nerve of the decomposition: a graph with one node per scope, an edge for each pair of scopes that share actions or variables, and a filled triangle for each triple that shares something. Locally consistent pieces can fail to glue only around loops in this nerve that are not filled in.

The prediction follows directly. The extra checking needed for global consistency should scale with the number of independent unfilled loops, the first Betti number $b_1$ of the nerve. It should not scale with how much the scopes overlap. Where that holds, completion can be replaced by a targeted check around a basis of nerve loops. The topology serves as a lens, not as machinery. Homotopy theorists ask when a structure survives localization, and their answers take the form "if the object is connected enough." We ask the same question of scope-based localization and expect an answer of the same shape.

Core Claim

Fix a constraint problem and a cover of its variables by scopes $U_1,\dots,U_k$. Let $N$ be the nerve described above, and let $b_1(N)$ count its independent loops that are not bounded by filled triangles. Our claim has two parts.

The first part concerns difference constraints, the Simple Temporal Problems (STPs) used in temporal planning. Suppose each scope is consistent on its own and each pairwise overlap agrees. Then every remaining inconsistency is a negative cycle whose image in $N$ is a non-trivial loop. Checking consistency therefore reduces to composing the boundary constraints around each of $b_1(N)$ basis loops. We call the result of that composition the loop's holonomy: the net constraint picked up by going once around the loop.

The second part concerns disjunctive and plan-level constraints, where the holonomy is a relation rather than a number. Here the loop check remains necessary. We conjecture it is also sufficient for row-convex constraint classes, and we will measure how often it fails outside that class.

The STP part matters less than it sounds. Multiagent Simple Temporal Problem: The Arc-Consistency Approach shows that arc-consistency already decides STPs, whatever their structure. For pure STPs, nerve topology is therefore of no algorithmic use. The STP case is our sanity check. The real target is the disjunctive and plan-constraint regime, which that paper explicitly leaves open.

How Direction 1 Shapes the Idea

Several results on homotopical localization set the template for the kind of theorem we want.

Homotopical localizations of module spectra shows that localizing a ring spectrum keeps its multiplication only under a connectivity hypothesis, or when the localization commutes with suspension. Without the hypothesis, low-dimensional distortion corrupts the algebra. Nilpotent types and fracture squares in homotopy type theory reconstructs a global object from its localized pieces by gluing them along shared data, but only for truncated types. Localization of algebras over coloured operads handles multi-sorted structures, such as a ring together with its modules, and requires the localization to be closed under the monoidal product.

All three papers motivate the form of our result: local-to-global preservation holds under a stated connectivity or finiteness condition. They do not supply an algorithm. None of them touches discrete constraints or complexity, and we do not claim to import a theorem from them.

The analog of their truncation hypothesis is concrete in our setting. On finite domains, composing relations around a loop stabilizes after finitely many passes. With unbounded metric horizons it may not, and that is exactly where we expect the guarantee to break. The research file flags this tension between truncation requirements and unbounded temporal horizons as an unexamined gap.

Research Program

The work has three parts.

Theory. We first prove the STP statement: every cross-scope negative cycle projects onto a non-null-homotopic loop of $N$, and filled triangles in $N$ kill the corresponding loops. We then try to extend the statement to connected row-convex relations, where relational composition behaves well. Where it fails, we characterize the counterexamples.

Algorithm. We will build "loop completion." It computes $N$ from any scope generator, including Lansky and Getoor's LOC generator as described in Scope and Abstraction: Two Criteria for Localized Planning and the regions of Localized Search for Multiagent Planning. It then extracts a cycle basis relative to the filled triangles and verifies holonomy around each basis loop. When a region changes, it re-verifies only the basis loops that pass through that region. This last rule replaces GEMPLAN's blanket reincarnation and completion.

Diagnosis. We will test whether $b_1(N)$ predicts completion overhead and local-only failure rate better than overlap volume does. Overlap volume means the number of shared actions or variables. This is the cheapest falsifiable piece of the program, and we will run it first.

Baselines

The naive reference point is local-only solving. Each scope is made consistent independently and the pieces are concatenated, with only pairwise overlap agreement checked. It costs least, and its failure rate on random overlapping covers is the quantity our theory predicts. It runs on identical instances and scope covers.

The flat global solver is the second baseline: path consistency over the whole network for STPs, and a monolithic constraint search for plans. It defines ground truth for global consistency. Temporal Milestones in HTNs reports that its localized DelayedPropagation algorithm achieves a quadratic speedup over this baseline on the Air Tasking Order domain, with up to 100 missions of roughly 58 tasks each. That gives a scale anchor.

The strongest existing competitor differs by regime. For pure STPs it is ACSTP/DisACSTP from Multiagent Simple Temporal Problem: The Arc-Consistency Approach. That paper reports ACSTP 100 to 1,000 times faster than $P^3C$ centrally and 5 to 12 times faster on the New York road network, and DisACSTP faster than D$\Delta$PPC by factors of 2 to 30. We do not expect to beat it on pure STPs. Matching its decisions at comparable cost would count as a pass for the sanity check.

For plan-level and disjunctive constraints, the strongest competitor is GEMPLAN-style full completion over the same regions. Localized Search for Multiagent Planning reports that localized configurations achieve "greater than 50%" speedups over non-localized search on building-construction problems of 49 to 97 actions. That paper also says completion cost is the overhead that grows with overlap. For COLLAGE's scope-based localization, no reported numeric runtime was found on Lacuna; results there are shown only graphically. Beating full completion means matching its global-consistency rate, measured against flat-solver ground truth, while doing fewer constraint re-checks. We expect the gap to widen with overlap volume at fixed $b_1$.

All methods share the same scope covers, the same underlying propagator, the same time budget per instance, and the same tuning budget for any heuristics.

Two ablations isolate the key ingredient. The first ignores filled triangles and checks every graph cycle, which tests whether the higher-order structure of the nerve earns its place. The second checks a random set of loops of the same size as the cycle basis, which tests whether the specific basis matters or merely the amount of checking.

Why not just…?

Why not just use arc-consistency, which already decides STPs locally? For pure STPs this objection is correct. Multiagent Simple Temporal Problem: The Arc-Consistency Approach makes nerve topology algorithmically unnecessary there. That is why the STP experiment serves only to validate the predicted cycle–loop correspondence. The algorithmic contribution is confined to disjunctive temporal and plan constraints, which the same paper lists as unaddressed.

Why not just coarsen the scopes until the nerve has no loops, or triangulate the network? This is the most serious alternative. Merging regions along every loop yields a tree of scopes, and the classical acyclic-gluing guarantees then apply. Merging, however, enlarges regions and gives back the search savings that motivated localization. Triangulation adds fill-in constraints between agents that never interact; Kong et al. report this as both slow and a privacy leak in $P^3C$. We will run a "merge-to-tree" baseline directly against loop completion. If merging matches loop completion's cost on the construction and multi-mission domains, we will report that loop counting is a good diagnostic for when to merge, rather than a better algorithm.

Why not just keep GEMPLAN's completion and tune region choice? Completion is sound but blind: it re-verifies everything that overlaps a change. If tuned regions already keep $b_1$ small, completion and loop completion will coincide. Our diagnosis experiment shows which case holds by plotting completion cost against $b_1$ and against overlap volume on the same covers.

Proposed Experiments

The data will come from regenerated versions of the evaluation domains in the research file. We will rebuild the multi-contractor, multi-room building-construction domain of Localized Search for Multiagent Planning at its reported 49–97 action scale. We will rebuild the floor-scaled office domain of Scope and Abstraction: Two Criteria for Localized Planning, and an Air Tasking Order-like multi-mission generator matching the mission counts and depth in Temporal Milestones in HTNs. Since the original instances may be unavailable, these will be faithful regenerations from the published descriptions, released with the code. For STPs we will add the scale-free synthetic graphs and the New York road network used by Kong et al., plus disjunctive variants made by replacing a controlled fraction of edges with two-way disjunctions.

The scope covers will come from three sources: LOC-style generation by constraint relevance, hand-specified contractor and room scopes, and synthetic covers in which $b_1$ and overlap volume are varied independently. The independent variation matters most, because it separates our hypothesis from the obvious confound.

The metrics are global-consistency agreement with the flat solver, number of constraint re-checks, wall-clock time, and the failure rate of local-only solving.

Three checks are decisive. First, on STPs, every inconsistency missed by local-only solving must be caught by some basis-loop check. A single miss falsifies the STP theorem. Second, across synthetic covers, $b_1(N)$ must explain local-only failure rate and completion cost substantially better than overlap volume does, judged by held-out regression fit. If overlap volume wins, the core idea is wrong. Third, on disjunctive and plan domains, loop completion must reach full completion's consistency rate with fewer re-checks, and the advantage must grow with overlap at fixed $b_1$. We will separately report how often loop checks miss inconsistencies outside row-convex classes, which tests where our analog of the truncation hypothesis fails.