Messy Genetic Algorithm for Optimum Solution Search of HTN Planning
Jiangfeng Luo · Journal of Information and Computational Science · 2013
Hierarchical Task Network (HTN) planning algorithm focuses on searching valid solution using knowledge learning or heuristic mechanism. 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 while many non-optimum solutions exist, or there are significance interactions between the abstract intermediate goals which are not independent. This paper put forward a Messy Genetic Algorithm (MGA) to solve the optimum solution searching of HTN planning in the above situations. Length-variant chromosome is introduced to represent the possible planning solution in form of decomposition tree with dynamic node number. It’s proved that new offspring decomposition trees can be returned through exchanging the equivalence subtrees of two parental decomposition trees. Based on this proposition, the crossover operation of MGA can be successfully performed. 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.