Planning Encodings Based On Quantified Boolean Formulas

Intelligent planning is an important branch in the field of artificial intelligence. In recent years, many domestic and foreign researchers have paid attention to it. And it had been developed quickly. In the real world, the different constraint conditions such as environment, resources, time and operations and so on depict the different kinds of intelligent planning problems. Early intelligent planning research mainly aimed at classic planning with many assuption. This strictly definition on time, world and even the actions usually doesn't accord with the actual needs. With the deep research, the researchers focused on non-deterministic programming problems that are much more difficult. It is also marked the intelligent planning research is gradually approaching to the practicability of the model.Non-deterministic planning problem is mainly divided into:conformant planning problem, conditional planning problem, probability planning and conditional probability planning problem, etc. Non-deterministic planning problem allows the non-deterministic existence of the action and the state which is more according with that people often don't know enough about the reality of the situation about the resources or environment. When the conditional planning problem is confined with no observation, it is exactly the famous conformant planning problem.Solving some non-deterministic planning problems based on Quantify Boolean Formulas (Quantified Boolean Formulas, the abbreviation QBF) evidently shows better performance, such as conditional planning problems. Obviously, the planning system which is based on QBF can be applied to solving conformant planning problems.This article mainly aims at the research on the non-deterministic planning problems. It puts forward an conditional planning and conformant planning encoding method based on Quantify Boolean Formulas forms——QBF-Cplan encoding. The specific design method are as these follows:First, it puts forward the action pretreatment encoding. It defines the non-deterministic effect of the conditional planning and conformant planning problems. It puts forward the pretreatment way by defining U-E and the execute conditions of the effect——U-E-exeC encoding. And it uses the U-E-exeC encoding describ the explanatory framework and the actual execution about the operation of the planning problems. It explains the execution of the U-E-exeC encoding by the example.Then, it gives the related contents about QBF-Cplan logical planning encoding. It puts forward the QBF planning system composition and planning framework. QBF-Cplan planning encoding frame. And it uses the U-E-exeC encoding in the QBF-Cplan action pretreatment part. Then, it introduces QBF-Cplan logical encoding and analyses through the example of the non-deterministic planning problems.Compared with the other solving conditional planning problem or conformant planning problem method based on QBF, QBF-Cplan encoding has the lower complexity. Compared with other planning systems of solving non-deterministic planning problems, the main advantage of the QBF-Cplan encoding is its flexibility. It can be applied to any different forms of QBF solver. Based on different kinds of QBF solver, this QBF-Cplan logical encoding can produce different effects of executions. When the QBF solver is created and it is suitable enough for the QBF-Cplan logical planning encoding, the efficiency of the QBF-Cplan logical planning encoding will be considerable.