A Study On The Possibilistic Sequential Decision Making Based On Possibility Theory

There exists a lot of sequential decision making problems in the real world, with the true probability of every event can not be informed that easily. However, most of the sequential decision making problems are based on probability theory, which means we have to quantify the uncertain information in a probabilistic way. And the process itself may lead to distortion of information. In fact, a way of modeling the possibilistic and imprecise information based on possibility theory should have implied to this field.The states get transfered by making the possibilistic decision, which is fixed through possibilistic objectives and possibilistic constraints. The possibilistic sequential decision is given the ultimate goal, and the optimal control sequence in the system is selected to make sure the optimal state of each part, so it is also called possibilistic dynamic programming.It has formed a lot of possibilistic evaluating criteria, namely:possibilistic qualitative criteria, possibilistic likely dominance, order of magnitude expected utility and so on. Each criterion has different conditions and scope of application, however, match the basic characteristics of dynamic programming for all, which means the optimal solution could be computed in polytime.In particular, the possibilistic Choquet integral criteria are well for the modeling of heterogeneous information, thus, more practical. But solving a sequential decision making problem of possibilistic Choquet integral is NP-hard, which we proved in this paper. Nevertheless, we still tried the way of dynamic programming, the experimental results showed that it has a very high rate to obtain the optimal solution or approximate optimal solution. Considering the imprecision of heterogeneous information itself, we believe that the results obtained by the way of dynamic programming is quite practical.