制定复杂决策(第17章)教学资料.ppt
制定复杂决策(第17章)0871-503130116 十一月 20222/信 息 学 院人工智能 一种现代方法延续式决策问题延续式决策问题 延续式决策问题：智能体的效用值取决于一个延续式决策问题：智能体的效用值取决于一个决策序列。效用函数不是由单一状态决定，取决于决策序列。效用函数不是由单一状态决定，取决于环境历史的一个状态序列。环境历史的一个状态序列。+1-1完全可观察环境完全可观察环境随机行为随机行为一阶马尔可夫转移一阶马尔可夫转移效用函数取决于状态序列效用函数取决于状态序列0.80.10.1up,up,right,right,right 0.85=0.32768成功概率：成功概率：0.14*0.8+0.85=0.32776转移模型转移模型 T(s,a,s):在状态在状态s完成行动完成行动a时到达状态时到达状态s的概率的概率0871-503130116 十一月 20223/信 息 学 院人工智能 一种现代方法0871-503130116 十一月 20224/信 息 学 院人工智能 一种现代方法0871-503130116 十一月 20225/信 息 学 院人工智能 一种现代方法0871-503130116 十一月 20226/信 息 学 院人工智能 一种现代方法延续式决策问题中的最优化（稳态）延续式决策问题中的最优化（稳态）假设智能体在状态序列之间的偏好是稳态的：假设智能体在状态序列之间的偏好是稳态的：若若s0,s1,和和s0,s1,以同样的状态起始，则以同样的状态起始，则两个序列的偏好次序和状态序列两个序列的偏好次序和状态序列s1,s2,和和s1,s2,的偏好次序是一致的。的偏好次序是一致的。计算状态序列的效用值，稳态性假设下的两种方法：计算状态序列的效用值，稳态性假设下的两种方法：累加回报：状态序列的效用值是各状态回报的累加和。累加回报：状态序列的效用值是各状态回报的累加和。Uh(s0,s1,sn)=R(s0)+R(s1)+折扣回报：状态序列的效用值是各状态回报的加权（折扣因子）折扣回报：状态序列的效用值是各状态回报的加权（折扣因子）累加和。折扣因子用于描述智能体对于当前与未来回报的偏好。累加和。折扣因子用于描述智能体对于当前与未来回报的偏好。0871-503130116 十一月 20227/信 息 学 院人工智能 一种现代方法延续式决策问题中的最优化延续式决策问题中的最优化无限期决策，效用值的计算的三种方法无限期决策，效用值的计算的三种方法:1、折扣回报：状态序列的效用值是各状态回报的加权、折扣回报：状态序列的效用值是各状态回报的加权(折扣因子）折扣因子）累加和。累加和。2、适当策略：确保能够达到终止状态的策略，可使用累积回报。、适当策略：确保能够达到终止状态的策略，可使用累积回报。3、平均回报：每一个时间步回报的平均数。、平均回报：每一个时间步回报的平均数。策略的值是所得到的折扣回报的期望和。策略的值是所得到的折扣回报的期望和。最优策略最优策略:0871-503130116 十一月 20228/信 息 学 院人工智能 一种现代方法价值迭代价值迭代基本思想：基本思想：计计算每个状算每个状态态的效用，以的效用，以选选出每个状出每个状态态中中的最的最优优行行动动。选择选择使后使后续续状状态态的期望效用最大的行的期望效用最大的行动动：*(s)=argmax a s T(s,a,s)*U(s)价值迭代算法：把每个状态的效用与其邻接状态的效用关联起来：价值迭代算法：把每个状态的效用与其邻接状态的效用关联起来：（贝尔曼方程）（贝尔曼方程）即当智能体选择最优行动，状态的效用值是在该状态得到的立即即当智能体选择最优行动，状态的效用值是在该状态得到的立即回报加上在下一个状态的期望折扣效用值。回报加上在下一个状态的期望折扣效用值。状态的效用值：可能跟随它出现的所有状态序列的期状态的效用值：可能跟随它出现的所有状态序列的期望效用值。望效用值。0871-503130116 十一月 20229/信 息 学 院人工智能 一种现代方法价值迭代价值迭代 价值迭代法总是价值迭代法总是收敛收敛到贝尔曼方程组的到贝尔曼方程组的唯一唯一解上。而对应的解上。而对应的策略是最优的。策略是最优的。贝尔曼更新贝尔曼更新迭代求解：迭代求解：+1-10871-503130116 十一月 202210/信 息 学 院人工智能 一种现代方法策略迭代策略迭代策略：指定智能体在可能达到的任何状态下智能体应策略：指定智能体在可能达到的任何状态下智能体应采取的行动。采取的行动。最优策略：就是产生最高期望效用值的策略。最优策略：就是产生最高期望效用值的策略。策略迭代：交替执行用当前策略计算状态的效用和用当前的效策略迭代：交替执行用当前策略计算状态的效用和用当前的效用改进当前的策略。用改进当前的策略。策略评价：对拟执行的策略策略评价：对拟执行的策略i 进行评价，计算进行评价，计算Ui=Ui，即该策，即该策略被执行后每个状态的效用值。略被执行后每个状态的效用值。策略改进：通过策略改进：通过Ui，计算新的，计算新的MEU策略策略i+1。每次迭代都将产生更好的策略。直到效用值不变，算法终止。则每次迭代都将产生更好的策略。直到效用值不变，算法终止。则该效用值也是贝尔曼方程组的解，该效用值也是贝尔曼方程组的解，i 一定是最优策略一定是最优策略。0871-503130116 十一月 202211/信 息 学 院人工智能 一种现代方法策略评价策略评价 n n个状态有个状态有n n个方程和个方程和n n个未知量，可用线性代数方法求解。个未知量，可用线性代数方法求解。也可用价值迭代计算效用值的近似：也可用价值迭代计算效用值的近似：修正策略迭代修正策略迭代异步策略迭代：每次迭代只更新部分选中的状态。异步策略迭代：每次迭代只更新部分选中的状态。+1-10871-503130116 十一月 202212/信 息 学 院人工智能 一种现代方法部份可观察的部份可观察的MDPMDP（POMDPPOMDP）智能体并不知道自己所处的状态，也不能给出其智能体并不知道自己所处的状态，也不能给出其转移模型，所以无法执行转移模型，所以无法执行(s)为该状态推荐的行动。为该状态推荐的行动。安全策略：安全策略：尽量向减少不确定的方向移动。尽量向减少不确定的方向移动。+1-10871-503130116 十一月 202213/信 息 学 院人工智能 一种现代方法部份可观察的部份可观察的MDPMDP（POMDPPOMDP）观察模型观察模型O(s,o):指定在状态指定在状态s感知到感知到o的概率。的概率。信度状态信度状态b：所有可能状态上的概率分布。：所有可能状态上的概率分布。例如：例如：3个状态的环境，个状态的环境，b(s):信度状态赋予实际状态信度状态赋予实际状态s的概率。的概率。更新信度状态：更新信度状态：最优策略：最优策略：最优行动取决于当前智能体的信度状态，最优行动取决于当前智能体的信度状态，*(b).0871-503130116 十一月 202214/信 息 学 院人工智能 一种现代方法POMDP智能体决策智能体决策过过程：程：（1）给给定当前的信度状定当前的信度状态态b，执执行行行行动动a=*(b).（2）得到）得到观观察察o（3）更新信度状）更新信度状态为态为Forward(b,a,o)，重复上述步，重复上述步骤骤。给定行动给定行动a，从，从b到到b的概率：的概率：信度状态空间的转移模型信度状态空间的转移模型信度状态空间的回报函数：信度状态空间的回报函数：求解求解POMDP可归约为信度状态空间上求解可归约为信度状态空间上求解MDP0871-503130116 十一月 202215/信 息 学 院人工智能 一种现代方法决策智能体的设计决策智能体的设计1、用动态贝叶斯网表示转移和观察模型。、用动态贝叶斯网表示转移和观察模型。2、用决策和效用节点扩展动态贝叶斯网，产生动态决策网络、用决策和效用节点扩展动态贝叶斯网，产生动态决策网络(DDN)。3、用滤波算法把每个新的感知信息与行动结合起来，对信度、用滤波算法把每个新的感知信息与行动结合起来，对信度状态表示进行更新。状态表示进行更新。4、通过向前投影可能的行动序列选择最佳行动制定决策。、通过向前投影可能的行动序列选择最佳行动制定决策。0871-503130116 十一月 202216/信 息 学 院人工智能 一种现代方法决策智能体决策智能体At-2Xt-1Rt-1Et-1At-1XtRtEtAtXt+1Et+1At+2Xt+3Et+2Ut+3Xt+2At+1Rt+1Rt+2Et+30871-503130116 十一月 202217/信 息 学 院人工智能 一种现代方法
