Heuristic Search in Cyclic State Graphs

26 concepts15 papers1 proposal

When an agent navigates a search space, the textbook assumption is often that the space behaves like a tree or an acyclic graph: every action pushes the agent forward into new territory. However, real-world domains—ranging from game-tree playing and automated planning to diagnosing circular dependencies in microservices—are filled with cycles. In these environments, actions can be reversible or repetitive, allowing a search path to loop back onto a previously visited state.

Standard search algorithms frequently fail in the presence of these cycles. Without explicit mechanisms to handle loops, solvers can become trapped in infinite search branches, failing to terminate or incorrectly concluding that a solvable problem is unsolvable. Over the past few decades, researchers have developed specialized heuristic and depth-first search architectures designed to detect, break, or even embrace cycles to guarantee completeness and optimality.

The Problem with the Acyclic Assumption

Why do traditional search algorithms struggle with cycles? The core issue lies in how algorithms track progress and manage memory.

In an acyclic space, moving deeper down a path guarantees that you are exploring new states. Many theoretical guarantees of completeness and optimality—such as those analyzed by Yuehua Xu et al. for online beam search ranking, or by Carlos Hernández Ulloa et al. for memory-bounded heuristic search—explicitly rely on the assumption of a finite, tree-shaped search space. When these algorithms are applied to general graphs where multiple paths lead to the same state, their convergence guarantees break down. Similarly, data structures like centroid trees, which provide tight approximation guarantees for search trees, do not naturally extend to non-tree topologies with loops, as noted by Benjamin Aram Berendsohn et al.

When an algorithm lacks a mechanism to recognize that it has returned to a parent state, it treats the revisited state as a brand-new subproblem. As highlighted by Arnaud Lallouet et al. in the context of infinite data streams, standard search strategies will continue exploring these redundant paths indefinitely, making it impossible to prove whether a solution exists. This trap is not just a theoretical concern; Hongcheng Guo et al. demonstrated that traditional graph-based diagnostic tools frequently enter non-terminating loops when trying to trace root causes through circular service dependencies in microservices.

Breaking Loops via Thresholds and Value Learning

To prevent infinite loops, search algorithms must find a way to force progress toward a terminal state. Two primary paradigms have emerged to achieve this: dynamic threshold control and depth-first value learning.

Dynamic Threshold Control

In game-tree search algorithms like Depth-First Proof-Number Search (DFPN), cycles cause the algorithm to repeatedly cycle through the same set of states instead of converging on a proof or disproof of a winning strategy. To resolve this, Akihiro Kishimoto introduced the Threshold Controlling Algorithm (TCA).

TCA works by dynamically managing search thresholds during the depth-first traversal. When the algorithm detects that it has returned to a previously visited node without making global progress, TCA alters the local thresholds required to continue expanding that branch. This effectively forces the search to abandon the loop and progress toward unvisited leaf nodes. Christopher Franz et al. later integrated TCA with DFPN to formally prove that this combination guarantees completeness on general graphs with cycles, ensuring the algorithm will always find a winning strategy if one exists.

Depth-First Value Learning

For complex AND/OR graphs—where an action can lead to a combination of subproblems that must all be solved—traditional best-first algorithms like AO* often struggle or fail to terminate when cycles are present. Blai Bonet et al. proposed an alternative approach called Learning in Depth-First Search (LDFS).

Best-First Search (e.g., AO*)         Depth-First Value Learning (LDFS)
   [State A]                             [State A] (Updates value on backtrack)
     │                                     ▲   │
     ▼                                     │   ▼
   [State B] ──► [State C]               [State B] ──► [State C]
     ▲             │                       ▲             │
     └─────────────┘                       └─────────────┘
(Gets stuck re-evaluating the loop)     (Value updates eventually push search 
                                         to escape the loop)

Instead of maintaining a massive explicit graph of open nodes, LDFS uses a depth-first traversal combined with iterative value updates. When the search hits a cycle, it backtracks and updates the heuristic values of the states within the loop. By updating these values locally, the algorithm effectively "fills in" the low-cost trap of the cycle. Over multiple iterations, the cost of entering the loop rises until it matches or exceeds alternative paths, naturally guiding the search to explore new, acyclic branches. This mechanism allows LDFS to handle cyclic state graphs far more robustly and efficiently than traditional best-first methods.

