Optimization Online


Random-Sampling Monte-Carlo Tree Search Methods for Cost Approximation in Long-Horizon Optimal Control

Shankarachary Ragi (shankarachary.ragi***at***sdsmt.edu)
Hans D Mittelmann (mittelmann***at***asu.edu)

Abstract: We develop Monte-Carlo based heuristic approaches to approximate the objective function in long horizon optimal control problems. In these approaches, to approximate the expectation operator in the objective function, we evolve the system state over multiple trajectories into the future while sampling the noise disturbances at each time-step, and find the average (or weighted average) of the costs along all the trajectories. We call these methods random sampling - multipath hypothesis propagation or RS-MHP. These methods (or variants) exist in the literature; however, the literature lacks results on how well these approximation strategies converge. This letter fills this knowledge gap to a certain extent. We derive stochastic convergence results for the cost approximation error from the RS-MHP methods and discuss their convergence (in probability) as the sample size increases. We consider two case studies to demonstrate the effectiveness of our methods - a) linear quadratic control problem; b) unmanned aerial vehicle path optimization problem.

Keywords: Optimal control, optimization, Markov processes, discrete event systems

Category 1: Applications -- Science and Engineering

Category 2: Applications -- Science and Engineering (Control Applications )


Download: [PDF]

Entry Submitted: 01/05/2021
Entry Accepted: 01/05/2021
Entry Last Modified: 02/01/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society