Research And Accomplishment Of Temporal Planning With Long Distance Mutual Exclusion

In recent years, intelligent planning and plan recognition is a hot research branch in AI. Intelligent planning is used widely in many fields including spacecraft, human-machine interaction, and language understanding. Lots of famous scholars home and abroad devote themselves to the research of intelligent planning in these several years, and specially, professor A.L.Blum and M.L.Furst provided the Graphplan algorithm which caused revolutionary progress in the intelligent planning area. However, the prevenient intelligent planning problems were all restricted to the STRIPS domain, i.e. classical intelligent planning problem which could not handle all real world problems. So, people tried to relax the restrictions of classical planning problem, and brought many new planning problems, such as probability planning, conformant planning and temporal planning and so on.Mutex is widely used in the solutions of intelligent planning problems. If we have good mutex method, we can get excellent efficiency in the process of finding solution. Forasmuch, there must have mutex in intelligent planner. But, all previous classical mutex can only detect the constraints between propositions or actions at the same time step. In 2007, Yinxin Chen proposed a new kind of mutex, long-distance mutual exclusion, which extended the area of mutex, prune the searching space, and improved the planning efficiency.Classical planning ignore the executing process, and make its action time to be a time point during that capture the effects of action. As all we known, there is a time duration for every actions. Temporal planning handle this special kind of actions which bring in time duration, and it must consider the start time and duration of actions. Depending on the classical intelligent planner, there are many outstanding temporal planners such as TGP, SAPA, CPPlanner. However, these temporal planners are all resticted to the classical mutex constraints, and didn't consider the minimum distance between actions or propositions.In our research, we analyse the relationship of original classical mutex and long-distance mutex, study the characteristic of temporal planning problem, and then propose new temporal long-distance mutual exclusion constraint, t-londex. We reserve the classical mutex's efficiency, and more, we bring in new temporal long-distance mutex constraints, in order to prune research space better and improve the efficiency of temporal planning system.