Research Of The Incremental Dynamic Probabilistic Planning

The research into intelligent planning, thanks to its contribution to artificial intelligence theory and broad applied foreground, is widely considered to be of essential importance. Recently, remarkable achievement has been witnessed. Meanwhile, to solve more factual and complex problems, researchers commit themselves to the study of uncertainty planning, in which one proper instance should be mentioned, the probabilistic planning.Researchers have investigated many probabilistic planning systems that allow one to solve shortest-path planning problems. However, while the environment changes, the original plans might no longer apply or might not be good enough anymore, therefore, corresponding systems should be replaned. It is true that the changes of the environment are usually gradual and therefore small, so the planning problems are more or less similar. In those gradual changes, there are many repeated plans and searching processes, and a complete computation of the best plan can be inefficient since some of the previous search results can be reused, which could be unbearable in some domains. How to remember the results of the plans and to seek a balance point between the time and the space is just what incremental search methods try to solve. Although there are some researches on the study of incremental planning, it is still not broad enough.In the thesis,we transforms the random probabilistic planning problem into the MDP problem and combines a heuristic search method to solve the shortest-path problem, and investigates the characteristics and disciplinarians of the method: when the environment changes, the system could be replaned by incremental planning. Through this, we could reduce the number of states and compute the heuristic value with speed and efficiency. The thesis aims at bringing forward the model and definition of the Incremental Dynamic Probabilistic Planning and designing relevant algorithms about the plan system.Moreover, all codes for the algorithm are written in C++, and a plan system about the racing car domain problem under linux system is also designed. The results of the experimentations prove the validity of the algorithm. Above all, the incremental plan minishes the state space and reduces the frequency of computing heuristic value, therefore save the time and enhance the continued plans'efficiency.