针对路标的启发式搜索智能规划方法的分析研究.pdf

重庆邮电大学硕十论文摘要摘要启发式搜索是智能规划领域的重要方法之一,其策略核心为启发式函数的拟定。路标是规划任务中成功规划必须实现的子目标,实验证明,基于路标的启发函数能有效引导启发式搜索过程并提高规划成功率和规划解质量。尽管基于路标的启发函数得到了一定的应用,但仍有一些问题需要进一步研究,如函数的可纳性、搜索代价等问题,本文针对此类问题进行了如下研究: 首先,为了增加路标启发函数的代价信息,在命题路标与动作路标提取的基础上结合动作路标的计数算法,改进了基于放松规划图扩张的事实和动作路标的提取过程,并结合事实路标的代价共享完善了新的路标提取结构。其次,随着路标探测的完备性提高,路标统计策略在提高规划质量的同时要求更高的开销。据此本文提出了一种将动作信息计数融入路标统计中去冗的方法,并采用双路标估算代价平衡函数的性能和开销,并证明了新函数的可纳性。最后,对传统的启发式规划器进行了路标信息的提取和路标函数的添加,设计完成了新的双路标启发规划系统,并对已发布的标准规划领域进行求解实验,结果表明新系统在规划效率和质量上都有一定改进。关键词:智能规划,启发式搜索,路标,动作路标,代价共享 Abstract Heuristic searching,guided by aheuristic function in astate—space search, is one ofthe most important methods ofintelligence planning problems. Landmarks for aplanning task are thesub goals that are necessarily made true at some time step for any ess isshowed that landmarks information can improves the heuristic planners inboth essful rate and thequality oftheplans. Though the heuristic with landmarks information are developed and applied is stillnecessary tofurther study some issues,such as the admissible ofthefunction and thesearching dissertation addresses thefollowing issues: Firstly,the count fortheaction landmarks istaken into account inthe extraction ofboth action and factlandmarks based on an adapted Relaxed Planning Graph propagation more cost knowledge,the algorithm is bined with the cost sharing offactlandmarks. thefurther requirement on landmarks counting heuristic functions on larger and plete landmark sets,a new landmark heuristic isproposed based on themutual landmarks counting and interaction restrictbetween them tobalance the performance andthe the prove of the new admissible heuristic iSgiven. Finally,the system isimplementing by feeding the landmark heuristic period to amodified FF planner results show thatthe new planning structure improves the plan quality on both the space cost and ESSful rate. Key words:intelligence planning,heuristic search,landmarks,action landmarks,