Research On Uncertainty Planning Algorithms

Artificial intelligence planning (AI planning) is one of the most advanced research areas of AI, and it is also a intercrossed subject, which contains knowledge representation, automated reasoning, nonmonotonic logic, human-computer interaction, cognitive science and so on. Researches on classical planning can be traced back to the initial developmental stage of AI. STRIPS, the first major planning system based on first-order predicate logic, was proposed by Nilsson in 1971. It can be seen as the rudiment of the planners nowadays. Blum and Furst proposed the Graphplan method based on planning graph, and designed an excellent planner named Graphplan. This approach makes artificial intelligence planning one of the hotspots of AI so far.It needs to emphasize that classical planning methods are mainly established on the base of strict restrictions, that is the information about planning problems is complete for planning agent; the effects of actions during planning process are deterministic; the actions can be seen as instantaneous transitions between different states without durative effects; the initial state is unique; the goal condition is deterministic and so on. All restrictions limit the extensive applications in real world problems to a great extend.Uncertainty planning is a further extension and the complement of classical planning. Based on classical planning, it is established by reinterpreting and extending the planning problem definitions, modifying operator rules and environment parameters, appending assistant information and so on. Uncertainty planning can obtain an optimal or sub-optimal plan, getting rid of the interference of uncertainty factors during planning process.In order to promote in-depth research on planning, the International Conference of Artificial Planning and Scheduling (ICAPS) held the first International Planner Competition (IPC) in 1998. Subsequently, it holds the IPC biyearly to promote the development of researches on AI planning. In 2004, the uncertainty planning problems were added to the benchmarks for standard testing for the first time. From that time, the relevant researches on uncertainty planning have been the hotspots of AI gradually. International journal of Artificial intelligence published a special issue on uncertainty planning in 2003.The mainstream aspects in uncertainty planning include the improvement of uncertainty planning efficiency, the guarantee of uncertainty planning algorithms'robustness, and the applications in real controlling systems. Simultaneously, the development of uncertainty planning will promote the classical planning researches.Compared with classical planning, uncertainty planning has more expressive and extensive application areas. However, it lacks of precise problem specifications and effective planning algorithms. For the complex problems, uncertainty planning usually can't find better solving policies. Therefore, it is important issue for us to find robust uncertainty planning algorithms.In this paper, we introduce the uncertainty planning problems and a sequence of relevant LAO* algorithms. And then we propose the robust methods to solve the uncertainty planning problems, in which the transition probabilities of actions are probabilistic intervals.Firstly, we define the conception of generalized interval of transition probabilities based on our problem specifications, which are up to real world problems. And then we define the expectation, the variance of generalized interval and the relevant computational formulae. We can estimate the utilities of different actions by comparing the expectations and the variances of generalized intervals of different useful actions of current state. Thirdly, we propose and implement an extension of uncertainty planning algorithm: GILAO* (Generalized Intervals-based LAO*) algorithm, which bases on the comparison of generalized intervals.We redesign the benchmark problems Race Track, and give the revision problems, which are more difficult and complex than before. After running LAO* algorithm, rLAO* algorithm and GILAO* algorithm on the revision planning problems respectively, we analysis the experimental results and validate the soundness of GILAO* algorithm. Finally, we demonstrate that GILAO* algorithm is sound and complete. We also briefly describe the qLAO* (Qualitative LAO*) algorithm, whose implementation is a revision of rLAO*.Extension rule (ER) method is a new theorem proving method, which appreciates to the knowledge expressions containing many mutual literals among the clauses. In this paper, we design and implement the ER methods based on propositional logic, modal logic and possibility logic. We demonstrate the validity and the adaptability through a great number of experimental results.Propositional ER method is an effective theorem proving method and the foundation of ER methods based on other non-classical logics. The implementation of modal ER method combines modal logic K with destructive ER. The destructive ER algorithm DMKER in K is sound and complete theoretically. In relevant experiments, DMKER is used to solve all of the axioms and some benchmark problems in modal logic K.ER method can be applied into the processing of possibility knowledge effectively. We propose the Incons-SPL algorithm to compute the inconsistent degree of a possibility formula set and test the random problems, which contain 15 variables, 200 or 400 clauses. The experimental results validate the soundness of this algorithm. Knowledge compilation method with possibility ER in finite steps obtains the theory, in which each pair clauses contain mutual literals. The theory obtained appreciates to the application of ER.The experimental results illustrate that ER method can be used in modal logic, possibility logic and other non-classical logics. The efficiency and problem solving capability of ER method provide a solid foundation for planning as ER method and relevant planners.