The DeepXube Software Package for Solving Pathfinding Problems with Learned Heuristic Functions and Search

DeepXube is a free, open-source Python package that automates pathfinding solutions by integrating deep reinforcement learning, heuristic search, and formal logic to train neural network-based heuristics and efficiently solve problems using GPU-accelerated algorithms.

The Gist

Imagine you are trying to find the fastest route through a massive, ever-changing maze. You could try to memorize every single turn (which takes forever), or you could try to guess the best direction based on a hunch.

DeepXube is a free software tool that teaches computers how to get really good at that "hunch" part. It combines the brainpower of Deep Learning (AI that learns from experience) with Heuristic Search (smart guessing strategies) to solve complex pathfinding problems.

Here is a breakdown of how it works, using some everyday analogies:

1. The Problem: The Infinite Maze

Pathfinding problems are everywhere. They aren't just about GPS navigation. They are about:

• Chemistry: Figuring out the steps to turn raw ingredients into a new medicine.
• Robotics: Teaching a robot arm how to move without hitting anything.
• Puzzles: Solving a Rubik's Cube.
• Quantum Computing: Arranging quantum circuits to solve math problems.

Traditionally, humans had to write specific rules for every single type of maze. DeepXube changes the game. It only needs a "Black Box" description of the maze (how you move from point A to point B) and a Neural Network (the computer's brain) to learn the rules on its own.

2. The Teacher: Learning by Doing (Reinforcement Learning)

How does the computer learn? Imagine a student trying to learn a video game.

• The Student (The Neural Network): Tries to solve a puzzle.
• The Game (The Domain): The computer generates random puzzles (like scrambling a Rubik's Cube).
• The Trial: The student tries to solve it. Sometimes they get stuck; sometimes they win.
• The Feedback Loop: DeepXube acts as the coach. It looks at the student's moves. If the student took a wrong turn, the coach says, "No, that path was too long." If they found a shortcut, the coach says, "Great job!"
• The Update: The student's brain (the Neural Network) adjusts its internal weights to remember that shortcut for next time.

DeepXube does this millions of times, but it's super fast because it uses CPUs (the computer's general brain) to generate the puzzles and GPUs (the computer's graphics muscle) to train the student's brain simultaneously.

3. The Two Types of "Hunches"

DeepXube teaches the AI two different ways to guess the best path:

• The "Distance" Guess (Heuristic-v): "I am at this spot. How far is the exit?" It estimates the total cost to finish.
• The "Action" Guess (Heuristic-q): "I am at this spot. If I turn left, how good is that? If I turn right, how good is that?" It evaluates specific moves.

4. The Search Engine: Finding the Path

Once the AI has learned its "hunches," it uses them to solve new problems. Think of this like a hiker with a magical compass:

• Standard Search (A):* The hiker looks at all nearby paths, picks the one that looks best based on the compass, and moves there.
• Batch Search: Instead of looking at one path at a time, the hiker looks at 10 or 100 paths at once. Because computers are great at doing many things at once (parallel processing), this is incredibly fast.
• Beam Search: Imagine a hiker who only keeps the top 5 best paths in their pocket and forgets the rest. This saves memory and keeps the search focused.

5. Special Tricks in the Toolkit

DeepXube has some clever features to make learning easier:

• Hindsight Experience Replay (The "What If" Trick): Sometimes the AI tries to solve a puzzle and fails miserably. Instead of throwing that attempt away, DeepXube says, "Okay, you failed to get to the intended goal, but you did get really good at getting to this other spot. Let's pretend that spot was the goal all along!" This turns failures into learning opportunities.
• The "Mix-in" System: Building a new maze usually requires writing a lot of code. DeepXube uses "Mix-ins," which are like pre-made Lego blocks. If you want a maze where you can reverse your steps (like sliding a puzzle), you just snap on the "Reversible" block. If you want to visualize the maze, you snap on the "Visual" block. It makes building new problems very easy.
• The Command Line: You don't need to be a coding wizard to use it. You can just type commands like deepxube train or deepxube solve to start the process, similar to giving instructions to a smart assistant.

Why Does This Matter?

Before tools like DeepXube, solving complex problems required a human expert to hand-craft the rules for every specific situation. DeepXube automates this. It allows us to teach computers to solve problems in fields we didn't even know how to program before, like chemical reactions or quantum computing, simply by showing them the rules of the game and letting them learn the strategy.

In short: DeepXube is a universal gym for AI. It generates the workouts (puzzles), trains the muscles (neural networks), and then sends the AI out to win the race (solve the problem) faster and smarter than ever before.

Technical Summary

1. Problem Statement

Pathfinding problems are ubiquitous in fields ranging from robotics and chemistry to quantum computing and puzzle solving. Traditional solutions rely on human-designed algorithms, pattern databases, or heuristics derived from formal domain representations. However, these methods often require significant domain expertise and pre-existing solvers.

Recent advances have shown that Deep Neural Networks (DNNs) can learn heuristic functions to guide search algorithms, often outperforming traditional methods while treating the domain as a "black box." Despite this potential, there is a lack of unified, open-source software that seamlessly integrates:

• Black-box domain definitions (arbitrary Python code).
• Deep Reinforcement Learning (DRL) and Supervised Learning for training heuristics.
• Scalable, parallelized heuristic search algorithms (A*, Q*, Beam Search) optimized for GPU acceleration.

DeepXube addresses this gap by providing a comprehensive, open-source Python package and command-line tool to automate the solution of pathfinding problems using learned heuristics.

2. Methodology

DeepXube employs a modular architecture that separates domain definition, neural network architecture, and search algorithms, allowing for flexible experimentation.

A. Domain Definition (Black-Box Approach)

Users define a pathfinding domain by implementing a set of core methods:

• samp_prob_insts: Sampling problem instances.
• samp_state_act: Sampling valid actions in a state.
• next_state: Computing state transitions and costs.
• is_solved: Goal testing.

To simplify development, DeepXube utilizes a multiple-inheritance "Mixin" system. These mixins provide pre-implemented functionality for:

• Action Spaces: Handling enumerable, fixed, or reversible action spaces (e.g., Rubik's Cube, Sokoban).
• Data Generation: Strategies for generating training data via random walks (forward or reverse) or goal sampling.
• Visualization & Logic: Support for Answer Set Programming (ASP) for abstract goal specification and NumPy integration for performance.

B. Neural Network Integration

DeepXube supports various heuristic types via PyTorch:

• Heuristic-v ($h_\theta$): Maps state and goal to a cost-to-go estimate. Trained via Value Iteration.
• Heuristic-q ($q_\theta$): Maps state, goal, and action to an action-value estimate. Trained via Q-Learning. It can also output $q$-values for all actions in a single forward pass (efficient for fixed action spaces).
• Policy Functions: Preliminary support for sampling actions directly from a distribution (useful for continuous or massive action spaces).

The system uses an NNetInput abstraction to convert Python objects into tensor representations suitable for specific DNN architectures (e.g., CNNs, Transformers).

C. Search Algorithms

DeepXube implements a suite of search algorithms that leverage DNNs and GPU parallelism:

• Graph Search: Includes A* (using $h$-v) and Q* (using $h$-q).
• Batched Variants: Batch Weighted A (BWAS)* and Batch Weighted Q (BWQS)*. These remove $B > 1$ nodes/edges per iteration, exploiting GPU parallelism for DNN inference.
• Beam Search: Maintains a fixed beam of size $B$, selecting top edges based on heuristic values or policy probabilities. Supports stochasticity (Boltzmann distribution) and $\epsilon$-greedy policies.

D. Training Pipeline

Training is highly parallelized:

• CPU Parallelism: Multiple CPU cores sample problem instances, perform pathfinding (generating search trees), and compute targets.
• GPU Parallelism: DNN updates (gradient descent) are distributed across available GPUs.
• Target Computation: Uses Limited-Horizon Bellman-based Learning (LHBL) for recursive backups or standard Q-learning/Value Iteration.
• Data Augmentation:
  • Hindsight Experience Replay (HER): If a search fails, the deepest node reached is treated as a new goal to generate a successful training example.
  • Supervised Learning: Can train on random walk path costs without reinforcement learning updates (faster target generation).
  • Replay Buffers: Stores recent transitions for stable training.

3. Key Contributions

1. Unified Open-Source Framework: DeepXube is the first package to combine state-of-the-art DRL, supervised learning, and heuristic search specifically for pathfinding in a single, extensible Python library.
2. Scalable Parallelization: It uniquely orchestrates training across both CPUs (for data generation and search) and GPUs (for DNN inference and updates), significantly speeding up the training loop.
3. Flexible Domain Abstraction: The "Mixin" architecture allows users to define complex domains (e.g., chemical synthesis, quantum circuits) with minimal boilerplate code, supporting arbitrary Python packages (like RDKit).
4. Advanced Goal Specification: Integration with Answer Set Programming (ASP) allows goals to be defined as logical predicates rather than specific states, enabling expressive goal specification in complex domains.
5. Comprehensive Tooling: Includes a command-line interface (deepxube) for easy execution, visualization tools (TensorBoard integration, custom progress plots), and profiling utilities for debugging and timing.

4. Results and Performance

While the paper focuses on the software architecture rather than a single benchmark comparison, it highlights the following capabilities and theoretical results:

• Efficiency: The parallelization strategy allows for rapid generation of training data and efficient DNN updates, making it feasible to train heuristics for complex domains like the Rubik's Cube and chemical reaction mechanisms.
• Versatility: The system has been successfully applied to diverse problems including:
  • Combinatorial puzzles (Rubik's Cube, sliding tiles).
  • Chemical reaction mechanism pathfinding.
  • Quantum algorithm compilation.
  • Cryptography and parking lot optimization.
• Algorithmic Flexibility: The framework supports switching between different search strategies (A*, Q*, Beam) and learning paradigms (RL vs. Supervised) simply by changing command-line arguments, facilitating rapid experimentation.

5. Significance

DeepXube represents a significant step forward in Automated Planning and Reinforcement Learning.

• Democratization of AI Planning: By abstracting the complexity of domain definition and search algorithm implementation, it lowers the barrier for researchers to apply deep learning to pathfinding in new domains.
• Bridging Theory and Practice: It bridges the gap between theoretical advances in DRL (like HER and LHBL) and practical application in real-world domains where transition functions are complex or unknown.
• Future-Proofing: The architecture is designed to accommodate future advancements, such as learning transition functions (Model-Based RL) and handling continuous action spaces via advanced policy networks.

In conclusion, DeepXube provides a robust, scalable, and user-friendly ecosystem for developing and deploying learned heuristics, enabling the solution of complex pathfinding problems that were previously intractable or required hand-crafted solvers.