《人工智能通识》5.3智能导航

5.2实践任务看图说话第5章人工智能怎么“思考”情景导入这个周末，小慧和同学打算到广州起义纪念馆和烈士陵园参观学习，小慧查了查地图，发现两个景点距离不远，决定步行前往。小慧得知小智你最近正在学习智能路径规划相关知识，所以请你为她们设计一个智能导航系统，帮助她们找到从广州起义纪念馆到烈士陵园最佳路线。任务描述在日常生活中，要去一个不熟悉的地方时，我们会使用手机上的地图软件导航。地图软件不仅能够给出从当前地点到目的地的最短路线，还可以根据当时的交通情况，推荐用时最少的路线。地图软件是怎样做到的呢？本任务要求根据给出的多个地点和各点连接道路的信息，计算出从甲地到乙地的最短路线。预备知识手机里有GPS（全球卫星定位系统）传感器，通过这个传感器可以接收卫星信号，计算出当前地点的坐标（经纬度），确定当前位置。地图软件有目的地的坐标，也有路的数据，经过合适的算法就可以计算出路线，显示给用户。导航问题是路径规划应用场景之一。预备知识一、路径规划路径规划是运动规划的主要研究内容之一。运动规划由路径规划和轨迹规划组成，连接起点位置和终点位置的序列点或曲线称之为路径，构成路径的策略称之为路径规划。路径规划的方法有很多。按照算法的基本原理和发现时间大致分为以下四大类：传统算法、图形学的方法、智能仿生学算法和其他算法。分类如图5-21路径规划算法分类所示。预备知识在众多的算法中，有些算法是属于人工智能的算法，有些不属于。现在介绍相对简单的Dijkstra算法。Dijkstra算法是一种经典的广度优先的搜索算法。算法从初始点开始一层一层地搜索，得到每一层的局部最优解，直到到达目标点。将地点抽象成点，道路对应成线段，线段标上两地间的距离（如果求最少时间，则标上时间），地图如图5-22。求从a点到b点的最短路线。示例拓扑图如图5-23。算法步骤步骤1：起点a为点1，所以点1的距离为0。到其它点为无穷大。步骤2：计算相邻点2、3、6的值。点1到点2为7，点1到点3为9，点1到点6为14，其他为无穷。如图5-25。相邻点2、3、6中，点2的值7为最小，所以将点2并入已完成的点。将已完成的点标记为红色。算法步骤步骤3：重新计算从起点到与红色点相邻的各点，如果到该点有多条路线，取值为最小的路线。例：计算点3的值。路线1：从点1到点3，值为9；路线2：从点1经点2到点3，值为7加10等于17。因路线1的值9小于路线2的17，所以取路线1的值为点3的值。点3的值为9。计算结果：点3为9，点4为20，点6为11。算法步骤步骤4：重新计算未加入的各点的值。计算点4：路线1：点1到点2到点4，7加15等于22；路线2：点1至点3到点4，9加11等于20。因路线2的值20小于路线1的22，取路线2的值20。点4值标为20。计算点6：路线1：点1至点3到点6，9加2等于11；路线2：点1到点6，值14。因路线1的值11小于路线2的14，取路线1的值11。点6值标为11。点6的值11小于点4的值20，将点6加入，标为红色。算法步骤步骤5：计算点4和点5，两值都是20，点5是终点，取点5。任务完成。最短路线是点1、3、6、5。距离为20。如图5-29。预备知识二、路径规划行业应用路径规划在很多领域应用广泛。小到家庭扫地机器人的行进路径，大到自动驾驶汽车的路线选择、无人机物流飞行路线等都在应用。机器人的自主行动，巡航导弹躲避雷达搜索,物流管理中的车辆问题，通信技术领域中的路由配置问题等，凡是可拓扑为点线网络规划问题基本上都可以采用路径规划的方法来解决。实现思路活动1：日常生活中，如果没有手机导航，要去一个陌生的地方，你是怎样解决路径问题的？活动2：你习惯使用哪个导航软件？有什么优点？实现思路路径规划一般步骤有以下三个步骤：环境建模、路径搜索、路径平滑。练技能积木块介绍以图形方式显示地图生成随机地图获取地图最短路径练技能任务实现思路展效果评过程环节1：与同组同学分享你在本节实验中的收获与体会。评过程课堂小结本次任务使用平台积木式编程完成了程序的编写，了解了导航的几个步骤，体会了如何在地图中找到最短路径。评过程环节1：与同组同学分享你在本节实验中的感想与体会。环节2：课后完成评价反思及巩固提升促巩固课后作业：完成评价反思完成课后巩固提升练习评价反思1.学习评价根据学习任务的完成情况，对照下表中“观察点”列举的内容进行自评或互评，并在对应的表格内下打“√”观察点完全

掌握基本

掌握尚未

掌握理解图片描述生成技术的原理

了解计算机实现图像描述生成的过程对看图说话实验完成的程度

评价反思2.学习反思回顾与反思简要描述知道了什么？

理解了什么？

能够做什么？

完成得怎么样？

还存在什么问题？

如何做得更好？

巩固提升1.下面不属于路径规划算法的是（）A遗传算法B排序算法C模拟退火算法D栅格法2.以下属于路