自动规划：理论和实践PDF电子书下载

第1章　引言和概述 1

1.1　规划的直观含义 1

1.2　规划的形式分类 2

1.3　领域无关规划 3

1.4　智能规划的概念模型 5

1.5　受限的模型 8

1.6　扩展模型 10

1.7　一个运行的例子：码头工机器人 12

第1部分　经典规划 15

第2章 经典规划的表示 17

2.1 引言 17

2.2　集合论表示 18

2.2.1　规划领域、规划问题和规划解 18

2.2.2　状态可达性 20

2.2.3 规划问题的表述 21

2.2.4 集合表示的性质 22

2.3　经典规划表示 24

2.3.1 状态 24

2.3.2　操作与动作 25

2.3.3 计划、规划问题和解 27

2.3.4 经典规划表示的语义 29

2.4　经典规划表示的扩展 30

2.4.1 简单的语法扩展 30

2.4.2　条件规划操作 31

2.4.3 定量表示 32

2.4.4　析取前提条件 33

2.4.5　利用公理推理 34

2.4.6 函数符号 35

2.4.7 附加程序 35

2.4.8　扩展的目标 35

2.5　状态变量表示 37

2.5.1 状态变量 37

2.5.2　操作和动作 39

2.5.3　领域和问题 40

2.5.4 性质 42

2.6 比较 43

2.7　讨论和有关历史的评论 44

2.8 练习 46

第3章 经典规划的复杂性 49

3.1 引言 49

3.2　预备知识 50

3.3 判定性和不可判定性结果 51

3.4　复杂性结果 52

3.4.1 二元计数器 54

3.4.2 无限制的经典规划 55

3.4.3 其他结果 57

3.5 局限性 59

3.6　讨论和关于历史的评论 59

3.7 练习 60

第4章　状态空间规划 61

4.1 引言 61

4.2　正向搜索 61

4.2.1 几个性质 62

4.2.2　确定的执行 64

4.3　反向搜索 65

4.4　STRIPS算法 67

4.5　特定领域的状态空间规划 69

4.5.1 集装箱堆放领域 70

4.5.2　规划算法 70

4.6　讨论和有关历史的评论 72

4.7 练习 72

第5章 规划空间规划 75

5.1 引言 75

5.2　部分规划的搜索空间 75

5.3　解规划 80

5.4　规划空间规划的算法 83

5.4.1　PSP算法 83

5.4.2　PoP算法 88

5.5　扩展 89

5.6　规划空间和状态空间规划的对比 90

5.7　讨论和有关历史的评论 92

5.8　练习 93

第2部分　类经典规划 99

第6章　图规划技术 101

6.1　引言 101

6.2　规划图 102

6.2.1　可达树 102

6.2.2　基于规划图的可达性分析 104

6.2.3 独立动作与分层规划 107

6.2.4　互斥关系 108

6.3　Graphplan规划器 110

6.3.1　扩展规划图 110

6.3.2　搜索规划图 112

6.3.3　Graphplan分析 116

6.4　Graphplan的扩展和改进 118

6.4.1　语言的扩展 118

6.4.2 规划器的改进 119

6.4.3 独立关系的扩充 121

6.5　讨论和有关历史的评论 123

6.6　练习 125

第7章　命题可满足技术 128

7.1 引言 128

7.2　规划问题表示为可满足问题 128

7.2.1 状态表示为命题公式 129

7.2.2　状态转换表示为命题公式 130

7.2.3　规划问题表示为命题公式 131

7.3 用可满足过程求解规划 135

7.3.1　Davis-Putnam 过程 135

7.3.2 随机过程 140

7.4　其他编码方法 143

7.4.1 动作的表示 144

7.4.2 框架公理 145

7.5 讨论和有关历史的评论 147

7.6 练习 148

第8章　约束可满足技术 149

8.1 引言 149

8.2　约束可满足问题 150

8.3　规划问题表示为CSP 153

8.3.1 规划问题编码为CSP 155

8.3.2 CSP编码的分析 158

8.4 CSP技术和算法 159

8.4.1 求解CSP的搜索算法 159

8.4.2　过滤技术 161

8.4.3　局部搜索技术和混合方法 165

8.5　扩展的CSP模型 165

8.5.1 活动的CSP 166

8.5.2　带值的CSP 167

8.6 规划中的CSP技术 167

8.6.1 规划空间搜索中的CSP技术 168

