Entropy Maximization for Markov Decision Processes Under Temporal Logic Constraints

We study the problem of synthesizing a policy that maximizes the entropy of a Markov decision process (MDP) subject to a temporal logic constraint. Such a policy minimizes the predictability of the paths it generates, or dually, maximizes the exploration of different paths in an MDP while ensuring t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2020-04, Vol.65 (4), p.1552-1567
Main Authors: Savas, Yagiz, Ornik, Melkior, Cubuktepe, Murat, Karabag, Mustafa O., Topcu, Ufuk
Format: Article
Language:English
Subjects:
Algorithms
Computational geometry
Convex functions
Convexity
Entropy
Markov analysis
Markov processes
Maximization
Maximum entropy
Motion planning
Optimization
Planning
Random variables
Specifications
Synthesis
Task analysis
Temporal logic
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the problem of synthesizing a policy that maximizes the entropy of a Markov decision process (MDP) subject to a temporal logic constraint. Such a policy minimizes the predictability of the paths it generates, or dually, maximizes the exploration of different paths in an MDP while ensuring the satisfaction of a temporal logic specification. We first show that the maximum entropy of an MDP can be finite, infinite, or unbounded. We provide necessary and sufficient conditions under which the maximum entropy of an MDP is finite, infinite, or unbounded. We then present an algorithm which is based on a convex optimization problem to synthesize a policy that maximizes the entropy of an MDP. We also show that maximizing the entropy of an MDP is equivalent to maximizing the entropy of the paths that reach a certain set of states in the MDP. Finally, we extend the algorithm to an MDP subject to a temporal logic specification. In numerical examples, we demonstrate the proposed method on different motion planning scenarios and illustrate the relation between the restrictions imposed on the paths by a specification, the maximum entropy, and the predictability of paths.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2019.2922583