《規划算法》是2011年清華大學出版社出版的圖書，作者是拉瓦利(StevenM.LaValle)。本書是作者多年來教學和科研工作的總結，系統地介紹了規劃領域中的基礎知識和成果。
基本介紹
- 書名：規划算法
- 作者：拉瓦利(StevenM.LaValle)
- ISBN：9787302230410
- 定價：99.00
- 出版社：清華大學出版社
- 出版時間：2011年1月1日
- 開本：16開
編輯推薦,內容簡介,圖書目錄,
編輯推薦
《規划算法》內容簡介：規劃是人類智慧的結晶，規劃問題廣泛地存在於人們的日常工作和生活中。現在，規劃已涉及計算機科學、人工智慧、力學、機械學、控制論、對策論、機率論、圖論、拓撲學、微分幾何、代數幾何等許多現代科學領域。作者將三個相對獨立的學科：機器人學、人工智慧和控制論巧妙地結合在一起。《規划算法》給出了大量內容詳實的實例，使本來相對比較難以理解的數學問題變得生動起來，課後的閱讀參考和練習題則能夠進一步加深和擴展讀者對相應內容的理解。
內容簡介
《規划算法》可以作為計算機類、控制類專業高年級本科學生或者研究生的教科書，也可以作為從事機器人學、控制科學、計算機科學研究的廣大讀者的參考書，其中的思想方法對社會科學工作者也大有益處。
圖書目錄
第Ⅰ部分介紹性的資料
第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
英漢辭彙對照表 674
