Learning Generalized Policy Automata for Relational Stochastic Shortest Path Problems
This work addresses the problem of scaling SSP solutions for goal-oriented real-world applications, offering a novel method that generalizes learned policies to new instances, though it is incremental in improving existing planning techniques.
The paper tackles the computational intractability of Stochastic Shortest Path Problems (SSPs) by learning Generalized Policy Automata (GPA), which are non-deterministic partial policies that exploit relational abstractions to generalize across problems with varying object counts. Empirical results show that this approach significantly outperforms state-of-the-art SSP solvers on test problems with far greater object counts than those used in training.
Several goal-oriented problems in the real-world can be naturally expressed as Stochastic Shortest Path Problems (SSPs). However, the computational complexity of solving SSPs makes finding solutions to even moderately sized problems intractable. Currently, existing state-of-the-art planners and heuristics often fail to exploit knowledge learned from solving other instances. This paper presents an approach for learning \emph{Generalized Policy Automata} (GPA): non-deterministic partial policies that can be used to catalyze the solution process. GPAs are learned using relational, feature-based abstractions, which makes them applicable on broad classes of related problems with different object names and quantities. Theoretical analysis of this approach shows that it guarantees completeness and hierarchical optimality. Empirical analysis shows that this approach effectively learns broadly applicable policy knowledge in a few-shot fashion and significantly outperforms state-of-the-art SSP solvers on test problems whose object counts are far greater than those used during training.