·22 智能系统学报 第2卷 3.1供电故障恢复问题(PSR) 任何时间都必须充满管道.流体被视为不可压缩，即 供电故障恢复问题(power supply restoration, 任意时段内管道中输入的流体体积与流出的流体体 PSR)是由Thiebaux S3s)等人引入到智能规划领域 积要基本相等，不同种类的流体有接合面，但不能大 的一个工程问题.图2(a)所示的简化供电网络包括 量掺混.每一个区域对不同的流体的储存能力有一 电力线路和2类设备：断路器（大方块）、开关（小方 定限制.流体输送到指定区域有一定的时间限制，操 块).设备最多只能连接2条线路并且只有2种状 作行为的描述必须与相应作用管段的内部状态保持 态：“拉开”和“闭合”.断路器被视为电源，当它闭合 一致.这需要复杂的操作行为描述方法。 时，处于供电状态的线路一直延伸到处于拉开状态 Miliditú38]等人采用FF算法对该问题进行求 的开关设备.在预先设定的设备状态下，不同的断路 解，但规模只限于数量为4~5个区域和管道的问 器为不同的区域供电.图中黑色和灰色的线路分别 题.Hoffman则用MIPs进行了实验，对于具有存储 表示“供电”与“未供电”状态.“拉开”与“合上”是仅 能力和时间限制的某些问题尚不能很好地解决」 有的操作行为.当某段线路发生故障时，相关区域停 x供电线路 电，规划的任务是如何使停电区域尽可能恢复正常 工作 PSR问题的特点是当某线路或设备状态发生 变化时，相关的区域的线路通断状态将随之发生变 打开关闭 化.由于系统中的设备和线路数量通常很多，网络运 断路器 行状态多变，倒闸操作行为对系统状态的改变很难 用行为的效果状态直接准确描述，因此该问题存在 多种不确定性，如系统信息只能部分可观察（不完 (a)PSR 全)、系统信息获取的不确定性、动作执行效果的不 确定性等 A2 Bertoli!2I在MBP中采用通用规划方法进行求 S12 34 解，能够成功地对一些典型案例生成满足特定目标 B8 的 的应急恢复方案.Bonet!361在GPT中将规划目标转 B9B10 为故障代价的最小化问题，将优化方法引入了不确 定性规划.Jesen R3则用智能体(Agent)代替动作 S43 B7 (action),并加入了环境Agent用来描述规划过程 中环境状态的不确定性，从并行、对立(adversarial) 的角度丰富了PSR问题的描述和求解框架 (b)pipeworld 3.2管道输送问题(pipesworld) 该问题源于石油管道输送领域，反映了工程系 统中管网输送流体的规划问题.pipeworld问题通常 转炉#1 吊车#1 Q加工议备#传送带加工设备1加工没备#3 包括区域（如配送中心、港口、提炼厂等）和输送管 等 道.图2(b)是一个包含4个区域5条输送管道的管 Q工设备料传送带#2加T设备#5 0 转炉#2 吊车#2 网系统.管道中可能依次输送多种不同批量的流体， 物○ 如柴油、汽油、煤油等.“压入”(push)与“抽出” 停 铸造设备 (pop)是该问题的2个操作行为.规划的目标是制 0 定合理的流体输送操作计划，以满足应用、安全、经 (c)SIDMAR 济等方面的需求 图2工程中的规划问题 与传统运输问题不同，pipeworld问题的运输工 Fig 2 Planning problems in engineering 具（管道）是静止的，而货物是运动的.流体在运输的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net311 供电故障恢复问题(PSR) 供电故障恢复问题(power supply restoration , PSR) 是由 Thiébaux S [35 ]等人引入到智能规划领域 的一个工程问题. 图 2 (a) 所示的简化供电网络包括 电力线路和 2 类设备 :断路器 (大方块) 、开关 (小方 块) . 设备最多只能连接 2 条线路并且只有 2 种状 态“: 拉开”和“闭合”. 断路器被视为电源 ,当它闭合 时 ,处于供电状态的线路一直延伸到处于拉开状态 的开关设备. 在预先设定的设备状态下 ,不同的断路 器为不同的区域供电. 图中黑色和灰色的线路分别 表示“供电”与“未供电”状态.“拉开”与“合上”是仅 有的操作行为. 当某段线路发生故障时 ,相关区域停 电 ,规划的任务是如何使停电区域尽可能恢复正常 工作. PSR 问题的特点是当某线路或设备状态发生 变化时 ,相关的区域的线路通断状态将随之发生变 化. 由于系统中的设备和线路数量通常很多 ,网络运 行状态多变 ,倒闸操作行为对系统状态的改变很难 用行为的效果状态直接准确描述. 因此该问题存在 多种不确定性 ,如系统信息只能部分可观察 (不完 全) 、系统信息获取的不确定性、动作执行效果的不 确定性等. Bertoli [21 ]在 MBP 中采用通用规划方法进行求 解 ,能够成功地对一些典型案例生成满足特定目标 的应急恢复方案. Bonet [36 ]在 GPT 中将规划目标转 为故障代价的最小化问题 ,将优化方法引入了不确 定性规划.J esen R [37 ]则用智能体 (Agent) 代替动作 (action) ,并加入了环境 Agent 用来描述规划过程 中环境状态的不确定性 ,从并行、对立 (adversarial) 的角度丰富了 PSR 问题的描述和求解框架. 312 管道输送问题 (pipesworld) 该问题源于石油管道输送领域 ,反映了工程系 统中管网输送流体的规划问题. pipeworld 问题通常 包括区域 (如配送中心、港口、提炼厂等) 和输送管 道. 图 2 (b) 是一个包含 4 个区域、5 条输送管道的管 网系统. 管道中可能依次输送多种不同批量的流体 , 如柴油、汽油、煤油等.“压入”( p ush) 与“抽出” (pop) 是该问题的 2 个操作行为. 规划的目标是制 定合理的流体输送操作计划 ,以满足应用、安全、经 济等方面的需求. 与传统运输问题不同 ,pipeworld 问题的运输工 具(管道) 是静止的 ,而货物是运动的. 流体在运输的 任何时间都必须充满管道. 流体被视为不可压缩 ,即 任意时段内管道中输入的流体体积与流出的流体体 积要基本相等. 不同种类的流体有接合面 ,但不能大 量掺混. 每一个区域对不同的流体的储存能力有一 定限制. 流体输送到指定区域有一定的时间限制. 操 作行为的描述必须与相应作用管段的内部状态保持 一致. 这需要复杂的操作行为描述方法. Milidiú[38 ] 等人采用 FF 算法对该问题进行求 解 ,但规模只限于数量为 4～5 个区域和管道的问 题. Hoffman 则用 MIPS 进行了实验 ,对于具有存储 能力和时间限制的某些问题尚不能很好地解决. (a) PSR (b) pipeworld (c) SIDMAR 图 2 工程中的规划问题 Fig12 Planning problems in engineering ·22 · 智 能 系 统 学 报 第 2 卷