并行概率规划综述

自动规划针对特定领域的特定问题,生成一个由可应用动作构成的规划。经典规划中的动作效果是确定的,且在每个时间步内只能执行一个动作。但在实际问题中,动作的效果往往是不确定性的,且动作的执行具有并发性。因此,并行概率规划(parallel and probabilistic planning,PPP)被提出,并且它的应用前景正在引起规划研究学术圈的关注。有鉴于此,对其进行综述,具体内容包括定义PPP领域、问题和规划解,介绍其描述语言、基准领域及规划器,并对其中两个有代表性的规划器进行实际测试。实验表明在求解效率方面测试结果与比赛结果基本一致,但部分规划器的求解规模与竞赛不完全一致。这可能是比赛中的某些未开源代码或手工干预得到的。

基于并行概率规划的股票指数模拟

在金融领域,股票指数(简称股指)模拟与分析是一个重要课题,用于股票市场的长期分析.然而,大多数的这类工作目前由专业的分析师来完成,非职业投资者难以涉及.另一方面,现有的基于数学或机器学习的股指模拟方法具有参数多、人工干预多、可解释性差等缺点.针对以上问题,本文基于并行概率规划(Parallel Probabilistic Planning,PPP),提出了一个股指模拟的规划领域模型,并能够进行自动求解.股票市场具有大量的不确定性和并发性,因此适合用并行概率模型来表示.方法的核心思想是将股指模拟问题转化为智能规划问题.首先,本文构建股指模拟问题的规划领域模型.由于股票市场的复杂性,需尽可能地考虑各种影响因素、约束条件、可能事件以及它们之间的关联.构建的规划领域模型由针对PPP的规划语言RDDL(Relational Dynamic Influence Diagram Language)来进行描述.接着,使用PPP的模拟求解工具——rddlsim来进行基于抽样的规划求解.rddlsim是国际概率规划大赛IPPC提供的求解工具,能够全面地解析RDDL描述.实验数据使用上证50指数和上证100指数的股票数据.即,从某个时间点开始,通过求解对应的规划问题来模拟未来一年股票指数的变化趋势.求解结果,一方面,与真实股票指数变化作对比;另一方面,与基于线性回归、基于SVM和基于LSTM的三种模拟方法的结果作对比.我们分别使用交叉熵、最小二乘和皮尔森相关系数作为损失函数.实验表明,本文的模拟效果比较贴近于真实的股指变化趋势;在大多数情况下,本文方法优于基于回归或SVM的模拟方法,且与基于LSTM的方法性能相当.并且,相对于对比的模拟方法,本文方法提供了较强的可解释性,且在求解过程中不需人工干预或调参.这是因为,形式化的规划领域描述展示了在股指模拟问题中各种因素如何相互影响,而且自动求解得到的规划解给出了导致模拟结果的状态变化轨迹.

基于因果图启发式的并行概率规划求解

并行概率规划(PPP)是近年来智能规划领域中的研究热点。在该类问题中,动作具有并发性和不确定性,非常贴近现实问题。然而现有的两种针对PPP的主要求解方法都有明显的缺点。因此,尝试使用高效的启发式搜索方法来求解这类问题。考虑到PPP问题采用RDDL语言来描述,其中的条件概率函数(CPF)非常适合用于构建因果图(CG),所以引入因果图启发(CGH)来进行求解。提出的启发式算法称为CGH_(RDDL),整体求解方法是使用rddlsim模拟状态演化以及用CGH_(RDDL)引导搜索。实验结果表明,在不允许手工干预和参数调整的前提下,该方法的求解效果要好于代表性规划器PROST和Glutton;并且与其他启发式相比,CGH_(RDDL)的求解质量高于随机搜索,求解速度快于爬山法,这表明在经典规划领域中高效的启发式搜索策略可扩展去求解这一类非经典规划问题。

图规划框架下的并行概率规划

针对具有并发性概率效果的规划问题,考虑了动作的概率效果和并发执行,通过定义并行动作集以及节点间互斥的概念,实现了在概率规划算法中处理并行动作和概率效果,打破了原有概率规划算法中"每个时间步只允许执行一个非空动作"的限制,弥补了原有算法的不足.该方法能生成非循环规划和循环规划,选择性地开发利用问题潜在的并行性,提高了概率规划器的求解质量,使得概率规划更适合于处理现实世界问题.