需求： 根据用户的需要来推荐车位，关键是让人少走路，这就要同时考虑到周边环境、已经内部结构对车位的影响了，我们可以根据内部结构，周边环境对车位进行编码，通过关联用户的目的地，来推荐车位

条件需求考虑：

1，从目的地——出口（指电梯口——对此需要考虑电梯的选择）

2，从入口——停车位（目的地）

路径规划

学习网址：https://zhuanlan.zhihu.com/p/51372134

https://blog.csdn.net/weixin_39594441/article/details/101243168?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162796210616780357299147%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162796210616780357299147&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-3-101243168.pc_search_result_control_group&utm_term=%E8%B7%AF%E5%BE%84%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

https://blog.csdn.net/tjcwt2011/article/details/112463027?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162796210616780357299147%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162796210616780357299147&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-112463027.pc_search_result_control_group&utm_term=%E8%B7%AF%E5%BE%84%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

提供代码库：https://github.com/zhm-real/PathPlanning/blob/master/README.md

基于搜索的路径规划

1.1 图搜索法

​ 广度优先搜索算法 bfs ——无回溯（队列）

​ 深度优先搜索算法 dfs ——存在回溯（递归）

---

1.1.1 可视图法 （机器人全局规划的经典算法）

​ 描述：机器人——点 障碍物——多边形

​

​ 将障碍物替换成多边形，再依据S与G的位置连线，最后相当于呈现出图的样子，再根据最短路的求解算法规划最短路径

​ 缺点：时间问题，灵活性 ( 停车场的车具有流动性，对此方法不适用)

---

1.1.2 Dijkstra算法

​ <图1.1.2—1>

从①到⑤，求最短路。

一般dij

​ <图1.1.2—2>

#include<bits\stdc++.h>
using namespace std;
using std::pair;

int dis[mmax];//待更新的顶点 即从1开始（1不算）每一个对应的i结点所产生的最短路径为dis[i]
int v[mmax];//记号，记录每一个顶点是否已经被查
int map[mmax][mmax]; //存储地图（需要更新）
/*	main操作：
	由上面的图举例<图1.1.2—2>
	将dis[]赋予第一行——使图搜索从①开始
*/

//核心代码：
void dij1(int t)
{
    for(int i=1;i<=t;i++)
    {
        dis[i]=map[1][i]; //这里的处理是将dis赋值上从1到所有边的权值
    }
    dis[1]=0;
    v[1]=0;
    for(int i=1;i<t;i++)
    {
        int min=inf;
        int pos;
        //求最短的路
        for(int j=1;j<=t;j++)
        {
            if(!v[j]&&dis[j]<min)
            {
                min=dis[j];
           		pos=j;
            }
        }
        v[pos]=1;
        //更新dis[]
        for(int j=1;j<=t;j++)
        {
            if(!v[j]&&map[pos][j]+dis[pos]<dis[j]&&map[pos][j]<inf)
            {
                dis[j]=dis[pos]+map[pos][j];
            }
        }
    }
}

优化dij——堆实现

①，边优化——vector实行邻接表

②，时间优化——优先队列

#include<bits\stdc++.h>
using namespace std;
using std::pair;

typedef pair<int, int> pii;

struct edge{
    int to; //指向的点
    int weight; //单路径权值
    edge(int to,int weight):to(to),weight(weight){}
};
vector<vector<edge>> G(mmax);
//核心代码：
void dij2(int s)
{
    priority_queue<pii, vector<pii>, greater<pii> >Q;
    dis[s]=0;
    Q.push(pii(0,s));
    while(!Q.empty())
    {
        int u = Q.top().second;
        Q.pop();
        if(!done[u])
        {
            done[u]=1;
            for(int i=0;i<G[u].size();i++)
            {
                edge& e = G[u][i];
                int v=e.to;
                int w=e.weight;
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    Q.push(pii(dis[v],v));
                }
            }
        }
            
    }
}

就目前情况来看，dij算法在获取所要信息上没有什么问题，停车场整体信息已知，需要修改的就是不同停车点的信息，此外可以首先通过计算，对应不同出口将所有的选取方案计算出来，后期只需变动调整停车位即可。

缺点待补：后续对比参照时间复杂度和空间复杂度 一般停车位（以千计算）

---

1.1.3 A*算法（静态路网中求解最短路最有效的方法 ）

大致理解：

相较于原始搜索算法，A*算法利用预估权值，减少了搜索次数

总权值 G = 步次 S + 预估 L

这里预估 L 有两种方式，即计算点到目的地的距离。

两个表格（open list && close list）

主要程序步骤：

1：把起点加入open list

2：遍历open list ，查找G值最小点 point

3：把这个点（point）移到close list

4：此时遍历point点的相邻方格：

 ① 遍历close list ，如果存在，则忽略

​ ②如果该方格中存在障碍物，则忽略

​ ③遍历open list ，如果已存在，则检查路径，是否存在一条更好的路径。

​ ④取最小G的方格加入open list （将此方格设置为下一方格的父节点） ——> 存入open list时需要注意还得存入G值和该结点的父节点。

5：①当终点存入open list 时，结束。

  ②当open list 为空且未存入终点时，说明路径不存在

​ ③当终点未存入且open list 不为空时，步骤从2开始。

6：保存路径，从终点开始，依据每次存储的父节点移到到起点。

核心还是如何取权值 / 求预估值。

重点是预估的方法：

