A Conformant Planning Method Based On Ordered Hill Climbing Search

AI planning is an important subject in artifical intelligence,mainly focus onplanning and tasks scheduling or sorting action sequence,has both research andapplication value,is an important field which is concerned by artificial intelligenceresearchers.Uncertain programming is a kind of AI planning.Uncertain programmingremove some unrealistic assumptions from traditional planning,add a series ofconditions and parameters,aimed at the planning problem which has uncertain initialconditions and actions,is closer to reality,which has both research and applicationvalue.The research on uncertain programming will make AI planning more useful inreality.Compared with the traditional ones,Uncertain planner is more suitable fordealing with the real problems.The conformant planning is an important sub-area inplanning research which received high attention,which means the planning problem must get the plan on condition that the initial condition and the action effect isuncertion,and the Agent can achieve the external knowledge on its own.This paper compared with the similar work at home and abroad,based on theConformant Fast-forwad(CFF),refer to the core method of CFF--greedy selectionmechanism, which named enforced hill climbing search,and improved the enforcedhill climbing search.In view of the disadventage of enforced hill climbing that in theheuristic search the there is no sorting in expand nodes,and the search isrecklessly,make full use of the domain knowledge,propose the concept of state offitness and fitness function.The state of fitness can be calculated according to therelaxed planning graph and the implication diagram.An ordered hill climbing searchmethod is proposed in this paper as a better method.Ordered hill climbing methodcan quickly evaluate and compare the node to be extended,sort the node in heuristicsearch,call SAT less times,which bring the search cost less resource,and improve theefficiency of the algorithm.A COFF planner is designed based on the open-source planner CFF whichprovided by HOFFMANN et al.,experiments is done in Logistics and Depots domains of IPC to compare the COFF and CFF,evaluate the availability and qualityof ordered hill climbing.Experiments shows that the ordered hill climbing search canimprove the speed of the heuristic search and reduce the search nodes and timesignificantly.The ordered hill climbing search method can improve the efficiency ofthe heuristic search in dealing with a certain scale of the problems,is a kind ofeffective method.