Proving Unsolvability under Memory Constraints

Finding a valid path through a cyclic graph is difficult, but proving that no path exists (unsolvability) is even harder—especially when memory is limited. If an algorithm cannot remember every state it has ever visited, how can it distinguish between an infinitely deep search space and a finite space wrapped in a loop?

Without a global memory buffer, standard algorithms can become trapped in infinite loops, failing to recognize that all available actions merely lead back to previously visited states. This limitation is particularly severe in models utilizing belief support abstractions; as shown by Marck van der Vegt et al., such abstractions can fail to find winning strategies in cyclic models even when a valid solution exists.

To solve this without exhausting memory, Akihiro Kishimoto et al. introduced path-specific logic into memory-limited AND/OR searches. Instead of trying to remember the entire global state graph, the algorithm tracks cycle-specific dependencies purely along the current active search path. This path-specific tracking allows the solver to recognize when a state is an inescapable dead-end or leads exclusively to cycles, enabling it to prove unsolvability without requiring an exhaustive memory layout.

A complementary approach is to prune the search space before loops can form. Subbarao Kambhampati tackled this in plan-space planning by introducing pruning strategies (such as Nsat-prune and Cutset-prune) based on the principle of plan minimality. Because plan-space planners can add operators indefinitely—creating infinite search branches even when the underlying state space is finite—these strategies explicitly detect when a newly added step is locally relevant but globally redundant. By safely discarding these non-minimal, looping paths, the planner can navigate infinite search branches without losing its ability to find optimal solutions.

Embracing the Loop: Strong Cyclic Solutions

Thus far, cycles have been treated as obstacles to be avoided or pruned. However, in non-deterministic or stochastic domains, cycles are often an inherent part of the solution.

Consider an agent operating in a Markov Decision Process (MDP) or a Fully Observable Non-Deterministic (FOND) environment. Actions can fail, blowing the agent back to a previous state. In these domains, an acyclic plan is often impossible. Instead, the planner must look for a strong cyclic solution: a policy that contains loops but guarantees that, as long as the agent keeps trying, it will eventually reach the goal.

Early foundations for this were established by algorithms like Generalized A (GA) and LAO. While traditional heuristic search algorithms were strictly limited to acyclic graphs, LAO extended heuristic search to handle the cyclic dependencies inherent in MDPs. By explicitly allowing loops to exist within the solution graph, LAO* focuses its heuristic evaluation only on the states that are reachable under the current policy, avoiding the need to evaluate the entire state space via brute-force dynamic programming.

To scale these concepts to massive state spaces, researchers have turned to hierarchical decomposition. Nicolas Meuleau et al. introduced HiAO*, which partitions large-scale MDPs into smaller sub-problems and uses "macro-connectors" to bypass intermediate states, allowing heuristic AND/OR searches to natively handle cyclic state spaces in stochastic domains.

More recently, Mohammad Yousefi et al. extended this capability to Hierarchical Task Network (HTN) planning. By compiling non-deterministic FOND HTN problems into deterministic relaxations, the authors enabled planners to leverage high-performance grounding and heuristic techniques to find strong cyclic solutions. This allows planners to handle complex, hierarchical tasks where loops are not a failure mode, but a necessary strategy for handling uncertainty.

Key Foundational Work

Generalized A* for Cyclic AND/OR Graphs (1998) — contributed 3 concept elements to this direction.
Heuristic Search in Cyclic AND / OR Graphs (1998) — contributed 2 concept elements to this direction.
Admissible Pruning Strategies based on plan minimality for Plan-Space Planning (1995) — contributed 1 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_infinite_search_loops_11a53b77,
  title = {infinite search loops},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinite-search-loops/rdr_11a53b773da1491881edae612081544c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_infinite_search_loops_11a53b77_v1,
  title = {infinite search loops},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinite-search-loops/rdr_11a53b773da1491881edae612081544c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake