Bounded Combinatorial Reconfiguration with Answer Set Programming

Yuya Yamada, Mutsunori Banbara, Katsumi Inoue, Torsten SchaubarXiv 2023 · DOI · arXiv

TL;DR

This paper introduces recongo, a high-performance solver for combinatorial reconfiguration problems (CRPs) built on Answer Set Programming (ASP). By applying "bounded" search techniques—similar to bounded model checking—and leveraging incremental "multi-shot" solving, the authors created a system that took first place in the "shortest path" category at the 2022 International CoRe Challenge.

What Problem Does This Paper Address?

Imagine you have a puzzle where you need to transform one valid solution into another by making small, legal moves. This is the essence of Combinatorial Reconfiguration (CR). For example, in the "Independent Set" problem, you might need to move "tokens" on a graph one by one, ensuring that at no point do two tokens sit on adjacent nodes.

While finding a single solution to a combinatorial problem is often NP-complete, figuring out if you can reach one solution from another is frequently much harder—often PSPACE-complete. Most existing tools are either highly specialized or rely on standard SAT solvers. The authors address the need for a declarative, general-purpose framework that can efficiently navigate these massive state spaces.

Methods

The authors propose Bounded Combinatorial Reconfiguration (BCR). This approach is inspired by Bounded Model Checking: it looks for a solution path of length $\ell$, and if none is found, it increments $\ell$ and tries again.

Key technical innovations include:

  • Multi-shot ASP Solving: Instead of restarting the solver from scratch every time the path length increases (which is computationally expensive), they use the clingo solver’s "multi-shot" capabilities. This allows them to incrementally add new "steps" to the logic program while retaining the work done in previous iterations.
  • Declarative Encodings: They provide a clean ASP encoding for the Independent Set Reconfiguration Problem (ISRP) using the "token jumping" rule.
  • Search Hints: To speed up the solver, they introduced several "hints"—extra constraints that prune the search space. These include domain-independent distance bounds (e.g., "you can't reach the goal in $k$ steps if you are more than $k$ moves away") and domain-specific heuristics that encourage the solver to find maximal independent sets.

Datasets

The approach was evaluated using the full benchmark set from the CoRe Challenge 2022, which consists of 369 instances across seven families (such as color04, grid, queen, and power). These instances vary significantly in scale, with graph sizes ranging from just 7 nodes to 40,000 nodes.

Key Insights and Ideas

  • The Power of Incrementalism: The "multi-shot" approach is the secret sauce. By treating the reconfiguration as an evolving logic program rather than a series of independent SAT problems, the solver avoids redundant "grounding" (the process of turning abstract logic into concrete constraints).
  • Hints are Essential: Adding "hints" wasn't just a minor optimization; it was transformative. For the "existent" metric (simply finding any path), adding hints increased the number of solved instances from 192 to 240.
  • ASP as a Competitive Alternative: Traditionally, PSPACE problems are the domain of specialized planners or SAT-based model checkers. This paper proves that a declarative ASP-based approach can not only compete but win against state-of-the-art specialized solvers.

Key Results

The resulting solver, recongo, showed impressive performance in the CoRe Challenge 2022 single-engine track:

  • 1st Place: Shortest path metric (finding the absolute minimum number of moves).
  • 2nd Place: Existent metric (deciding reachability) and Longest path metric.
  • Efficiency: In the color04 and queen families, recongo was particularly dominant, finding shortest reconfiguration sequences for all instances in the former.

Limitations and Future Work

  • Unreachability: Because the method is "bounded," it is inherently incomplete for proving that a goal is unreachable unless the maximum possible path length (the diameter of the solution space) is known in advance.
  • Long Paths: The solver struggles with problem families like power or square, where the shortest paths are extremely long. The current linear search (checking length 1, then 2, then 3...) becomes a bottleneck here.
  • Future Directions: The authors plan to investigate "numeric abstraction" (a technique used by the competing PARIS solver) and more advanced search strategies, such as exponential search, to handle instances with very deep solution paths.

Summary updated

BibTeX
@misc{yamada2023bounded,
  author = {Yuya Yamada and Mutsunori Banbara and Katsumi Inoue and Torsten Schaub},
  title = {{Bounded Combinatorial Reconfiguration with Answer Set Programming}},
  year = {2023},
  eprint = {2307.10688},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.10688},
}

Loading related content...

Figure