路徑規劃之A演算法

A. 局部路徑規劃演算法

局部路徑規劃，常用的演算法有柵格法、人工勢場法、遺傳演算法、空間搜索法、層次法、動作行為法、Dijkstra演算法、Lee演算法、Floyd演算法等

B. 有哪些應用於移動機器人路徑規劃的演算法

機器人家上了解到，在二維二值地圖（FREE or OCCUPIED）場景下進行路徑規劃的方法。我看之前有同學在回答的時候配上了這幅圖：

這幅圖上的演算法羅列的還是很全面的，體現了各個演算法的出生順序。但是並不能很好的對他們進行一個本質的分類。剛剛那位同學說的graph-based和sampling-based的分類方法我感覺有點概念重疊不能夠對規劃演算法進行這樣的分類，下面通過自己這一年多的研究和實踐對規劃演算法進行一個簡單的分類：

這幅圖上的演算法羅列的還是很全面的，體現了各個演算法的出生順序。但是並不能很好的對他們進行一個本質的分類。剛剛那位同學說的graph-based和sampling-based的分類方法我感覺有點概念重疊不能夠對規劃演算法進行這樣的分類，下面通過自己這一年多的研究和實踐對規劃演算法進行一個簡單的分類：

兩大類：
1. 完備的（complete)
2. 基於采樣的（sampling-based）又稱為概率完備的

一 完備的規劃演算法

A*演算法

所謂完備就是要達到一個systematic的標准，即：如果在起始點和目標點間有路徑解存在那麼一定可以得到解，如果得不到解那麼一定說明沒有解存在。
這一大類演算法在移動機器人領域通常直接在occupancy grid網格地圖上進行規劃（可以簡單理解成二值地圖的像素矩陣）以深度優先尋路演算法、廣度優先尋路演算法、Dijkstra(迪傑斯特拉)演算法為始祖，以A*演算法(Dijstra演算法上以減少計算量為目的加上了一個啟發式代價)最為常用，近期的Theta*演算法是在A*演算法的基礎上增加了line-of-sight優化使得規劃出來的路徑不完全依賴於單步的柵格形狀（答主以為這個演算法意義不大，不就是規劃了一條路徑再簡單平滑了一下么）。
完備的演算法的優勢在與它對於解的捕獲能力是完全的，但是由此產生的缺點就是演算法復雜度較大。這種缺點在二維小尺度柵格地圖上並不明顯，但是在大尺度，尤其是多維度規劃問題上，比如機械臂、蛇形機器人的規劃問題將帶來巨大的計算代價。這樣也直接促使了第二大類演算法的產生。

二 基於采樣的規劃演算法

RRT-connect演算法
這種演算法一般是不直接在grid地圖進行最小柵格解析度的規劃，它們採用在地圖上隨機撒一定密度的粒子來抽象實際地圖輔助規劃。如PRM演算法及其變種就是在原始地圖上進行撒點，抽取roadmap在這樣一個拓撲地圖上進行規劃；RRT以及其優秀的變種RRT-connect則是在地圖上每步隨機撒一個點，迭代生長樹的方式，連接起止點為目的，最後在連接的圖上進行規劃。這些基於采樣的演算法速度較快，但是生成的路徑代價（可理解為長度）較完備的演算法高，而且會產生「有解求不出」的情況（PRM的逢Narrow space卒的情況）。這樣的演算法一般在高維度的規劃問題中廣泛運用。

三 其他規劃演算法
除了這兩類之外還有間接的規劃演算法：Experience-based（Experience Graph經驗圖演算法）演算法：基於經驗的規劃演算法，這是一種存儲之前規劃路徑，建立知識庫，依賴之進行規劃的方法，題主有興趣可以閱讀相關文獻。這種方法犧牲了一定的空間代價達到了速度與完備兼得的優勢。此外還有基於廣義Voronoi圖的方法進行的Fast-marching規劃，類似dijkstra規劃和勢場的融合，該方法能夠完備地規劃出位於道路中央，遠離障礙物的路徑。答主最近也在研究此類演算法相關的工作。

APF（人工勢場）演算法

至於D* 、勢場法、DWA(動態窗口法)、SR-PRM屬於在動態環境下為躲避動態障礙物、考慮機器人動力學模型設計的規劃演算法。

C. A*演算法用於路徑規劃，有什麼缺點

