主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
范长杰,陈小平.实时动态规划的最优行动判据及算法改进.软件学报,2008,19(11):2869-2878
实时动态规划的最优行动判据及算法改进
Optimal Action Criterion and Algorithm Improvement of Real-Time Dynamic Programming
投稿时间:2007-10-10  修订日期:2008-02-04
DOI:
中文关键词:  马尔可夫决策过程  实时动态规划  收敛判据  增量求解  启发式搜索
英文关键词:MDP (Markov decision process)  RTDP (real-time dynamic programming)  convergence criterion  incremental solving  heuristic search
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60745002 (国家自然科学基金); the National Basic Research Program of China under No.2003CB317002 (国家重点基础研究发展计划(973))
作者单位
范长杰 中国科学技术大学 计算机科学与技术系,安徽 合肥 230027 
陈小平 中国科学技术大学 计算机科学与技术系,安徽 合肥 230027 
摘要点击次数: 2817
全文下载次数: 4006
中文摘要:
      主要以提高求解马尔可夫决策问题的实时动态规划(real-time dynamic programming,简称RTDP)算法的效率为目的.对几类典型的实时动态规划算法所使用的收敛判据进行了对比分析,并利用值函数上界、下界给出了称为最优行动判据的收敛判据,以及一个更适合实时算法的分支选择策略.最优行动判据可以更早地标定当前状态满足精度要求的最优行动供立即执行,而新的分支选择策略可以加快这一判据的满足.据此设计了一种有界增量实时动态规划(bounded incremental RTDP,简称BI-RTDP)算法.在两种典型仿真实时环境的实验中,BI-RTDP均显示出优于现有相关算法的实时性能.
英文摘要:
      This paper is primarily to improve the efficiency of real-time dynamic programming (RTDP) algorithm for solving Markov decision problems. Several typical convergence criteria are compared and analyzed. A criterion called optimal action criterion and a corresponding branch strategy are proposed on the basis of the upper and lower bound theory. This criterion guarantees that the agent can act earlier in a real-time decision process while an optimal policy with sufficient precision still remains. It can be proved that under certain conditions one can obtain an optimal policy with arbitrary precision by using such an incremental method. With these new techniques, a bounded incremental real-time dynamic programming (BI-RTDP) algorithm is designed. In the experiments of two typical real-time simulation systems, BI-RTDP outperforms the other state-of-the-art RTDP algorithms tested.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利