规划算法PDF电子书下载

第Ⅰ部分 介绍性的资料 2

第1章 绪论 2

1.1 从规划（的过程）到规划（的结果） 2

1.2 实例与应用 3

1.3 规划的基本组成 11

1.4 算法、规划器与规划 12

1.4.1 算法 12

1.4.2 规划器 13

1.4.3 规划 13

1.5 本书的组织安排 15

第2章 离散规划 18

2.1 离散可行规划简介 18

2.1.1 问题表述 18

2.1.2 离散规划的实例 19

2.2 可行规划的搜索 21

2.2.1 一般前向搜索 21

2.2.2 特殊前向搜索 23

2.2.3 其他搜索方案 26

2.2.4 搜索方法的统一描述 28

2.3 离散最优规划 29

2.3.1 最优定长规划 30

2.3.2 不指定长度的最优规划 34

2.3.3 再论Dijkstra算法 37

2.4 用逻辑来表示离散规划 38

2.4.1 类似STRIPS的表示 39

2.4.2 转换到状态空间表示 41

2.5 基于逻辑的规划方法 42

2.5.1 部分规划空间中的搜索 43

2.5.2 建立规划图 44

2.5.3 满足性规划 46

进一步阅读 48

习题 49

实现 50

第Ⅱ部分 运动规划 55

第3章 几何表示与变换 55

3.1 几何建模 55

3.1.1 多边形与多面体模型 56

3.1.2 半代数模型 59

3.1.3 其他模型 60

3.2 刚体变换 62

3.2.1 一般概念 62

3.2.2 二维变换 64

3.2.3 三维变换 65

3.3 物体运动链的变换 68

3.3.1 二维运动链 68

3.3.2 三维运动链 70

3.4 运动树的变换 77

3.5 非刚体的变换 82

进一步阅读 83

习题 83

实现 85

第4章 位形空间 86

4.1 拓扑的基本概念 86

4.1.1 拓扑空间 86

4.1.2 流形 90

4.1.3 路径与连通 94

4.2 位形空间 97

4.2.1 二维刚体：SE（2） 97

4.2.2 三维刚体：SE（3） 100

4.2.3 物体的链与树 103

4.3 位形空间障碍物 104

4.3.1 基本运动规划问题 104

4.3.2 显式建模Cobs：平移情况 106

4.3.3 显式建模Cobs：一般情形 110

4.4 闭运动链 112

4.4.1 数学概念 113

4.4.2 R2上的运动链 115

4.4.3 定义一般连杆组的簇 118

进一步阅读 121

习题 121

实现 124

第5章 基于采样的运动规划 125

5.1 C-空间中的距离与体积 126

5.1.1 度量空间 126

5.1.2 运动规划中重要的度量空间 127

5.1.3 基本测度理论的定义 129

5.1.4 使用正确的测度 130

5.2 采样理论 131

5.2.1 目的与基本概念 131

5.2.2 随机采样 133

5.2.3 低离散度采样 135

5.2.4 低差异采样 139

5.3 碰撞检测 141

5.3.1 基本概念 141

5.3.2 层次法 142

5.3.3 增量法 143

5.3.4 检验路径片段 144

5.4 递增采样与搜索 147

5.4.1 一般架构 147

5.4.2 改进离散搜索算法 149

5.4.3 随机势场 152

5.4.4 其他方法 153

5.5 快速探索稠密树 154

5.5.1 探索算法 155

5.5.2 有效地发现最近点 157

5.5.3 在规划中使用树 159

5.6 多疑问问题的路线图方法 160

5.6.1 基本方法 160

5.6.2 可视路线图 163

5.6.3 改进路线图的启发式方法 164

进一步阅读 166

习题 167

实现 168

第6章 组合运动规划 169

6.1 简介 169

6.2 多边形障碍区域 170

6.2.1 问题的表示 170

6.2.2 垂直胞腔剖分 172

6.2.3 最大间隙路线图 175

6.2.4 最短路径路线图 176

6.3 胞腔剖分 179

6.3.1 一般定义 179

6.3.2 二维剖分 181

6.3.3 三维垂直剖分 183

6.3.4 线段机器人的剖分 184

6.4 计算代数几何 190

6.4.1 基本定义与概念 190

6.4.2 圆柱代数剖分 193

6.4.3 Canny的路线图算法 198

6.5 运动规划的复杂性 201

6.5.1 下界 202

6.5.2 Davenport-Schinzel序列 204

