【利元亨 | 市场】AGV如何准确高速进行最优路径搜索

2019年12月11-13日，以“生态互联•逆势突围”为主题的“利元亨•2019高工机器人年会”将在深圳机场凯悦酒店举行，欢迎踊跃报名，扫描上方二维码进入报名链接。

引言

为了准确又高效的把货物送到目的地，最优搜索算法至关重要。在路径搜索问题中，最优搜索算法可以生成一个精确的最优解，按照搜索逻辑不同，可以分为深度优先法和广度优先法。但是，在实际工程上会使用一些近似算法去解决路径搜索问题，主要分为启发式搜索的A*、D*、Focused D*算法和准启发式搜索的退火、进化、蚁群优化算法。
小蓝（杭州蓝芯科技有限公司）通过介绍启发式搜索的A*算法和准启发式搜索的遗传进化算法，让大家感受这两类算法的特色与魅力。

A*算法

A*算法作为经典启发式搜索算法，正广泛运用于智能机器人、无人驾驶等领域。详细来说，A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。从公式上的描述是：f(n)=g(n)+h(n)

• f(n) 是从初始状态经由状态n到目标状态的代价估计，

• g(n) 是在状态空间中从初始状态到状态n的实际代价，

• h(n) 是从状态n到目标状态的最低的估计代价。

那么什么是代价呢，为了便于理解，你可以直接认为这里的代价就是距离。假设如图1中场景，从出发点begin到目标点end，该如何选择路线呢？首先从出发点开始，可以选择去a点，也可以选择去d点。那么究竟去哪个点更合适呢？d点说了，我到目标点的直线距离是4.5，出发点到我距离是2，最近预估总距离只要6.5，选我选我~。a点轻蔑的一笑道：我到目标点的直线距离是4，出发点到我的距离只要1.5，最近的预估总距离只要5.5。那么机智的小蓝下一步该怎么走呢，小蓝只能从a点出发，去往唯一的目的地b点，掐指一算，已经走过的距离是3.5，到目标点的直线距离是2，总距离还是5.5。小蓝轻轻瞟了一眼躲在角落怀揣6.5的d点，二话不说向b点奔去。
到了b点以后，抬头一看，下面只有c点。到了c点以后，已经走过的距离变成了6.5，到目标点的直线距离是4，总距离一下子变成了10.5。于是小蓝深情的看着d点已经它手中的6.5的牌牌，留下了悔恨的泪水。俗话说，浪子回头金不换，d点也接受了小蓝，让他可以重新开始。
重新选择了从d点出发的小蓝，抬头望向了e点。嗯很好，到e点实际距离也只有5，到目标点的直线距离是2，总距离也只有7。又回忆起c点的10.5的预估距离，小蓝不禁一阵后怕。

到达e点，小蓝便见到了金光闪闪的终点二字。这便结束了么？不，如今的小蓝已经可以称得上是一个老江湖了，万一最后是一段望山跑死马的远路，岂不是得亏亏亏死…于是再次打起了自己的小算盘，e点到终点的距离是2，那么走过的总距离是7，掰掰手指头就知道比途径c点更近。于是小蓝便方向大胆的迈向了终点，获取了一条最低代价的路径。
这就是一次A*搜索的全部过程啦。为了加深大家的记忆，小蓝决定再次祭出学习A*算法之必备组图，看看在棋盘格地图中，小蓝是如何进行A*最优路径搜索滴。

进化算法

进化算法也是在人工智能领域中用于解决最优化问题的一种准启发式搜索算法。进化算法的思想参考了生物界的遗传进化理论，让达尔文爷爷的思想从豌豆领域出发，进军计算机领域。简单来说，进化算法将优化问题的解（特征值集合）表示为一个编码串，称为个体或者染色体，个体中的每一位，就叫做基因。那么很多个体就可以组成一个种群。为了避免局部最优，进化算法同样借鉴了生物学中的遗传/突变/自然选择以及杂交等。
那么进化算法是如何为最后路径搜索服务的呢，小蓝通过遗传算法进行举例说明，假设下图中，小蓝要从0点出发到15点。那么首先要对该图进行整理，也就是编码过程，编码表格如下所示：然后检查两点之间是否可达，形成路径连接表，如下表所示：这样就可以通过适应度函数进行路径评估了，不可达的路径的适应度为0。适应度函数表达如下所示：
这样，通过添加随机数，并加入首尾后，就能生成一群初始化群体了。生成初始化群体以后，开始遗传啦。遗传过程如下图所示，通过选择，交叉和变异产生新的群体，然后按照适应度进行筛选，通过重采样的方式留下适应度高的个体，进行下一轮的计算。
看到想加几个就加几个的基因，故而遗传算法是可以同时对多个可行解进行搜索，且不容易陷入局部最优。同时还允许使用非常复杂的适应度函数，还能对变量的变化范围加以限制。但是很遗憾的是，遗传算法目前都还没有一个很完美的数学解释，所以遗传算法还是非常考验我们码农的技术滴。
2019年12月11-13日，由高工机器人举办的“利元亨•2019高工机器人年会”将在深圳机场凯悦酒店举行，本次大会以“生态互联•逆势突围”为主题，作为本次大会的赞助商，蓝芯科技营销总裁刘志伟将在会议上讲述视觉感知系统让机器人更智能，助力机器人看懂世界，服务世界。小蓝在现场等你哦。

利元亨总冠名

2019高工机器人年会关于高工机器人年会系列报道请点击：☞2019高工机器人年会议程官宣☞利元亨冠名高工机器人年会：生态互联•逆势突围☞2019高工年会观风向⑤：控制器的PLC、PC-Based和PAC之争☞2019高工年会观风向⑥：工业机器人“变软”☞2019高工年会观风向⑦：机器视觉规模化落地靠什么？☞2019高工年会观风向⑧：机器人夹爪这三年☞2019高工年会观风向⑨：机器人“圈地运动”☞2019高工年会观风向⑩：谐波减速器乱战何时休☞2019高工年会观风向⑪：协作机器人七宗“最”☞2019高工年会观风向⑫：AGV三两事
关于高工机器人年会时间/地点：☞时间：12月11-13日
☞地点：深圳机场凯悦酒店

长按报名

招募作者

高工机器人正在招募兼职内容创作者和专栏作家，请将简历和原创作品投至邮箱：[e-mail] 

我们对职业、所在地等没有要求，欢迎有兴趣有能力的朋友加入！

往期推荐

▪ 押注AGV 3.0时代的风口
▪ 9款产品“碰撞”，谁才是六轴机器人的“杠把子”？▪ 埃夫特冠名闭幕式：工业互联时代下的机遇和挑战

码字不易，支持下小编吧！