核心思想：贪婪+广搜

这里引申一种 IDA*算法 —— 迭代启发算法 （待补充）

相关题目链接：https://www.luogu.com.cn/problem/P2324

1.1.4 D*算法（动态路网）

• 维护一个优先队列（OpenList）来对场景中的路径节点进行搜索

先用A*寻找出路静，再从终点朝起点进行搜索

while()
{
从OPEN表中取k值最小的节点Y;
遍历Y的子节点a,计算a的h值 h(a)=h(Y)+Y到子节点a的权重C(Y,a)
{
    if(a in OPEN)     比较两个a的h值 
    if( a的h值小于OPEN表a的h值 )
    {
更新OPEN表中a的h值;k值取最小的h值
          有未受影响的最短路经存在
          break; 
    }
    if(a in CLOSE) 比较两个a的h值 //注意是同一个节点的两个不同路径的估价值
    if( a的h值<CLOSE表的h值 )
    {
	   更新CLOSE表中a的h值; k值取最小的h值;将a节点放入OPEN表
  	   有未受影响的最短路经存在
       break;
    }
    if(a not in both)
        将a插入OPEN表中;　//还没有排序
}
放Y到CLOSE表；
OPEN表比较k值大小进行排序；
}

D算法常用于移动机器人领域的路径规划，其衍生算法如Focused D ，D* lite，Field Ｄ* 目前已经是机器人路径规划的核心算法。

​ 相较于A*算法的比较：

​ A ∗ 算法实际上只适用于已经给定了从起始点到终点范围的明确地图或规划空间的情况。然而在很多实际应用场景中，智能体并不完全清楚自己周边的环境信息，或者只拥有一张不完整的地图。那么如果我们基于起始状态的地图进行规划得到的路径大概率是不正确的或是次优的。因此要求智能体具备根据最新状态来实时更新地图以及重规划的能力。一个简单的方法是每次收集到新的信息后就根据更新的地图进行一次上文中的A ∗ 。但是这样对计算资源的损耗与浪费是极大的，尤其是当更新信息不会实际影响到当前求解出的最优路径时。所以更优的方法应该是基于上一个周期的规划路径结合新的更新信息做一定的修复改变。这类算法就是增量式的重规划算法D * 。

​ D* 的主要特点就是由目标位置开始向起始位置进行路径搜索，当物体由起始位置向目标位置运行过程中，发现路径中存在新的障碍时，对于目标位置到新障碍之间的范围内的路径节点，新的障碍是不会影响到其到目标的路径的。新障碍只会影响的是物体所在位置到障碍之间范围的节点的路径。在这时通过 将新的障碍周围的节点加入到Openlist中进行处理然后向物体所在位置进行传播，能最小程度的减少计算开销。

基于采样的路径规划

1.2 RRT算法

通过不断产生随机点生成随机树，再通过结点距离树目的地的距离来形成最终路线

步骤：

在图中随机找一个点，连接现有树中点距离随机点最近的那个点（最开始只有一个点即那个点连接），按步长增长。

判断该边是否通过障碍物，如果没有则加入该边到树中，否则忽略此边。

1.2.1 RRT*

相较于RRT，此算法多了两步（在产生，连接，已插入新的结点之后）

① 对于新结点——重新选择父结点，这里需要”手动画圆“，即自定义大小的范围，使重新选择的父节点从该范围内寻找。

寻找父结点时，选择从0到该新结点的权值和最小

②对于新结点——同样”手动画圆“（同①），只不过这里将x看做父节点，寻找由此出发的更优子节点

寻找子节点时，选择从0到新节点再到子节点的权值和最小

1.2.2 informed RRT*

也是从RRT*出发，找到那条边（相较最短）

再从两个端点依据下图画椭圆，使随机点集中生成在椭圆内部，继续进行RRT*，这个过程中椭圆会越来越扁（离心率越来越大），最后使线路尽可能最佳。

总结对比

方向（正反）搜索： 与是否能处理动态规划有关

在静态环境中全局地图信息已知，则无论正向搜索还是反向搜索都可以发挥效能。但是在动态环境中，面对未知地图，要想获得最短路径则需要不断的尝试，正向搜索很容易产生与最优路径背道而驰的现象，而此时反向搜索算法能够很好的处理这种情况。

启发式和非启发式： 启发式搜索带来的时效能的提高，避免全局盲目搜寻

启发式算法能够在每次搜索时将搜索方向导向目标点，替代了非启发式算法向四周无规则遍历的局限，正常情况下能够大大提高搜索效率。但是在启发式路径受阻的情况下，搜索效果将适得其反。

启发式和增量式： 增量式搜索则代表着迭代信息的二次利用，提高算法效率

发式搜索是利用启发函数来对搜索进行指导，从而实现高效的搜索，启发式搜索是一种“智能”搜索。

增量搜索是对以前的搜索结果信息进行再利用来实现高效搜索，大大减少搜索范围和时间

算法	搜索方向	形式	特点	优点	缺点
dijstra	正向	无	静态规划	一定你找到最短路径	遍历节点多，计算过于复杂
A*	正向	启发式	静态规划	比dijkstra提高了算法搜索效率
D*	反向	增量式	动态规划	在A*的基础上改进，减少了对相同时间数据的重复计算，提高看路径规划的效率

考虑到停车库的地形和路线整体方正，rrt算法不太适合这种图，因此这里将rrt排除。

——————附录

• ​