第1章 绪论 1
1.1 智能规划发展历史 1
1.2 智能规划的应用 2
1.2.1 在航空航天中的应用 2
1.2.2 在机器人中的应用 2
1.2.3 在智能工厂中的应用 3
1.2.4 在商业中的应用 4
1.3 本书概要 5
参考文献 5
第2章 规划表示语言 8
2.1 STRIPS表示 8
2.2 动作描述语言 9
2.3 规划领域定义语言 9
2.3.1 PDDL的提出及其背景 9
2.3.2 PDDL各版本简介 10
2.4 规划语言的发展 15
参考文献 15
第3章 图规划 16
3.1 经典规划 16
3.1.1 问题定义 16
3.1.2 状态空间规划 16
3.1.3 规划空间规划 18
3.1.4 偏序规划与全序规划 19
3.1.5 现代经典规划 19
3.2 图规划方法 20
3.2.1 基本概念 20
3.2.2 扩张规划图算法 22
3.2.3 搜索有效规划算法 23
3.2.4 Graphplan的局限性与未解决问题 27
3.3 求解方向的变形 27
3.3.1 正向求解 27
3.3.2 反向求解 28
3.3.3 基于双向并行的图规划 36
3.4 最小承诺的图规划 38
3.4.1 预备知识 38
3.4.2 最小承诺的图规划算法 40
3.4.3 简单的规划问题举例 41
3.4.4 最小承诺的图规划算法的优缺点 43
3.5 图规划中的条件效果 43
3.5.1 条件效果 44
3.5.2 全扩展法 44
3.5.3 要素扩展法 46
3.5.4 IP2扩展法 47
3.5.5 利用兄弟元件改进要素扩展法 50
3.5.6 四种方法的比较 51
3.6 利用约束可满足问题在规划图中求解 51
3.6.1 约束满足问题 51
3.6.2 约束满足问题求解技术 52
3.6.3 用EBL和DDB提高图规划搜索效率 52
3.7 灵活图规划算法 54
3.7.1 图规划的局限性 54
3.7.2 灵活规划问题 56
3.7.3 灵活图规划算法描述 58
3.7.4 以目标为导向的灵活图规划 60
3.7.5 基于启发式搜索的灵活规划 63
3.7.6 基于软约束的多智能体灵活规划 66
3.7.7 灵活图规划方法特性 77
3.8 数值图规划 77
3.8.1 ADL中的基本概念 78
3.8.2 BRL 82
3.8.3 搜索算法 87
3.8.4 嵌入模糊部件的数值图规划算法 95
3.9 时序规划 100
3.9.1 概述 100
3.9.2 时序动作 101
3.9.3 时序规划图 102
3.9.4 解搜索 106
参考文献 107
第4章 启发式规划方法 111
4.1 启发式的设计原则——放松 111
4.2 HSP 112
4.2.1 启发式 112
4.2.2 搜索算法 114
4.2.3 HSP2.0——最优最先搜索规划器 115
4.3 HSP-r 115
4.3.1 状态空间 116
4.3.2 启发式 116
4.3.3 互斥 117
4.3.4 搜索算法 118
4.3.5 相关工作 118
4.4 FF规划系统 119
4.4.1 FF系统结构 119
4.4.2 符号说明 120
4.4.3 用Graphplan作为启发式估计 120
4.4.4 爬山算法的一个新的变体 125
4.4.5 剪枝技术 127
4.4.6 扩展到ADL域 130
4.4.7 基于部分延迟推理的快速前向规划系统 132
4.5 LPG 139
4.5.1 在动作图空间中的局部搜索 140
4.5.2 相邻状态的提炼 143
4.5.3 模型化规划质量 147
4.6 基于因果图启发的多值规划算法 150
4.6.1 基本概念 150
4.6.2 AMCG规划算法 154
4.6.3 启发函数的设计 158
4.7 小结 162
参考文献 162
第5章 符号模型检测理论 165
5.1 域描述语言NADL 165
5.1.1 采用NADL描述的规划问题 165
5.1.2 NADL语法 166
5.1.3 NADL语义 167
5.1.4 NADL的OBDD表示 168
5.2 符号模型检测方法的由来 170
5.3 逻辑及形式化表示 170
5.3.1 量化布尔公式 170
5.3.2 Kripke结构 171
5.3.3 计算树逻辑 171
5.4 二元决策图 173
5.4.1 OBDD的值 173
5.4.2 BDD的化简 173
5.5 符号模型检测 175
5.6 转移关系的划分 176
参考文献 177
第6章 不确定规划 178
6.1 不确定规划简介 178
6.1.1 不确定规划问题 178
6.1.2 不确定规划问题的解 178
6.1.3 不确定规划方法 179
6.2 图规划框架下的概率规划 180
6.2.1 PGP概述 181
6.2.2 图规划框架下的表示方法 181
6.2.3 图扩张算法 182
6.2.4 有效规划提取算法 183
6.2.5 缩减状态空间方法 185
6.2.6 结论及未解决问题 187
6.3 一致图规划 187
6.3.1 CGP概述 187
6.3.2 预备知识 188
6.3.3 CGP算法 189
6.3.4 结论及未解决问题 196
6.4 感知图规划 197
6.4.1 SGP概述 197
6.4.2 预备知识 198
6.4.3 SGP算法 198
6.4.4 结论 204
6.5 基于决策理论的多目标概率规划 204
6.5.1 规划问题模型 204
6.5.2 多目标评价函数 206
6.5.3 多目标概率规划求解算法 210
6.5.4 启发式的应用 220
6.5.5 多目标概率规划器 221
6.6 图规划框架下的可能性规划 223
6.6.1 为什么引入可能性规划 223
6.6.2 可能性规划表示 224
6.6.3 相关定义 225
6.6.4 可能性规划图算法 227
6.6.5 结论 230
参考文献 230
第7章 对象集合动态可变的图规划 233
7.1 图规划框架下可创建/删除对象的规划 233
7.1.1 关于可创建/删除对象的规划问题分类 233
7.1.2 关于可创建/删除对象规划的动作的表示 234
7.1.3 对象命题化的思想 235
7.1.4 可创建/删除对象的图规划的基本思想与算法 235
7.1.5 一个例子：关于火车运输问题 237
7.1.6 算法分析 240
7.2 可创建/删除对象的快速前向规划 240
7.2.1 CDOFF中的基本概念及理论框架 241
7.2.2 对象元件命题化算法 242
7.2.3 部分放宽方法 244
7.2.4 启发函数的设计 245
7.2.5 加强爬山法及剪枝策略 246
7.3 基于条件效果的对象动态可变图规划 249
7.3.1 基于条件效果的对象动态可变的规划问题 249
7.3.2 CECDOP规划 251
7.3.3 结论 254
7.4 对象集合动态可变的概率规划 255
7.4.1 算法背景 255
7.4.2 基本概念 256
7.4.3 对象动态可变的概率规划算法 257
参考文献 260
第8章 八届国际规划比赛综述 261
8.1 第一届国际规划竞赛IPC-1 261
8.1.1 参赛规划器 261
8.1.2 比赛所用的语言及测试域 261
8.1.3 比赛结果 261
8.1.4 冠军介绍 261
8.2 第二届国际规划竞赛IPC-2 262
8.2.1 参赛规划器 262
8.2.2 比赛所用的语言及测试域 262
8.2.3 比赛结果 262
8.2.4 冠军介绍 263
8.3 第三届国际规划竞赛IPC-3 263
8.3.1 参赛规划器 263
8.3.2 比赛所用的语言及测试域 263
8.3.3 比赛结果 264
8.3.4 冠军介绍 264
8.4 第四届国际规划竞赛IPC-4 264
8.4.1 参赛规划器 265
8.4.2 比赛所用的语言及测试域 265
8.4.3 比赛结果 265
8.4.4 冠军介绍 265
8.5 第五届国际规划竞赛IPC-5 266
8.5.1 参赛规划器 266
8.5.2 比赛所用的语言及测试域 266
8.5.3 比赛结果 267
8.5.4 冠军介绍 267
8.6 第六届国际规划竞赛IPC-6 268
8.6.1 参赛规划器 268
8.6.2 比赛所用的语言及测试域 269
8.6.3 比赛结果 269
8.6.4 冠军介绍 269
8.7 第七届国际规划竞赛IPC-7 269
8.7.1 参赛规划器 270
8.7.2 比赛所用的语言及测试域 270
8.7.3 比赛结果 270
8.7.4 冠军介绍 270
8.8 第八届国际规划竞赛IPC-8 271
8.8.1 参赛规划器 271
8.8.2 比赛结果 271
8.9 智能规划中未解决的问题与展望 272
8.9.1 未解决的问题 272
8.9.2 展望 273
参考文献 273
第9章 规划识别 275
9.1 规划识别综述 275
9.1.1 规划识别分类 275
9.1.2 规划识别方法 277
9.1.3 规划识别的应用 294
9.2 Kautz的规划识别理论 299
9.2.1 相关概念 300
9.2.2 事件层描述 302
9.2.3 四种假设 305
9.2.4 举例 309
9.2.5 Kautz规划识别算法 316
9.3 基于目标图分析的目标识别 319
9.3.1 域表示 320
9.3.2 目标图、有效规划和一致目标 325
9.3.3 目标识别算法 328
9.3.4 目标冗余以及最一致目标 333
9.4 基于回归图的规划识别方法 334
9.4.1 域表示 335
9.4.2 回归图 336
9.4.3 回归图算法 337
9.5 基于规划知识图的概率规划识别算法的研究 339
9.5.1 事件间的两种关系 340
9.5.2 规划知识图算法存在的问题 340
9.5.3 支持程度及KGPPR算法的解图描述 342
9.5.4 KGPPR系统的相关概念和算法设计 344
9.6 基于灵活规划的规划识别算法 350
9.6.1 基于灵活规划识别算法的目的 350
9.6.2 FPRA算法思想 351
9.6.3 FPRA算法描述 352
9.7 关键问题与展望 354
9.7.1 关键问题 354
9.7.2 展望 355
参考文献 355
第10章 对手规划的识别与应对 360
10.1 对手规划简介 360
10.1.1 对手规划 360
10.1.2 对手规划领域的特点 361
10.1.3 对手规划问题的发展 363
10.2 对手规划的识别与应对 366
10.2.1 基于目标驱动的HTN规划方法 367
10.2.2 基于OBDD强循环对手规划方法 374
10.2.3 基于完全目标图的对手规划的识别方法 383
10.2.4 基于多智能体的对手规划的识别与应对 392
10.3 对手规划领域存在的问题与展望 399
10.3.1 存在的问题 399
10.3.2 对手规划研究的展望 399
参考文献 400
第11章 敌意规划的识别与应对 401
11.1 基于目标驱动理论的应对规划 401
11.1.1 相关概念 401
11.1.2 基于目标驱动的应对算法 405
11.1.3 应对算法描述 405
11.1.4 算法的功能与特点 408
11.2 复杂领域中多智能体条件下敌意规划的识别与应对 408
11.2.1 相关知识 408
11.2.2 敌意规划识别系统的组成 409
11.2.3 敌意规划的识别 410
11.2.4 敌意规划的应对 413
11.2.5 结论 413
11.3 基于规划语义树图的敌意规划识别 415
11.3.1 规划知识图和Kautz方法的不足之处 415
11.3.2 规划语义树图表示 416
11.3.3 带标记的双向搜索的敌意规划算法 418
11.4 基于DCSP的敌意规划识别算法 423
11.4.1 传统的规划识别理论中的假设和应用条件 423
11.4.2 相关概念 424
11.4.3 基于DCSP的识别方法 426
11.4.4 基于DCSP识别模型的特性 427
11.5 基于抢占式动作的敌意规划 428
11.5.1 相关定义 428
11.5.2 抢占算法在敌意规划中的应用 429
11.6 敌意规划的识别与应对系统 434
11.6.1 敌意系数与敌意动作 434
11.6.2 敌意规划识别系统 435
11.6.3 敌意规划识别算法 436
11.6.4 敌意规划的应对 438
11.7 应对规划器模型 444
11.7.1 基本概念及敌意规划分类 444
11.7.2 模块组成及功能 445
11.7.3 运行流程图及系统特点 451
11.8 基于战术的敌意规划识别 452
11.8.1 战术规划识别应用领域的特点 452
11.8.2 规划与规划模板 453
11.8.3 规划识别的形式化定义 454
参考文献 465
第12章 网络信息对抗领域的敌意规划的识别与应对 467
12.1 网络信息对抗领域 467
12.2 基于行为状态图的入侵检测问题 469
12.2.1 研究前提与基本原则 469
12.2.2 行为状态图的组成与抽象表示 470
12.2.3 基于行为状态图的登录问题描述 472
12.2.4 基于行为状态图的规划识别算法 474
12.2.5 ASGPR算法描述 480
12.2.6 一个规划识别算法的实例 482
12.3 基于应对规划的入侵防护系统的设计与研究 485
12.3.1 基于应对规划的入侵防护系统框架设计 485
12.3.2 一种系统应用方案 486
12.3.3 技术特色 486
12.3.4 开放的问题 487
12.4 基于待定集的入侵检测方法 488
参考文献 489
附录A 相关项目与会议 490
附录B 主要智能规划器 491
附录C Kautz规划识别的算法描述 493