一种路径规划算法的改进与设计

一种路径规划算法的改进与设计内容摘要：

线 凸极值点是函数图象的某段子区间内极大值的横坐标，极值点出现在函数 的驻点或不可导处；极值点上函数的导数为零或不存在，且函数的单调性必然变化。 若一个 函数 的某一点存在某一邻域，在该邻域内函数处处都有定义，而该点的函数值为最大（小），则该函数在该点处的值就是一个极大（小）值。 如果它比邻域内其他各点处的 函数值 都大（小），它就是一个严格极大（小）值。 该点就相应地称为一 个极值点 或严格极值点。 在极值点的左右，函数的增减性不一样，比如说在极值点的左方邻域内函数单调增加，则在极值点的右方邻域内函数单调减小。 极值是对函数某一区间的取值；极值不一定是整个函数定义域内的最值。 几何上，切线指的是 一条刚好触碰 到曲线 上某一点的直线。 更准确的说，当切线经过曲线上的某点（即切点）时，切线的方向与曲线上该点的方向是相同的，此时， “ 切线在切点附近的部分 ” 最接近 “ 曲线在切点附近的部分 ” （无限逼近思想）。 2． 3． 3 区域的划分与存储 根据拟合的曲线和过凸极值点做的水平切线，将整个地图划分为小块的区域，存储每个区域的边界值。 通过计算每个区域的边界值，将每个区域抽象为一个点。 2． 3． 4 构造连通无向图 在 图论 中，连通图基于连通的概念。 在一个 无向图 G 中，若从 顶点 vi 到顶点 vj 有路径相连 (当然从 vj 到 vi 也一 定有路径 )，则称 vi 和 vj 是连通的。 如果 G 是 有向图 ，那么连接 vi 和 vj 的路径中所有的边都必须同向。 如果图中任意两点都是连通的，那么图被称作连通图。 图的连通性是图的基本性质。 将区域抽象为一个点后，根据原来区域的关联性，将相应的点连接起来，构造连通无向图，使用邻接表或其他数据结构存储无向图。 2． 3． 5 设定权值，确定最优路径 最优路径就是路径中最符合某种需求的一条路径，比如最短路径，就是从起点到终点的权值和最小的 边。 对图求最优路径的方法即称为最优路径算法，通常用计算机编程实现。 中北大学 2020 届毕业设计说明书 第 6 页 共 31 页 在公路运输中，为了使运 输的时间和花费最少（花费可以是油耗和费用），需要找到起点和终点的最优路径。 这条最优路径可以是路程最短的路径，也可以是油耗最省的路径，依 据 实际需求而定。 在实际应用中，知道起点和终点，便可用最优路径算法计算出路径，这对车辆的行驶有很好的指导作用。 使用计算机编程实现，更能提高效率。 2． 4 系统规划 该系统主要分为三部分，分别是基本的障碍物拟合及水平切线的求取、区域存储并构造无向图、设定权值然后寻找最优路径。 2． 4． 1 基本的障碍物拟合及水平切线的求取 本部分主要包括多个障碍物的曲线拟合、求取每个障碍物 的凸极值点和过凸极值点做水平切线。 2． 4． 2 区域存储并构造无向图 本部分主要包括对整个地图的区域进行遍历与编号和无向图的构造 2． 4． 3 设定权值及寻找最优路径 本部分主要包括起点与终点的设定，计算出一个或多个通路，然后根据权值寻找出最优的路径 2． 5 系统流程分析 通过调查和分析，本系统的业务流程主要是：用户通过在画板上点击相应的点来构造障碍物，当障碍物完成之后，点击‘画切线’按钮开始对地图中所有的障碍物进行凸极值点的计算，然后在凸极值点处画水平切线，将整个地图划分为多个区域；之后用户选择 出起点和终点，然后输入起点和终点所在的区域；最后点击‘完成’按钮，程序开始计算所有可行的路径，并标记出最优的路径。 在用户的操作过程中和系统运行的过程中，程序都要时刻地记下重要的数据，方便之后的计算。 程序存储的数据主要有：用户点击的点的坐标、每个障碍物的边界经过的点的坐标、每个障碍物的凸极值点的坐标、过凸极值点做的水平切线的两个端点的坐标和用来存储无向图的邻接表等等。 中北大学 2020 届毕业设计说明书 第 7 页 共 31 页 图 21 系统流程图 中北大学 2020 届毕业设计说明书 第 8 页 共 31 页 3 系统设计 3． 1 系统配置 硬件平台： CPU： 内存： 1GB 以上 软件平台： 操作系统： windows、 linux 等 开发工具：支持 HTML5 的浏览器、 notepad++ 3． 2 系统结构模型设计 基于 jQuery 的 JavaScript 框架的图形化实现，数据由用户进行输入，数据处理分布在格子的类中，通过与界面类进行交互。 根据系统的总体目标，本系统开发采用了面向消息机制的实时消息处理机制。 不断的监听用户的动作，以做出相应的处理。 在点击面板 后，程序会做出相应的处理。 同时采用了面向对象的思路和方法，对比较相似的操作写进一个类中，方便操作，提高了系统的安全性能，便于以后的扩展和维护。 Jquery 是一个 非常 优秀的 Javascript 框架。 它是轻量级的 js 库 ，它兼容 CSS3，还兼容各种浏览器（ IE +, FF +, Safari +, Opera +）。 jQuery 使用户能更方便地处理 HTML documents、 events、实现动画效果，并且方便地为网站提供AJAX 交互。 jQuery 还有一个比较大的优势是，它的文档说明 很全，而且各种应用也说得很详细，同时还有许多成熟的插件可供选择。 jQuery 能够使用户的 html页面保持代码和 html 内容分离，也就是说，不用再在 html 里面插入一堆 js 来调用命令了，只需定义 id 即可。 jCanvaScript 是一个面向 HTML5 画布（ canvas）的 Javascript 类库，它提供了许多方法用于简化处理 HTML5 画布（ canvas）元素的内容，只要支持 canvas 和Javascript 的浏览器都可以使用它，包括 iPhone、 iPad 和 Android 等平台。 中北大学 2020 届毕业设计说明书 第 9 页 共 31 页 图 31 功能结构图 3． 3 系统数据结构设计 3． 3． 1 逻辑结构设计要点 本系统内所使用的每个数据结构的名称、标识符以及它们之中每个数据项、记录、问卷和系的标识、定义、长度及它们之间的层次的或表格的相互关系。 3． 3． 2 基本物理结构设计要点 本系统内所使用的每个数据结构中的每个数据项的存储要求，访问方法、存取单位、存取的物理关系（索引、设备、存储区域）、设计考虑和保密条件。 3． 3． 3 数据结构 定义如下数据结构： 表 31 圆的数据结构 字段 类型 长度 描述 x float 11 横坐标 y float 11 纵坐标 b int 11 半径 c color 8 颜色 bool boolean 1 是否填充 circleId string 15 编号 中北大学 2020 届毕业设计说明书 第 10 页 共 31 页 表 32 线段的数据结构 字段 类型 长度 描述 points array 端点的坐标集合 color color 8 颜色 lw float 11 线段的宽度 lineId string 8 编号 表 33 三次贝赛尔曲线的数据结构 字段 类型 长度 描述 points array 11 端点的坐标集合 extrapoints array 11 额外点的坐标集合 color color 8 颜色 lw float 11 宽度 fill boolean 1 是否填充 表 34 文本的数据结构 字段 类型 长度 描述 string array 11 文本内容 x array 11 文本左下方的横坐标 y color 8 文本左下方的纵坐标 maxWidth float 11 文本的最大宽度 color color 8 字体颜色 fill boolean 1 是否填充 中北大学 2020 届毕业设计说明书 第 11 页 共 31 页 4 功能模块划分 根据要实现的目标和思路，主 要划分了以下的模块：障碍物拟合模块、凸极值点计算模块、水平切线划分区域模块、区域存储模块、无向图构造模块和路径寻找模块。 每个模块都有着承上启下的作用，缺少了任何一个模块，都将无法进行。 4． 1 障碍物拟合模块 该模块需要实现的功能主要有：获取用户点击的点的坐标，计算出所需要画三次贝赛尔曲线所需要的数据，调用画图函数拟合出障碍物，计算边界经过的点的坐标。 图 41 障碍物拟合模块 当用户的鼠标处于画图区域中时，时刻检测鼠标的位置，当用户点击下左键时马上获取当前的坐标值并存储。 用户点击一个障碍物完成之后， 就开始计算三次贝赛尔曲线需要的其他的点的坐标；计算完成之后调用画图函数完成一个障碍物的拟合。 同时在这个模块中还要计算该障碍物经过的所有点的坐标，方便之后的区域存储模块的执行。 障碍物的绘制与障碍物经过的点坐标使用的是不同的方法：障碍物的绘制调用的是 jCanvaScript 类库中的方法，画出来的三次贝赛尔曲线是平滑的；而障碍物经过的点的坐标是使用三次贝赛尔曲线方程计算出来的，因此这些点是不连续的，相邻两点之间的距离也是不确定的。 4． 2 凸极值点计算模块 在本系统中，凸极值点的含义是：边界上的点相对于障碍 物的内部来说更偏中北大学 2020 届毕业设计说明书 第 12 页 共 31 页 向于外界。 而且本系统仅仅使用水平方向上的凸极值点。 对于某个障碍物的边界点，我们可以根据该点与相邻两点的 y 值进行比较，能够确认该点是不是极值点，但是目前还不能确认该点是否是凸极值点，因为某些极值点是向障碍物内部凹陷的。 在计算极值点时要确认该极值点是向上凸的还是向下凸的，若该极值点是向上凸的则向下做射线，否则向上做射线；然后计算该射线与障碍物边界交点的个数，若交点个数是奇数则该极值点是凸极值点，否则不是。 图 42 凸极值点计算模块 4． 3 水平切线划分区域模块 该模块的主要功能是将 整个地图划分出几个区域，对每个区域和区域之间进行权值的计算，然后可以寻找出最优的路径。 在凸极值点计算模块已经计算出所有障碍物的凸极值点，便可以过凸极值点做水平切线划分区域了。 这个模块的难点是如何计。