Computer Engineering and Applications 计算机工程与应用 2010，46（22） 43 求解随机机会约束规划的混合智能算法 肖 宁 XIAO Ning 陕西职业技术学院 计算机科学系，西安 710100 Department of Computer Science，Shaanxi Vocational & Technical College，Xi’an 710100，China E-mail：xnwyh@126.com XIAO Ning.Solving stochastic chance-constrained programming problems with hybrid intelligent algorithm.Computer Engineering and Applications，2010，46（22）：43-46. Abstract： Stochastic chance-constrained programming belongs to a class of stochastic programming problems，in the paper， random simulation is used to produce training samples for BP neural network to approximate the stochastic function，fitness value is calculated and feasible solution is checked by the trained neural network in PSO，and a hybrid intelligent algorithm for stochastic chance-constrained programming is presented.Finally，the simulation results show the correctness and effective- ness of the algorithm. Key words：stochastic chance-constrained programming；Particle Swarm Optimization（PSO） algorithm；random simulation；neu- ral network 摘 要：随机机会约束规划是一类有着广泛应用背景的随机规划问题，采用随机仿真产生样本训练 BP 网络以逼近随机函数，然 后在微粒群算法中利用神经网络计算适应值和实现检验解的可行性，从而提出了一种求解随机机会约束规划的混合智能算法。 最后通过两个实例的仿真结果说明了算法的正确性和有效性。 关键词：随机机会约束规划；微粒群算法；随机仿真；神经网络 DOI：10.3778/j.issn.1002-8331.2010.22.015 文章编号：1002-8331（2010）22-0043-04 文献标识码：Ａ 中图分类号：O221.5 1 引言 随机机会约束规划（Stochastic Chance-Constrained Pro- gramming，SCCP）是由 Charnes 和 Cooper 提出的一类随机规 划 [1]，其显著特点是随机约束条件至少以一定的置信水平成 立。它实质是决策者考虑到所作决策在不利的情况下发生时 可能不满足约束条件而采用的一种原则，即允许所作决策在 一定程度上不满足约束条件（不考虑违反约束条件的惩罚）只 要求该决策使约束条件成立的概率不小于某一置信水平。 随机机会约束规划模型通常表示为： Max fˉ ì ïï s.t. Pr{ f (xξ) ³ fˉ} ³ β í ïï î (xξ) £ 0 j = 12p} ³ α Pr{g j 其中，x，ξ分别是决策、随机向量，Pr{}是事件的概率，α，β是决 策者预先给定的置信水平，fˉ是目标函数 f (xξ)在置信水平至 少为β时所取的最大值。 类似地，对极小化问题，有： Min fˉ ì ïï s.t. Pr{ f (xξ) £ fˉ} ³ β í ïï î Pr{g j (xξ) £ 0 j = 12p} ³ α 作者简介：肖宁（1975-），女，硕士，研究方向为智能计算。 收稿日期：2009-02-23 修回日期：2009-07-03 其中，fˉ是目标函数 f (xξ)在置信水平至少为β时所取的最 小值。 随机机会约束规划问题的提取并不困难，但其求解却很 难。因此，探索高效的随机机会约束规划的算法就非常有研 究价值。 处理随机机会约束规划的主要方法是将机会约束规划转 化成其确定的等价形式，然后对等价的确定模型进行求解，但 这种方法只适用一些特殊情形。另一种方法是采用逼近法， 利用随机仿真与智能算法相结合来进行，其中以遗传算法 （Genetic Algorithm，GA）最为成功[2]。目前，国内外学者仍在 继续探索处理该类问题的新的、更为有效的算法[2-3]。 随着计算机技术的迅速发展，使得智能技术具有解决大 规模、更复杂优化问题的能力。微粒群算法（Particle Swarm Optimization，PSO）是由 Eberhart 与 Kennedy 于 1995 年提出的 一种新的智能技术 [4]，它与 GA 类似，采用基于种群的并行全 局搜索策略，但不具有选择、变异等操作，仅采用简单的速度 —位置模型实现对整个空间的寻优操作，这是它不同于 GA 的 最显著之处，也是该算法所呈现出许多优良特性的关键。该 算法只需调整很少的参数，具有简单、易于编程实现，收敛速 度快，精度高等优点。它已在各类问题的求解及应用中展现 

44 2010，46（22） Computer Engineering and Applications 计算机工程与应用 了它的特点和魅力[5-6]。然而将 PSO 算法应用于随机机会约束 规划这一类问题的求解相当少，将 PSO 算法与随机仿真相结 合成功实现了该类问题的求解[7]，其解的质量优于 GA，但利用 随机仿真估计不确定函数这一过程比较费时，考虑到神经网 络在函数逼近中的成功应用，为了实现加速求解的过程，利用 前向神经网络逼近不确定函数，再将训练好的神经网络嵌套 在 PSO 算法中理论上能解决这一问题。试利用随机仿真、神 经网络、PSO 算法三者相结合的混合智能算法求解该类问题， 通过仿真实验取得了十分满意的效果，从而在质量和速度上 实现了以 PSO 算法为核心的混合智能算法对这一大类连续空 间随机规划问题的高效求解。 2 微粒群算法 微粒群算法是最新的群智能算法，由 Eberhart 和 Kennedy 于 1995 年提出，其基本思想是受他们早期对鸟类群体行为研 究结果的启发并利用了生物学家 Frank Heppner 的生物模 型。它的进化规则与“优胜劣态，适者生存”的 GA 截然不同， 强调的是群体中个体间信息的社会共享和协同进化。 微粒群中的每一个粒子定义为 D 维空间（待优化问题的 解空间）中的粒子，以一定的速度 Vi（Vi1，Vi2，…，Vid）在搜索空间 中飞行。算法开始时，初始化一组随机解（x1，x2，…，xN，N 为粒 子的个数），然后粒子根据自己在解空间中的飞行经验以及群 体的飞行经验动态调整自己位置、速度，并用适应值来评价解 的优劣，选出 Pbest（个体极值）与 Gbest（全局极值）并记录它 们的位置，再根据速度、位置更新方程（1）、（2）、（3）更新下一 代粒子的速度、位置，通过迭代寻找最优值。PSO 算法的数学 描述为： id id id max max （2） = V max = -V > V max < -V ，if V id ，if V Vid=ω*Vid+c1*rand（）*（Pid-Xid）+c2*rand（）*（Pgd-Xid） （1） V ì í V î Xid=Xid+Vid 1≤i≤N （3） 其中，ω为惯性权重，它使微粒保持运动的惯性，使其有能力探 索新的区域；c1，c2为正的加速度常数，一般取值为 2，它们使每 个微粒向 Pbest 和 Gbest 位置加速运动，分别起到了协调“勘探 “和”开发“解之间的作用；rand（）为[0，1]上均匀分布的随机 数，它们用来模拟自然界中群体行为的轻微扰动；Pid、Pgd分别 为个体极值、全局极值的第 d 维分量；式（2）对微粒的最大速 度进行了最大限制：如果当前对微粒的加速将导致它的某维 的速度分量 Vid超过该维的最大速度限额 Vmax，则该维的速度被 限制为 Vmax，它决定了微粒在解空间的搜索精度，如果 Vmax 过 大，粒子容易飞过最优解；反之，粒子容易陷入局部搜索空间 而无法进行全局搜索，若问题的搜索空间限制在[-Xmax，Xmax] 内，则可设定 Vmax=k*Xmax，0.1≤k≤1.0[5]。 3 求解随机机会约束规划的混合智能算法 在利用 PSO 算法求解该类问题时，其核心是对随机函数 进行计算，这显然可以利用随机仿真的方法进行估计，而要使 估计值尽量精确，则仿真的次数必须加大，这使得求解过程很 费时；此外，在 PSO 算法中，初始化时要用到随机仿真来实现 检验解的可行性和计算微粒群中每个微粒的适应值；尤其在 每一迭代过程中也要利用它计算每个微粒的适应值、实现检 验解的可行性，当微粒数目和迭代次数很多时利用随机仿真 进行估计很显然计算量相当大。在实际应用中，算法的执行 效率是一个不容忽视的问题，而神经网络这一智能算法在函 数逼近中已得到广泛的应用，为了减少计算量以加速求解过 程，利用训练好的前向神经网络对随机函数进行计算应该是 可行的，而要对神经网络进行训练以使其能逼近给定的不确 定函数，这就需要解决训练样本的获取和网络学习算法的选 择这两个问题。对于网络的学习算法可采用既成熟又简单的 BP 算法，而对于训练样本的产生可通过随机仿真取得。针对 本文的需要，下面给出三种随机仿真的估计算法。 设 ξ 为 定 义 在 概 率 空 间(ΩΑPr)上 的 n 维 随 机 向 量 ， f: Rn ® R为可测函数。利用随机仿真求解：L = Pr{ f (ξ) £ 0}。 随机仿真算法 1：概率估计算法 步骤 1 置N'=0； 步骤 2 根据概率测度 Pr，从Ω中产生样本ω； 步骤 3 如果 f（ξ（ω））≤0 则N'++； 步骤 4 重复步骤 2 和步骤 3 共N次； 步骤 5 L = N'/N。 设 ξ 为 定 义 在 概 率 空 间(ΩΑPr)上 的 n 维 随 机 向 量 ， f: Rn ® R 为 可 测 函 数 。 利 用 随 机 仿 真 确 定 最 大 的 fˉ 使 得 Pr{ f (ξ) ³ fˉ} ³ α，其中α为预先给定的置信水平，0 < α < 1。 随机仿真算法 2：乐观值估计算法 步骤 1 置N'为α*N 的整数部分； ω 步骤 2 根据概率测度 Pr，从 Ω中产生 N 个样本 ω 1 ； N 步骤 3 返回{ f (ξ(ω 1 )),f (ξ(ω ))f (ξ(ω ))}中的第N'个最  2 N 2 ,ω 大的元素。 随机仿真算法 3：悲观值估计算法：与乐观值估计算法类 )) 似 ，仅 将 乐 观 值 估 计 算 法 中 步 骤 3 改 为 ：返 回 { f (ξ(ω 1 f (ξ(ω )),f (ξ(ω ))}中的第N'个最小的元素。 2 基于 PSO 算法，结合随机仿真、神经网络求解随机机会约 N 束规划的混合智能算法的具体步骤描述如下： 步骤 1 利用随机仿真的概率估计、乐（悲）观值估计算法 为不确定函数 U1，U2产生输入输出数据：（xt，yk），t，k 分别为输 入、输出神经元的个数。利用线性函数转换法对 xt，yk分别进 行归一化预处理，以归一化后的输入输出数据作为训练样本。 j (xξ) £ 0 j = 12p} : x ® Pr{g : x ® Max fˉ(或Min fˉ) U 1 U 步骤 2 利用以上训练样本训练一个 BP 神经网络以逼近 2 不确定函数 U1，U2。 步骤 3 在 d 维问题空间上对微粒群进行初始化：设定群 体规模为 popsize，在决策向量 x 的可行域中产生一随机数，归 一化后利用神经网络计算网络的仿真输出值并进行反归一化 (xξ) £ 0 j = 12p}的值），然后检验该随机 （即计算Pr{g (xξ) £ 0j = 12 数 的 可 行 性（即 判 断 x 是 否 满 足 Pr{g p} ³ α)，重复该过程 popsize 次，从而得到 popsize 个初始可行的 微粒：X i=（xi1，xi2，…，xid），i=1，2，…，popsize，然后再对速度等 进行初始化。 j j 步骤 4 利用训练好的神经网络计算每个归一化后微粒的 网络仿真输出值，并进行反归一化（即计算Max fˉ或Min fˉ)，作 为每个微粒的适应值。 

