路径规划之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、视图法。