教育用路径可规划智能车研发

李志帅，熊 刚，沈 震，董西松，刘希未，吕 键，刘 畅



教育用路径可规划智能车研发

李志帅1,2，熊 刚1,3，沈 震1,4，董西松1,4，刘希未3,4*，吕 键5，刘 畅6

（1. 中国科学院云计算中心，广东 东莞 523808；2. 中国科学院大学，人工智能学院，北京 100049； 3. 中国科学院自动化研究所复杂系统管理与控制国家重点实验室&北京市智能化技术与系统工程技术研究中心， 北京 100190；4. 青岛智能产业技术研究院，智慧教育研究所，山东 青岛 266109；5. 广东朗呈医疗器械 科技有限公司，广东 东莞 523808；6. 四川大学，计算机学院，四川 成都 610207）

针对高中科技社团和大学计算机相关专业科技创新教育需求，开发一种可以用于电子和计算机科技教学的智能小车。智能小车在完成路径规划后，可以按照规划的路径完成任务；还可以设定目标点与障碍点，智能小车基于改进的Dijkstra算法自动搜索到达终点的最优路径。除了培养学生电子设计能力，通过智能小车编程实践，也训练了学生对优化算法的学习。首先，采用微软基础类MFC与Matlab混合编程编写上位机界面，调用改进的Dijkstra算法进行路径规划。然后，将规划好的路径通过串口传到下位机，由STM32控制执行。最后，在栅格地图中，通过仿真运行和实际应用验证了改进的Dijkstra算法的可行性，取得了较好的效果。

智能车路径规划；智慧教育；混合编程；Dijkstra算法；A*算法

0 引言

随着人工智能技术的快速发展，人工智能与教育科学的深度融合以及人工智能技术的教育普及，都受到教育行业的高度重视并上升为国家战略。围绕这一战略需求，首先需要研发相关教育装备、设计多学科融合的课程体系，通过项目式课程训练学生实践动手能力、培训创新精神[1]。

智能车，也称为轮式机器人，是广泛应用于当前的社会科学，包括科学技术教育，风险检测等领域。他们可以取代甚至超越人类来完成一些危险的环境任务。智能汽车在现实中发挥了重要作用，特别是在宇宙探测，海底和地震等灾难救援领域。作为集成了高科技的产品，智能小车可用于模拟和实验，如路径规划，环境感知和自动驾驶等[2]。

路径规划用于解决机器人的最优轨迹问题，即根据一些优化标准（如最小工作成本，最短行驶路径或最短行驶时间等）来找到工作空间的起点，目标状态可以获得躲避障碍物的最佳路径[3,4]。机器人的路径规划广泛用于应用场景，例如地图导航、扫地机器人、无人驾驶车辆和仓库分拣机器人等。

本文旨在开发一种智能小车，可用于高中科技学会的电子和计算机科学与技术教学或计算机科学或相关科目的科技创新教育需要。

我们项目开发用于教育的智能小车采用路径优化算法，可以独立找到最优路径，为用户学习智能汽车及相关算法提供应用案例和优化算法开发平台。在路径规划完成后，可以控制小车根据自己的计划路径完成任务，同时也可以人为地设定目标点和障碍点。优化算法（遗传算法，A*算法等）可以在现实中应用以找到最优路径。路径优化算法在教育教学应用和智能交通路径选择与规划中非常重要。

本文安排如下，在第一部分介绍了智能车系统的整体设计；在第二部分介绍描述了路径规划算法以及本系统所使用的遗传算法（GA）和A*算法两种优化方法；第三部分详述了两种优化算法在寻找通过目标点最优路径和栅格避障地图的具体应用和改进；第四部分介绍了结合智能车硬件得出在交互平台应用结果；最后，在第五部分对实验结果做出了分析与改进方向。

1 教育用智能车系统的整体设计