肖 宁：求解随机机会约束规划的混合智能算法 2010，46（22） 45 步骤 5 对每个微粒，将其适应值与所经历的最好位置的 操作系统为 Microsoft WindowsXP 的 PC 机上运行程序。 适应值进行比较，较好者作为当前最好位置。 步骤 6 对每个微粒，将其最好适应值与全局所经历的最 好适应值进行比较，较好者作为当前的全局最好位置。 步骤 7 根据方程（1）、（2）和（3）进化。 步骤 8 对更新后的微粒再次进行归一化处理。 步骤 9 利用神经网络计算网络的仿真输出值并进行反归 (xξ) £ 0 j = 12p})然后检验微粒的 (xξ) £ 0 j = 12p} ³ α)， j 可行性（即判断 x 是否满足Pr{g 若为可行解，则接受，否则保持原位置不变。 j 一化（即计算Pr{g 步骤 10 重复步骤 4 至步骤 9 至一个预设的最大迭代次数 或一个足够好的适应值。 步骤 11 给出最好的微粒及对应的适应值作为最优解及 对应的最优值。 4 实例仿真 为了测试该算法的性能并便于比较，特选文献[2]的实例 来进行。 例 1 下面是具有三个决策变量和 9 个随机参数的 maxi- max 机会约束规划： max fˉ ì ï ïïï s.t. ( f 1 ( f í ï ïïï ( f x 1x î 2 3 = Pr{ξ + ξ x x 1 1 2 = Pr{η + η x2 1 1 = Pr{τ + τ x3 1 1 x ³ 0 2 2 + ξ x 2 3 + η x2 2 2 + τ x3 2 ³ fˉ}) ³ 0.90 3 £ 8}) ³ 0.80 x2 3 3 £ 15}) ³ 0.85 x3 3 3 3 分别服从均匀分布 U（1，2），U（2，3）， 其中随机变量ξ ，η ，τ 1 1 1 分别服从正态分布 N（1，1），N（2，1）， ，τ ，η U（3，4），随机变量ξ 2 2 2 N（3，1），随机变量ξ ，η ，τ 分别从指数分布 EXP（1），EXP（2）， 3 3 EXP（3）。 3 例 2 以下是具有三个决策变量和 9 个随机参数的机会约 束目标规划： 2 3 2 d - 2 d - } 3 ) £ d - + x + x = (Pr{2 - (τ })) ³ 0.95第一优先级 x 3 1 1 1 2 + x ) £ d - + τ = (Pr{4 - (x })) ³ 0.90第二优先级 x 2 3 1 2 ) £ d - = (Pr{5 - (x + x + τ })) ³ 0.85第三优先级 x 3 1 3 2 3 ü £ ξ + x + x ïï 2 1 3 £ ξ )³ 0.80 + x x ý 2 ïï + η £ ξ x þ ì lex min{d - ï 1 ï s.t. ( f ï ï 1 ïï ( f ï ï ( f ï ï í ï ï ï ï ïï ï ï ï ï î 其中ξ 1 ，τ 分别服从指数分布 EXP（1），EXP（20），EXP（3），η ，η τ 2 1 3 别服从正态分布 N（1，1），N（2，1），N（3，1）。 ì η ïï 1 x í 1 ïï x î 1 ³ 0d - i 分别服从均匀分布 U（6，7），U（7，8），U（8，9），τ ， 1 分 3 ，η 2 ³ 0i = 123 x 1 + η + x i ，ξ 3 ( f = Pr ，ξ 2 x 2 3 3 2 3 2 3 在实例 1 中取与文献[2]相同的模拟次数：5 000，训练样本 个数：3 000，迭代次数：3 000，种群规模：30，输入神经元个数： 3，隐层神经元个数：15，输出神经元个数：3，运行次数：1。 在实例 2 中取与文献[2]相同的模拟次数：5 000，训练样本 个数：3 000，迭代次数：1 000，种群规模：30，输入神经元个数： 3，隐层神经元个数：18，输出神经元个数：4，运行次数：1。 此外，ω从 0.9~0.4 线性递减，微粒的最大速度取为搜索空 间最大值的 0.1 倍。 利用 VC++6.0 编程，在 CPU 的主频：2.5 GHz，内存：2 ＧB， 对于例 1，从解的质量方面分析：运行一次的结果如表 1 所示，从表中可以看出，其结果明显优于文献[2]；为了更直观 地体现迭代过程，将实例的迭代过程抽样 15 次，如图 1 所示， 该算法不仅收敛速度相当快而且精度高，在 200 代时的最优 值就已超过文献[2]在迭代 3 000 代时的最优值。为避免一次 运行结果的偶然性，将程序运行 10 次，其结果见表 2：显然，利 用该算法所得平均最优值优于文献[2]且 10 次运行中每次所 得结果也均优于文献[2]；从时间方面：运行程序 1 次，从产生 训练样本、网络学习 1 次（BP 算法执行 1 次）到得出运行结果 花费时间为 9 分 33 秒；对于已训练好的网络得出结果花费时 间仅为 1 分 31 秒；而利用文献[7]在相同条件下运行一次程序 需 2 小时 53 秒。 表 1 实例 1 结果比较 算法 x1 x2 x3 最优值 文献［2］ 文献［7］ 1.404 0.468 0.924 1.317 0.660 0.841 本文 1.461 0.519 0.867 2.21 2.25 2.32 f1 0.90 f2 0.80 f3 0.85 0.90 0.85 0.97 0.91 0.80 0.85 表 2 实例 1 运行 10 次结果统计 运行次数 x1 x2 x3 最优值 第 1 次 第 2 次 第 3 次 第 4 次 第 5 次 第 6 次 第 7 次 第 8 次 第 9 次 第 10 次 平均值 1.460 0.519 0.868 1.460 0.519 0.867 1.460 0.518 0.868 1.460 0.519 0.867 1.460 0.519 0.868 1.460 0.518 0.868 1.460 0.519 0.868 1.461 0.519 0.867 1.460 0.519 0.868 1.460 0.519 0.868 1.460 0.519 0.868 2.31 2.32 2.32 2.32 2.32 2.32 2.32 2.32 2.32 2.32 2.32 f1 0.91 f2 0.80 f3 0.85 0.90 0.80 0.85 0.91 0.80 0.85 0.90 0.80 0.85 0.91 0.80 0.85 0.91 0.80 0.85 0.90 0.80 0.85 0.91 0.80 0.85 0.91 0.80 0.85 0.90 0.80 0.85 0.91 0.80 0.85 2.315 0 2.314 9 2.314 8 2.314 7 2.314 6 2.314 5 2.314 4 2.314 3 2.314 2 2.314 1 2.314 0 2.313 9 2.313 8 2.313 7 值 优 最 0 0 2 0 0 4 0 0 6 0 0 8 0 0 0 0 0 2 1 1 0 0 4 0 0 6 0 0 8 1 1 1 迭代次数 0 0 0 2 0 0 2 0 0 4 0 0 6 0 0 8 2 2 2 2 0 0 0 3 图 1 实例 1 抽样图 对于例 2，从解的质量方面分析：运行 1 次及 10 次的平均 值见表 3 的第 4、5 行。从时间方面：运行程序一次，从产生训 练样本、网络学习一次到得出结果花费时间为 19 分 50 秒，对 于训练好的网络得出结果时间仅为 26 秒；而利用文献[7]在相 表 3 实例 2 结果比较 算法 文献[2] 文献[7] 本文 平均值 x1 x2 x3 d - 1 2.242 9 0.673 3 1.212 7 0.00 d - 2 0.40 d - 3 f 1.54 0.80 f1 0.95 f2 0.90 f3 0.85 2.400 9 0.779 8 1.109 5 0.00 0.33 1.31 0.80 0.96 0.91 0.85 2.378 9 0.706 6 1.186 4 0.00 0.31 1.32 0.80 0.85 0.91 0.85 2.379 0 0.707 4 1.185 6 0.00 0.31 1.32 0.80 0.95 0.91 0.85 

46 2010，46（22） Computer Engineering and Applications 计算机工程与应用 同条件下运行一次需 55 分 10 秒。 从以上结果可明显看出，本文的算法不仅在解的质量上 优于文献[2，7]，且在执行速度上优于文献[7]。 该算法性能之所以优越，一方面在于用神经网络代替随 机仿真对不确定函数进行逼近，这是因为通过使用训练数据 神经网络完全能够逼近不确定函数，且训练好的神经网络运 算速度相当快；另一方面在于 PSO 算法搜索速度快，在搜索性 能上优于 GA。PSO 算法没有 GA 那样复杂的遗传操作，仅仅 是利用个体在解空间中的随机速度来改变个体，表现出更强 的随机性，使其计算复杂度比 GA 低；在 GA 中染色体互相共 享信息，所以整个种群的移动是比较均匀地向最优区域移动， 而 PSO 算法中信息的提供仅是全局最优值，这是信息的单向 流动，整个种群的搜索更新过程是跟随当前的全局最优解的 过程，与 GA 相比，在大多数情况下，所有的微粒有可能更快地 收敛于最优解；此外，微粒具有“记忆”特性，它们通过“自我” 学习及向“同伴”学习，使得下一代能从上一代继承更多的信 息，从而可在较短时间内找到最优解。 5 结论 提出了一种基于 PSO 算法求解随机机会约束规划问题的 混合智能算法，通过仿真实验与基于 GA 的混合智能算法的进 行了比较，其优化性能相当明显，此外，为了体现该算法的执 行速度，在运行时间上同 PSO 算法与随机仿真相结合的随机 机会约束规划算法进行了比较，该混合智能算法的高效性不 言而喻。这一优点可使本文的算法能更有效地处理大规模连 （上接 25 页） [3] 饶东宁，蒋志华，姜云飞，等.从规划解中学习一阶派生谓词规则[J]. 计算机学报，2010，33（2）：251-266. [4] 饶东宁，蒋志华，姜云飞，等.从 WSBPEL 程序中学习 Web 服务的 不确定动作模型[J].计算机研究与发展，2010，47（3）：445-454. [5] 陈蔼祥，柴啸龙，胡桂武.HTN 规划及其复杂度分析[J].计算机工程 与应用，2008，44（16）：37-41. [6] Fikes R，Nilsson N.STRIPS：A new approach to the application of theorem proving to problem solving[J].Artificial Intelligence， 1971，2（3/4）：189-208. [7] Pednault E.ADL：Exploring the middle ground between STRIPS and the situation calculus[C]//Proceedings of the First Interna- tional Conference on Principles of Knowledge Representation and Reasoning（KR-89），Toronto，Canada，May 1989：324-332. [8] Fox M，Long D.PDDL2.1：An extension to PDDL for express- Intelli- ing temporal planning domains[J].Journal of Artificial gence Research，2003，20：61-124. [9] Edelkamp S，Hoffmann J.PDDL2.2：The language for the classi- cal part of the fourth international planning competition，Techni- cal Report：195[R].Albert Ludwigs Universitat，Institut fur Infor- matik，Freiburg，Germany，2004. [10] Gerevini A，Long D.Plan constraints and preferences in PD- DL3：The language of the fifth international planning competi- tion[R].University of Brescia，Italy，2005. [11] Lifschitz E.On the semantics of STRIPS[C]//Proceedings of ß 1986 Workshop：Reasoning about Actions and Plans，1986. [12] Cla en J，Lakemeyer G.A semantics for ADL as progression in the situation calculus[C]//Proceedings of the 11th Work- shop on Nonmonotonic Reasoning（NMR 2006），Windermere， 续空间的随机机会约束规划问题，同时也拓展了 PSO 算法的 应用领域，在应用中展现了该算法的优势。 值得一提的是：将随机仿真、神经网络及 PSO 算法相结合 的混合智能算法应用于随机期望值模型[8]、随机相关机会规划 也取得了与本文类似的效果。将 PSO 算法应用于离散空间的 随机规划问题是下一步要重点研究的内容。 参考文献： [1] Charnes A，Cooper W W.Chance-constrained programming[J]. Management Science，1959，6：73-79. [2] 刘宝碇，赵瑞清，王纲.不确定规划及应用[M].北京：清华大学出版 社，2003. [3] 彭锦，刘宝碇.不确定规划的研究现状及其发展前景[J].运筹与管 理，2002，11（2）：1-10. [4] Kennedy J，Eberhart R C.Particle swarm optimization[C]//Pro- IEEE International Conference on Neural Net- ceedings of works，Australia，1995：1942-1948. [5] 曾建潮，介婧，崔志华.微粒群算法[M].北京：科学出版社，2004. [6] Parsopoulos K E，Vrahatis M N.Unified particle swarm optimi- zation for research problems[C]//Proceed- ings of the 2005 IEEE Swarm Intelligence Symposium，USA， 2005：53-59. tackling operations [7] 肖宁，曾建潮.基于随机模拟与 PSO 算法相结合的随机机会约束规 划算法[J].计算机应用与软件，2009，24（4）：40-58. [8] 肖宁，曾建潮.基于 PSO 求解随机期望值模型的混合智能算法[J]. 计算机工程与应用，2009，45（10）：45-48. England，2006. ß [13] Cla en J，Hu Y，Lakemeyer G.A situation-calculus semantics the Intelligence，AAAI for an expressive fragment of PDDL[C]//Proceedings of Twenty-Second Conference on Artificial 2007，Vancouver，Canada，2007. [14] Lin F，Reiter R.How to progress a database[J].Artificial Intelli- gence，1997，92（1/2）：131-167. [15] Bacchus F.The power of modeling：A response to PDDL2.1[J]. Journal of Artificial Intelligence Research，2003，20：125-132. [16] Boddy M.Imperfect match：PDDL 2.1 and Real Applications[J]. Journal of Artificial Intelligence Research，2003，20：133-137. [17] McDermott D.PDDL2.1：The art of the possible? Commentary on fox and long[J].Journal of Artificial Intelligence Research， 2003，20：145-148. [18] Smith D.The case for durative actions：A commentary on PD- Intelligence Research，2003，20： DL2.1[J].Journal of Artificial 149-154. [19] Geffner H.PDDL 2.1： Representation vs Computation[J].Jour- nal of Artificial Intelligence Research，2003，20：139-144. [20] Fox M，Long D.Modelling mixed discrete-continuous domains Intelligence Research， planning[J].Journal of Artificial for 2006，27：235-297. [21] Penna G，Magazzeni D，Mercorio F，et al.UPMurphi：A tool for universal planning on PDDL + problems[C]//Proceedings of the 19th International Conference on Automated Planning and Scheduling，ICAPS 2009，Thessaloniki，Greece，September 19-23 2009：106-113. [22] Hatzi O，Vrakas D，Bassiliades N，et al.A visual programming system for automated problem solving[J].Expert Systems With Applications，Elsevier，2010，37（6）：4611-4625.