Localized Constraint Propagation for Temporal Reasoning and Planning

22 concepts14 papers9 proposals

When reasoning about complex systems—whether tracking a web of historical events, coordinating a fleet of autonomous robots, or solving massive logic puzzles—we inevitably run into the wall of combinatorial explosion.

If every action or event can potentially affect every other action or event, verifying that a plan is valid or that a timeline is consistent requires global constraint propagation. In practice, this means computing expensive operations like full transitive closures or checking every rule against every state variable. As the problem size grows, the computational cost grows exponentially.

However, real-world problems are rarely fully coupled. What happens in a kitchen usually has no bearing on the schedule of a delivery truck miles away. Localized constraint propagation exploits this inherent sparsity. By partitioning a global problem into localized regions, scopes, or neighborhoods, we can confine expensive logical reasoning to small fragments of the domain, drastically reducing computational overhead while maintaining global consistency.


Localizing Time via Reference Intervals

Early temporal reasoning systems treated time as a flat network of relations. If you learned that Event A happened before Event B, you had to propagate this constraint across the entire network to update every other event's relative position.

To solve this, James F. Allen introduced an interval-based representation of time in An Interval-Based Representation of Temporal Knowledge. Instead of allowing a fully connected network, Allen introduced reference intervals to act as local anchors.

[Global Timeline Reference]
    ├── [Workday Reference]
    │       ├── [Meeting A]
    │       └── [Meeting B]
    └── [Evening Reference]
            ├── [Dinner]
            └── [Movie]

Instead of comparing "Meeting A" to "Dinner" directly, both are localized to their respective reference intervals ("Workday" and "Evening"). Constraint propagation is strictly bounded within these local clusters. If a new constraint is added to "Meeting B", the system only updates intervals sharing the "Workday" reference. This localization prevents a combinatorial explosion, making large-scale temporal knowledge bases computationally manageable.

Louis J. Hoebel formalized this intuition as the locality of effects in Tractable Anytime Temporal Constraint Propagation. Because most temporal constraints only influence events within a close spatial or temporal proximity, structuring the network into a reference hierarchy allows the system to ignore the vast majority of the global network during updates.

Similarly, Gerevini et al. demonstrated in Efficient Temporal Reasoning through Timegraphs that complex relations (such as "not equal" constraints) can be resolved efficiently by focusing on localized graph configurations—like diamond structures within temporal chains—rather than propagating changes globally.


Scope-Based Localization in Planning

In multiagent planning, a similar bottleneck occurs. Traditional planners evaluate constraints globally to ensure that one agent's actions do not interfere with another's.

In Localized Representation and Planning Methods for Parallel Domains, Lansky et al. proposed partitioning planning domains into localized regions to guarantee non-interference. If two sub-problems are structurally disjoint, events within one region cannot violate constraints in the other. This directly mitigates the classic frame problem by drastically reducing the number of constraints that must be re-evaluated when a new action is added.

In Localized Search for Multiagent Planning, Amy L. Lansky implemented this via regional "mini-planners" in the GEMPLAN system. Instead of a single global search space, constraints are localized to specific sub-regions of a plan.

Global Plan Search Space (Exponential Explosion)
   └── Localized Search (GEMPLAN)
          ├── Mini-Planner A (Confined Constraints)
          ├── Mini-Planner B (Confined Constraints)
          └── Sparse Inter-Region Coordination

But how should these regions be divided? While many systems rely on hierarchical abstraction (grouping by high-level vs. low-level tasks), Lansky et al. introduced scope-based localization in Scope and Abstraction: Two Criteria for Localized Planning.

Scope-based localization partitions a problem based on the direct relevance of constraints to specific action types. As explored further in Scope, grouping plan fragments by constraint scope prevents regions from collapsing into one another or becoming unnecessarily large. By keeping regions small and focused, calculating temporal closures remains computationally cheap.

This strategy of isolating sub-problems and aggregating them minimally is also highly effective in Hierarchical Task Networks (HTNs). Yaman et al. developed a localized propagation strategy using "temporal milestones" in Temporal Milestones in HTNs. By computing the temporal requirements of sub-missions independently and only aggregating their constraints at the very top level of the hierarchy, they achieved a quadratic speedup in reasoning time over traditional global consistency algorithms.


Scaling Combinatorial Solvers and Logics

The power of localized reasoning extends beyond planning and timelines into pure constraint satisfaction (CSP), Boolean satisfiability (SAT), and description logics.

In SAT solving, the way a problem is encoded dictates its tractability. Metodi et al. introduced Boolean Equi-propagation in Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems. Their core insight was that applying computationally expensive reasoning to small, localized fragments of a constraint model can uncover hidden variable equalities. Identifying these equalities globally would be far too expensive, but finding them locally allows them to propagate outwards, simplifying the entire global formula and shrinking the search space.

A parallel approach is used in heavy-duty optimization and software testing. In Combining Genetic Algorithms and Constraint Programming to Support Stress Testing of Task Deadlines, Di Alesio et al. combined heuristic search with exact constraint solvers. Exact solvers easily suffer from state explosion when tackling large systems globally. By restricting the exact solver to a small, localized neighborhood around a promising heuristic solution, the solver operates within a strictly bounded radius, allowing it to verify and optimize complex timing deadlines efficiently.

Even in formal logic, localization dictates the boundary between what is computable and what is not. The authors of Temporalized proved that unrestricted temporal description logic is undecidable for query answering. However, by enforcing a strict structural constraint—restricting the usage of roles to be strictly local within the temporal fragments ($TEL^\circ_{loc}$)—the data complexity drops dramatically to PTIME-complete, rendering atomic query answering practically tractable.


Why It Works: The Sparsity Principle

Localized constraint propagation works because it replaces a single, massive, high-degree problem graph with a collection of smaller, loosely coupled sub-graphs.

If a global network has $N$ elements, a standard constraint propagation algorithm might scale quadratically ($O(N^2)$) or cubically ($O(N^3)$). If we partition that network into $k$ localized regions of size $m$ (where $N = k \times m$), performing propagation inside the local regions costs $k \times O(m^3)$. Because $m \ll N$, this local cost is a fraction of the global cost.

The trade-off is that we must occasionally coordinate between these regions. Whether through Allen's reference intervals, Lansky's scope boundaries, or Yaman et al.'s temporal milestones, the field of localized reasoning demonstrates that coordinating local summaries is orders of magnitude faster than allowing constraints to propagate globally without boundaries.

Key Foundational Work

An Interval-Based Representation of Temporal Knowledge (1981) — contributed 2 concept elements to this direction.
Localized Representation and Planning Methods for Parallel Domains (1987) — contributed 2 concept elements to this direction.
An Interval-Based Representation of Temporal Knowledge (1981) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scope_based_localization_b743af58,
  title = {scope-based localization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scope-based-localization/rdr_b743af58290f4de88f900b46fe5306c1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_scope_based_localization_b743af58_v1,
  title = {scope-based localization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scope-based-localization/rdr_b743af58290f4de88f900b46fe5306c1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake