Abstract
This paper introduces a framework that leverages Reinforcement Learning (RL) to automatically synthesize search heuristics for complex temporal planning problems. By training a neural network to estimate the value of planning states within a specific domain, the authors create a bridge between deep learning and symbolic reasoning. This hybrid approach significantly outperforms traditional planning methods and pure RL policies in terms of both problem coverage and plan quality.
1. Introduction
Automated temporal planning involves finding a sequence of actions to reach a goal while satisfying strict timing constraints, a common requirement in industrial robotics and logistics. While symbolic planners are powerful, their general-purpose heuristics often struggle to scale to complex real-world scenarios. Conversely, Reinforcement Learning (RL) is adept at pattern recognition but often fails at the rigorous logic and backtracking required for planning. This work addresses this gap by automatically synthesizing domain-specific heuristics that enhance symbolic planners with learned intuition.
2. Methodology
The proposed "learning-then-planning" pipeline consists of several key components:
2.1 MDP Encoding and the Logarithmic Bridge
The authors map the temporal planning problem into a Markov Decision Process (MDP). A key theoretical contribution is the derivation of a logarithmic transformation that links the optimal RL value function ($V^*$) to the optimal distance to a goal ($h^*$): $h^*(s) = \log_\gamma(V^*(s))$. This provides a principled way to utilize RL outputs as search heuristics.
2.2 State Vectorization and Neural Architecture
To feed symbolic planning states into a neural network, the authors developed a method to convert predicates, active actions, goals, and temporal constraints into fixed-size vectors. Temporal information from the Simple Temporal Network (STN) is summarized into a set of "time-passed" values, capturing essential temporal dynamics without requiring complex graph-based architectures.
2.3 Value Iteration and Heuristic Search
The neural network ($V_{nn}$) is trained using an episodic RL algorithm. A specialized sampling strategy focuses training on more difficult problems to ensure robust learning. Once trained, $V_{nn}$ is integrated into the TAMER planner as a heuristic ($h_{nn}$), guiding systematic search with the learned value function.
3. Experimental Setup
The approach was evaluated on two challenging domains:
- MAJSP (Multi-Agent Job-Shop Scheduling): An industrial problem involving 770 instances where agents coordinate item movement between machines.
- Kitting: A warehouse domain with 1092 instances where a robot collects components to build kits in synchronization with a human operator.
A 10-fold cross-validation setup was employed, training on 90% of instances and testing on the remaining 10%.
4. Results and Discussion
The experimental results highlight the clear advantage of the hybrid approach.
4.1 Performance and Coverage
In the MAJSP domain, the RL-guided planner solved 744 instances, compared to 560 by the standard symbolic planner. The improvement was even more dramatic in the Kitting domain, where the proposed method solved 1015 instances versus the baseline's 395.
4.2 Plan Quality
The search-based version ($h_{nn}$) consistently found shorter, more efficient plans than the pure RL policy ($\pi_{nn}$). This demonstrates that while RL provides good "intuition," the systematic search of the TAMER planner is essential for optimizing the final path.
4.3 Input Sensitivity
Ablation studies (shown in the figure above) revealed that for complex domains, the network requires access to all state information—fluents, actions, and temporal data—to maintain a high solving rate. Removing any single component significantly degraded performance.
5. Conclusion and Future Work
This research demonstrates that synthesizing search heuristics via RL effectively bridges the gap between symbolic reasoning and deep learning for temporal planning. While the current framework requires a fixed maximum number of objects, future work aims to utilize more flexible architectures like Graph Neural Networks to improve generalization across varying problem sizes and domain definitions.
Summary updated