AGV路径规划
专注于易胜博官网首页无人叉车自动化整体解决方案

400-086-6223

15869185255

安徽官网游戏易胜博官网首页科技有限公司

基于 A*算法的路径规划

发布日期:2021-09-01 浏览次数:111

基于A*算法的路径规划


基于 A*算法的路径规划

路径规划作为移动机器人导航技术的重要组成部分,是移动机器人技术研究的重要领域。目前主要有两种规划方式:一种为全局路径规划,一种为局部路径

规划。在这两种类型的规划方法中采用的搜索算法主要有 A*算法、D*算法、蚁

群算法、人工势场法等。本章节根据第二章构建出的地图,再将所得地图根据实

际场景栅格化,转化为栅格地图,再根据第三章的定位方法获得起始点和目标点,

最后根据 A*算法生成全局路径。

4.1 路径规划步骤

为实现在环境中进行路径规划,一般包括环境建模、路径搜索、路径修剪三个步骤

1)环境建模。环境建模是路径规划的首要步骤,其目的是将环境信息转化为路径规划所用的地图,常用的方法包括栅格建模法、拓扑建模法以及几何建模法等,路径搜索将根据构建地图的方法选择相应的搜索算法。一般情况下,首先通过构图方法获得环境地图,再通过相应的方法转化为可使用的地图,从而完成对环境的建模。

2)路径搜索。路径搜索环节是在建立的环境模型的基础上采用相应路径搜索算法搜寻一条可行的路径,本环节主要涉及到相关的路径规划算法的应用以及改进。

3)路径修剪。在实际使用中根据机器人的实际尺寸、运动方式和控制方法需要对搜索出的路径进行修剪,使其成为一条可行且高效的路径。

4.2 环境地图建模

4.2.1 拓扑建模法

拓扑建模法是指在环境建模时引入拓扑图的概念,将现场环境转化为拓扑地图,从而适应实际环境的柔性配置。拓扑地图由节点以及节点和节点间的连接关系组成,首先根据任务中的起始点和目标点,标注出路径中可行的点作为地图中的节点;再通过各节点的位置构建连接关系作为地图中的节点连接关系;最后进行路径规划时利用搜索算法通过计算路径当前点和其他节点的距离惩罚值获得路径中的下一个节点,最终获得最优节点集合作为路径规划获得路径。其中路径中的每个节点从起始点到目标点依次排列,节点信息包括下个节点的位置、方向值。通过拓扑建模法构建的拓扑地图有以下优点:

1)更直观的表现出环境中的特征,更加贴近工业现场的真实环境;


2)提高路径搜索的效率,规划出的路径更加高效;

3)通常用图的模式来表示路径与路径之间的可行性,可适应性高。

4.2.2 栅格建模法

栅格建模法是指将环境地图按照工业生产要求划分为栅格,并对栅格的属性进行描述从而达到与现实环境相吻合的栅格地图。实际上,栅格建模法是一种粗略模拟现实环境的方法,栅格的精度决定现实环境与栅格地图的匹配度,栅格分辨率越高,精度越高,栅格密集程度越高,构建出的地图越符合实际环境特征,但同时也带来了算法复杂性过高的问题,因此,在实际使用中需根据现场的环境特征以及移动机器人的运动精度进行栅格的划分,既可以满足对于地图精度的要求又可以在一定程度上减少路径搜索时计算的时间复杂度。通过栅格建模法构建的栅格地图有以下优点:

1)地图构建方法较为简单;

2)对于短路径的规划更方便;

3)地图的可维护性较高。

因在第二章节中通过 Karto-SLAM 构建的地图为分辨率为 3cm 的栅格地图,故本文将采用栅格建模法对环境的地图进行重新构建,以达到可供路径规划所用的栅格地图的目的,考虑到路径搜索的效率,需将其按照固定比例转换为路径规划模块所需的栅格地图。地图转换流程如下:

1)根据全局地图的分辨率、路径站点间距以及机器人的尺寸确定转化比

例;

2)选定从起始点作为栅格的中心点,由该点向外扩展划分将全局地图划分为大分辨率的地图;

3)对每一个大栅格进行搜索,若其中的小栅格出现一个障碍点,即该大栅格为障碍栅格,否则即为空闲栅格,即为可行栅格;

4)将全局地图映射到栅格地图,标定出其中的空闲和障碍,表示地图中每个栅格的信息,得到包含环境信息的栅格地图。

4.3 常用路径搜索算法

4.3.1A*算法

A*算法作为经典的路径规划算法,是用于全局路径规划算法之一,广泛应

用于环境信息已知的全局路径规划,其是采用启发式搜索的算法,启发式估价函

数,如式(4.1)所示,通过当前点向附近节点扩展,计算到各个节点的代价值,选择代价值最小的节点作为路径中的下一个节点,直至搜索到目标点,从而获得最优路径。


f ( n) = g ( n) + h( n)

(4.1)

式中: f ( n) 为从起始点经过节点 n 到目标节点的估计代价函数; g ( n) 为从起始节点到节点 n 的实际代价函数;h ( n) 为由节点 n 到目标节点的估计代价函数,在实际应用中, h ( n) 常取两点间的欧几里得距离或曼哈顿距离。

