Research On First-order Decision-theoretic Planning In Relational Uncertain Environments

As the fast development of the embedded device and artificial intelligence,large-scale intelligent system gradually filters every aspect of our lives, and has moreand more important effect. The environment of these systems is uncertainly and scale ofthese systems is big. How to design decision-making method which can adapt hugescale system in uncertainly environment becomes one of the most important problems inthe domain of artificial intelligence. General enumerating POMDP and it’s solvingmethods are thought as an important way of decision-making planning problem,however, there are only a few hundreds of states which could been solved by planningproblem, and the size of solving problem could not meet the increasing needs ofintelligent system. For solving this problem, FO-POMDP model which is used for hugescale POMDP problem is proposed in abstract level. Now the model and algorithms ofFO-POMDP are still at the beginning time, related theories and methods should beenexplored and researched.Whereas the above causes are specialized, this paper researches the model andalgorithms of first-order POMDP at the abstract level. In the aspect of modelresearching, we propose concept of first-order belief state, classifying state space byfirst order logic language, to reduce the dimensionality of general belief state; we alsopropose an updating method of first order belief state in the abstract level; thenFOB-POMDP is constructed. In the aspect of algorithm researching, we propose themethod of summing up the granularity of first-order belief state, this method is based onfluent critical degree for consolidating the granularity of first order belief state; we alsoexpress the PBVI with the framework of fluent calculus. FO-PBVI algorithm in theabstract level is proposed for sloving the FOB-POMDP. We propose the concept ofFO-ADD based on ADD. Then we denote the FO-PBVI with the FO-ADD form, andcompare the performance of these two forms by experiments. We apply theFOB-POMDP to cyber-physical system (CPS), forming a comparatively integritytheoretic and methodological system which is form model to algorithm, form algorithmto application. Detailed speaking, the main contributions of this paper are as follows:(1) We propose a denoting method of belief state and its updating method in theabstract level. We build the FOB-POMDP model.We bring forward the concept of first-order belief state through classifying thestate space and describing the belief state in the abstract level. Then we propose anupdating method of first-order belief state in the abstract level based on related theory offluent calculus, aiming at stochastic observed and transmitted actions. So acomparatively perfect abstract POMDP model named FOB-POMDP is constructed.FOB-POMDP is simple and compact. It integrates the dynamic characteristic of POMDP, ability of abstract generalizing and logci expression.(2) First-order belief point-based value interation for FOB-POMDP is proposed.We research on the first-order belief state in the abstract level, including items asfollows: we put forward the concept of first-order delief state granularity which is usedfor measurement the thickness degree of classifying state space in first order belief state;we propose summing up method of granularity which is used for summing up thedefferent first-order belief state to the same granularity. On the foundation of aboveresearching, we lift the PBVI to FO-PBVI, including all of the operations used in thePBVI, such as distance between the first order belief states, value updating on the firstorder belief state, and the collect of first-order belief states. Our simulation-basedexperimental studies show that our method can solve huge scale programming problembecause the solving time is not affected by the scale of problem.(3) FO-ADD denoting method of FO-PBVI is proposed.Firstly, we propose constructed method of FO-ADD based on fluent critical degree,this method abstract ADD to first-order logic level, then implement different kinds ofelements and basic operations, including fisrt-order belief state, αCase elements andupdating of first-order belief state, casemax, x and progression by FO-ADD. So theoperations in the FO-PBVI are expressed by FO-ADD, such as the operations of backupand COLLECT. The experiments show that FO-ADD denoting method based on theFO-PBVI can solve huge scale problems, however, solving time is a little longer thanFO-PBVI.(4) CPS decision-making system based on FOB-POMDP is designed andimplemented.At first, we analyze the concept, characteristic and decision-making trait of CPS,and then we implement the model and algorithm of FOB-POMDP to CPSdecision-making. CPS decision-making system based on the FOB-POMDP not onlyrealizes the engineer practice of FOB-POMP model and algorithm, but also providesdecision support for development and applications of CPS.(5) Evolution strategy based value iteration is proposed to solve the POMDPproblem.We research not only on the FOB-POMDP model and solving method in theabstract level, but also on the solving methods of general POMDP model. We proposePOMDP iteration algorithm based on genetic algorithm. ESVI (Evolution strategy basedvalue iteration) selects optimal action under certain belief state via constructing utilitymatrix based on random iteration process, after which adopts Bayesian rule to updatebelief state. Random iteration process selects population using evolution strategy andupdate utility matrix due to the selected population. The Tag problem and Hallway2problem are solved using ESVI, experiments show that ESVI can obtain better profitvalue and approximate optimal action atrategy when solving POMDP problems. In conclusion, this paper extends the solving scope of POMDP planning method byreaserching on FOB-POMDP model and algorithms in the abstract level. It has theoreticsignificance because it develops the research field and proposes a new efficientintelligent programming method; it also has practice significance because it provide thedecision support for development of CPS and impulse the development of huge scaleintelligent system such as CPS.