Influence and Variance of a Markov Chain: Application to Adaptive Discretization in Optimal Control

Remi Munos and Andrew Moore
IEEE Conference on Decision and Control, December, 1999, pp. 1464 - 1469.


Download
  • Adobe portable document format (pdf) (207KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
This paper addresses the difficult problem of deciding where to refine the resolution of adaptive discretizations for solving continuous time-and-space deterministic optimal control problems. We introduce two measures, influence and variance of a Markov chain. Influence measures the extent to which changes of some state affect the value function at other states. Variance measures the heterogeneity of the future cumulated active rewards (whose mean is the value function). We combine these two measures to derive a nonlocal efficient splitting criterion that takes into account the impact of a state on other states when deciding whether to split. We illustrate this method on the non-linear, two dimensional "Car on the Hill" and the 4d "space-shuttle" and "airplane-meeting" control problems.

Notes
Associated Lab(s) / Group(s): Auton Lab
Associated Project(s): Auton Project
Number of pages: 6

Text Reference
Remi Munos and Andrew Moore, "Influence and Variance of a Markov Chain: Application to Adaptive Discretization in Optimal Control," IEEE Conference on Decision and Control, December, 1999, pp. 1464 - 1469.

BibTeX Reference
@inproceedings{Munos_1999_2940,
   author = "Remi Munos and Andrew Moore",
   title = "Influence and Variance of a Markov Chain: Application to Adaptive Discretization in Optimal Control",
   booktitle = "IEEE Conference on Decision and Control",
   pages = "1464 - 1469",
   month = "December",
   year = "1999",
   volume = "2",
}