规划算法LaValle 中文版

eisbergeisberg · 发表于 2022-6-21 15:19:32

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？注册

x

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

第Ⅰ部分介绍性的资料
第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
第Ⅱ部分运动规划
第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