路徑規劃算法--Dijkstra算法，A*算法，CBS算法

路徑規劃算法

寫的比較糙，作為筆記，寫到自己看懂的程度，細節沒展開寫，也在學習中，歡迎讨論

一、Dijkstra算法

基本思想：通過Dijkstra計算圖G中的最短路徑時，需要指定起點s。

流程：

（1）引進兩個集合，open list：存放未求出最短路徑的頂點及其距離；close list存放已求出最短路徑的頂點及其距離。

（2）初始時，close list隻有起點s，距離為0；open list是除起點s之外的所有頂點及其距離。

（3）從open list取出距離最短的頂點及其距離放入到close list中；接着，更新open list中頂點的距離。

（4）更新完後，重複（3）的操作，直到找到目标點或open list 變為空。

二、A*算法總結

基本思想

A算法把Dijkstra算法（靠近初始點的結點）和最佳優先搜尋算法（BFS）（靠近目标點的結點）的資訊塊結合起來。

在讨論A算法的标準術語中，g(n)表示從初始結點到任意結點n的代價，h(n)表示從節點n到目标點的啟發式評估代價，當從初始點向目标點移動時，A*權衡這兩者。每次進行主循環時，它檢查f(n)最小的結點n，其中f(n)=g(n) + h(n).

流程：

（1）引進兩個集合，open list：存放待檢測的結點及F值；close list：已檢測過的結點及F值。

（2）初始時，把起點s放入到open list中，close list為空。

（3）取出open list中F值最小的結點，設為目前結點，把目前結點放入到close list中；周遊目前結點的相鄰可達結點，相鄰結點在close list，則跳過，否則加入/更新open list ；加入或更新的結點以目前結點為父節點。

（4）重複（3）操作，直到目前節點為目标結點或open list變為空。

三、CBS算法（基于沖突的搜尋算法）

上層：解決多AGV之間的路徑沖突 ，引入限制樹結點的概念；

下層：多個單AGV路徑規劃。

流程：

（1）下層使用A*算法求出多個單AGV路徑規劃。

（2）引入優先級隊列 open list，将限制樹根節點R放入open list，以R.cost為鍵值，R包含R.constraints（為空），R.solution（多個單AGV的路徑規劃集合），R.cost（解的成本）。

（3）open list取出成本最低的結點N，N.solution無沖突，則N.cost為所求解；否則，對第一個沖突處理，針對沖突的點，分裂為若幹個子節點，繼承目前結點的全部限制和解，并分别添加新的限制，更新路徑和cost值。

（4）重複執行（3）操作，直到open list的成本最低節點N的解無沖突或求解失敗

四、IDA*算法

疊代加深搜尋算法，在搜尋過程中采用估值函數，以減少不必要的搜尋。

IDA* 算法核心：設定每次可達的最大深度depth，若沒有到達目标狀态則加深最大深度。采用估值函數，剪掉f(n)大于depth的路徑。

優點：

使用回溯方法，不用儲存中間狀态，大大節省了空間。

缺點：

重複搜尋：回溯過程中每次depth變大都要再次從頭搜尋。

用途：

和A*算法大緻相同。