2012 | OriginalPaper | Chapter
Messy Genetic Algorithm for the Optimum Solution Search of the HTN Planning
Authors : Jiangfeng Luo, Cheng Zhu, Weiming Zhang
Published in: Foundations of Intelligent Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The classic algorithms of Hierarchical Task Network (HTN) planning focus on searching valid solutions with knowledge learning or heuristic mechanisms. However, there is little work on the planning optimization, especially on handling the problem in the situation that there is little heuristic knowledge to guide the optimum solution search process while many non-optimum solutions exist, or there is significance interactions between the abstract intermediate goals as which are not independent. This paper put forward a messy genetic algorithm (MGA) to solve the optimum solution searching problem of HTN planning in the above situations. Length-variant chromosome is introduced to represents the possible planning solution in form of decomposition tree with dynamic node numbers. Simulation results indicate that the MGA can locate the optimum solution among the huge search space with about 3×2
14
possible solutions within 6 seconds.