Stochastic shortest path problem and its applications in Over the Air Programming - 02/03/2006

XiangPing (Sandra) Qin

Stochastic shortest path problem is a classic problem used in many applications. We will introduce the basic formulation of both the deterministic and stochastic shortest path problems, and how it can be used to formulate the problem of optimizing the control strategies in the over the air programming. A simple example of single hop and single channel is given. Dynamic programming is a standard method to solve the stochastic shortest path problem. It is used to solve the simple scenario of single hop and single channel scenario. Many other applications, such as the optimal strategy searching in a multi-channel scenario, can also be formulated as a stochastic shortest path problem, and the small scale solution can be obtained by dynamic programming.