缺點：A*演算法通過比較當前路徑柵格的8個鄰居的啟發式函數值F來逐步確定下一個路徑柵格，當存在多個最小值時A*演算法不能保證搜索的路徑最優。
A*演算法；A*（A-Star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好。A*[1] （A-Star)演算法是一種靜態路網中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索演算法。之後涌現了很多預處理演算法（ALT，CH，HL等等），在線查詢效率是A*演算法的數千甚至上萬倍。公式表示為： f(n)=g(n)+h(n),其中 f(n) 是從初始點經由節點n到目標點的估價函數，g(n) 是在狀態空間中從初始節點到n節點的實際代價，h(n) 是從n到目標節點最佳路徑的估計代價。保證找到最短路徑（最優解的）條件，關鍵在於估價函數f(n)的選取：估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。並且如果h(n)=d(n)，即距離估計h(n)等於最短距離，那麼搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的。如果 估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

D. 機器人路徑規劃中傳統演算法和智能演算法的區別

傳統演算法雖然結果一定是最優解，但是運算量極大，可能會有lag。
相反，採用一定的智能演算法，雖然每次選擇不一定最優，但是基本上都能快速（<=0.1s）判斷，而且只要設定一定的糾錯演算法，總體效率遠高於傳統演算法。

E. 常見的路徑規劃方法有那些

最速下降法、部分貪婪演算法， Dijkstra演算法、Floyed演算法、SPFA演算法(Bellman_Ford的改進演算法)、A*演算法、D*演算法、圖論最短演算法，遺傳演算法、元胞自動機、免疫演算法、禁忌搜索、模擬退火、人工神經網路、蟻群演算法、粒子群演算法等

F. 路徑規劃有幾種方法

路徑規劃模塊需要根據局部環境感知、可用的全局車道級路徑、相關交通規則，提供能夠將車輛引導向目的地（或目的點）的路徑。路徑規劃可分為全局路徑規劃方法、局部路徑規劃方法和混合路徑規劃方法三種。

G. 模糊演算法路徑規劃C語言實現的程序，感激不盡。

僅供參考~

#define MAX_VERTEX_NUM 100 //最大頂點數
#define MAX_INT 10000 //無窮大

typedef int AdjType;

typedef struct{
int pi[MAX_VERTEX_NUM];//存放v到vi的一條最短路徑
int end;
}PathType;
typedef char VType; //設頂點為字元類型

typedef struct{
VType V[MAX_VERTEX_NUM]; //頂點存儲空間
AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //鄰接矩陣
}MGraph;//鄰接矩陣表示的圖

//Floyd演算法
//求網G（用鄰接矩陣表示）中任意兩點間最短路徑
//D[][]是最短路徑長度矩陣，path[][]最短路徑標志矩陣
void Floyd(MGraph * G,int path[][MAX_VERTEX_NUM],int D[][MAX_VERTEX_NUM],int n){
int i,j,k;
for(i=0;i<n;i++){//初始化
for(j=0;j<n;j++){
if(G->A[i][j]<MAX_INT){
path[i][j]=j;
}else{
path[i][j]=-1;
}
D[i][j]=G->A[i][j];
}
}
for(k=0;k<n;k++){//進行n次試探
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(D[i][j]>D[i][k]+D[k][j]){
D[i][j]=D[i][k]+D[k][j];//取小者
path[i][j]=path[i][k];//改Vi的後繼
}
}
}
}
}

int main(){
int i,j,k,v=0,n=6;//v為起點，n為頂點個數
MGraph G;
int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各頂點的最短路徑向量
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各頂點最短路徑長度向量
//初始化
AdjType a[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={
{0,12,18,MAX_INT,17,MAX_INT},
{12,0,10,3,MAX_INT,5},
{18,10,0,MAX_INT,21,11},
{MAX_INT,3,MAX_INT,0,MAX_INT,8},
{17,MAX_INT,21,MAX_INT,0,16},
{MAX_INT,5,11,8,16,0}
};
for(i=0;i<n;i++){
for(j=0;j<n;j++){
G.A[i][j]=a[i][j];
}
}
Floyd(&G,path,D,6);
for(i=0;i<n;i++){//輸出每對頂點間最短路徑長度及最短路徑
for(j=0;j<n;j++){
printf("V%d到V%d的最短長度:",i,j);
printf("%d\t",D[i][j]);//輸出Vi到Vj的最短路徑長度
k=path[i][j];//取路徑上Vi的後續Vk
if(k==-1){
printf("There is no path between V%d and V%d\n",i,j);//路徑不存在
}else{
printf("最短路徑為:");
printf("(V%d",i);//輸出Vi的序號i
while(k!=j){//k不等於路徑終點j時
printf(",V%d",k);//輸出k
k=path[k][j];//求路徑上下一頂點序號
}
printf(",V%d)\n",j);//輸出路徑終點序號
}
printf("\n");
}
}
system("pause");
return 0;
}

H. 全局路徑規劃演算法

全局路徑規劃，主要演算法有
1、網格法、
2、拓撲法、
3、視圖法。