Scientific Computing Group Seminars - Detail View

Speaker: A. Vladimirsky

Affiliation: Cornell University

Talk Title: Label-setting methods for stochastic shortest path problems & static PDEs of deterministic optimal control.

Invited by: Chi-Wang Shu

Time: Dec. 07 2007 11 a.m.

Location: 182 George Street, Room 110

Abstract:

Dijkstra's and Dial's methods are the well-known "label-setting" algorithms for finding deterministic shortest paths on graphs with positive edge-costs. The stochastic shortest path (SSP) problem is a natural generalization, for which such efficient (non-iterative) methods are usually unavailable. In SSPs, the current state of the system is still described by a specific node of a directed graph. At each stage of the process we select one from a (possibly node-dependent) compact set of available control values. The chosen control determines the cost incurred at that stage and the probability distribution over the successor-nodes for the next transition. The process continues until a transition to one of the "exit nodes". The goal is to find a policy minimizing the expected value of the total cost up to the termination. Bellman's optimality for the value function results in a system of coupled nonlinear equations, which has to be solved iteratively and generally requires an infinite number of iterations. Additional structure of an optimal policy can sometimes be used to prove that only a finite number of iterations is needed and that label-setting algorithms are, in fact, applicable. We will introduce a class of "multimode" SSPs, for which such a structure is guaranteed to be present in _all_ optimal policies. SSPs provide a natural discretization for static Hamilton-Jacobi-Bellman PDEs of continuous optimal control. Hence, label-setting for the former yields efficient (non-iterative) numerical methods for the latter. We will illustrate this point using time-optimal control problems on a continuous domain.