顺序价值迭代算法求解不确定规划.pdfVIP

第1期 微处理机 No．1 2011年2月 MICROPROCESSORS Feb．．2011 顺序价值迭代算法求解不确定规划 刘小飞1，杨大全1，李明杰2，聂庆欣3，杨婷婷1 (1．海南大学三亚学院理工分院，三亚572022； 2．海南大学三亚学院公共基础分院，三亚572022；3．敦化市职业技术学院，敦化133700) 摘要：基于Markov决策过程(MDP)的规划方法可以处理多种不确定规划问题，价值迭代算 法(VI)是求解MDP的经典算法，但VI需要计算更新每个状态的值，求解过程相当缓慢。在分析 了MDP状态图本身的因果依赖关系的基础上，提出一种改进的价值迭代算法，称为顺序价值迭代 算法(sVI)。它先将一个MDP分解成多个拓扑有序的强连通分量，然后应用价值迭代算法顺序求 解各个分量，这样处理可以避免对大量无用状态的计算并使得可用状态排成拓扑序列。对比实验 结果证明了该算法的有效性及优异性能。 关键词：智能规划；不确定规划；Markov决策过程；价值迭代 DOI编码：10．3969／i．issn．1002—2279．2011．01．020 中图分类号：TP319文献标识码：A ValUeIteratiOnfOr SeqUentiaI SOIvinqUnCertaintVPIanning LIU Xiao—feil，YANCDa—qualll，UMing—jie2，NIEQing—xin3，YANGTing一￡in91 (1．coffe酽。厂5ci肌ce。ndE增in船^昭，执iⅣ。，t‰觇mi￡yS0n地co讹驴，＆n弘572022，C硒w； 2．Co如geQ厂Com脚n曰∞ic＆duc础!Dn，舶iⅣⅡn‰i勘e”蚵乩儿沌cDfZ昭e，So，咿572022，∞i舱； 3．DunⅣuol，0cofio，tⅡf一￡ec^ni(·ofSc^oof．Di‘，o^un133700．C^!n血) methodof basedonMarkovdecision handlea of Abstract：The va矗ety planning process(MDP)can uncertain thevalueiteration isaclassical for planningpmblems，and algorithm(VI) aIgorithmsolving VIneedtocalculatetheValueofeach solution is slow．Inthis we MDP，but state，the processVery paper thecausal relationsthestatesina we thevalueiterative analyze dependenciesamong MDP，andimpmVed Valueiteratjon aMDPinto algorithm，calledsequential algorithm(SVI)，itdecompose strongtopological orderconnected then valueiteration tosolvethe in components，andusing order