6.5.3 上界 205

进一步阅读 207

习题 208

实现 209

第7章 基本运动规划的扩展 210

7.1 时变问题 210

7.1.1 问题的表述 210

7.1.2 直接解 212

7.1.3 速度调节方法 214

7.2 多机器人 215

7.2.1 问题的表述 215

7.2.2 解耦规划 218

7.3 离散与连续空间的混合空间 221

7.3.1 混合系统的架构 221

7.3.2 操作规划 225

7.4 闭运动链的规划 228

7.4.1 运动规划算法的适应性修改 229

7.4.2 主动-被动连杆的分解 232

7.5 机器人学和生物学中的折叠问题 235

7.6 覆盖规划 239

7.7 最优运动规划 241

7.7.1 一个机器人的最优性 241

7.7.2 多机器人的最优性 245

进一步阅读 246

习题 247

实现 248

第8章 反馈运动规划 250

8.1 目的 250

8.2 离散状态空间 251

8.2.1 反馈规划 251

8.2.2 将反馈规划作为导航函数 253

8.2.3 运动规划的基于栅格的导航函数 255

8.3 向量场与积分曲线 257

8.3.1 Rn上的向量场 258

8.3.2 平滑流形 263

8.4 连续空间中的完备方法 269

8.4.1 反馈运动规划 269

8.4.2 胞腔复形上的向量场 272

8.4.3 最优导航函数 273

8.4.4 考虑动力学的向量场 275

8.5 连续空间中基于采样的方法 279

8.5.1 计算一个漏斗组合 279

8.5.2 带插值的动态规划 283

进一步阅读 290

习题 291

实现 292

第Ⅲ部分 决策论规划 295

第9章 基本决策理论 295

9.1 基本概念 295

9.1.1 最优化 295

9.1.2 回顾概率论 298

9.1.3 随机策略 300

9.2 与大自然之间的对策 301

9.2.1 对大自然的建模 301

9.2.2 非确定模型和概率模型 302

9.2.3 利用观测 305

9.2.4 最优决策的例子 307

9.3 两人零和对策 310

9.3.1 对策表述 310

9.3.2 确定的策略 311

9.3.3 随机策略 314

9.4 非零和对策 317

9.4.1 两人对策 317

9.4.2 多人对策 322

9.5 对决策理论的进一步思考 323

9.5.1 效用理论与合理性 324

9.5.2 关于概率模型的问题 328

9.5.3 关于非确定模型的问题 330

9.5.4 关于对策论的有关问题 332

进一步阅读 332

习题 333

实现 335

第10章 序贯决策理论 336

10.1 与大自然之间的序贯对策 336

10.1.1 模型定义 336

10.1.2 前向投影与后向投影 340

10.1.3 一个规划及其执行 343

10.2 计算反馈规划的算法 345

10.2.1 值迭代 345

10.2.2 策略迭代 349

10.2.3 图搜索方法 351

10.3 无限范围问题 354

10.3.1 问题表述 354

10.3.2 求解技术 355

10.4 强化学习 358

10.4.1 一般原理 358

10.4.2 通过模拟来评估规划 359

10.4.3 Q-学习：计算最优规划 362

10.5 序贯对策论 363

10.5.1 对策树 364

10.5.2 状态空间上的序贯对策 369

10.5.3 其他序贯对策 372

10.6 连续状态空间 374

进一步阅读 377

习题 378

实现 379

第11章 传感器与信息空间 380

11.1 离散状态空间 381

11.1.1 传感器 381

11.1.2 历史信息空间 384

11.1.3 定义规划问题 385

11.2 衍生的信息空间 388

11.2.1 信息映射 388

11.2.2 非确定的信息空间 390

11.2.3 概率信息空间 392

11.2.4 有限记忆信息空间 394

11.3 离散状态空间的实例 394

11.3.1 基本的非确定性的实例 394

11.3.2 非确定的有限自动机 397

11.3.3 概率情形：POMDPs 400

11.4 连续状态空间 400

11.4.1 离散阶段信息空间 400

11.4.2 连续时间信息空间 401

11.4.3 衍生的信息空间 402

11.5 连续状态空间的例子 407

11.5.1 传感器模型 407

115.2 简单投影的例子 412

11.5.3 大自然感测行动的例子 414

11.5.4 在没有传感器的情况下获得信息 416

11.6 计算概率信息状态 417

11.6.1 卡尔曼滤波 417