本文将优化算法与智能车相结合，研究的重点在于设计交互界面和智能车硬件系统并根据不同任务在实现路径自主寻优。系统包含智能车硬件以及单片机控制系统以及电脑可操控交互界面：生成二维现场地图，在地图中可以人为规划智能车的运动轨迹并使智能车按照指定轨迹运动，在此基础上使用Matlab编写最优化算法实现最优化路径，找到通过选定点的最短路径，并将路径发送给智能车，用单片机控制使之按照优化后路径走完地图，在完成最优化算法的同时，实现面向教育、教学使用的智能车开发。

本文采用微软基础类MFC编写上位机交互界面，通过调用Matlab引擎的方式运行Matlab编写好的遗传算法和A*算法等优化算法，分别针对不同优化任务进行路径规划；然后将规划好的路径通过串口控制智能车行进；最后通过仿真运行和实际应用验证了混合编程来进行路径规划算法的可行性，学习者只需在Matlab端将优化算法实现，在本文设计的交互平台上通过调用Matlab引擎的方式加载优化算法进而控制智能车，而无需自行设计交互界面以及编写智能车程序和硬件设置，以便将更多的精力放在优化算法学习实践上。

由需要设计系统结构我们可以得到智能车控制的过程如图1所示。

图1 总体方案设计流程图

一个完整智能车控制系统的实现需要各个模块相互结合共同作用，由上述流程和它们之间的关系，我们可得系统的总体设计方案，总体方案（图1）分成上位机设计，通信模块，智能车系统控制三部分。

上位机的交互界面实现了三个功能案例，可以按照不同的需求进行路径规划：

功能一在交互界面通过使用鼠标键点击来设置路径，通过串行通信模块控制智能车按照自己设定的路径进行行驶；

功能二使用鼠标来设定多个目标点，每个点只经过一次，找到智能小车通过每个点的最短路径，类似于TSP（旅行商）问题，然后控制小车按照该最短路径行进；

功能三通过按键响应来生成的栅格地图并在其中随意设置障碍点和目标终点，相当于制作了一个迷宫，起点设在左上角的坐标原点，使用优化算法规划出通过该迷宫的最短路径并通过串口发送给智能车控制其按该最短路径行驶，增加趣味性同时也鼓励学生深入探究优化算法，以体现其教育应用价值。

本文设计的系统同时也在下位机进行了智能车硬件搭建以及单片机控制程序设计，以上三个功能各自在实现后，将规划好的路径通过串口发送给智能小车，接收串口数据并将得到的数据进行处理，然后控制智能车按照该数据前进。

由于本系统设计应用在教育场景，考虑到易于中学生学习优化准则以及加快算法运行速度，在功能二设置目标点寻找经过所有点最的短路径过程采用了遗传算法(GA)，功能三在栅格图上模拟真实场景采用A*(A-Star)算法进行智能车的路径规划，并针对栅格迷宫地图设计了对应的启发函数h(x)。而功能一是用来给学生等用户自主设置路径，因此无需优化。

2 路径规划算法描述

常见路径规划算法可大致分为：基于采样的方法，如维诺图，概率图法PRM和快速拓展随机树法RRT等；基于节点的方法，如A*、D*算法等；基于数学模型方法，如混合整数非线性规划MILP等；基于生物启发式算法，如遗传算法、粒子群算法等[5]。近几年随着机器学习的快速发展，基于神经网络和强化学习的路径规划也逐渐开始占据重要地位。

2.1 遗传算法GA描述

遗传算法（GeneticAlgorithm，GA）是通过模拟生物进化过程来完成优化搜索，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不以梯度信息为基础。适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域[6]。作为一种全局优化搜索算法，遗传算法以简单通用、鲁棒性强、适于并行处理的优点取得了广泛的应用。

遗传算法的基本操作有选择、交叉和变异。

选择是从群体中选择优胜的个体，淘汰劣质的个体的操作。选择算子，有时又称为再生算子（Rep­roduction operator）选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下集中：适应度比例方法、随机遍历抽样法、局部选择法[7]。

2.2 A*(A-Star)算法描述

