Dynamic Uncertain Environment Under Real-time Planning System

As a very important and familiar intelligent activity a capability, planning is one of the key fields in artificial intelligence research. It had received attentions very early before. Planning in dynamic nondeterministic environment becomes the focus and hot spot, since this environment is more real and the research on it is more valuable.In this thesis, main characters of dynamic non-deterministic environment are analyzed in the beginning. They areDynamic environment - The environment always keeps changing. It is affected not only by the agent itself but also by other agents and other factors in the environment.Limit knowledge of agents - In general, any agent has not all knowledge of the environment it lives. It can't know every factor which can affect the environment. And it also can not know other agents completely. One agent can only hold a part of them and even be utterly ignorant in some fields.Nondeterministic result of actions - Agents can perform some actions in the environment. But the results of these actions are not deterministic and unpredictable.Partial observation -- In general, agents' observations on the environment is partial. At each time, an agent can only observe a part of the situation of the environment.Nondeterministic observation -- agents' observations on the environment could be not accurate and even be completely false.Then, existing planning systems are analyzed in the capability of adapting in dynamic nondeterministic environment. Advantages and shortcomings are pointed out.Besides analyzing above, the main work of this thesis is introducing a new planning system POMDPRS which is better on adapting dynamic nondeterministic environment. It's based on PRS and decision theory planning. This thesis also discusses two approaches to improve efficiency of decision making. Abstract details are as below1) A new planning system POMDPRS which is better on adapting dynamic nondeterministic environment is introduced. The basic model and formal description are provided. POMDPRS reserves the continued planning mechanism to adapt dynamic character and depicts the belief of an agent with a distribution over the state space to adapt nondeterministic character. Therefore, POMDPRS satisfied requirements on both sides.2) The factorial depiction of states in POMDPRS is introduced. And the formal description of factorial POMDPRS - FPOMDPRS - is provided. POMDPRS depicts the belief of an agent with a distribution over the state space, and updates the belief with actions the agent performed and observations it received. Unfortunately, in many cases, the state apace is very large. This makes time consuming of belief updating very high. It does meet the real-time requirement of system. Factorial approach divides the properties of the environment, which construct states, into groups according to their dependency relations. This makes a big state space change into several smaller sub-state spaces. Therefore the belief is also transform into several distributions over sub-state spaces. In this way, belief updating is performed in these sub-state spaces independently. The time consuming of belief updating is reduced.3) The Monte Carlo filter in POMDPRS is introduced. And the formal description of Monte Carlo filter POMDPRS - MCPOMDPRS -- is provided. Monte Carlo filter is another way to reduce time consuming of belief updating. It use limit number of values (known as samples) to descript the whole distribution. And this sample set is updated by SIR method with actions and observations. It makes the time consuming depend on the size of the sample set. Therefore, we can control the size of sample set to limit time consuming of belief updating.Factorial state and Monte Carlo filter can be combined to apply in POMDPRS. First, state is factorized. Then, Monte Carlo filter is introduced into the sub-state sets which are still large in size. In this way, the efficiency of belief updating can be more improved. This thesis also describes a robot control system called P-DOG which runs on real robots. It's an instance of the combination of FPOMDPRS and MCPOMDPRS. This system on real robot proves the feasibility of POMDPRS and its variations.