A*算法的搜索步骤如下:

1)在地图中设置起始点 s 和目标点 t 并将起点 s 添加到开启列表中;

2)将起点的周围点都加入到开放列表中,起点 s 从开放链表中删除,并将其添加到关闭列表中,再利用式(4.1)计算各点的代价值,在开启链表中选择代价值最小的点,记为点 a

3)获取点 a 的周围点,判断是否已在开放链表中,若不在,则将其加入开放链表中;

4)将点 a 从开放链表中删除,并将其添加到关闭列表中,再利用式(4.1)计算各点的代价值,在开启链表中选择代价值最小的点,记为点 b,如此循环下去;

5)若目标点 t 在开启链表中,则成功搜索出路径,若开启链表中没有路径点,则路径搜索失败。

4.3.2D*算法

D*算法为动态 A*算法,广泛应用于动态环境下的路径规划,搜索方法类似

A*算法,区别在于 D*算法是从目标点搜索到起始站点。其通过维护一个优先队列来搜索地图中的路径节点,,从目标节点向起始节点采用 Dijstar 算法搜索,通过计算地图中目标点到各个节点的最短路径和该位置到目标点的实际代价值,如式(4.2)所示,选择代价值最小的节点组成的路径作为最优路径。

h( n) = c ( next , n) + next

(4.2)

式中:h ( n) 为当前点到目标点的实际代价值;c ( next , n) 为当前点到下一节点的新权值,next 为下一节点的原代价值。

4.4 路径规划模型设计

在栅格地图中,移动机器人根据各栅格的信息利用 A*搜索算法进行路径规划,获得从起始点到达目标点的最优路径。

首先,以构建的环境地图左下角作为原点 O,以原点 O 相连的两条边分别

X 轴和 Y 轴,从而建立直角坐标系 XOY ,将环境地图按照一定的分辨率划分为大小 M ´ N 的矩阵,如式(4.3)所示。


é a00

a01

L

a0 N ù

ê a

a

L

a

ú

(4.3)

A= ê

10

11

1N ú

M ´N

ê

M

M L

M ú

ê

aM 1

ú

ë aM 0

LaMN û

式中:M 为栅格地图 AM ´N 的横向栅格数,N 为栅格地图 AM ´N 的纵向栅格数,每个栅格作为一个站点,全图共 M ´ N 个站点;aMN 为栅格地图 AM ´N 上坐标 (M , N ) 的栅格的状态,若 aMN = 0 ,表示该栅格为空闲点,若 aMN =1 ,则表示该栅格为障碍点。

其次,在栅格地图 AM ´N 中根据移动机器人的位姿和任务要求设置起始点和目标点,并以 Y 轴正方向作为起始点的路径搜索方向;

最后,根据起始点与目标点以及栅格站点的状态,利用 A*算法的启发式函数搜索生成路径。

4.5 结果与分析

4.5.1 栅格地图转化结果

根据第二章的构建环境地图,按照 4.2.2 节栅格构建法对环境地图划分为路径规划的栅格地图。移动机器人当前位置映射到全局地图中,根据车辆尺寸和路径站点间距,确定分辨率,从而将全局地图划分为大分辨率的栅格地图。第二章节构建的环境全局地图的分辨率 resolution = 3cm ,同时在实际应用过程中,一般选择将栅格地图中的栅格的中心小栅格位姿作为该站点的位姿,因此,栅格划分

采用分辨率为 31 倍全局地图的分辨率以及 25 倍全局地图的分辨率,结果如图 4.1 和图 4.2 所示。


障碍点


空闲点


4.1 31 resolution 栅格地图 Fig4.1 31 X resolution grid map

障碍点

空闲点

4.2 25 resolution 栅格地图 Fig4.2 25 X resolution grid map

4.5.2 路径规划仿真结果与分析

本次仿真采用 Ubuntu14.04 系统和 QT 软件,根据 4.5.1 节获得的栅格地图,设置起始站点和目标站点,采用曼哈顿距离,调用 A*算法进行路径规划,同时在拐点处进行路径修剪,获得全局路径。结果如图 4.3 4.4 所示。

目标点

拐点

起始点

4.3 A*算法在 31 resolution 栅格地图规划路径

Fig4.3 Application of A* algorithm in 31 X resolution grid map path planning


目标点

拐点

起始点

4.4 A*算法在 25 resolution 栅格地图规划路径

Fig4.4 Application of A* algorithm in 25 X resolution grid map path planning

4.6 本章小结

本章节主要介绍了路径规划的相关内容,主要包括路径规划的一般步骤,即

环境地图建模,路径搜索、路径修剪;其次介绍了环境建模中的拓扑建模法和栅

格建模法,同时阐述了本文中采用的栅格建模法的实现步骤;其次对 A*算法和

D*算法进行了简要概述;再构建路径规划的模型,简明的介绍了基于 A*路径规

划的步骤;最后,通过对环境地图进行划分构建路径规划所用的地图,并基于划

分的栅格地图和 A*算法进行仿真。


  • 上一篇:无
  • 下一篇:激光导航AGV应用场景简要介绍
  • 400-086-6223
    15869185255

    手机二维码