Admissible Landmark Ordering And It's Application In Ai Planning

AI Planning is an important branch of Artificial Intelligence.In recent years,major breakthroughs have been made in the field of AI planning.There have been significant improvements in the scale and the efficiency of the solution,besides,successes have been achieved in many practical fields.However,there are still many problems that need to be solved in large-scale planning domains.On the other hand,from the perspective of application,AI planning is not widely used in reality world.Further researches are still needed in modeling and solving the complex real-world domain planning problems.The work of this thesis focuses on two core issues,exploring methods and techniques to improve the efficiency for large-scale planning problems,and solving realistic problems based on AI planning technology.This thesis starts with the landmark sorting method,and studies the related methods and techniques of using landmark information to improve the planning efficiency.On the other hand,from the perspective of the application,we analyze the characteristics of warehouse field,build knowledge modeling in warehouse domain,and propose an AI planning solution for warehouse problems.The main work of this thesis is as follows:1.Landmark ordering relationship is of great significance for landmark information heuristic search planning algorithm.However,the existing ordering relationship solving methods require strict constraints,thus it's difficult to find complete landmark ordering relationship in many fields.This thesis proposes a new landmark ordering relationship,named admissible ordering.We present a formal definition of admissible ordering relation,then one sufficient condition and its strict proof are given for the admissible ordering relationship.A polynomial time complexity algorithm is given to approximate the landmark admissible ordering.We designed an Admissible Landmark Ordering Planner(ALOP),which is based on LMC heuristic and admissible ordering.All the ideas presented in the thesis are implemented in our planning system and the effectiveness of our techniques is demonstrated on benchmarks from IPCs.The results show that our techniques can efficiently solve large scale planning problems and lead to great improvement on planning performance.2.A complete set of prototype solutions,named WUPT,to solve the storage and delivery scheduling problems in automated storage area is provided.The application of AI planning technology has certain requirements about the domain.This thesis analyzes some restrictions on the application of AI planning technology in the field of reality.We studied the current status and characteristics of robots in warehousing and logistics.Based on the characteristics of intelligent planning technology and warehouse domain,the feasibility of applying intelligent planning technology in storage field is discussed.A complete set of feasible plans for the application of intelligent planning technology to the overall planning and scheduling of warehousing logistics robots is given.Through a simple example,it is proved that intelligent planning technology can effectively solve the multi robot scheduling problem in warehousing field,and has good scalability and portability.