A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法[9]。算法中的设计的启发函数()距离估算值与实际值()越接近，最终搜索速度越快。公式表示为：

其中，()是从初始状态经由状态n到目标状态的代价估计，()是在状态空间中从初始状态到状态n的实际代价，()是从状态n到目标状态的最佳路径的估计代价。

保证找到最短路径条件，关键在于估价函数()和启发函数()的选取。我们以()表达状态n到目标状态的真实距离耗散，那么()的选取大致有如下三种情况：在()<()这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。当()=()，即距离估计()等于最短距离时，路径搜索过程将严格沿着最短路径进行，此时的搜索效率是最高的。如果()>()，搜索的点数少，搜索范围小，效率高，但却不能保证得到最优解[10]。本文在A*算法应用时结合栅格地图的特点设计了不同的启发函数，并对比了不同启发函数之间的性能差异。

3 遗传算法和A*算法的应用

3.1 遗传算法的应用

本文遗传算法求解过程参数设置如下：

（1）种群初始化。将每一个人为设定的目标点进行个体编码，采用1-n的实数随机排列的实数编码方式，初始化的参数有种群个数M、染色体基因个数（即目标点的个数）、迭代次数C、交叉概率P、变异概率P。

（2）适应度函数。对于任意两个目标点之间的距离(,)已知，每个染色体（即n个目标点的随机排列）可计算出总距离，因此可将一个随机全排列的总距离的倒数作为适应度函数()：

即距离越短，适应度函数越好。

（3）选择操作。本文采用轮盘赌法，产生初始群体后，根据计算的个体适应度，对整个群体进行适应度从小到大排序，设定选择百分比p，为保持群体的多样性在进行选择时，规定选择p/2的好个体，再选择p/2的个体放入到交配池中进行交叉、变异等遗传操作。

（4）交叉操作。对于个体，随机的选择两个个体，在对应位置交换若干个基因片段，同时保证每个个体依然是1-n的随机排列，防止进入局部收敛。

（5）变异操作。对于变异操作，随机选取个体，同时随机选取个体的两个基因进行交换以实现变异操作。

在染色体编解码和交叉变异算子等参数设计完成后，接下来考虑遗传算法的具体实现步骤，本文所使用的遗传算法具体步骤如表1所示。

表1 遗传算法设计步骤

Tab.1 The steps of designing Genetic algorithm

3.2 A*算法的应用

本文使用A*算法使之应用于功能三的栅格地图迷宫中，在应用之前首先我们需要确定栅格的位置，进行栅格的标识，一般用以下方法[11]：

（1）直角坐标法。使用直角坐标系的方法，按照左上为坐标原点，水平向右设置为X轴，竖直向下设置为Y轴，计数x，y轴栅格的个数使用()坐标将栅格的位置进行标记,如式（4）所示。

（2）序号法。不使用直角方法，直接对栅格进行计数标记序号，从左上角为1，按照从上到下，从左到右的顺序依次标号，上述两种栅格标识方法分别为公式（4）和（5），都是表示的同一个位置：

=+ 10´（4）

式（5）中，mod表示取p/10之余数，int表示取p/10之整数[12]。

本文采用的是序号法，应用过程如下：

以10*10的栅格图为例，假设为有向有权图，每一个点为一个状态，且该状态只可以到达与之相邻八个状态，其位置用序号法表示的差值为[-11,-10,-9,-1, 0, 1, 9, 10, 11]，且真实距离()为[1.4, 1, 1.4, 1, 0, 1, 1.4, 1, 1.4]，在定义的地图上设置障碍点和终点。

真实距离函数()已经得到，接下来进行启发函数()的设置，()一般选择Manhattan距离，也可以将h(n)设置成0，此时A*算法将退化成Dijkstra算法。由于栅格地图的特点，状态点到其他状态点距离d≥1总是成立，结合启发函数0≤()≤()的特点，将启发函数设置为() = 1，通过对比采用不同启发函数算法所消耗的总时间，可以发现，虽然最终规划好的路径一致，但() = 1时的算法运行时间远小于() = 0的运行时间，也即启发函数越接近目标真实距离算法运行总时间越短。

