Backtracking Research

Researchers have already extended the original backtracking algorithm, and it may be suitable for Backtrex to draw inspiration from it. This page is an ongoing effort to make sense of what variations of the problem domain and algorithms have been explored. To start, these slides on Multi-Agent Constraint Problem Solving offer an overview.

Several reformulations of backtracking involving multiple agents seemingly don't align with Backtrex's intended direction (although others may). In such models each agent maintains the state of a subset of the unknowns and, with information from other agents about their state, determines if it's own state is consistent with theirs. This perspective could be useful, for instance, in a distributed sensor/actuator network trying to discover a consistent state with limited communication, but at the moment it's not the intended direction for Backtrex.

Backtrex, for now, always starts with a single agent having access to the entire problem statement and a pure validity checker. Backtrex could solve the aforementioned sort of problems if all data from agents are first gathered and a pure consistency checker is available. The plan is to optimize the starting agent's job of finding solutions by dividing its work into subproblems and delegating to other agents (see issue #3).

Papers to consider

The abstracts of these papers suggest they may help.

• An Easy-to-use Scalable Framework for Parallel Recursive Backtracking
• A Decentralized Load Balancing Approach for Parallel Search-Tree Optimization
• Parallel, Scalable, Memory-Efficient Backtracking for Combinatorial Modeling of Large-Scale Biological Systems
• Better Algorithms for Parallel Backtracking