Robust Control For Uncertain Semi-Markov Decision Processes Based On Performance Potentials

As a basic model of discrete event dynamic systems (DEDS), semi-Markov decision process is aiming to address the problem of stochastic sequential decisions. Its performance analysis and optimization may be very helpful to most real systems. In SMDPs, transition probabilities and instant performance are crucial to the system's performance accumulation. However, due to the difficulty of modeling and external disturbance, the exact transition probabilities are always hard to get in practical, and the instant performance may varies with the change of outside environment as well. On behalf of the need in such uncertain systems, this paper is concerned with the robust control for a class of SMDPs with uncertain parameters, while finding a policy that generates optimal performance in the worst case is a major task.According to the structure of embedded chain, SMDP can be categorized as recurrent chain, unichain and multichain. Consider the simplest model at first. A policy-iteration algorithm is provided to search the optimal robust control policy for the recurrent chain in the case of independent parameters. Then we discuss the convergence of policy iteration. As for the case of dependant parameters, we introduce the application of genetic algorithm in detail. For multichain, given the existence of multiple recurrent classes and transient states, the optimal robust control policy is hard or even impossible to obtain. With the constraint of some assumptions, we study the optimal equation for multichain SMDPs under the average criteria, and the corresponding policy iteration is also provided. Since the states number is increasing, in order to improve the efficiency, we introduce a parallel genetic algorithm for multichain under the case of dependant parameters. With the parallel search on multiple processors, the optimization can be accelerated greatly. Here two implementation of migration operation are suggested for the parallel genetic algorithms. Since the unichain can be treated as a special multichain with only one recurrent class, so that all the algorithms developed for multichain can be applied directly to the unichain models.Several numerical examples are presented to illustrate the application of these algorithms, and we analyze the effectiveness of these algorithms by our experiment results.