规划算法

《规划算法》是2011年清华大学出版社出版的图书，作者是拉瓦利(StevenM.LaValle)。本书是作者多年来教学和科研州工作的总结，系统地介绍了规划领域中的基础知识和成果。

• 书名 规划算法
• 作者 拉瓦利(StevenM.LaValle)
• ISBN 9787302230410
• 定价 99.00
• 出版社 清华大学出版社

编辑推荐

　　《规划算法》内容简介:规划是人类智慧的结晶，规划问题广泛地存在于人们的日常工作和生活中。现在，规划已涉及计算机科学、人工智能、力学、机械学、控制论、对策论、概率论、图论、拓扑学、微分几何、代数几何等许多现代科学领域。作者将三个相来自对独立的学科:机器人学、人工智能和控制论巧妙地结合在一起。《规划算法》给出了大量内容详实的实例，使本来相对比较难以理解的数学问题变得生动起来，课后的阅读参考和练习题则能够进一步加深和扩展读者对相应内容的理解。

内容简介

　　《规划算法》可以作为计算机类、控制类专业高年级本科学360百科生或者研究生的教科书，也可以作为从事机器人学、控制科学、计算机科学研仍晚究的广大读者的参宜理节永考书，其中的思想方法对社会科学工作者也大有益处。

图来自书目录

　　第Ⅰ部分介绍360百科性的资料

　　第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 类似S赶坚需体背TRIPS的表示 39

　　2.4.2 转换到状态空间表示 41

　　2.5 基于逻辑的规划方法 42

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

　　2.5.2 建立规划图 44

　　2.5.3 满足性规划 46

　　进一步阅读 48

　　习题 49

　　实现 50

　　第Ⅱ部分 运 动 规 划

　　第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 上的运动链 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 上的向量场 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

　　第Ⅲ部分 决策论规划

　　第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

　　11.5.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

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

　　第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