图2 搜索环境简图

在设定障碍点后需要把所有点到此障碍点的距离函数()设置为无穷大(inf)，构造相应的权值矩阵，初始化并进行规划过程：

（1）初始化权值矩阵，由于是10*10栅格有100个位置，所以权值矩阵大小为100*100，其对角阵为0，只有附近的点才能到达，因此除了附近的点其余点距离都是无穷大，位于边界的点有部分也是不可达的也要将相邻位置设为无穷远。注意的是，在四条边界上，即使在数字上相邻也不可以认为能到达，比如，10在第一行的最后一列，11在第二行的第一列，二者在栅格中不相邻，它们之间的距离设置为无穷大。

（2）设置障碍点和终点，将所有点的状态到障碍点距离设置为无穷大（inf），这样即使点的位置在栅格中相邻，也变成了不可达，终点作为算法的一个输入变量，可以任意设置。

（3）将权值矩阵和终点输入A*算法函数中进行计算得到实现路径。

A*算法设计步骤如表2所示。

表2 A*算法设计过程

Tab.2 A* algorithm design process

3.3 遗传算法的实现效果

在Matlab程序中设定：群体规模为10，最大演化代数为1000，交叉概率为0.4，变异概率为0.2。得到最优路径结果如图3所示，其中左上目标点为起点。

3.4 A*算法的实现效果

图3 由遗传算法得到的最优路径结果

图4 用A*算法对不同障碍物位置进行网格地图规划结果

3.5 结合交互界面的算法设计效果

在运行内存4GB，Intel core i3 CPU，Windows 10 系统的PC机上进行算法实现，开发环境为Visual Stdio 2013和Matlab，使用MFC编写交互界面，鼠标点击目标点后，调用Matlab引擎进行路径规划，上位机交互界面MFC编写，实现了在交互界面的编辑路径后，调用Matlab进行路径规划，然后将规划结果信息通过串口发送智能车。

整体设计界面如图5(a)所示。用户使用功能一在图5(b)中随意设置交互界面中的路径后，单击“发送”按钮，从com发送出规划好的路径信息。智能车串行模块接收该数据，然后SCM控制电机按照信息运行。图5(c)显示功能二的实现：在空白地图中，随机设置10个人工点。在Matlab中实现遗传算法后，在交互界面上调用Matlab引擎，找到通过10个点的最短路径，然后将规划好的最优路径信息返回给上位机。当点击“发送”按钮时，路径信息将被发送到智能车的串行数据接收模块。图5(d)显示了功能三的实现过程：在网格图中，我们可以随意设置障碍点和目标节点来模拟迷宫然后我们设置路径的这些信息被发送到Matlab引擎并写入m文件在Matlab中开始执行使用有关障碍物和目的地的路径信息并实现A*算法，我们可以找到通过迷宫的最佳路径并将路径信息返回到交互式界面。从结果中可以看出，获得的路径是最优的。

图5 （a）通过Visual C ++实现交互界面的整体设计；（b）功能一的工作图：学习者使用Matlab引擎实现遗传算法，然后将计划优化从Matlab传输到VC接口，和其他用户可以随意设置路径；（c）功能二的实现：随机人工设置10个目标点；（d）功能三的实现过程：可以在网格图中随意设置障碍点和最终节点。然后将最终结点和障碍物数据信息传递给Matlab引擎。

4 智能车的系统实现

4.1 智能车硬件结构的设计

智能车硬件采用RP5履带车、L298n驱动电机，控制核心板为STM32f103c8t6，用蓝牙串口与上位机通信，使用光电编码器作为转角与前进距离的反馈，采用J-LINK仿真器JTAG接口模式进行程序下载调试。

4.2 下位机智能车控制程序设计

4.2.1 控制智能车的设计