11.6.2 基于采样的方法 419

11.7 对策论中的信息空间 421

11.7.1 对策树中的信息状态 421

11.7.2 状态空间上对策的信息空间 424

进一步阅读 426

习题 427

实现 429

第12章 存在感测不确定性条件下的规划 430

12.1 一般方法 431

12.1.1 将信息空间作为一个大的状态空间 431

12.1.2 非确定的I-空间中的算法 433

12.1.3 概率I-空间中的算法（POMDPs） 434

12.2 定位 435

12.2.1 离散定位 435

12.2.2 连续定位的组合方法 440

12.2.3 定位的概率方法 442

12.3 环境不确定性与制图 444

12.3.1 栅格问题 445

12.3.2 Stentz算法（D*） 450

12.3.3 未知连续环境中的规划 452

12.3.4 没有几何模型情况下的最优导航 456

12.3.5 概率定位与制图 460

12.4 基于可视性的追-逃问题 462

12.4.1 问题的表述 462

12.4.2 一个完备算法 465

12.4.3 其他类型 467

12.5 存在感测不确定性下的操作规划 468

12.5.1 原像规划 468

12.5.2 非抓握操作 473

进一步阅读 476

习题 477

实现 479

第Ⅳ部分 微分约束条件下的规划 482

第13章 微分模型 482

13.1 位形空间上的速度约束 482

13.1.1 隐含表示与参数表示 482

13.1.2 轮式系统的运动学 487

13.1.3 速度约束的其他实例 492

13.2 动力系统的相空间表示 495

13.2.1 通过增加维数来减小自由度 496

13.2.2 线性系统 498

13.2.3 非线性系统 499

13.2.4 通过增加积分器来对模型进行扩展 500

13.3 基本牛顿-欧拉力学 502

13.3.1 牛顿模型 503

13.3.2 质点运动 504

13.3.3 刚体运动 508

13.4 先进的力学概念 513

13.4.1 拉格朗日力学 514

13.4.2 一般拉格朗日表达式 518

13.4.3 欧拉-拉格朗日方程的扩展 521

13.4.4 哈密顿力学 524

13.5 多决策者 526

13.5.1 微分决策 526

13.5.2 微分对策论 527

进一步阅读 528

习题 529

实现 530

第14章 微分约束条件下基于采样的规划 531

14.1 简介 531

14.1.1 问题表述 531

14.1.2 不同类型的规划问题 533

14.1.3 相空间中的障碍物 535

14.2 可达性与完备性 538

14.2.1 可达集合 538

14.2.2 离散时间模型 540

14.2.3 运动本原 545

14.3 再论基于采样的运动规划 546

14.3.1 基本组成 546

14.3.2 系统模拟器 548

14.3.3 局部规划 551

14.3.4 微分约束下的一般框架 552

14.4 递增采样和搜索方法 553

14.4.1 在网格上进行搜索 554

14.4.2 结合状态空间离散化 559

14.4.3 RDT方法 562

14.4.4 其他方法 565

14.5 微分约束条件下的反馈规划 566

14.5.1 问题的定义 566

14.5.2 带插值的动态规划 566

14.6 解耦规划法 568

14.6.1 解耦大问题的不同方法 568

14.6.2 规划与变换 569

14.6.3 具有路径约束的轨迹规划 571

14.7 基于梯度的轨迹优化 577

进一步阅读 579

习题 580

实现 580

第15章 系统理论与分析技术 582

15.1 系统的基本特性 582

15.1.1 稳定性 582

15.1.2 李亚普诺夫函数 584

15.1.3 可控性 586

15.2 连续时间动态规划 588

15.2.1 Hamilton-Jacobi-Bellman方程 588

15.2.2 线性二次型问题 590

15.2.3 庞特里亚金最小值原理 591

15.3 一些轮式车辆的最优路径 595

15.3.1 Dubins曲线 595

15.3.2 Reeds-Shepp曲线 598

15.3.3 Balkcom-Mason曲线 600

15.4 非完整性系统理论 602

15.4.1 仿射控制系统 602

15.4.2 确定一个系统是否是非完整的 604

15.4.3 确定可控性 611

15.5 非完整性系统的操控方法 616

15.5.1 使用Philip Hall基 616

15.5.2 采用正弦行动轨迹 621

15.5.3 其他操控方法 624

进一步阅读 625

习题 626

实现 627

参考文献 628

英汉词汇对照表 674