电子科技大学学报
電子科技大學學報
전자과기대학학보
JOURNAL OF UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA
2013年
3期
464-468
,共5页
智能规划%启发式搜索%有序爬山法%状态适应度函数
智能規劃%啟髮式搜索%有序爬山法%狀態適應度函數
지능규화%계발식수색%유서파산법%상태괄응도함수
AI planning%heuristic search%ordered hill climbing algorithm%state adaptive function
根据快速前向启发式搜索规划器FF中放宽规划图和有利动作之间的关系,定义了状态适用度函数的概念,可对后继扩展状态的启发式估值进行快速近似的比较.在此基础上,结合增强型爬山法搜索后继状态的贪婪选择机制,提出了一种改进的局部搜索算法——有序爬山法,即根据状态适应度函数对所有待扩展的后继状态进行排序,并加入到扩展优先队列.在启发式估值阶段,适应度高的状态将被优先计算评估,有利于更快地发现较优状态,从而减少调用启发式估值程序的次数.通过在国际规划大赛基准测试领域的实验结果表明,该方法减少了搜索节点的数目和搜索时间,有效地提高了启发式搜索效率,而计算状态适应度及对状态进行排序的时间消耗几乎可以忽略,因此整体规划性能比FF有显著的提升.
根據快速前嚮啟髮式搜索規劃器FF中放寬規劃圖和有利動作之間的關繫,定義瞭狀態適用度函數的概唸,可對後繼擴展狀態的啟髮式估值進行快速近似的比較.在此基礎上,結閤增彊型爬山法搜索後繼狀態的貪婪選擇機製,提齣瞭一種改進的跼部搜索算法——有序爬山法,即根據狀態適應度函數對所有待擴展的後繼狀態進行排序,併加入到擴展優先隊列.在啟髮式估值階段,適應度高的狀態將被優先計算評估,有利于更快地髮現較優狀態,從而減少調用啟髮式估值程序的次數.通過在國際規劃大賽基準測試領域的實驗結果錶明,該方法減少瞭搜索節點的數目和搜索時間,有效地提高瞭啟髮式搜索效率,而計算狀態適應度及對狀態進行排序的時間消耗幾乎可以忽略,因此整體規劃性能比FF有顯著的提升.
근거쾌속전향계발식수색규화기FF중방관규화도화유리동작지간적관계,정의료상태괄용도함수적개념,가대후계확전상태적계발식고치진행쾌속근사적비교.재차기출상,결합증강형파산법수색후계상태적탐람선택궤제,제출료일충개진적국부수색산법——유서파산법,즉근거상태괄응도함수대소유대확전적후계상태진행배서,병가입도확전우선대렬.재계발식고치계단,괄응도고적상태장피우선계산평고,유리우경쾌지발현교우상태,종이감소조용계발식고치정서적차수.통과재국제규화대새기준측시영역적실험결과표명,해방법감소료수색절점적수목화수색시간,유효지제고료계발식수색효솔,이계산상태괄응도급대상태진행배서적시간소모궤호가이홀략,인차정체규화성능비FF유현저적제승.