在运行内存4 GB，Intel core i3 CPU，Windows 10系统的PC机上使用Keil uversion 5进行单片机程序的编译和下载调试。

使用Timer2的4个通道产生4路PWM波，分别控制两个轮子的正反转，使用Timer3和Timer4定时器正交编码模式，分别测量两轮编码器的转的圈数进行角度和距离的反馈，及时控制校正小车的运动轨迹，在直行时读取两个编码器的偏差，将偏差通过PID控制器改变PWM波的占空比来进行校正；在转弯时，将两轮的编码器圈数相加，通过公式（6）来计算：

4.2.2 引入PID控制器来消除误差

在直线前进过程中会产生误差累积，导致偏离直线轨迹，产生较大误差，因此引入PID控制器，两轮的编码器差值输入到控制器中，通过PID运算修正输出的PWM波，将误差消除[13]。

4.3 智能车设计结果

图6(a)是小车的实物图，硬件组成已在图中标明。收到串口数据后，STM32核心板开始控制智能车按照规划好的轨迹行进。直行给前进的电机PWM波，转弯时采用原地转弯的方式，一个电机正向转，另一个电机反向转来实现。

图6(b)是上位机的USB转串口模块以及蓝牙发送模块，负责将路径信息发送至下位机。

图6 智能车系统所需硬件设计

5 结果分析与讨论

5.1 应用验证

设置上位机路径规划的距离与现实的比例尺为1 : 45，即在上位机设计的1厘米就是实际的0.45米，验证过程如下：

在实际中设置障碍物，在上位机上录入障碍点，设定目标点之后进行路径规划，不仅在上位机中出现了路径，同时调用Matlab画出了行动轨迹，智能车按照上位机规划的路（图7）前进即为最优路径。

结果分析：在上位机进行路径规划之后，传到下位机执行时会产生一定的误差，经过分析与查找，

可能的来源如下：

（1）编码器不够精确，导致直行以及转角计数不够，角度产生偏差；

（2）在转角时可能并不是理性情况下原地转，重心会有一定的偏离；

（3）两个轮子的电机对称性不够理想，虽然控制输出的PWM波相同，但电机转速不同，产生偏差，引入PID控制消除两轮转速偏差时，会引起小车位置的偏离。

5.2 结语

本文利用MFC和Matlab等实现了对智能车的实际路径规划，加入遗传算法和A*路径规划优化算法使之分别应用于目标点寻找最优路径和栅格地图迷宫避障中，验证了其可行性，不仅在仿真中可以实现，将这种算法理论应用于实际控制智能车方面也取得了比较好的效果。针对控制智能车产生的偏差，可以通过引入更多反馈措施例如定位装置等进行修正；同时，交互界面的设计还需要继续完善，以满足教育研究者的不同需求。

本文使用VC设计的交互平台进行方便中学生的教育、教学过程，通过在交互界面调用Matlab引擎的方式运行Matlab文件中的遗传算法和A*等优化算法，分别针对不同优化任务进行路径规划，将规划好的路径通过串口控制智能车行进。通过仿真运行和实际应用验证了利用VC和Matlab混合编程方法，使用不同的路径优化算法控制智能车的可行性，学习者在学习实践智能车路径规划时，只需编写不同的路径规划算法再通过VC调用即可，无需再另行设计交互界面和编写智能车程序，大大减少中学生和大学生的编程难度，从而可以进行更多的探索与尝试。

图7 录入障碍点并规划路径

总体来说，控制效果比较理想，完成了按照规划之后的路径行驶，能够成功加载优化后的路径信息并实现现实中避障。

[1] LIU, X W, Gong X Y, Wang F Y, Sun R, Gao Y, Zhang Y, Zhou J, and Deng X. A new framework of science and technology innovation education for k-12 in Qingdao, China. [C]// 2017 ASEE International Forum, June 28, 2017. Columbus, OH, USA.

[2] 陈平. 辅助驾驶中控制与决策关键技术研究[D]. 上海交通大学, 2011.

