  Density function describes the density of states in the state space of a
dynamic system or a Markov Decision Process (MDP). Its evolution follows the
Liouville equation. We show that the density function is the dual of the value
function in the optimal control problems. 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 equation to get
the density function under a fixed control strategy and updates the
perturbation term. Moreover, the proposed method can be extended to the case
with exogenous disturbance, and guarantee robust safety under the worst-case
disturbance. We apply the proposed method to three examples, a robot navigation
problem and a traffic control problem in sim, and a segway control problem with
experiment.
