Symbolic Heuristic Search for Factored Markov Decision Processes

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Planning

We describe a planning algorithm that integrates two approaches to solving Markov decision processes with large state spaces. State abstraction is used to avoid evaluating states individually. Forward search from a start state, guided by an admissible heuristic, is used to avoid evaluating all states. We combine these two approaches in a novel way that exploits symbolic model-checking techniques and demonstrates their usefulness for decision-theoretic planning.