[3] DAI B, XIAO X M, CAI Z X. Current Status and Future Development of Mobile Robot Path Planning Technology [J]. Control Engineering of China, 2005, 12(3): 198-202.

[4] 沈小伟. 移动机器人路径规划研究[J]. Engineering of China, 2005, 12(3): 198-202.

[5] 贾亚军. 生物启发式算法及其改进研究[D]. 中国科学技术大学, 2010.

[6] 孙健, 钟义信, 王伟. 利用遗传算法求解TSP(Travelling Salesman Problem)问题的探讨[C]// 全国信息论与通信理论学术会议. 2000.

[7] 金希东. 遗传算法及其应用[D]. 西南交通大学, 1996.

[8] 梁宇宏, 张欣. 对遗传算法的轮盘赌选择方式的改进[J]. 信息技术, 2009, 33(12): 127-129.

[9] 黄蓉, 刘敏. 基于A*算法求解最短路径的实现原理[J]. 企业家天地(下半月刊), 2009(7): 124-125.

[10] 尹芳. 一次路由计算实现层次路由的拓扑方法: CN, CN 1816000 A[P]. 2006.

[11] 任世军, 洪炳镕, 黄德海. 一种基于栅格扩展的机器人路径规划方法[J]. 哈尔滨工业大学学报, 2001, 33(1): 68-72.

[12] ZHAO Y L. Data structures and algorithms [M]. Tsinghua University press, 2008.

[13] 刘金琨. 先进PID控制MATLAB仿真[电子资源][M]. 电子工业出版社, 2004

Development of Educational Smart Car with Path Planning Algorithm

LI Zhi-shuai1,2, XIONG Gang1,3, SHEN Zhen1,4, DONG Xi-song1,4, LIU Xi-wei3,4*, LU Jian5, LIU Chang6

(1. Cloud Computing Center, Chinese Academy of Sciences, Dongguan 523808, China; 2. School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing 100049, China; 3. The State Key Laboratory of Management and Control for Complex Systems & The Beijing Engineering Research Center of Intelligent Systems and Technology, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China;4. Institute of Smart Education Systems, Qingdao Academy of Intelligent Industries, Qingdao 266109, China; 5. Guangdong Launca Medical Device Technology Co., Ltd. Dongguan 523808, China; 6. College of Software Engineering, Sichuan University, Chengdu 610207, China)

Aiming at the demand of science & technology club in high schools and college computer science innovation education in colleges, we developed a smart car which can be used in electronic and computer science and technology teaching to provide students with a platform to study smart cars and path optimization algorithms. The host computer system is developed by Visual C++ and calls the Matlab engine to run the genetic algorithm and A* or other optimization algorithms, carrying out path planning for different tasks and controlling the smart car through the serial port. Through simulation and practical application, it is verified that in our interactive platform, different path planning algorithms designed by Matlab can be implemented to control the smart cars. When students want to study the path planning and then control the smart car, they only need to use Matlab to implement the path planning algorithm of the smart car, without designing a platform of interactive interface and a program of smart car controlling in addition.

Smart car path planning; Smart education; hybrid programming; Genetic algorithm; A-star algorithm

TP3

A

10.3969/j.issn.1003-6970.2018.09.001

国家重点研发计划项目(No.2018YFB1004800)，国家自然科学基金项目(61773381, 61773382, 61533019)；广东省科技厅项目(2016B090910001, 2017B090912001)；青岛市科技惠民专项项目(16-6-2-62-nsh)；2017湖北省中科院省院合作专项项目；广东省引进领军人才计划(00201511)；东莞创新领军人才项目(熊刚，吕键)等

李志帅（1995-），男，硕士研究生在读，主要从事智能系统、复杂系统管理与控制等方面的科研工作。

刘希未，副研究员，主要研究方向：智慧教育，复杂系统管理与控制等。

本文著录格式：李志帅，熊刚，沈震，等. 教育用路径可规划智能车研发[J]. 软件，2018，39（9）：01-08