【智能轮椅的路径规划案例分析4500字】

智能轮椅的路径规划案例分析目录TOC\o"1-3"\h\u5477智能轮椅的路径规划案例分析 1105191.1传统的A*算法 1326291.2改进的A*算法研究 3215471.3改进A*算法的对比仿真分析 6271451.4室内环境路径规划 12全局路径规划技术是建立在拥有完整信息的基础上进行的，包括地图信息，轮椅在地图上的精确位置信息。在第二章位姿感知和第三章室内地图构建的基础上，智能轮椅可以根据室内环境地图进行自主导航，从起始点出发，寻找一条到目标点的过程中无碰撞的较短路径。A*算法ADDINNE.Ref.{72C9861F-2760-46F8-81C7-2B21A2BA5820}[47]是一种应用性较强的全局路径搜索算法常应用于自动导航系统，本章节针对传统的A*算法规划效率低、路径多转折等问题做出改进，通过增加A*算法搜索时的连接距离扩展近邻栅格范围，提高路径规划效率，减少无效路径长度，同时令其从起始点和目标点双向搜索，缩短路径规划时间，使智能轮椅安全高效地完成路径规划。传统的A*算法1986年，Nilsson在Dijkstras算法ADDINNE.Ref.{12738F8C-1E43-4FF7-8CB0-FA93558729FB}[48]的基础上提出了A*算法，目前已被广泛应用于自动导航系统的全局路径规划。Dijkstras算法是一种经典的扩展式搜索算法，从起始点出发逐层向外扩展搜索与起始节点最短的路径节点，并对路径长度进行迭代，规划出一条最短路径。A*算法是在此扩展式搜索基础上采用了估价函数融入启发信息对搜索节点进行评估ADDINNE.Ref.{97AA3BBB-9363-4DEA-A640-21CC5B7FC462}[48]，是一种启发式搜索算法，有针对性地搜索方式提高了算法效率。A*算法规划的路径质量取决于估价函数，不同的估价函数得到的路径也不相同，本章节使用的估价函数为： fn=g式中：f(n)为估价函数；gn为实际代价函数；h(n)启发函数表示任一节点到目标点的距离，而表示两点距离的形式有三种，分别为：欧几里得距离、切比雪夫距离和曼哈顿距离ADDINNE.Ref.{C3572C24-3D1F-4AE1-93A5-DE5F5E9C9644}[49]三种。欧几里得距离表示当前节点到目标节点的直线距离；切比雪夫距离表示当前节点到目标节点按照对角线行驶的距离与按照直线行驶的距离之和；曼哈顿距离表示当前节点与目标节点间垂直距离与水平距离之和。假设当前时刻位置节点的位置坐标为(xn,yn) hn=( hn=x hn=x如图4-1为三种启发函数示意图：(1)欧几里得距离(2)切比雪夫距离 (3)曼哈顿距离图4-1三种启发函数示意图启发函数的选取直接关系着A*算法全局路径规划的质量ADDINNE.Ref.{D2BA672D-1F4B-4792-BB95-80EB540615B8}[50]，如果h(n)总是比gn小或者相等，此时A*算法一定能规划出一条最短路径，但是h(n)越小，A*算法搜索的节点越多，搜索过程越慢。如果h(n)比gn，那么A*算法不一定能找到一条最短路径，但是运行会变得更快。本文选择的启发函数为欧几里得距离，实验单位可以朝着任意方向移动，且比切比雪夫距离和曼哈顿距离都短，但同时搜索的节点更多，搜寻最佳路径时间变长。A*算法ADDINNE.Ref.{E6D528B7-66B9-4168-A93B-82DE4227C4C1}[51]实质上是寻找令式4-1的估价函数最小的节点，并且把该节点作为下一次搜索的起始节点。在A*算法搜索开始的时候会创建两个表，OPEN表和CLOSE表。OPEN表里储存着所有已知的但尚未被搜索到的节点，CLOSE表里储存着已经被搜索过的节点。根据启发函数计算OPEN表中的节点，选取OPEN表中启发函数最小值的节点，然后循环这一过程，知道OPEN表中出现目标节点。A*算法实现流程图如图4-2所示：图4-2A*算法实现流程图传统A*算法的全局路径规划从起始节点开始，逐步向外扩展搜索，直到找寻到目标节点。整个过程遍历节点多，搜索效率低，并且规划的路径距离长，有许多不必要的转折和无效的路径。改进的A*算法研究在使用栅格地图的传统A*算法中，当从一个节点开始扩展路径时，只考虑了相邻的8个栅格，即连接距离为1(connectingdistance)ADDINNE.Ref.{15ADA515-B4AE-4183-8D9E-C327CA69C747}[52]。这将路径规划的方向限制在为8个方向，角度以45度为增量向外扩展节点，这会导致规划的路径出现次优路径。如图4-3所示，传统A*算法路径搜索的8个方向。图4-3连接距离为1时路径搜索方向为了避免连接距离限制当前节点的相邻可达节点的数量，本文提出可以增加一个节点的连接距离。图4-4表示在连接距离增加时，路径规划的可能搜索方向。（a）连接距离=1的搜索方向（b）连接距离=2的搜索方向（c）连接距离=3的搜索方向（d）连接距离=4的搜索方向图4-4不同连接距离的路径搜索方向由图4-4中可以看出，当连接距离为2、3、4时，扩展节点超过传统A*算法周围的8个栅格，相邻栅格的搜索方式扩大至16、32、56个栅格。随着连接距离的增加，路径搜索可能的方向也迅速增加，理论上可以减少路径的锯齿效果，使得结果更加平滑。但同时会导致计算的节点数量增加，路径规划时间变长。为了改进连接距离增加导致计算的节点数量增多和计算时间变长，在此基础上进行A*算法的双向搜索ADDINNE.Ref.{E1F8247A-6F9D-45FA-916D-733EF3A63C2F}[53]。传统A*算法只有一个搜索方向，从起始点出发逐步向外扩展，直至OPEN表中出现目标节点。在双向A*算法中，分别以起始点为出发点目标点为终点进行正向搜索，以目标点为出发点起始点为终点进行反向搜索。在双向搜索交替进行的过程中，以当前产生的最优节点作为下一次搜索的目标节点。双向A*算法的实现步骤为：1）建立两个OPEN表和CLOSE表，分别用于储存正向搜索过程中的待检测节点和已被搜索过的节点，和反向搜索过程中的待检测节点和已被搜索过的节点；2）将起始点放入正向搜索的OPEN表中，目标节点放入反向搜索的OPEN表中，同时将两个CLOSE表清空；3）双向搜索交替进行，详细搜索步骤与传统A*算法相同，但需要更新每次搜索的目标节点，将本次搜索产生的最优节点作为下一次搜索的目标节点；4）重复上述步骤，直到正向反向搜索的CLOSE表里出现相同的最优节点，此时说明两个方向的扩展节点重合，完成双向搜索过程；5）从重合的最优节点开始，向两个方向依次连接父节点，此时得到的路径为双向A*算法的最优路径。双向A*算法实现框图如图4-5所示。图4-5双向A*算法框图改进A*算法的对比仿真分析如图4-6所示，假设有一个10米*10米的室内环境，将它划分为一个100*100的栅格地图，此时的地图分辨率为10，即将实际环境中的1米划分为10个栅格。建立地图的坐标系，左上角（0,0）点为坐标原点，沿该点水平向右的方向为x轴，沿该点垂直向下的方向为y轴。假设起始点坐标为(20,80)，目标点坐标为(22,78)，黑色区域为存在障碍物的不可行区域，白色区域为无障碍物可通行区域。在连接距离为1、2、4、8的情况下，进行路径规划仿真，灰色区域为路径规划过程中的已搜索区域，如图4-6所示。（a）连接距离=1的最优路径（b）连接距离=2的最优路径（c）连接距离=4的最优路径（d）连接距离=8的最优路径图4-6不同连接距离的路径规划由图4-6（a）可以看出，传统A*算法计算当前节点相邻8个栅格时，只是将这8个中代价函数最小的节点挑选出来，作为下一次搜索的父节点。这种方式搜索区域小，搜索效率低，不适合大场景的室内环境，容易造成无效路径，增加路径长度。由图4-6（b）、（c）、（d）可以看出，随着连接距离的增加，由父节点向外搜索的方向增多，搜索区域增大，规划出的路径更简洁平滑。图4-7为连接距离为1和8时规划出的最优路径的对比。图4-7连接距离为1和8的最优路径对比由图4-7可以看出，连接距离为1的传统A*算法规划在搜索相邻8个栅格时的最优路径在障碍物附近存在许多不必要的转折，路径长度增加，搜索效率低。在室内环境较复杂的情况下，往往不能清晰地寻找到接下来的方向。采取增加连接距离的计算方式，扩大搜索的相邻栅格范围，可以减少无效路径长度，平滑路径减少锯齿效应。选择四种连接距离下规划的路径长度、计算节点的个数以及平均运行一次所需的CPU时间三种算法性能指标进行对比，如表4-1所示。表4-1不同连接距离的路径长度及平均CPU时间连接距离(ConnectingDistance)路径长度(用节点数量表示)计算节点个数平均CPU时间1198101580.6082164140410.7024122288450.796889518511.591表4-1可以看出，连接距离等于1和连接距离等于8时，最优路径长度的差别，连接距离为8的路径长度比连接距离为1的路径长度减少55.1%，但是计算的节点个数是原来的5倍，平均运行一次程序的CPU时间增加了161.7%。虽然增加连接距离可以有效提高路径规划的质量，但同时也增加了计算的节点数量和计算时间。在与图4-6相同的实验条件下，对双向A*算法进行不同连接距离的仿真，规划路径结果如图4-8所示：（a）连接距离=1的双向最优路径（b）连接距离=2的双向最优路径（c）连接距离=4的双向最优路径（d）连接距离=8的双向最优路径图4-8不同连接距离的双向路径规划图4-8中，黄色路径是双向A*算法的正向搜索结果，紫色路径是双向A*算法的反向搜索结果，它们一起组成了双向A*算法的最优路径。左侧灰色区域为正向已搜索区域，右侧灰色区域为反向已搜索区域，相交处的节点为正向反向搜索的相同最优节点。图4-9、4-10为A*算法改进前后的平均CPU时间和路径长度的对比。图4-9改进前后的CPU时间对比图4-10改进前后的路径长度对比由图4-9可以看出，随着连接距离的增加，搜索时间变长，但双向A*算法效率改进效果明显，相较于单向A*算法效率最少提升53.8%，最大提升了113.9%。由图4-10可以看出，增加连接距离后规划的路径长度减小，路径更加平滑。但当连接距离相同时，双向A*算法搜索出的最优路径长度与单向A*算法相比增长较小，最多增长了9.84%。综上所述，本章节提出的在传统A*算法的基础上增加连接距离和双向搜索的算法，不但平滑了路径，减小了路径长度和弯折，同时也明显地降低了CPU完成该进程的时间。改进的A*算法在路径质量和搜索效率方面比传统算法都有明显提升，可以合理地应用于轮椅的室内路径规划中。室内环境路径规划在第三章构建的室内环境地图的基础上，用本文改进后的采用多近邻栅格计算方式的单向和双向A*算法进行路径规划仿真，单向搜索算法结果如图4-11所示，双向搜索算法结果如图4-12所示：（a）连接距离=1的最优路径（b）连接距离=2的最优路径（c）连接距离=4的最优路径（d）连接距离=8的最优路径图4-11多近邻栅格的单向路径规划图4-11中，栅格地图的分辨率为30，蓝色圆点为起始点，红色三角为目标点，黄色连线为A*算法规划出的最优路径，灰色区域为A*算法路径规划时搜索的区域。可以看出，随着连接距离的增加，搜索邻近栅格的区域扩大，有助于直接找出大邻近栅格区域的最优节点，减少了对次优节点的向外扩展栅格的计算次数，使搜索过的区域面积减小。在实际大场景室内环境下，连接距离增加计算节点减少，算法效率提升。（a）连接距离=1的双向最优路径（b）连接距离=2的双向最优路径（c）连接距离=4的双向最优路径（d）连接距离=8的双向最优路径 图4-12多近邻栅格的双向路径规划 由图4-12可以看出，在实际室内地图下，传统A*算法搜索节点多，路径弯折多，路径长。采用多近邻栅格计算方式的双向搜索的A*算法也能完成路径规划，并且较少弯折地图质量较好。改进前后的路径长度与CPU时间指标对比，如表4-2所示。表4-2改进前后路径规划性能对比连接距离多近邻栅格A*多近邻栅格+双向A*路径长度/mCPU时间路径长度CPU时间18.535.8815.871.34226.932.9175.771.48246.072.6215.331.23285.432