8.6.2 图规划技术的CSP 169

8.7　讨论和有关历史的评论 170

8.8　练习 171

第3部分 启发式信息和控制策略 173

第9章 规划中的启发式信息 177

9.1 引言 177

9.2　启发式信息设计原则：放宽原问题 178

9.3　状态空间规划的启发式信息 179

9.3.1　放宽条件下的状态可达性 179

9.3.2 反向启发式搜索 182

9.3.3　状态空间启发式信息的可纳性 183

9.3.4 启发式搜索规划器：Craphplan 185

9.4　规划空间规划的启发式信息 186

9.4.1 选择缺陷的启发式信息 187

9.4.2 选择修复办法的启发式信息 190

9.5　讨论和有关历史的评论 191

9.6 练习 193

第10章 规划中的控制规则 194

10.1 引言 194

10.2　简单时态逻辑 195

10.3　公式的前向计算 197

10.4　规划程序 199

10.5 扩展 200

10.6　扩展目标 201

10.7 讨论和有关历史的评论 203

10.8 练习 204

第11章 分层任务网络规划 206

11.1 引言 206

11.2　简单任务网络（STN）规划 208

11.2.1 任务和方法 208

11.2.2 规划问题及规划解 212

11.3 全序STN规划 215

11.4　部分序STN规划 216

11.5 HTN规划 220

11.5.1　任务网络 221

11.5.2 HTN方法 222

11.5.3 HTN规划问题及规划解 224

11.5.4　规划程序 225

11.6 比较 226

11.6.1 HTN规划与STN规划的比较 226

11.6.2 HTN方法与控制规则的比较 228

11.7 扩展 229

11.7.1 来自第2章的扩展 229

11.7.2　其他扩展 232

11.8 扩展目标 232

11.9　讨论和有关历史的评价 234

11.10 练习 236

第12章　演绎规划中的控制策略 239

12.1 引言 239

12.2　情景演算 240

12.2.1 情景 240

12.2.2 动作 241

12.2.3　规划领域、规划问题和规划解 243

12.2.4 基于情景演算的纲要规划 244

12.3 动态逻辑 246

12.3.1　动态逻辑语言 247

12.3.2 动态逻辑的语义 247

12.3.3 演绎原理 248

12.3.4　规划领域、规划问题和规划解 249

12.3.5　扩展 250

12.3.6 用户自定义控制策略 251

12.4　讨论和有关历史的评论 252

12.5 练习 254

第4部分　时间和资源约束规划 257

第13章 规划中的时间 260

13.1 引言 260

13.2　时态参照和关系 260

13.3　定性时态关系 264

13.3.1 点代数 264

13.3.2 区间代数 267

13.3.3 区间代数的几何解释 272

13.3.4 区间代数与点代数的比较 273

13.4　定量时态约束 275

13.4.1 简单时态约束 275

13.4.2 时态约束网络 277

13.5　讨论和有关历史的评论 278

13.6 练习 279

第14章　时态规划 281

14.1 引言 281

14.2　采用时态操作的规划方法 282

14.2.1 时态表示和时态数据库 282

14.2.2 时态规划操作 285

14.2.3 领域公理 288

14.2.4 时态规划领域、规划问题和规划解 290

14.2.5　有干扰效果的并行动作 291

14.2.6　一个时态规划程序 293

14.3　含年代记的规划方法 296

14.3.1　状态变量、时间线和年代记 296

14.3.2　将年代记作为规划操作 303

14.3.3　年代记规划程序 305

14.3.4 CP中的约束管理 308

14.3.5　CP中的搜索控制策略 310

14.4　讨论和有关历史的评论 312

14.5 练习 314

第15章 规划与资源调度 317

15.1 引言 317

15.2　调度问题的要素 319

15.2.1 动作 319

15.2.2 资源 320

15.2.3 约束和费用函数 322

15.3　机器调度问题 323

15.3.1 机器调度问题的分类 323

15.3.2　机器调度的复杂性 325

15.3.3　机器调度问题的求解 326

15.3.4　规划和机器调度 326

15.4　结合规划和调度 328

15.4.1 表示 328

15.4.2 检测资源冲突 332

15.4.3 管理资源冲突缺陷 335

15.5　讨论和有关历史的评论 337

15.6 练习 338

第5部分　不确定规划 341

第16章 基于Markov决策过程的规划 344

16.1 引言 344

16.2　在完全可观察的领域内作规划 345

