Symbolic Dynamic Programming for First-Order MDPs
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 690-699.
Abstract
We present a dynamic programming approach for the solution of first-order Markov decisions processes. This technique uses an MDP whose dynamics is represented in a variant of the situation calculus allowing for stochastic actions. It produces a logical description of the optimal value function and policy by constructing a set of first-order formulae that minimally partition state space according to distinctions made by the value function and policy. This is achieved through the use of an operation known as decision-theoretic regression. In effect, our algorithm performs value iteration without explicit enumeration of either the state or action spaces of the MDP. This allows problems involving relational fluents and quantification to be solved without requiring explicit state space enumeration or conversion to propositional form.
@inproceedings{ijcai2001p95,
title = {Symbolic Dynamic Programming for First-Order MDPs},
author = {Boutilier, Craig and Reiter, Raymond and Price, Bob},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {690--699},
year = {2001},
url = {https://ijcai.org/proceedings/2001/95},
}
TY - CPAPER TI - Symbolic Dynamic Programming for First-Order MDPs AU - Boutilier, Craig AU - Reiter, Raymond AU - Price, Bob T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 690 EP - 699 UR - https://ijcai.org/proceedings/2001/95 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
