Duality between density function and value function with applications in constrained optimal control and Markov Decision Process

Abstract

Density function describes the density of states in the state space with some initial state distribution. Its evolution follows the Liouville Partial Differential Equation (PDE). We show that the density function is the dual of the value function in the optimal control problems and strong duality holds. By utilizing the duality, constraints that are hard to enforce in the primal value function optimization such as safety constraints in robot navigation, traffic capacity constraints in traffic flow control can be posed on the density function, and the constrained optimal control problem can be solved with a primal-dual algorithm that alternates between the primal and dual optimization. The primal optimization follows the standard optimal control algorithm with a perturbation term generated by the density constraint, and the dual problem solves the Liouville PDE to get the density function under a fixed control strategy and updates the perturbation term. We show examples in robot navigation and traffic control to demonstrate the capability of the proposed formulation.