規劃算法 LaValle 中文版

規劃算法  LaValle  中文版

第Ⅰ部分介紹性的資料

第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