计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2012年
8期
1620-1633
,共14页
梁瑞仕%姜云飞%边芮%陈蔼祥
樑瑞仕%薑雲飛%邊芮%陳藹祥
량서사%강운비%변예%진애상
前向规划%启发式搜索%领域无关剪枝策略%前向搜索邻居%完备搜索
前嚮規劃%啟髮式搜索%領域無關剪枝策略%前嚮搜索鄰居%完備搜索
전향규화%계발식수색%영역무관전지책략%전향수색린거%완비수색
前向启发式搜索和放宽规划方法被很多领域无关的规划器所采用,被认为是一种有效的规划范型.FF规划器利用放宽规划图计算状态的启发式估值,并提取有利动作集合进行前向搜索的剪枝.但过大的有利动作集合造成了过多的消耗.文中提出了一种新的高质量的领域无关剪枝策略.该策略根据放宽规划图的动作层和命题层之间的关系,提取出所谓的直接效用动作集合,此集合之外的其它动作都被剪枝.直接效用动作集合比FF的有利动作集合更加精简,更具启发性,能指导前向搜索集中在那些离目标更近的状态.根据直接效用动作作者开发了一种新的lookahead搜索邻居,并应用在改进后的增强型爬山搜索算法中,使得前向搜索具备良好的前瞻性.当增强型爬山法失败时,采取一种从局部极小值重启完备搜索的策略以保持系统完备性.通过对国际规划大赛基准问题的测试表明,基于该剪枝策略及前向搜索算法实现的前向规划系统有效地缩小了搜索空间,搜索的节点数目比FF的有利动作策略明显要少,搜索效率有显著的提升.
前嚮啟髮式搜索和放寬規劃方法被很多領域無關的規劃器所採用,被認為是一種有效的規劃範型.FF規劃器利用放寬規劃圖計算狀態的啟髮式估值,併提取有利動作集閤進行前嚮搜索的剪枝.但過大的有利動作集閤造成瞭過多的消耗.文中提齣瞭一種新的高質量的領域無關剪枝策略.該策略根據放寬規劃圖的動作層和命題層之間的關繫,提取齣所謂的直接效用動作集閤,此集閤之外的其它動作都被剪枝.直接效用動作集閤比FF的有利動作集閤更加精簡,更具啟髮性,能指導前嚮搜索集中在那些離目標更近的狀態.根據直接效用動作作者開髮瞭一種新的lookahead搜索鄰居,併應用在改進後的增彊型爬山搜索算法中,使得前嚮搜索具備良好的前瞻性.噹增彊型爬山法失敗時,採取一種從跼部極小值重啟完備搜索的策略以保持繫統完備性.通過對國際規劃大賽基準問題的測試錶明,基于該剪枝策略及前嚮搜索算法實現的前嚮規劃繫統有效地縮小瞭搜索空間,搜索的節點數目比FF的有利動作策略明顯要少,搜索效率有顯著的提升.
전향계발식수색화방관규화방법피흔다영역무관적규화기소채용,피인위시일충유효적규화범형.FF규화기이용방관규화도계산상태적계발식고치,병제취유리동작집합진행전향수색적전지.단과대적유리동작집합조성료과다적소모.문중제출료일충신적고질량적영역무관전지책략.해책략근거방관규화도적동작층화명제층지간적관계,제취출소위적직접효용동작집합,차집합지외적기타동작도피전지.직접효용동작집합비FF적유리동작집합경가정간,경구계발성,능지도전향수색집중재나사리목표경근적상태.근거직접효용동작작자개발료일충신적lookahead수색린거,병응용재개진후적증강형파산수색산법중,사득전향수색구비량호적전첨성.당증강형파산법실패시,채취일충종국부겁소치중계완비수색적책략이보지계통완비성.통과대국제규화대새기준문제적측시표명,기우해전지책략급전향수색산법실현적전향규화계통유효지축소료수색공간,수색적절점수목비FF적유리동작책략명현요소,수색효솔유현저적제승.
