Nothing Special   »   [go: up one dir, main page]

CN110442128A - 基于特征点提取蚁群算法的agv路径规划方法 - Google Patents

基于特征点提取蚁群算法的agv路径规划方法 Download PDF

Info

Publication number
CN110442128A
CN110442128A CN201910657050.XA CN201910657050A CN110442128A CN 110442128 A CN110442128 A CN 110442128A CN 201910657050 A CN201910657050 A CN 201910657050A CN 110442128 A CN110442128 A CN 110442128A
Authority
CN
China
Prior art keywords
grid
barrier
ant
group algorithm
vertex
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201910657050.XA
Other languages
English (en)
Other versions
CN110442128B (zh
Inventor
赵江
王晓博
郝崇清
朱江岭
孟晨阳
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Hebei University of Science and Technology
Original Assignee
Hebei University of Science and Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Hebei University of Science and Technology filed Critical Hebei University of Science and Technology
Priority to CN201910657050.XA priority Critical patent/CN110442128B/zh
Publication of CN110442128A publication Critical patent/CN110442128A/zh
Application granted granted Critical
Publication of CN110442128B publication Critical patent/CN110442128B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0214—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with safety or protection criteria, e.g. avoiding hazardous areas
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0221—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory involving a learning process
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0223—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory involving speed control of the vehicle
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0276—Control of position or course in two dimensions specially adapted to land vehicles using signals provided by a source external to the vehicle
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00—Road transport of goods or passengers
    • Y02T10/10—Internal combustion engine [ICE] based vehicles
    • Y02T10/40—Engine management systems

Landscapes

  • Engineering & Computer Science (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明提供了一种基于特征点提取蚁群算法的AGV路径规划方法，该方法包括环境建模和路径规划，环境建模包括栅格图的建立和特征点的提取，根据预先知道的AGV环境地图信息，将三维障碍物投影到二维平面栅格图后，将障碍物投影图分割为大小相同的栅格，再将障碍物阴影进行膨胀化，得到初始栅格图，将其中黑色障碍物栅格的顶点提取出来，并通过栅格可行性判断重新构造邻接矩阵，利用蚁群算法在特征点之间进行路径规划，最终得到一条从起点到终点的无障碍物路径。该方法克服了传统蚁群算法逐点搜索效率低下的问题，有效地节约了计算的时间，提高搜索效率，使规划出的路径更加平滑；同时新的栅格可行性判断方法，更有利于AGV的安全可靠运行。

Description

基于特征点提取蚁群算法的AGV路径规划方法
技术领域
本公开涉及计算机算法中的AGV路径规划技术领域，尤其是一种基于特征点提取蚁群算法的AGV路径规划方法。
背景技术
现有的AGV路径规划方法是先通过环境建模，建立一个与AGV运行环境一致的栅格环境模型，再在该环境模型上确定起点和终点，利用蚁群算法寻找出一条从起点到终点的无障碍物路径。但是该方法虽然能够成功求得一条从起点到终点的无障碍物路径，但是其搜索过程属于逐格搜索具有一定的盲目性，搜索过程中会搜索大量的非最优解使得收敛速度慢，严重影响了算法计算的效率，同时，仅根据栅格是否为障碍物栅格来判断其可行性会使规划出的路径频繁经过障碍物的顶点，影响AGV的安全运行。
发明内容
为了解决现有技术中的问题，本公开提出了一种基于特征点提取蚁群算法的AGV路径规划方法。该方法经过栅格法构建出AGV的运行环境模型后，将黑色障碍物栅格的顶点栅格作为特征点提取出来，利用蚁群算法在这些顶点栅格之间进行路径搜索，可以有效地引导搜索过程，减少规划时算法的计算量，并且，由于在特征点提取之后，原有的栅格之间的连接关系被打破，利用新的栅格可行性判断的方法来判断栅格之间的连接关系，得出的路径更加安全平滑，更加有利于AGV的运行。
第一方面，本公开实施例提供了一种基于特征点提取蚁群算法的AGV路径规划方法，包括以下步骤：确定AGV运行地图中障碍物的位置，并将所述障碍物的三维位置投射到二维平面上；对投射至二维平面上的障碍物投影图进行分割；对分割后的所述障碍物投影图中的障碍物阴影进行膨胀化处理，并将设置为黑色障碍物栅格的顶点栅格作为特征点进行提取；对提取出的栅格进行可行性判断并构造邻接矩阵；对蚁群算法的多个初始参数值进行设置并将当前代所有蚂蚁置于起点进行路径搜索；根据转移概率以及构造的所述邻接矩阵中的非0栅格选择下一个栅格直至到达终点。
在其中一个实施例中，所述对投射至二维平面上的障碍物投影图进行分割包括：将所述障碍物投影图分割为大小相同的栅格，栅格的数量为a*a。
在其中一个实施例中，对分割后的所述障碍物投影图中的障碍物阴影进行膨胀化处理包括：在对所述障碍物投影图分割后的栅格中存在障碍物的阴影，则将其设置为黑色障碍物栅格，否则设置为白色无障碍物栅格。
在其中一个实施例中，所述对提取出的栅格进行可行性判断并构造邻接矩阵包括：构造邻接矩阵D，其大小为a2*a2。
在其中一个实施例中，所述对蚁群算法的多个初始参数值进行设置包括：m为每代种群蚂蚁的数量，n为蚂蚁总共的代数，τ(0)为初始信息素浓度；
禁忌表Tabu为细胞结构大小为m*n，用以记录每一只蚂蚁行走的路线，路径长度矩阵PL的大小为m*n，用以记录每一代每一只蚂蚁爬行的路线长度；
初始化信息素衰减系数ρ，信息素启发因子α，距离启发因子β，迭代次数t；以及
对起点和终点的初始参数值进行设置。
在其中一个实施例中，还包括：判断当前代所有蚂蚁是否全部完成路径搜索，若全部完成搜索，则记录一次迭代次数，其中，迭代次数t＝t+1；判断迭代次数t是否满足迭代次数的要求，若满足则输出最短路径；若不满足迭代次数的要求，则更新信息素并执行派出下一代蚂蚁操作；将派出的所述下一代蚂蚁操作视为当前代，将当前代所有蚂蚁置于起点执行路径搜索。
在其中一个实施例中，还包括：判断当前代所有蚂蚁是否全部完成路径搜索，若未全部完成搜索，则根据转移概率以及所述邻接矩阵中的非0栅格选择下一个栅格直至到达终点。
在其中一个实施例中，所述将设置为黑色障碍物栅格的顶点栅格作为特征点进行提取包括：将所有单独黑色障碍物栅格的四个顶角栅格，所有组合黑色障碍物栅格的所有顶角和凹角栅格作为特征点进行提取。
在其中一个实施例中，所述对提取出的栅格进行可行性判断包括：若两个顶点栅格之间存在黑色障碍物栅格，则判定两个顶点栅格不可见，互为不可行栅格；若两个顶点栅格之间不存在黑色障碍物栅格，则判断两个顶点栅格的连线是否经过黑色障碍物栅格的顶点，若经过黑色障碍物栅格的顶点，则判定两个顶点栅格不可见，互为不可行栅格，若不经过黑色障碍物栅格的顶点，则判定两个顶点栅格可见，互为可行栅格。
在其中一个实施例中，还包括：所述转移概率公式为：
其中，τij(t)为在迭代次数为t时栅格i与j之间的信息素浓度，为迭代次数为t时栅格i与j之间的距离启发函数，alloweds为邻接矩阵D中，D(i，s)≠0时s代表的栅格。
在其中一个实施例中，所述信息素公式为：
τij(t+1)＝(1-ρ)τij(t)+Δτij(t)
其中，τij(k+1)为在迭代次数为t时，栅格i和j之间的信息素浓度，Δτij(t)为当前代蚂蚁在栅格i和j之间留下的信息素增量之和，为在迭代次数为t时，第k只蚂蚁在栅格i和j之间留下的信息素增量。
本发明提供的一种基于特征点提取蚁群算法的AGV路径规划方法，该方法包括环境建模和路径规划，环境建模包括栅格图的建立和特征点的提取，根据预先知道的AGV环境地图信息，将三维障碍物投影到二维平面栅格图后，将障碍物投影图分割为大小相同的栅格，再将障碍物阴影进行膨胀化，得到初始栅格图，将其中黑色障碍物栅格的顶点提取出来，并通过栅格可行性判断重新构造邻接矩阵，利用蚁群算法在特征点之间进行路径规划，最终得到一条从起点到终点的无障碍物路径。该方法本发明的AGV路径规划方法，克服了传统蚁群算法逐点搜索效率低下的问题，有效地节约了计算的时间，提高搜索效率，使规划出的路径更加平滑；同时，新的栅格可行性判断方法，可以有效解决规划出的路径距离障碍物过近的缺点，更有利于AGV的安全可靠运行。
附图说明
为了更清楚地说明本公开实施例的技术方案，下面对实施例描述中所需要使用的附图作简单地介绍：
图1为本发明一个实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法的步骤流程图；
图2为本发明另一实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法的步骤流程图；
图3为本发明一个实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法中的实际环境的障碍物投影图；
图4为本发明一个实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法中的实际环境的栅格图；
图5为本发明一个实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法中经过编号的顶点栅格分布图；
图6为本发明一个实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法中栅格可行性判断分析图；以及
图7为本发明一个实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法中该环境下路径规划仿真结果图。
具体实施方式
下面结合附图和实施例对本申请进行进一步的详细介绍。
在下述介绍中，术语“第一”、“第二”仅为用于描述的目的，而不能理解为指示或暗示相对重要性。下述介绍提供了本公开的多个实施例，不同实施例之间可以替换或者合并组合，因此本申请也可认为包含所记载的相同和/或不同实施例的所有可能组合。因而，如果一个实施例包含特征A、B、C，另一个实施例包含特征B、D，那么本申请也应视为包括含有A、B、C、D的一个或多个所有其他可能的组合的实施例，尽管该实施例可能并未在以下内容中有明确的文字记载。
为了使本发明的目的、技术方案及优点更加清楚明白，以下通过实施例，并结合附图，对本发明一种基于特征点提取蚁群算法的AGV路径规划方法的具体实施方式进行进一步详细说明。需要说明的是，本公开涉及涡轮机械旋转通道近壁面边界层内速度和温度测量技术领域，应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。
如图1所示，为一个实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法的流程示意图，具体包括以下步骤：
步骤101，确定AGV运行地图中障碍物的位置，并将所述障碍物的三维位置投射到二维平面上。
步骤102，对投射至二维平面上的障碍物投影图进行分割。
具体的，对投射至二维平面上的障碍物投影图进行分割包括：将障碍物投影图分割为大小相同的栅格，栅格的数量为a*a。
步骤103，对分割后的障碍物投影图中的障碍物阴影进行膨胀化处理，并将设置为黑色障碍物栅格的顶点栅格作为特征点进行提取。
具体的，将设置为黑色障碍物栅格的顶点栅格作为特征点进行提取包括：将所有单独黑色障碍物栅格的四个顶角栅格，所有组合黑色障碍物栅格的所有顶角和凹角栅格作为特征点进行提取。
具体的，对分割后的障碍物投影图中的障碍物阴影进行膨胀化处理包括：在对障碍物投影图分割后的栅格中存在障碍物的阴影，则将其设置为黑色障碍物栅格，否则设置为白色无障碍物栅格。
步骤104，对提取出的栅格进行可行性判断并构造邻接矩阵。
具体的，对提取出的栅格进行可行性判断并构造邻接矩阵包括：构造邻接矩阵D，其大小为a2*a2。
进一步地，对提取出的栅格进行可行性判断包括：若两个顶点栅格之间存在黑色障碍物栅格，则判定两个顶点栅格不可见，互为不可行栅格；若两个顶点栅格之间不存在黑色障碍物栅格，则判断两个顶点栅格的连线是否经过黑色障碍物栅格的顶点，若经过黑色障碍物栅格的顶点，则判定两个顶点栅格不可见，互为不可行栅格，若不经过黑色障碍物栅格的顶点，则判定两个顶点栅格可见，互为可行栅格。
步骤105，对蚁群算法的多个初始参数值进行设置并将当前代所有蚂蚁置于起点进行路径搜索。
具体的，对蚁群算法的多个初始参数值进行设置包括：m为每代种群蚂蚁的数量，n为蚂蚁总共的代数，τ(0)为初始信息素浓度；
禁忌表Tabu为细胞结构大小为m*n，用以记录每一只蚂蚁行走的路线，路径长度矩阵PL的大小为m*n，用以记录每一代每一只蚂蚁爬行的路线长度；
初始化信息素衰减系数ρ，信息素启发因子α，距离启发因子β，迭代次数t；以及对起点和终点的初始参数值进行设置。
步骤106，根据转移概率以及构造的所述邻接矩阵中的非0栅格选择下一个栅格直至到达终点。
具体的，转移概率公式为：
其中，τij(t)为在迭代次数为t时栅格i与j之间的信息素浓度，为迭代次数为t时栅格i与j之间的距离启发函数，alloweds为邻接矩阵D中，D(i，s)≠0时s代表的栅格。
此外，在一个实施例中，本公开提出的基于特征点提取蚁群算法AGV路径规划方法还包括：判断当前代所有蚂蚁是否全部完成路径搜索，若全部完成搜索，则记录一次迭代次数，其中，迭代次数t＝t+1；判断迭代次数t是否满足迭代次数的要求，若满足则输出最短路径；若不满足迭代次数的要求，则更新信息素并执行派出下一代蚂蚁操作；将派出的下一代蚂蚁操作视为当前代，将当前代所有蚂蚁置于起点执行路径搜索。
其中，需要说明的是，信息素公式为
τij(t+1)＝(1-ρ)τij(t)+Δτij(t)
其中，τij(k+1)为在迭代次数为t时，栅格i和j之间的信息素浓度，Δτij(t)为当前代蚂蚁在栅格i和j之间留下的信息素增量之和，为在迭代次数为t时，第k只蚂蚁在栅格i和j之间留下的信息素增量。
进一步地，在一个实施例中，本公开提出的基于特征点提取蚁群算法AGV路径规划方法还包括：判断当前代所有蚂蚁是否全部完成路径搜索，若未全部完成搜索，则根据转移概率以及所述邻接矩阵中的非0栅格选择下一个栅格直至到达终点。
综上所述可知，现有的路径规划方法中，算法往往是从全部栅格中层层扩展，逐格规划来得到从起点到终点的无障碍物路径的，这会使算法的计算量过大，搜索的非最优解过多，造成算法效率低，迭代次数过多的问题，本发明对栅格图进行特征点提取的处理，将算法的搜索范围从所有栅格缩小到所有黑色障碍物栅格的顶点栅格，可减少算法的计算量，加快收敛速度。
进一步地，现有的栅格间可行性判断，是通过判断当前栅格周围的八个栅格是否为障碍物栅格来判断的，若为黑色障碍物栅格，则两个栅格之间不可行，若为白色非障碍物栅格，则两个栅格之间是可行的，这会造成规划出的路径无法避开黑色障碍物栅格的顶角，从而影响AGV运行的安全性，本发明采用的新的栅格可行性判断将经过黑色障碍物栅格顶点的路径设为不可行路径，使规划出的路径更加安全平滑，有利于AGV的运行。
本公开提出的基于特征点提取蚁群算法的AGV路径规划方法克服了传统蚁群算法逐点搜索效率低下的问题，有效地节约了计算的时间，提高搜索效率，使规划出的路径更加平滑；同时，新的栅格可行性判断方法，可以有效解决规划出的路径距离障碍物过近的缺点，更有利于AGV的安全可靠运行。
为了更清楚地理解与应用本公开提出的基于特征点提取蚁群算法的AGV路径规划方法，进行以下示例。需要说明的是，本公开所保护的范围不限于以下示例。
具体的，如图2-图7所示，图2为本发明另一实施例中的一种基于特征点提取蚁群算法的AGV路径规划方法的步骤流程图。具体步骤如下
S1：确定AGV运行地图中障碍物的位置，并将三维障碍物投影到二维平面上，障碍物投影图如图3所示。
S2：对障碍物投影图进行分割，将其分割为大小相同的栅格，栅格的数量为a*a。
S3：将障碍物阴影膨胀化，只要该栅格中存在障碍物的阴影，则将其设置为黑色障碍物栅格，否则为白色无障碍物栅格，栅格图如图4所示。
S4：将黑色障碍物栅格的顶点栅格作为特征点提取出来，经过编号的顶点栅格分布图如图5所示。
S5：对提取出的顶点栅格进行可行性判断，重新构造邻接矩阵D，其大小为a2*a2。
S6：设定蚁群算法的初始参数值：m为每代种群蚂蚁的数量，n为蚂蚁总共的代数，τ(0)为初始信息素浓度，禁忌表Tabu为细胞结构大小为m*n，用以记录每一只蚂蚁行走的路线，路径长度矩阵PL的大小为m*n，用以记录每一代每一只蚂蚁爬行的路线长度；同时初始化信息素衰减系数ρ，信息素启发因子α，距离启发因子β，迭代次数t，以及起点和终点。
S7：将当前代所有蚂蚁置于起点，开始进行路径搜索。
S8：根据转移概率以及邻接矩阵中的非0栅格选择下一个栅格，直到到达终点，完成一次路径搜索。
S9：判断当前代所有蚂蚁是否全部完成路径搜索，若全部完成搜索，进入S10，否则返回S8。
S10：记录一次迭代次数，t＝t+1。
S11：判断迭代次数t是否满足迭代次数的要求，若满足则输出最短路径，否则，进入S12，最终得到的最优路线如图7所示。
S12：更新信息素，并派出下一代蚂蚁，返回S7。
进一步，所述步骤S4中，提取的特征点包括：所有单独黑色障碍物栅格的四个顶角，所有组合黑色障碍物栅格的所有顶角和凹角。
进一步，所述步骤S5中，栅格可行性判断的方法为，如图6所示，若两个顶点栅格之间存在黑色障碍物栅格，则判定两个顶点栅格不可见，互为不可行栅格；若两个顶点栅格之间不存在黑色障碍物栅格，则判断两个顶点栅格的连线是否经过黑色障碍物栅格的顶点，若经过黑色障碍物栅格的顶点，则判定两个顶点栅格不可见，互为不可行栅格，若不经过黑色障碍物栅格的顶点，则判定两个顶点栅格可见，互为可行栅格。
进一步，所述步骤S8中，蚂蚁选择下一个栅格的转移概率公式为：
其中，τij(t)为在迭代次数为t时栅格i与j之间的信息素浓度，为迭代次数为t时栅格i与j之间的距离启发函数，alloweds为邻接矩阵D中，D(i，s)≠0时s代表的栅格。
进一步，所述步骤S12中，信息素的更新公式为：
τij(t+1)＝(1-ρ)τij(t)+Δτij(t) (2)
其中，τij(k+1)为在迭代次数为t时，栅格i和j之间的信息素浓度，Δτij(t)为当前代蚂蚁在栅格i和j之间留下的信息素增量之和，为在迭代次数为t时，第k只蚂蚁在栅格i和j之间留下的信息素增量。
综上所述，本公开提出的一种基于特征点提取蚁群算法的AGV路径规划方法克服了传统蚁群算法路径规划存在的弊端，通过提取特征点和新的栅格可行性判断方法，提高了算法的效率，规划出的路径更加安全平滑，得到了更优的结果。与此同时，该方法可以减少路径规划时算法的计算量，同时使规划出的路径更加安全平滑，有利于AGV安全可靠地运行。
本发明提供的一种基于特征点提取蚁群算法的AGV路径规划方法，该方法包括环境建模和路径规划，环境建模包括栅格图的建立和特征点的提取，根据预先知道的AGV环境地图信息，将三维障碍物投影到二维平面栅格图后，将障碍物投影图分割为大小相同的栅格，再将障碍物阴影进行膨胀化，得到初始栅格图，将其中黑色障碍物栅格的顶点提取出来，并通过栅格可行性判断重新构造邻接矩阵，利用蚁群算法在特征点之间进行路径规划，最终得到一条从起点到终点的无障碍物路径。该方法本发明的AGV路径规划方法，克服了传统蚁群算法逐点搜索效率低下的问题，有效地节约了计算的时间，提高搜索效率，使规划出的路径更加平滑；同时，新的栅格可行性判断方法，可以有效解决规划出的路径距离障碍物过近的缺点，更有利于AGV的安全可靠运行。
本发明实施例还提供了一种计算机可读存储介质，该计算机可读存储介质上存储有计算机程序，该程序被图1中处理器执行。
本发明实施例还提供了一种包含指令的计算机程序产品。当该计算机程序产品在计算机上运行时，使得计算机执行上述图1的方法。
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-Only Memory，ROM)或随机存储记忆体(Random AccessMemory，RAM)等。
以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对本发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。因此，本发明专利的保护范围应以所附权利要求为准。
以上结合具体实施例描述了本公开的基本原理，但是，需要指出的是，在本公开中提及的优点、优势、效果等仅是示例而非限制，不能认为这些优点、优势、效果等是本公开的各个实施例必须具备的。另外，上述公开的具体细节仅是为了示例的作用和便于理解的作用，而非限制，上述细节并不限制本公开为必须采用上述具体的细节来实现。
本公开中涉及的器件、装置、设备、系统的方框图仅作为示例性的例子并且不意图要求或暗示必须按照方框图示出的方式进行连接、布置、配置。如本领域技术人员将认识到的，可以按任意方式连接、布置、配置这些器件、装置、设备、系统。诸如“包括”、“包含”、“具有”等等的词语是开放性词汇，指“包括但不限于”，且可与其互换使用。这里所使用的词汇“或”和“和”指词汇“和/或”，且可与其互换使用，除非上下文明确指示不是如此。这里所使用的词汇“诸如”指词组“诸如但不限于”，且可与其互换使用。
另外，如在此使用的，在以“至少一个”开始的项的列举中使用的“或”指示分离的列举，例如“A、B或C的至少一个”的列举意味着A或B或C，或AB或AC或BC，或ABC(即A和B和C)。此外，措辞“示例的”不意味着描述的例子是优选的或者比其他例子更好。
为了示例和描述的目的已经给出了以上描述。但此描述不意味着将本公开的实施例限制到在此公开的形式。

Claims (10)

1.一种基于特征点提取蚁群算法的AGV路径规划方法，其特征在于，包括以下步骤：
确定AGV运行地图中障碍物的位置，并将所述障碍物的三维位置投射到二维平面上；
对投射至二维平面上的障碍物投影图进行分割；
对分割后的所述障碍物投影图中的障碍物阴影进行膨胀化处理，并将设置为黑色障碍物栅格的顶点栅格作为特征点进行提取；
对提取出的栅格进行可行性判断并构造邻接矩阵；
对蚁群算法的多个初始参数值进行设置并将当前代所有蚂蚁置于起点进行路径搜索；
根据转移概率以及构造的所述邻接矩阵中的非0栅格选择下一个栅格直至到达终点。
2.根据权利要求1所述的基于特征点提取蚁群算法的AGV路径规划方法，其特征在于，所述对投射至二维平面上的障碍物投影图进行分割及障碍物膨胀化处理包括：将所述障碍物投影图分割为大小相同的栅格，栅格的数量为a*a，若分割后的栅格中存在障碍物阴影，则将其设置为黑色障碍物栅格，否则设置为白色无障碍物栅格。
3.根据权利要求1所述的基于特征点提取蚁群算法的AGV路径规划方法，其特征在于，所述对提取出的栅格进行可行性判断并构造邻接矩阵包括：构造邻接矩阵D，其大小为a2*a2。
4.根据权利要求1所述的基于特征点提取蚁群算法AGV路径规划方法，其特征在于，所述对蚁群算法的多个初始参数值进行设置包括：m为每代种群蚂蚁的数量，n为蚂蚁总共的代数，τ(0)为初始信息素浓度；
禁忌表Tabu为细胞结构大小为m*n，用以记录每一只蚂蚁行走的路线，路径长度矩阵PL的大小为m*n，用以记录每一代每一只蚂蚁爬行的路线长度；
初始化信息素衰减系数ρ，信息素启发因子α，距离启发因子β，迭代次数t；以及
对起点和终点的初始参数值进行设置。
5.根据权利要求1所述的基于特征点提取蚁群算法AGV路径规划方法，其特征在于，还包括：判断当前代所有蚂蚁是否全部完成路径搜索，若全部完成搜索，则记录一次迭代次数，其中，迭代次数t＝t+1；
判断迭代次数t是否满足迭代次数的要求，若满足则输出最短路径；
若不满足迭代次数的要求，则更新信息素并执行派出下一代蚂蚁操作；
将派出的所述下一代蚂蚁操作视为当前代，将当前代所有蚂蚁置于起点执行路径搜索。
6.根据权利要求1所述的基于特征点提取蚁群算法AGV路径规划方法，其特征在于，还包括：判断当前代所有蚂蚁是否全部完成路径搜索，若未全部完成搜索，则根据转移概率以及所述邻接矩阵中的非0栅格选择下一个栅格直至到达终点。
7.根据权利要求1所述的基于特征点提取蚁群算法AGV路径规划方法，其特征在于，所述将设置为黑色障碍物栅格的顶点栅格作为特征点进行提取包括：将所有单独黑色障碍物栅格的四个顶角栅格，所有组合黑色障碍物栅格的所有顶角和凹角栅格作为特征点进行提取。
8.根据权利要求1所述的基于特征点提取蚁群算法AGV路径规划方法，其特征在于，所述对提取出的栅格进行可行性判断包括：若两个顶点栅格之间存在黑色障碍物栅格，则判定两个顶点栅格不可见，互为不可行栅格；
若两个顶点栅格之间不存在黑色障碍物栅格，则判断两个顶点栅格的连线是否经过黑色障碍物栅格的顶点，若经过黑色障碍物栅格的顶点，则判定两个顶点栅格不可见，互为不可行栅格，若不经过黑色障碍物栅格的顶点，则判定两个顶点栅格可见，互为可行栅格。
9.根据权利要求1所述的基于特征点提取蚁群算法的AGV路径规划方法，其特征在于，还包括：所述转移概率公式为：
其中，τij(t)为在迭代次数为t时栅格i与j之间的信息素浓度，为迭代次数为t时栅格i与j之间的距离启发函数，alloweds为邻接矩阵D中,D(i，s)≠0时s代表的栅格。
10.根据权利要求6所述的基于特征点提取蚁群算法的AGV路径规划方法，其特征在于，所述信息素公式为
τij(t+1)＝(1-ρ)τij(t)+Δτij(t)
其中，τij(k+1)为在迭代次数为t时，栅格i和j之间的信息素浓度，Δτij(t)为当前代蚂蚁在栅格i和j之间留下的信息素增量之和,为在迭代次数为t时，第k只蚂蚁在栅格i和j之间留下的信息素增量。
CN201910657050.XA 2019-07-20 2019-07-20 基于特征点提取蚁群算法的agv路径规划方法 Active CN110442128B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201910657050.XA CN110442128B (zh) 2019-07-20 2019-07-20 基于特征点提取蚁群算法的agv路径规划方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201910657050.XA CN110442128B (zh) 2019-07-20 2019-07-20 基于特征点提取蚁群算法的agv路径规划方法

Publications (2)

Publication Number Publication Date
CN110442128A true CN110442128A (zh) 2019-11-12
CN110442128B CN110442128B (zh) 2022-08-16

Family

ID=68430977

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201910657050.XA Active CN110442128B (zh) 2019-07-20 2019-07-20 基于特征点提取蚁群算法的agv路径规划方法

Country Status (1)

Country Link
CN (1) CN110442128B (zh)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111413965A (zh) * 2020-03-11 2020-07-14 西安工程大学 一种基于uav协同感知的ugv行驶路径规划方法
CN112099493A (zh) * 2020-08-31 2020-12-18 西安交通大学 一种自主移动机器人轨迹规划方法、系统及设备
CN112528444A (zh) * 2020-12-04 2021-03-19 国网浙江省电力有限公司嘉兴供电公司 一种输电线路三维设计方法及系统
CN112669466A (zh) * 2020-12-23 2021-04-16 北京像素软件科技股份有限公司 虚拟空间路径规划方法、装置、电子设备及存储介质
CN115268423A (zh) * 2022-05-05 2022-11-01 安徽理工大学 基于改进蚁群算法的列车送餐机器人路径规划方法
CN117670162A (zh) * 2023-12-06 2024-03-08 珠海市格努信息技术有限公司 一种场内智能物流解决方法

Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103439972A (zh) * 2013-08-06 2013-12-11 重庆邮电大学 一种动态复杂环境下的移动机器人路径规划方法
CN103472828A (zh) * 2013-09-13 2013-12-25 桂林电子科技大学 基于改进蚁群粒子群算法的移动机器人路径规划方法
CN104535061A (zh) * 2015-01-06 2015-04-22 常州先进制造技术研究所 一种基于多传感器数据融合的导航系统
US20160171316A1 (en) * 2014-12-10 2016-06-16 Honda Research Institute Europe Gmbh Method and system for adaptive ray based scene analysis of semantic traffic spaces and vehicle equipped with such system
CN106200650A (zh) * 2016-09-22 2016-12-07 江苏理工学院 基于改进蚁群算法的移动机器人路径规划方法及系统
CN106599936A (zh) * 2016-12-29 2017-04-26 湖北工业大学 一种基于二进制蚁群算法的特征选择方法及系统
CN107092252A (zh) * 2017-04-11 2017-08-25 杭州光珀智能科技有限公司 一种基于机器视觉的机器人主动避障方法及其装置
CN108413963A (zh) * 2018-02-12 2018-08-17 淮安信息职业技术学院 基于自学习蚁群算法的条形机器人路径规划方法
CN108827309A (zh) * 2018-06-29 2018-11-16 炬大科技有限公司 一种机器人路径规划方法及具有它的吸尘器

Patent Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103439972A (zh) * 2013-08-06 2013-12-11 重庆邮电大学 一种动态复杂环境下的移动机器人路径规划方法
CN103472828A (zh) * 2013-09-13 2013-12-25 桂林电子科技大学 基于改进蚁群粒子群算法的移动机器人路径规划方法
US20160171316A1 (en) * 2014-12-10 2016-06-16 Honda Research Institute Europe Gmbh Method and system for adaptive ray based scene analysis of semantic traffic spaces and vehicle equipped with such system
CN104535061A (zh) * 2015-01-06 2015-04-22 常州先进制造技术研究所 一种基于多传感器数据融合的导航系统
CN106200650A (zh) * 2016-09-22 2016-12-07 江苏理工学院 基于改进蚁群算法的移动机器人路径规划方法及系统
CN106599936A (zh) * 2016-12-29 2017-04-26 湖北工业大学 一种基于二进制蚁群算法的特征选择方法及系统
CN107092252A (zh) * 2017-04-11 2017-08-25 杭州光珀智能科技有限公司 一种基于机器视觉的机器人主动避障方法及其装置
CN108413963A (zh) * 2018-02-12 2018-08-17 淮安信息职业技术学院 基于自学习蚁群算法的条形机器人路径规划方法
CN108827309A (zh) * 2018-06-29 2018-11-16 炬大科技有限公司 一种机器人路径规划方法及具有它的吸尘器

Non-Patent Citations (6)

* Cited by examiner, † Cited by third party
Title
JIANG ZHAO;WENYAN XUE;CHONGQING HAO: "Heterogeneous Feature Ant Colony Optimization Algorithm Based on Effective Vertexes of Obstacles", 《2018 CHINESE AUTOMATION CONGRESS (CAC)》 *
JIANG ZHAO;YAZHE DING;CHANG TIAN;CHONGQIGN HAO;LINGGANG MENG: "Path planning of the Omni-directional Mobile Vehicle in Warehouse environment", 《2017 CHINESE AUTOMATION CONGRESS (CAC)》 *
刘琳琳: "基于栅格地图环境的机器人路径规划算法", 《机电信息》 *
张晓玲等: "基于蚁群算法的移动机器人路径规划", 《激光杂志》 *
成伟明: "移动机器人自主导航中的路径规划与跟踪控制技术研究", 《中国优秀博硕士学位论文全文数据库(博士)信息科技辑》 *
薛文艳: "地面机器人路径规划及其控制研究", 《中国优秀硕士学位论文全文数据库 信息科技辑》 *

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111413965A (zh) * 2020-03-11 2020-07-14 西安工程大学 一种基于uav协同感知的ugv行驶路径规划方法
CN112099493A (zh) * 2020-08-31 2020-12-18 西安交通大学 一种自主移动机器人轨迹规划方法、系统及设备
CN112099493B (zh) * 2020-08-31 2021-11-19 西安交通大学 一种自主移动机器人轨迹规划方法、系统及设备
CN112528444A (zh) * 2020-12-04 2021-03-19 国网浙江省电力有限公司嘉兴供电公司 一种输电线路三维设计方法及系统
CN112669466A (zh) * 2020-12-23 2021-04-16 北京像素软件科技股份有限公司 虚拟空间路径规划方法、装置、电子设备及存储介质
CN115268423A (zh) * 2022-05-05 2022-11-01 安徽理工大学 基于改进蚁群算法的列车送餐机器人路径规划方法
CN117670162A (zh) * 2023-12-06 2024-03-08 珠海市格努信息技术有限公司 一种场内智能物流解决方法

Also Published As

Publication number Publication date
CN110442128B (zh) 2022-08-16

Similar Documents

Publication Publication Date Title
CN110442128A (zh) 基于特征点提取蚁群算法的agv路径规划方法
CN109101694B (zh) 一种安全疏散标志引导的人群行为仿真方法及系统
CN103528585B (zh) 一种不等距分割可通行区域的路径规划方法
CN106097311A (zh) 机载激光雷达数据的建筑物三维重建方法
AU2022204569B2 (en) Method for multi-agent dynamic path planning
CN106125764A (zh) 基于a*搜索的无人机路径动态规划方法
CN107478231A (zh) 基于多边形障碍检测的无人机路线规划算法
CN107121146A (zh) 基于路链深度的最优路径规划方法
CN107883954A (zh) 用于生成旨在供飞行器遵循的最佳飞行路径的方法和设备
CN103559705A (zh) 一种比较不同植物形态相似度的计算机方法
CN106529029A (zh) 输电线路杆塔的点云数据提取方法及装置
CN110196059A (zh) 一种无人艇全局路径规划方法
US20210142527A1 (en) Sytems and methods for labeling areas on an airport map
CN114625150A (zh) 基于危险指数和距离函数的快速蚁群无人艇动态避障方法
CN110411454A (zh) 一种改进随机路径图法的移动机器人路径规划方法
CN109947129A (zh) 基于Dijkstra与改进粒子群算法的旋翼无人机路径规划方法
CN107918953A (zh) 基于三维空间的激光扫描电力线点云的提取方法及装置
CN109472416A (zh) 基于自动路网数据提取的室内路径规划方法及装置、客户端
CN110443816A (zh) 基于道路交叉口检测的遥感影像上城市道路提取方法
CN110162060A (zh) 一种基于改进烟花爆炸算法的机器人路径规划方法
CN117191017A (zh) 一种化工场景下巡检机器人高精度安全路径规划方法
CN109885082A (zh) 一种基于任务驱动下的无人机航迹规划的方法
CN116661502A (zh) 一种智能农业无人机路径规划方法
CN109241369B (zh) 基于网格延展法的降雨等值线构建方法
Yang et al. Research intelligent fire evacuation system based on ant colony algorithm and MapX

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
EE01 Entry into force of recordation of patent licensing contract
EE01 Entry into force of recordation of patent licensing contract

Application publication date: 20191112

Assignee: SHIJIAZHUANG JIAKE ELECTROMECHANICAL TECHNOLOGY Co.,Ltd.

Assignor: HEBEI University OF SCIENCE AND TECHNOLOGY

Contract record no.: X2023980043391

Denomination of invention: AGV Path Planning Method Based on Ant Colony Algorithm for Feature Point Extraction

Granted publication date: 20220816

License type: Common License

Record date: 20231013