论文部分内容阅读
随着嵌入式设备和人工智能技术的飞速发展，大型智能系统逐渐渗入到人们生活的方方面面，并起着越来越重要的作用。这些系统所处的环境大都是不确定的，而且系统规模越来越大，如何在不确定环境下设计出能够适应大规模系统的决策方法成为了当前人工智能领域最为重要的研究课题之一。常规的状态枚举式POMDP及其求解方法往往被作为解决不确定环境中规划问题的重要方法，但是目前可以求解的规划问题状态数量仍然只限于数百个，求解问题的规模尚不能满足规模日益增大的智能系统的需要。为了解决这个问题，出现了在抽象层次上，利用问题结构特征，解决大规模规划问题的FO-POMDP模型及算法。但是目前FO-POMDP的模型和算法的研究都尚处于起步阶段，其相关理论和方法还需要进行系统的探索和研究。鉴于以上原因，本文针对抽象层次的一阶POMDP模型及其算法进行了研究。在模型方面，利用一阶逻辑语言对状态空间进行分类，提出一阶信念状态的概念，缩小常规信念状态的维度；并利用流演算的相关概念和逻辑推理方法，提出一阶信念状态在抽象层面上的更新方法；构建了FOB-POMDP模型。在算法研究方面，为了建立基于一阶信念点的求解算法，对一阶信念点进行了详细分析研究，提出了一阶信念粒度的概念以及基于流关键度的粒度归结方法，实现一阶信念点粒度的统一；用流演算的框架表示PBVI，建立了抽象层面上的FO-PBVI算法，实现对FOB-POMDP的近似求解。在ADD的基础上提出了FO-ADD的概念和构造方法，将FO-PBVI用FO-ADD表示，并利用实验对这两种方式的近似求解方法进行分析比较。最后在应用方面，将FOB-POMDP模型和算法应用于CPS，设计并实现基于FOB-POMDP的CPS决策系统。以上这些方法和技术的研究循序渐进，相辅相成，形成了一套从模型到算法再到应用的比较完整的理论和方法体系。具体来说，本文的主要贡献体现在以下几个方面：（1）提出了信念状态在抽象层次上的一种描述及更新方法，构建了FOB-POMDP模型。通过对状态空间的分类，描述抽象层面上的信念状态，提出了一阶信念状态的概念。基于流演算的相关理论，针对随机观察行动和随机转移行动，分别给出了一阶信念状态的抽象层面上的更新方法。从而利用流演算的框架将信念状态上升到抽象层面，实现信念状态及其更新的抽象描述，构建一个相对比较完善的抽象POMDP模型，即FOB-POMDP模型。通过对Tiger和Tag问题的建模可见，该模型简洁、紧凑，充分融合了POMDP动态性、抽象概括能力和逻辑演算表达能力的优势。（2）提出了基于一阶信念点的FOB-POMDP值迭代方法。首先对抽象层面的一阶信念状态进行分析研究，主要包括：提出了一阶信念粒度的概念，度量一阶信念中状态空间的划分粗细程度；提出了流关键度的概念，衡量不同流在模型中的重要程度；提出了基于流关键度的粒度归结方法，将不同粒度的一阶信念状态归结到同一粒度。在此基础上，将常规基于点的值迭代中的各种运算上升到抽象层，用FOB-POMDP模型中的要素表示算法，包括一阶信念点距离度量、一阶信念点集上的值更新和一阶信念点集的COLLECT运算等，提出了基于一阶信念点的FOB-POMDP值迭代方法（FO-PBVI），将常规基于信念点的值迭代算法上升到抽象层面上。实验证明，FO-PBVI的求解时间基本不受问题规模大小的影响，因此FO-PBVI能够求解大规模的规划问题。（3）提出了FO-PBVI的FO-ADD表示方法。首先，基于ADD提出了FO-ADD的概念，将ADD抽象到一阶逻辑层。然后提出了基于流关键度的FO-ADD构造方法，实现从状况表达式到FO-ADD的转换。用FO-ADD实现FO-PBVI中的各种元素表示和基本操作，包括有一阶信念状态、αCase等元素和一阶信念更新、状况最大化、存在量词、前推等运算。实现一阶信念点集上的值更新运算和一阶信念点集的COLLECT运算的FO-ADD表示，形成了基于一阶信念值迭代的FO-ADD表示方法。实验证明，FO-PBVI的FO-ADD表示方法能够对较大规模问题进行求解，但是求解效率略逊于FO-PBVI。（4）设计和实现了基于FOB-POMDP的CPS决策系统。分析总结了CPS概念、特性及其决策特点；将FOB-POMDP模型与算法应用于CPS决策，设计并实现相应的CPS决策系统。基于FOB-POMDP的CPS决策系统不仅实现了FOB-POMDP模型和算法的工程实践，而且对CPS的开发应用提供了决策支持。（5）提出了基于遗传策略的POMDP值迭代方法。不仅对抽象层次的FOB-POMDP模型及其求解方法进行研究，还对常规POMDP的求解算法进行研究。提出了基于遗传策略的POMDP值迭代方法。通过构造一个效用矩阵来决定在某个信念状态点上所要采取的最优行动，在随机迭代过程中采用遗传策略选取最优种群，并根据所选取的最优种群对效用矩阵更新。实验证明，基于遗传策略的POMDP值迭代方法在解决一定规模的POMDP问题时能够迅速收敛到较好的收益值而获得最优行动策略。综上所述，本文对抽象层次的FOB-POMDP模型及其算法进行了研究，扩大了求解问题的规模。理论方面，FOB-POMDP模型及其算法拓展了POMDP的研究领域，提出了一种新的有效的智能规划方法；实践方面，为CPS的发展提供决策方法支持，推进CPS等大规模智能系统的发展。