第一章 绪论 1
1.1智能规划发展历史 1
1.2智能规划的应用 2
1.2.1在航空航天中的应用 2
1.2.2在机器人中的应用 2
1.2.3在智能工厂中的应用 3
1.2.4在商业中的应用 3
1.3本书概要 4
参考文献 5
第二章 规划表示语言 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
第三章 图规划 17
3.1经典规划 17
3.1.1问题定义 17
3.1.2状态空间规划 17
3.1.3规划空间规划 19
3.1.4偏序规划与全序规划 20
3.1.5现代经典规划 20
3.2图规划方法 21
3.2.1基本概念 21
3.2.2扩张规划图算法 23
3.2.3搜索有效规划算法 24
3.2.4 Graphplan的局限性与未解决的问题 28
3.3求解方向的变形 29
3.3.1正向求解 29
3.3.2反向求解 31
3.3.3基于双向并行的图规划 37
3.4最小承诺的图规划 39
3.4.1预备知识 39
3.4.2最小承诺的图规划算法 41
3.4.3简单的规划问题举例 43
3.4.4最小承诺的图规划算法的优缺点 44
3.5图规划中的条件效果 44
3.5.1条件效果 44
3.5.2全扩展法 45
3.5.3要素扩展法 47
3.5.4 IPP扩展法 48
3.5.5利用兄弟元件改进要素扩展法 50
3.5.6四种方法的比较 52
3.6利用约束可满足问题在规划图中求解 52
3.6.1约束可满足问题 52
3.6.2约束可满足问题求解技术 53
3.6.3利用EBL和DDB提高图规划搜索效率 53
3.7灵活图规划算法 55
3.7.1图规划的局限性 55
3.7.2灵活图规划问题 56
3.7.3灵活图规划算法描述 59
3.7.4灵活图规划方法特性 61
3.8数值图规划 61
3.8.1 ADL中的基本概念 62
3.8.2 BRL 66
3.8.3搜索算法 71
3.9时序规划 79
3.9.1概述 79
3.9.2时序动作 80
3.9.3时序规划图 81
3.9.4解搜索 85
参考文献 86
第四章 启发式规划方法 89
4.1启发式的设计原则——放松 89
4.2 HSP 90
4.2.1启发式 90
4.2.2搜索算法 91
4.2.3 HSP2.0——最优最先搜索规划器 92
4.3 HSP-r 93
4.3.1状态空间 93
4.3.2启发式 94
4.3.3互斥 94
4.3.4搜索算法 95
4.3.5相关工作 96
4.4 FF规划系统 96
4.4.1 FF系统结构 97
4.4.2符号说明 97
4.4.3用Graphplan作为启发式估计 98
4.4.4爬山算法的一个新的变体 102
4.4.5剪枝技术 104
4.4.6扩展到ADL域 108
4.5 LPG 110
4.5.1在动作图空间中的局部搜索 110
4.5.2相邻状态的提炼 113
4.5.3模型化规划质量 118
4.6小结 120
参考文献 121
第五章 符号模型检测理论 123
5.1域描述语言NADL 123
5.1.1采用NADL描述的规划问题 123
5.1.2 NADL语法 124
5.1.3 NADL语义 125
5.1.4 NADL的OBDD表示 126
5.2符号模型检测方法的由来 127
5.3逻辑及形式化表示 128
5.3.1量化布尔公式 128
5.3.2 Kripke结构 129
5.3.3计算树逻辑 129
5.4二元决策图 130
5.4.1 OBDD的值 130
5.4.2 BDD的化简 131
5.5符号模型检测 132
5.6转移关系的划分 133
参考文献 134
第六章 不确定规划 135
6.1不确定规划简介 135
6.1.1不确定规划问题 135
6.1.2不确定规划问题的解 135
6.1.3不确定规划方法 136
6.2图规划框架下的概率规划 137
6.2.1 PGP概述 137
6.2.2图规划框架下的表示方法 138
6.2.3图扩张算法 139
6.2.4有效规划提取算法 140
6.2.5缩减状态空间方法 142
6.2.6结论及未解决的问题 143
6.3一致图规划 144
6.3.1 CGP概述 144
6.3.2预备知识 145
6.3.3 CGP算法 146
6.3.4结论及未解决的问题 153
6.4感知图规划 153
6.4.1 SGP概述 153
6.4.2预备知识 154
6.4.3 SGP算法 155
6.4.4结论 160
参考文献 161
第七章 五届国际规划比赛综述 163
7.1第一届国际规划竞赛IPC-1 163
7.1.1参赛规划器 163
7.1.2比赛所用的语言及测试域 163
7.1.3比赛结果 163
7.1.4冠军介绍 163
7.2第二届国际规划竞赛IPC-2 164
7.2.1参赛规划器 164
7.2.2比赛所用的语言及测试域 164
7.2.3比赛结果 164
7.2.4冠军介绍 165
7.3第三届国际规划竞赛IPC-3 165
7.3.1参赛规划器 165
7.3.2比赛所用的语言及测试域 165
7.3.3比赛结果 166
7.3.4冠军介绍 166
7.4第四届国际规划竞赛IPC-4 166
7.4.1参赛规划器 167
7.4.2比赛所用的语言及测试域 167
7.4.3比赛结果 167
7.4.4冠军介绍 167
7.5第五届国际规划竞赛IPC-5 168
7.5.1参赛规划器 168
7.5.2比赛所用的语言及测试域 168
7.5.3比赛结果 169
7.5.4冠军介绍 169
7.6智能规划中未解决的问题与展望 170
参考文献 171
第八章 规划识别 173
8.1规划识别综述 173
8.1.1规划识别的分类 173
8.1.2规划识别的方法 175
8.1.3规划识别的应用 192
8.2 Kautz的规划识别理论 197
8.2.1相关概念 197
8.2.2事件层描述 199
8.2.3四种假设 202
8.2.4举例 206
8.2.5 Kautz规划识别算法 212
8.3基于目标图分析的目标识别 215
8.3.1域表示 216
8.3.2目标图、有效规划和一致目标 221
8.3.3目标识别算法 224
8.3.4目标冗余以及最一致目标 229
8.4基于回归图的规划识别方法 230
8.4.1域表示 230
8.4.2回归图 231
8.4.3回归图算法 232
8.5关键问题与展望 235
8.5.1关键问题 235
8.5.2展望 236
参考文献 236
第九章 对手规划 240
9.1对手规划简介 240
9.1.1对手规划的定义 240
9.1.2对手规划领域的特点 241
9.1.3对手规划问题的发展 243
9.2对手规划的识别与应对 246
9.2.1基于目标驱动的HTN规划方法 247
9.2.2基于OBDD的强循环对手规划方法 254
9.2.3战术规划识别 263
9.2.4网络信息对抗领域的规划方法简介 276
9.3对手规划领域存在的问题与研究展望 279
9.3.1对手规划领域存在的问题 279
9.3.2对手规划研究的展望 280
参考文献 280
附录A相关项目与会议 282
附录B主要智能规划器 283