16.2.1 规划领域、规划和规划问题 345

16.2.2 规划算法 350

16.3　在部分可观察的领域内作规划 356

16.3.1　规划领域、规划和规划问题 356

16.3.2　规划算法 359

16.4 可达性目标和扩展目标 360

16.5　讨论和有关历史的评论 361

16.6 练习 363

第17章 基于模型检测的规划 365

17.1 引言 365

17.2　对可达性目标作规划 366

17.2.1　规划领域、规划和规划问题 367

17.2.2　规划算法 370

17.3　对扩展目标作规划 376

17.3.1　规划领域、规划和规划问题 376

17.3.2　规划算法 380

17.3.3 另一种表示规划目标的方法 383

17.4　在部分可观察的领域内作规划 386

17.4.1　规划领域、规划和规划问题 387

17.4.2　规划算法 391

17.5 基于模型检测的规划方法与MDP规划方法之间的比较 393

17.6　讨论和有关历史的评论 394

17.7 练习 395

第18章 用于不确定规划的类经典技术 397

18.1 引言 397

18.2 可满足规划 397

18.2.1 规划问题 397

18.2.2　将规划问题编码成命题公式 399

18.2.3 可满足规划　 402

18.2.4 QBF规划　 403

18.3 图规划　 403

18.4　讨论和有关历史的评论　 406

18.5 练习　 407

第6部分　案例研究与应用　 409

第19章 空间应用 411

19.1 引言 411

19.2　深度空间一号　 411

19.3 自治的远程代理系统 412

19.4　远程代理的系统架构 413

19.5　规划器的架构 417

19.6　深度空间一号的试验 421

19.6.1　检验任务 421

19.6.2　试验计划 422

19.6.3 试验结果 423

19.6.4 经验总结　 425

19.7　讨论和有关历史的评论　 425

第20章　机器人规划 427

20.1 引言　 427

20.2　路径和运动规划 429

20.3　规划用于鲁棒控制器设计　 434

20.3.1 传感马达功能　 435

20.3.2 模式　 437

20.3.3　控制器　 440

20.3.4 本方法的分析　 443

20.4　码头工人机器人　 444

20.5　讨论和有关历史的评论　 446

第21章 工艺性能分析规划　　 448

21.1 引言　 448

21.2　加工后的零件 449

21.3　特征抽取　 450

21.4　产生抽象的规划 451

21.5　解决目标的相互作用 454

21.6　附加步骤 455

21.7　加工操作规划评价 456

21.8　效率的考虑 457

21.9　结语 458

第22章　应急疏散规划　 459

22.1 引言　 459

22.2 疏散行动 460

22.3　知识表示 461

22.3.1 分层任务网络　 461

22.3.2　案例　 462

22.4　分层任务编辑器　 462

22.5　SiN　 463

22.5.1 SiN工作过程　 463

22.5.2　SiN的正确性　 464

22.5.3　完全的世界信息 465

22.6 例子 466

22.7 总结 468

22.8　讨论和有关历史的评价　 469

第23章　桥牌游戏中的规划 470

23.1 引言　 470

23.2　桥牌简介 470

23.3　桥牌中博弈树搜索 471

23.4　用于桥牌的改进全序HTN规划 473

23.5　实现与结果　 476

第7部分　结论 477

第24章　其他规划方法　 478

24.1　基于案例的规划　 478

24.2　线性和整数规划 480

24.3　多agent规划 481

24.4　计划合并与计划重写 482

24.5　抽象层次 483

24.6　领域分析 484

24.7　规划与学习 485

24.8　规划与行动，情景规划和动态规划 486

24.9　计划识别 488

24.10　对将来工作的建议 490

第8部分　附录 491

附录A 搜索程序和计算复杂性　 492

A.1　不确定问题求解 492

A.2 状态空间搜索 493

A.3 问题归约搜索 497

A.4　程序的计算复杂性 499

A.5 问题的计算复杂性 499

A.6 将规划领域转换为语言识别问题 501

A.7　讨论和有关历史的评论 502

附录B 一阶逻辑 503

B.1 引言 503

B.2　命题逻辑 503

B.3 一阶逻辑 505

附录C 模型检测 508

C.1　引言 508

C.2　直观解释 508

C.3　模型检测问题 510

C.4　模型检测算法 512

C.5　符号模型检测 513

C.6　基于BDD的符号模型检测 516

参考文献 519

英汉名词对照索引 555