[go: up one dir, main page]

CN111487957B - 一种agv路径规划方法、装置、电子设备及存储介质 - Google Patents

一种agv路径规划方法、装置、电子设备及存储介质 Download PDF

Info

Publication number
CN111487957B
CN111487957B CN201910079511.XA CN201910079511A CN111487957B CN 111487957 B CN111487957 B CN 111487957B CN 201910079511 A CN201910079511 A CN 201910079511A CN 111487957 B CN111487957 B CN 111487957B
Authority
CN
China
Prior art keywords
agv
path
target
congestion
size
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.)
Active
Application number
CN201910079511.XA
Other languages
English (en)
Other versions
CN111487957A (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.)
Hangzhou Hikrobot Co Ltd
Original Assignee
Hangzhou Hikrobot Co Ltd
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 Hangzhou Hikrobot Co Ltd filed Critical Hangzhou Hikrobot Co Ltd
Priority to CN201910079511.XA priority Critical patent/CN111487957B/zh
Publication of CN111487957A publication Critical patent/CN111487957A/zh
Application granted granted Critical
Publication of CN111487957B publication Critical patent/CN111487957B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

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/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/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/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
    • Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
    • Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
    • Y02P90/60—Electric or hybrid propulsion means for production processes

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)
  • Traffic Control Systems (AREA)

Abstract

本发明实施例提供了一种AGV路径规划方法、装置、电子设备及存储介质，该方法包括：将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，将当前路径点与相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段，根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，如果是，根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；如果支持，将相邻路径点保存为目标AGV的可达路径点。这样，可以在路径规划时，通过AGV的尺寸以及道路的宽度来确定该道路是否会发生拥堵，可以避免对道路进行“加锁”，从而提高了道路的利用率。

Description

一种AGV路径规划方法、装置、电子设备及存储介质
技术领域
本发明涉及工业控制技术领域，特别是涉及一种AGV路径规划方法、装置、电子设备及存储介质。
背景技术
随着制造业和物流业自动化程度的提高，AGV(Automated Guided Vehicle，自动导引运输车)得到了广泛应用，该AGV上装备有自动引导装置(例如，电磁引导装置或光学引导装置)，可以装载着被载物体，自动沿引导路径行驶。该引导路径通常是在该AGV从初始位置出发前，为该AGV规划的。
在AGV的实际应用中，通常以系统的形式应用，例如，在一个物流仓库的AGV系统中，包括：地面控制设备和多个AGV，该地面控制设备对该多个AGV进行管理，例如，为该多个AGV分别规划对应的引导路径，每个AGV按照对应的引导路径行驶。
具体的，该地面控制设备中预先保存有目标环境的电子地图，该电子地图中预先设置有多个路径点，每个路径点在目标环境中具有对应的位置。该地面控制设备在规划AGV的行驶路径时，通过采用路径规划算法在该选择从该AGV的初始位置至目标位置之间的预先设置的路径点中依次选择多个路径点，然后由该AGV的初始位置、选择的多个路径点以及目标位置组成该AGV的行驶路径。
地面控制设备在规划路径时，需要避免任意两个AGV在道路上发生拥堵。目前常用的避免拥堵的方式是：避免任意两个AGV在相同的时间通过同一个位置，或者，避免任意两个AGV在相同的时间段通过同一个路段。例如，现有技术中提出的一种动态路径规划方法：地面控制设备对先接到调度命令的AGV即将路过的所有路段“加锁”，使得后接到调度命令的AGV无法通过该“加锁”的路段，待该先接到调度命令的AGV经过该“加锁”的路段后，将经过后的路段“解锁”。该方法虽能让后接到调度命令的AGV选择绕行，避免AGV发生碰撞，但是，当该先接到调度命令的AGV在该“加锁”的路段发生故障时，该“加锁”的道路一直处于“加锁”状态，其他AGV无法通过该处于“加锁”状态的道路，降低了道路的利用率，进而降低了AGV系统的工作效率。
发明内容
本发明实施例的目的在于提供一种AGV路径规划方法、装置、电子设备及存储介质，以提高道路的利用率，进而提高AGV系统的工作效率。具体技术方案如下：
第一方面，本发明实施例提供了一种AGV路径规划方法，该方法包括：
将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，针对当前路径点和查找到的相邻路径点执行以下处理：
将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；
根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；
如果是，则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；
如果支持，将相邻路径点保存为目标AGV的可达路径点。
可选的，在判断第一重合区域是否支持第一AGV和目标AGV并行通过之后，该AGV路径规划方法还包括：
如果第一重合区域不支持第一AGV和目标AGV并行通过，则查找与当前路径点相邻的新的相邻路径点，针对当前路径点和新的相邻路径点返回执行上述处理。
可选的，计算目标AGV通过待定子路径的待定时间段，包括：
计算目标AGV到达当前路径点的第一预估时刻和到达相邻路径点的第二预估时刻，将第一预估时刻至第二预估时刻的时间段确定为目标AGV通过待定子路径的待定时间段；
可选的，在将相邻路径点保存为目标AGV的可达路径点之后，该AGV路径规划方法还包括：
保存第二预估时刻。
可选的，在将相邻路径点保存为目标AGV的可达路径点之后，该AGV路径规划方法还包括：
判断相邻路径点是否为目标AGV的目标路径点；
如果是，则根据已保存的目标AGV的可达路径点，输出目标AGV从起始路径点到目标路径点的路径；
如果否，则将相邻路径点作为新的当前路径点，查找与新的当前路径点相邻的路径点，针对新的当前路径点和与新的当前路径点相邻的路径点返回执行上述处理。
可选的，在判断是否存在第一AGV之后，该AGV路径规划方法还包括：
如果否，将相邻路径点保存为目标AGV的可达路径点。
可选的，该AGV路径规划方法还包括：
如果第一重合区域不支持第一AGV和目标AGV并行通过，则将计算得到的目标AGV通过待定子路径的待定时间段向后推延第一固定时长，得到第一待定时间段，第一固定时长大于或等于目标AGV以预设行驶速度通过待定子路径所花费的时长；
针对第一待定时间段和已保存的其他AGV的路径信息，返回执行判断是否存在第一AGV的步骤。
可选的，在根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV的步骤之前，该AGV路径规划方法还包括：
判断当前是否发生拥堵，如果否，执行根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV的步骤；
如果是，则获取拥堵拓扑图，其中，拥堵拓扑图为：根据引起拥堵的拥堵源AGV和各个AGV之间的阻塞关系建立的具有多级子节点的拓扑图；其中，引起拥堵的拥堵源AGV为根节点，每个子节点对应的AGV的路径中包含其父节点对应的AGV的位置；拥堵拓扑图中，还包括：各个子节点到达父节点的位置的时长；
获取拥堵拓扑图中各个节点对应的AGV的路径信息；
根据待定时间段、拥堵拓扑图和各个节点对应的AGV的路径信息，判断拥堵拓扑图中是否存在第二AGV；其中，第二AGV满足以下条件：第二AGV从其所处位置到达其父节点对应的AGV所处位置之间的路径与待定子路径存在第二重合区域，且，第二AGV通过第二重合区域到达其父节点对应的AGV所处位置的累加时间段与待定时间段存在交集；
如果是，则根据第二AGV的尺寸、目标AGV的尺寸和第二重合区域所在道路的第二宽度，判断第二重合区域是否支持第二AGV和目标AGV并行通过；
如果支持，将相邻路径点保存为目标AGV的可达路径点。
可选的，拥堵拓扑图通过如下步骤建立：
获得引起拥堵的拥堵源AGV及其位置作为根节点；
获得拥堵源AGV的关联AGV及其位置作为根节点的子节点；其中，拥堵源AGV的关联AGV满足以下条件：与拥堵源AGV有阻塞关系，且拥堵源AGV的关联AGV从其所在位置至拥堵源AGV的位置之间的子路径中，不包含其他与拥堵源AGV有阻塞关系的AGV，拥堵源AGV的关联AGV的路径中包含拥堵源AGV的位置；
对各个子节点，获得与该子节点有阻塞关系的各个关联AGV及其位置作为下一级子节点；对下一级子节点执行本步骤，直到下一级子节点没有有阻塞关系的关联AGV；各个子节点的路径中包含其父节点的位置；
计算各个子节点对应的AGV从其所处位置到达父节点对应的AGV所处位置的到达时长，并将各个子节点对应的到达时长添加至对应的各个子节点。
可选的，在获得与拥堵源AGV有阻塞关系的各个关联AGV及其位置作为根节点的子节点之前，该AGV路径规划方法还包括：
获取拥堵源AGV的尺寸和行驶路径包含拥堵源AGV所处位置的第三AGV的尺寸；
根据第三AGV所处位置至拥堵源AGV所处的位置之间的道路的第三宽度、拥堵源AGV的尺寸和第三AGV的尺寸，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV的尺寸和第三AGV并行通过；
在第三AGV所处位置至拥堵源AGV所处的位置之间的道路，不支持拥堵源AGV的尺寸和第三AGV并行通过时，将第三AGV作为与拥堵源AGV有阻塞关系的关联AGV。
可选的，其特征在于，拥堵源AGV的尺寸包括：拥堵源AGV本体的尺寸、拥堵源AGV装载的物体的尺寸，第三AGV的尺寸包括：第三AGV本体的尺寸、第三AGV装载的物体的尺寸；
根据第三AGV所处位置至拥堵源AGV所处的位置之间的道路的第三宽度、拥堵源AGV的尺寸和第三AGV的尺寸，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV的尺寸和第三AGV并行通过，包括：
按照拥堵源AGV本体、拥堵源AGV装载的物体、第三AGV本体和第三AGV装载的物体从低到高的顺序，分别以拥堵源AGV本体、拥堵源AGV装载的物体、第三AGV本体和第三AGV装载的物体的最高点所在的水平面，确定高度不同的多个第一分层面；
根据各个第一分层面的高度，对拥堵源AGV的竖直尺寸和第三AGV的竖直尺寸进行分层，得到拥堵源AGV本体在每一分层的水平尺寸、拥堵源AGV装载的物体在每一分层的水平尺寸、第三AGV本体在每一分层的水平尺寸和第三AGV装载的物体在每一分层的水平尺寸；
针对每一分层，根据拥堵源AGV本体在该分层的水平尺寸、拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三AGV装载的物体在该分层的水平尺寸以及第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过。
可选的，针对每一分层，根据拥堵源AGV本体在该分层的水平尺寸、拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三AGV装载的物体在该分层的水平尺寸以及第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过，包括：
针对每一分层，基于拥堵源AGV本体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV本体在该分层的水平尺寸、第三AGV装载的物体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV装载的物体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过。
可选的，在判断拥堵拓扑图中是否存在第二AGV之后，该AGV路径规划方法还包括：
如果否，将相邻路径点保存为目标AGV的可达路径点。
可选的，第二AGV的尺寸包括：第二AGV本体的尺寸和第二AGV装载的物体的尺寸，目标AGV的尺寸包括：目标AGV本体的尺寸和目标AGV装载的物体的尺寸；
根据第二AGV的尺寸、目标AGV的尺寸和第二重合区域所在道路的第二宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过，包括：
按照第二AGV本体、第二AGV装载的物体、目标AGV本体和目标AGV装载的物体从低到高的顺序，分别以第二AGV本体、第二AGV装载的物体、目标AGV本体和目标AGV装载的物体最高点所在的水平面，确定高度不同的多个第二分层面；
根据各个第二分层面的高度，对第二AGV的竖直尺寸和目标AGV的竖直尺寸进行分层，得到第二AGV本体在每一分层的水平尺寸、第二AGV装载的物体在每一分层的水平尺寸、目标AGV本体在每一分层的水平尺寸和目标AGV装载的物体在每一分层的水平尺寸；
针对每一分层，第二AGV本体在该分层的水平尺寸、第二AGV装载的物体在该分层的水平尺寸、目标AGV本体在该分层的水平尺寸、目标AGV装载的物体在该分层的水平尺寸以及第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过。
可选的，针对每一分层，根据第二AGV在该分层的水平尺寸、目标AGV在该分层的水平尺寸以及第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过，包括：
针对每一分层，基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV本体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV本体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过。
可选的，该AGV路径规划方法还包括：
如果第二重合区域不支持目标AGV与第二AGV并行通过；
将计算得到的目标AGV通过待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段，第二固定时长大于或等于第二AGV从第二AGV所在位置到达对应的父节点AGV所在位置的时长；
针对第二待定时间段和拥堵拓扑图，返回执行判断拥堵拓扑图中是否存在第二AGV的步骤。
可选的，当第二AGV对应的父节点包括多个子节点时，在将计算得到的目标AGV通过待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段之前，该AGV路径规划方法还包括：
针对第二AGV对应的父节点的每个子节点，获取该子节点对应的AGV从其所处位置到达其父节点对应的AGV所处位置的到达时长；
将第二AGV对应的父节点的所有子节点对应的AGV的到达时长中的最大到达时长，作为第二固定时长，并执行将计算得到的目标AGV通过待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段的步骤。
第二方面，本发明实施例还提供了一种AGV路径规划装置，该装置包括：
相邻路径点查找模块，用于将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，并触发第一待定时间段计算模块；
第一待定时间段计算模块，用于将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；
第一AGV判断模块，用于根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；如果是，触发第一并行通过判断模块；
第一并行通过判断模块，用于则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；如果支持，触发路径点保存模块；
路径点保存模块，用于将相邻路径点保存为目标AGV的可达路径点。
可选的，该AGV路径规划装置，还包括：
第二相邻路径点查找模块，用于如果第一重合区域不支持第一AGV和目标AGV并行通过，则查找与当前路径点相邻的新的相邻路径点，并触发第一待定时间段计算模块。
可选的，第一待定时间段计算模块，具体用于：
计算目标AGV到达当前路径点的第一预估时刻和到达相邻路径点的第二预估时刻，将第一预估时刻至第二预估时刻的时间段确定为目标AGV通过待定子路径的待定时间段；
可选的，该AGV路径规划装置，还包括：
第二预估时刻保存模块，用于保存第二预估时刻。
可选的，该AGV路径规划装置，还包括：
目标路径点判断模块，用于判断相邻路径点是否为目标AGV的目标路径点，如果是，触发目标路径输出模块，如果否，则触发第三相邻路径点查找模块；
触发目标路径输出模块，用于根据已保存的目标AGV的可达路径点，输出目标AGV从起始路径点到目标路径点的路径；
第三相邻路径点查找模块，用于将相邻路径点作为新的当前路径点，查找与新的当前路径点相邻的路径点，并触发第一待定时间段计算模块。
可选的，第一AGV判断模块，还用于在判断不存在第一AGV时，触发路径点保存模块。
可选的，第一并行通过判断模块，还用于：如果第一重合区域不支持第一AGV和目标AGV并行通过，则触发第二待定时间段计算模块。
第二待定时间段计算模块，用于将计算得到的目标AGV通过待定子路径的待定时间段向后推延第一固定时长，得到第一待定时间段，第一固定时长大于或等于目标AGV以预设行驶速度通过待定子路径所花费的时长；并针对第一待定时间段和已保存的其他AGV的路径信息，触发第一AGV判断模块，判断是否存在第一AGV。
可选的，该AGV路径规划装置，还包括：
当前拥堵判断模块，用于判断当前是否发生拥堵，如果否，触发第一AGV判断模块；如果是，触发拥堵拓扑图获取模块；
拥堵拓扑图获取模块，用于获取拥堵拓扑图，其中，拥堵拓扑图为：根据引起拥堵的拥堵源AGV和各个AGV之间的阻塞关系建立的具有多级子节点的拓扑图；其中，引起拥堵的拥堵源AGV为根节点，每个子节点对应的AGV的路径中包含其父节点对应的AGV的位置；拥堵拓扑图中，还包括：各个子节点到达父节点的位置的时长；
路径信息获取模块，用于获取拥堵拓扑图中各个节点对应的AGV的路径信息；
第二AGV判断模块，用于根据待定时间段、拥堵拓扑图和各个节点对应的AGV的路径信息，判断拥堵拓扑图中是否存在第二AGV；其中，第二AGV满足以下条件：第二AGV从其所处位置到达其父节点对应的AGV所处位置之间的路径与待定子路径存在第二重合区域，且，第二AGV通过第二重合区域到达其父节点对应的AGV所处位置的累加时间段与待定时间段存在交集；如果是，触发第二并行通过判断模块；
第二并行通过判断模块，用于根据第二AGV的尺寸、目标AGV的尺寸和第二重合区域所在道路的第二宽度，判断第二重合区域是否支持第二AGV和目标AGV并行通过；如果支持，触发路径点保存模块。
可选的，该AGV路径规划装置，还包括：
AGV位置获取模块，用于获得引起拥堵的拥堵源AGV及其位置作为根节点；
关联AGV位置获取模块，用于获得拥堵源AGV的关联AGV及其位置作为根节点的子节点；其中，拥堵源AGV的关联AGV满足以下条件：与拥堵源AGV有阻塞关系，且拥堵源AGV的关联AGV从其所在位置至拥堵源AGV的位置之间的子路径中，不包含其他与拥堵源AGV有阻塞关系的AGV，拥堵源AGV的关联AGV的路径中包含拥堵源AGV的位置；
节点关系建立模块，用于对各个子节点，获得与该子节点有阻塞关系的各个关联AGV及其位置作为下一级子节点；对下一级子节点执行本步骤，直到下一级子节点没有有阻塞关系的关联AGV；各个子节点的路径中包含其父节点的位置；
到达时长计算模块，用于计算各个子节点对应的AGV从其所处位置到达父节点对应的AGV所处位置的到达时长，并将各个子节点对应的到达时长添加至对应的各个子节点。
可选的，该AGV路径规划装置，还包括：
AGV尺寸获取模块，用于获取拥堵源AGV的尺寸和行驶路径包含拥堵源AGV所处位置的第三AGV的尺寸；
第三并行通过判断模块，用于根据第三AGV所处位置至拥堵源AGV所处的位置之间的道路的第三宽度、拥堵源AGV的尺寸和第三AGV的尺寸，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV的尺寸和第三AGV并行通过；
在第三AGV所处位置至拥堵源AGV所处的位置之间的道路，不支持拥堵源AGV的尺寸和第三AGV并行通过时，触发关联AGV确定模块；
触发关联AGV确定模块，用于将第三AGV作为与拥堵源AGV有阻塞关系的关联AGV。
可选的，拥堵源AGV的尺寸包括：拥堵源AGV本体的尺寸、拥堵源AGV装载的物体的尺寸，第三AGV的尺寸包括：第三AGV本体的尺寸、第三AGV装载的物体的尺寸；
第三并行通过判断模块，包括：
第一分层面确定子模块，用于按照拥堵源AGV本体、拥堵源AGV装载的物体、第三AGV本体和第三AGV装载的物体从低到高的顺序，分别以拥堵源AGV本体、拥堵源AGV装载的物体、第三AGV本体和第三AGV装载的物体的最高点所在的水平面，确定高度不同的多个第一分层面；
第一分层子模块，用于根据各个第一分层面的高度，对拥堵源AGV的竖直尺寸和第三AGV的竖直尺寸进行分层，得到拥堵源AGV本体在每一分层的水平尺寸、拥堵源AGV装载的物体在每一分层的水平尺寸、第三AGV本体在每一分层的水平尺寸和第三AGV装载的物体在每一分层的水平尺寸；
第三并行通过判断子模块，用于针对每一分层，根据拥堵源AGV本体在该分层的水平尺寸、拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三AGV装载的物体在该分层的水平尺寸以及第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过。
可选的，第三并行通过判断子模块，具体用于：
针对每一分层，基于拥堵源AGV本体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV本体在该分层的水平尺寸、第三AGV装载的物体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV装载的物体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过。
可选的，第二AGV判断模块，还用于在判断拥堵拓扑图中不存在第二AGV时，触发路径点保存模块。
可选的，第二AGV的尺寸包括：第二AGV本体的尺寸和第二AGV装载的物体的尺寸，目标AGV的尺寸包括：目标AGV本体的尺寸和目标AGV装载的物体的尺寸；
第二并行通过判断模块，包括：
第二分层面确定子模块，用于按照第二AGV本体、第二AGV装载的物体、目标AGV本体和目标AGV装载的物体从低到高的顺序，分别以第二AGV本体、第二AGV装载的物体、目标AGV本体和目标AGV装载的物体最高点所在的水平面，确定高度不同的多个第二分层面；
第二分层子模块，用于根据各个第二分层面的高度，对第二AGV的竖直尺寸和目标AGV的竖直尺寸进行分层，得到第二AGV本体在每一分层的水平尺寸、第二AGV装载的物体在每一分层的水平尺寸、目标AGV本体在每一分层的水平尺寸和目标AGV装载的物体在每一分层的水平尺寸；
第二并行通过判断子模块，用于针对每一分层，第二AGV本体在该分层的水平尺寸、第二AGV装载的物体在该分层的水平尺寸、目标AGV本体在该分层的水平尺寸、目标AGV装载的物体在该分层的水平尺寸以及第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过。
可选的，第二并行通过判断子模块，具体用于：
针对每一分层，基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV本体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV本体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过。
第二并行通过判断模块，还用于：如果第二重合区域不支持目标AGV与第二AGV并行通过，则触发第三待定时间段计算模块。
第三待定时间段计算模块，用于将计算得到的目标AGV通过待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段，第二固定时长大于或等于第二AGV从第二AGV所在位置到达对应的父节点AGV所在位置的时长；并针对第二待定时间段和拥堵拓扑图，触发第二AGV判断模块，判断拥堵拓扑图中是否存在第二AGV。
可选的，当第二AGV对应的父节点包括多个子节点时，该AGV路径规划装置，还包括：
到达时长获取模块，用于针对第二AGV对应的父节点的每个子节点，获取该子节点对应的AGV从其所处位置到达其父节点对应的AGV所处位置的到达时长；
到达时长更新模块，用于将第二AGV对应的父节点的所有子节点对应的AGV的到达时长中的最大到达时长，作为第二固定时长，并触发第三待定时间段计算模块。
第三方面，本发明实施例还提供了一种电子设备，包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过通信总线完成相互间的通信；
存储器，用于存放计算机程序；
处理器，用于执行存储器上所存放的程序时，实现上述第一方面提供的一种AGV路径规划方法的步骤。
第四方面，本发明实施例还提供了一种计算机可读存储介质，计算机可读存储介质内存储有计算机程序，计算机程序被处理器执行时实现上述第一方面提供的一种AGV路径规划方法的步骤。
本发明实施例提供的一种AGV路径规划方法、装置、电子设备及存储介质，在为目标AGV规划路径时，可以将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，然后针对当前路径点和查找到的相邻路径点执行以下处理：将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；如果是，则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；如果支持，将相邻路径点保存为目标AGV的可达路径点。这样，可以使得在路径规划时，通过AGV的尺寸信息以及道路的宽度信息来确定该道路是否会发生拥堵，可以避免对道路进行“加锁”，从而提高了道路的利用率，进而提高了AGV系统的工作效率。当然，实施本发明的任一产品或方法并不一定需要同时达到以上所述的所有优点。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1为本发明实施例的一种AGV路径规划方法第一种实施方式的流程图；
图2为本发明实施例的一种AGV电子地图的示意图；
图3为本发明实施例的一种AGV路径规划方法第二种实施方式的流程图；
图4为本发明实施例的一种AGV路径规划方法第三种实施方式的流程图；
图5为本发明实施例的一种AGV路径规划方法第四种实施方式的流程图；
图6a为本发明实施例的一种AGV路径规划方法中的AGV位置示意图；
图6b为本发明实施例的一种AGV路径规划方法中的拥堵拓扑图示意图；
图7为本发明实施例的一种AGV路径规划方法中父节点AGV与子节点AGV的投影示意图；
图8为本发明实施例的一种AGV路径规划方法第五种实施方式的流程图；
图9为本发明实施例的一种AGV路径规划装置的结构示意图；
图10为本发明实施例的一种电子设备的结构示意图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
为了解决现有技术存在的问题，本发明实施例提供了一种AGV路径规划方法、装置、电子设备及存储介质，以提高道路的利用率，进而提高AGV系统的工作效率。
下面，首先对本发明实施例的一种AGV路径规划方法进行介绍，如图1所示，为本发明实施例的一种AGV路径规划方法第一种实施方式的流程图，该方法可以应用于AGV系统中的地面控制设备，或者，也可以应用于AGV系统中的AGV。以下以应用于地面控制设备为例进行说明，参见图1，该方法可以包括：
S110，将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点。
在一些示例中，该目标AGV为AGV系统中接收到任务，等待规划路径的AGV。地面控制设备可以向该目标AGV发送任务消息，该目标AGV在接收到任务消息后，可以从该任务消息中获取到任务，通常情况下，该任务消息中还可以包括任务的起始位置和终止位置，例如，该任务可以是通知该目标AGV将待运输的物品从一个位置运输到另一个位置。
在一些示例中，当该目标AGV处于该任务的起始位置时，则可以将该任务的起始位置作为自身的起始路径点，将该任务的终止位置作为自身的目标路径点。
该地面控制设备在得到该目标AGV的起始路径点和目标路径点后，可以根据目标AGV的起始路径点和目标路径点，采用预设路径规划算法，为该目标AGV规划路径。
在又一些示例中，当该目标AGV不在该任务的起始位置时，则可以将该目标AGV自身所处的位置作为起始路径点，将该任务的起始位置作为自身的目标路径点，为该目标AGV规划路径。以使得该目标AGV从自身所处的位置移动至该任务的起始位置获取待运输的物品。
示例性的，上述的地面控制设备可以采用多种路径规划算法为该目标AGV规划路径，例如，采用A*路径规划算法，或者采用Dijkstra最短路径规划算法。则该预设路径规划算法可以是该A*路径规划算法或者Dijkstra最短路径规划算法等。
上述的地面控制设备在采用预设路径规划算法为该目标AGV规划路径时，可以从该目标AGV的起始路径点开始依次寻找路径点，直至寻找到的路径点为该目标AGV的目标路径点为止。
该地面控制设备在确定出一个路径点后，可以寻找该路径点的下一路径点，并采用本发明实施例的路径规划方法来确定下一路径点是否可以作为该目标AGV的可达路径点。
例如，该地面控制设备可以将起始路径点作为当前路径点，采用该预设路径规划算法，查找与该当前路径点相邻的路径点为下一路径点。
示例性的，如图2所示，假设该目标AGV的起始路径点为图2所示的点A，则该地面控制设备可以采用预设路径规划算法，查找出与当前路径点点A相邻的路径点点B。
上述的地面控制设备在确定出当前路径点和当前路径点相邻的相邻路径点后，可以针对当前路径点和查找到的相邻路径点执行以下处理：
S120，将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段。
在一些示例中，上述的地面控制设备在确定当前路径点和该当前路径点的相邻路径点后，可以将该当前路径点与该当前路径点的相邻路径点之间的路径确定为待定子路径，然后可以确定该目标AGV到达当前路径点的第一预估时刻，和到达该相邻路径点的第二预估时刻，并将第一预估时刻至第二预估时刻的时间段作为目标AGV通过待定子路径的待定时间段。
在一些示例中，当该当前路径点为该目标AGV的起始路径点时，该第一预估时刻为该目标AGV处于该起始路径点时的时刻。
当该当前路径点不是该目标AGV的起始路径点，是起始路径点和目标路径点之间的任一中间路径点时，例如，是如图2所示的点A(起始路径点)与点J(目标路径点)之间的点D时，则该第一预估时刻为目标AGV从自身的起始路径点点A到达点D花费的时长和该目标AGV处于起始路径点点A时的时刻的总和。
在一些示例中，上述的地面控制设备可以为目标AGV设置一个行驶速度，然后依据该目标AGV的起始路径点与当前路径点的距离和该行驶速度，来计算该目标AGV从起始路径点到达点D花费的时长。
同样的，该第二预估时刻为该目标AGV从该当前路径点到达该当前路径点的相邻路径点花费的时长与该第一预估时刻的总和，该地面控制设备可以依据该当前路径点与该当前路径点的相邻路径点之间的距离和该行驶速度来确定该目标AGV从该当前路径点到达该当前路径点的相邻路径点花费的时长。
上述的地面控制设备在得到目标AGV通过待定子路径的待定时间段后，可以执行步骤S130。
在一些示例中，该地面控制设备还可以对该第二预估时刻进行保存，以便在通过后续步骤将该当前路径点的相邻路径点保存为可达路径点，将该相邻路径点作为新的当前路径点时，将该第二预估时刻作为该新的当前路径点对应的第一预估时刻。
S130，根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV。如果是，则执行步骤S140。
其中，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；其他AGV为AGV系统的所有AGV中，除目标AGV外的AGV。
在一些示例中，该路径信息可以是该其他AGV的行驶路径以及行驶经过该行驶路径上任一位置的时间。
在一些示例中，上述的地面控制设备中可以保存有AGV系统中所有AGV的路径信息，因此，该地面控制设备可以得到该所有AGV中，除目标AGV外的其他AGV的路径信息。
上述的地面控制设备可以根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV。
在一些示例中，上述的地面控制设备可以依据该其他AGV的路径信息，确定该其他AGV中各个AGV在上述的待定时间段内的行驶路径。然后可以判断其他各个AGV在该待定时间段内的行驶路段是否与待定子路径存在第一重合区域。
在一些示例中，上述的地面控制设备可以依据每个AGV不同时间信息对应的不同的位置信息，来确定该其他AGV中的各个AGV在上述待定时间段内的行驶路段。如果判断存在第一AGV，则执行步骤S140。
在一些示例中，上述的地面控制设备还可以依据该其他AGV的路径信息，确定该其他AGV中各个AGV的路径信息中，是否存在与该待定子路经存在第一重合区域的路径，如果存在，根据该其他AGV的路径信息，判断该其他AGV中与该待定子路经存在第一重合区域的AGV通过该第一重合区域的时间是否与该待定时间段存在重合区域，如果是，则判断存在第一AGV。执行步骤S140。
S140，根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过。
在一些示例中，现有技术中的地面控制设备规划的AGV路径中，可能存在两辆AGV的路径具有重合区域，而由于现有技术中的地面控制设备没有记录该两辆AGV的尺寸信息，使得该两辆AGV在该重合区域发生拥堵，还可能存在两辆AGV可以在重合区域可以同时通行，但该地面控制设备为了防止在该重合区域发生拥堵，而直接为其中一辆AGV重新规划路径。从而出现对AGV路径的不合理规划。
对此，上述的地面控制设备在判断存在第一AGV时，为了确定该第一AGV与目标AGV实际是否发生碰撞，可以依据该第一AGV的尺寸、目标AGV的尺寸以及第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过。
在一些示例中，当该第一AGV和目标AGV上都没有装载物体或者，各自装载的物体的宽度都小于对应的AGV的宽度时，可以将该第一AGV的宽度与该目标AGV的宽度相加，与第一重合区域所在道路的第一宽度对比，来判断第一重合区域是否支持第一AGV和目标AGV并行通过。
当第一AGV的宽度与该目标AGV的宽度的总值大于该道路的宽度时，则说明第一重合区域不支持第一AGV和目标AGV并行通过，反之，则说明第一重合区域支持第一AGV和目标AGV并行通过，该目标AGV与第一AGV不会发生碰撞。
在一些示例中，当该第一AGV上装载的物体的宽度大于该第一AGV的宽度，目标AGV上装载的物体的宽度大于该目标AGV的宽度时，则可以将该第一AGV上装载的物体的宽度与目标AGV上装载的物体的宽度相加，与第一重合区域所在道路的第一宽度对比，来判断第一重合区域是否支持第一AGV和目标AGV并行通过。
在一些示例中，该第一AGV在行驶过程中，可能会行驶在道路中间，对此，当预测目标AGV与第一AGV不会发生碰撞时，上述的地面控制设备可以向该第一AGV发送通知信息，以使得该第一AGV在行驶到该第一重合区域时，调整自身在道路中的位置，以便该第一重合区域所在道路可以同时容纳该第一AGV与目标AGV通过。
如果判断第一重合区域支持第一AGV和目标AGV并行通过，则执行步骤S150。
S150，将相邻路径点保存为目标AGV的可达路径点。
当上述的地面控制设备在判断第一重合区域支持第一AGV和目标AGV并行通过时，则说明该第一重合区域所在道路的宽度可以同时容纳该目标AGV与该第一AGV并排通行，该第一AGV的行驶不会影响目标AGV的行驶，进而可以说明该待定子路径与第一AGV的路径实际并不冲突，则可以将相邻路径点保存为目标AGV的可达路径点。以便依据该可达路径点为该目标AGV规划路径。
本发明实施例的一种AGV路径规划方法，在为目标AGV规划路径时，可以将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，然后针对当前路径点和查找到的相邻路径点执行以下处理：将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；如果是，则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；如果支持，将相邻路径点保存为目标AGV的可达路径点。这样，可以使得在路径规划时，通过AGV的尺寸信息以及道路的宽度信息来确定该道路是否会发生拥堵，可以避免对道路进行“加锁”，从而提高了道路的利用率，进而提高了AGV系统的工作效率。
在图1所示的AGV路径规划方法的基础上，本发明实施例还提供了一种AGV路径规划方法，如图3所示，为本发明实施例的一种路径规划方法第二种实施方式的流程图，该方法还可以包括：
如果在步骤S130中判断不存在第一AGV时，可以执行步骤S150。
在一些示例中，如果不存在第一AGV，则可以说明该其他AGV中的各个AGV的行驶路径与该第一路径存在第一重合区域不存在重合区域。则可以直接将该相邻路径点保存为该目标AGV的可达路径点。
在一些示例中，该方法还可以包括：
如果在步骤S140中判断第一重合区域不支持第一AGV和目标AGV并行通过，则执行步骤S160。
S160，查找与当前路径点相邻的新的相邻路径点。并针对当前路径点和新的相邻路径点返回执行步骤S120。
在一些示例中，如果判断第一重合区域不支持第一AGV和目标AGV并行通过，则说明该第一AGV与目标AGV在该第一重合区域会发生碰撞，为了避免发生碰撞，上述的地面控制设备可以重新为该目标AGV查找与该当前路径点相邻的新的相邻路径点，然后将该当前路径点与该找到的新的相邻路径点之间的路径确定为待定子路径，并计算该目标AGV通过该待定子路径的待定时间段。
在一些示例中，该目标AGV的起始路径点与目标路径点之间的路径点可以有一个也可以有多个，为了确定出该目标AGV的起始路径点与目标路径点之间的路径，上述的地面控制设备在执行上述步骤150将相邻路径点保存为目标AGV的可达路径点后，可以执行步骤S170，以确定该相邻路径点是否为该目标路径点，进而确定是否为该目标AGV寻找到所有路径点。
S170，判断相邻路径点是否为目标AGV的目标路径点。
通过判断该相邻路径点是否为目标路径点，上述的地面控制设备可以确定是否为该目标AGV寻找到所有路径点。
如果该相邻路径点不是目标路径点，说明还没有为该目标AGV寻找所有路径点，则可以执行步骤S180。如果该相邻路径点为目标路径点，说明完成了为该目标AGV寻找所有路径点，则可以执行步骤S190。
S180，将相邻路径点作为新的当前路径点，查找与新的当前路径点相邻的路径点，针对新的当前路径点和与新的当前路径点相邻的路径点返回执行步骤S120。
上述的地面控制设备在确定该相邻路径点不是目标路径点时，则可以将该相邻路径点作为当前路径点，并返回重新执行步骤S120。
通过将该相邻路径点作为当前路径点，查找与新的当前路径点相邻的路径点，上述的地面控制设备可以继续采用本发明实施例的一种AGV路径规划方法为目标AGV规划路径，直至完成为该目标AGV寻找所有路径点，然后依据为该目标AGV寻找的所有路径点，为该目标AGV规划完整的行驶路径。
S190，根据已保存的目标AGV的可达路径点，输出目标AGV从起始路径点到目标路径点的路径。
上述的地面控制设备在确定该相邻路径点是目标路径点时，则说明该地面控制设备为该目标AGV寻找到了所有路径点。则可以根据已保存的目标AGV的可达路径点，输出目标AGV从起始路径点到目标路径点的路径。
例如，假设该目标AGV的起始路径点为图2所示的点A，目标路径点为图2所示的点J，通过本发明实施例的一种路径规划算法确定出的可达路径点分别为点B、点C、点D、点E、点G、点H、点I，点A与点B之间的路径为路径AB，点B与点C之间的路径为路径BC，点C与点D之间的路径为路径BC，点D与点E之间的路径为路径DE，点E与点G之间的路径为路径EG，点G与点H之间的路径为路径GH，点H与点I之间的路径为路径HI，点I与点J之间的路径为路径IJ，则上述的地面控制设备可以基于路径AB、路径BC、路径DE、路径EG、路径GH、路径HI、路径IJ，确定该目标AGV的行驶路径为路径：A—B—C—D—E—G—H—I—J。
在图1所示的AGV路径规划方法的基础上，上述的地面控制设备如果判断第一重合区域不支持第一AGV和目标AGV并行通过，本发明实施例还提供了一种可能的实现方式，如图4所示，为本发明实施例的一种路径规划方法第三种实施方式的流程图，在通过步骤S130判断第一重合区域不支持第一AGV和目标AGV并行通过之后，该方法还可以包括：
S200，将计算得到的目标AGV通过待定子路径的待定时间段向后推延第一固定时长，得到第一待定时间段，针对第一待定时间段和已保存的其他AGV的路径信息，返回执行步骤S130，判断是否存在第一AGV。
其中，第一固定时长大于或等于目标AGV以预设行驶速度通过待定子路径所花费的时长。
如果预测目标AGV与第一AGV会发生碰撞，上述的地面控制设备可以调整该目标AGV的行驶时间，以避免与该第一AGV发生碰撞。
在一些示例中，上述的地面控制设备可以将计算得到的目标AGV通过待定子路径的待定时间段向后推延第一固定时长，得到第一待定时间段，然后针对第一待定时间段和已保存的其他AGV的路径信息，返回执行步骤S130，判断是否存在第一AGV。
在一些示例中，上述的地面控制设备可以将该第二预估时刻作为该目标AGV在起始路径点时的时刻，然后，可以基于该目标AGV的行驶速度和待定子路径的长度，计算该目标AGV经过待定子路径所花费的时长。进而可以将该第二预估时刻和经过待定子路径所花费的时长之和，与第二预估时刻之间的时间段作为第一待定时间段。这样，可以调整该目标AGV在当前路径点至第一待定路径点之间的路径上行驶的时间。以期望避免与第一AGV发生碰撞。
上述的地面控制设备在调整该待定子路径上的行驶时间段后，为了确定调整的行驶时间是否合适，是否会与其他AGV发生碰撞。可以执行步骤S130。
在本发明实施例的一个实施例中，上述的地面控制设备在为该目标AGV规划路径时，该AGV系统中可能已发生拥堵，也可能未发生拥堵。
当该AGV系统中已发生拥堵时，在图1所示的一种AGV路径规划方法的基础上，本发明实施例还提供了一种可能的实现方式，如图5所示，为本发明实施例的一种AGV路径规划方法第四种实施方式的流程图，在步骤S120，将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段之后，本发明实施例的一种AGV路径规划方法，还可以包括：
S210，判断当前是否发生拥堵。
在一些示例中，上述的地面控制设备在判断当前是否发生拥堵时，可以判断其他AGV中的任一个AGV至当前时刻，在同一位置的停留时间是否超过停留时间阈值，如果超过，则可以判断该在同一位置的停留时间超过停留时间阈值的AGV所处的位置在当前时刻发生拥堵。
在一些示例中，该当前时刻为该目标AGV在起始路径点时的时刻。
在本发明实施例的一个实施例中，上述的地面控制设备还可以接收其他AGV发送的故障信息，当该地面控制设备接收到一个AGV发送的故障信息时，上述的地面控制设备可以依据该故障信息判断该发送故障信息的AGV所处的位置是否发生拥堵。
在本发明实施例的又一个实施例中，当该其他AGV中的任一个AGV在同一个位置的停留时间超过停留时间阈值时，该在同一个位置的停留时间超过停留时间阈值的AGV可以向上述的地面控制设备发送拥堵报告信息，该拥堵报告信息中可以包含有该AGV当前的位置信息。该地面控制设备可以依据该拥堵报告来判断该发送拥堵报告的AGV所处的位置是否发生拥堵。
如果没有发生拥堵，则执行步骤S130；如果发生拥堵，则执行步骤S220。
S220，获取拥堵拓扑图。
其中，拥堵拓扑图为：根据引起拥堵的拥堵源AGV和各个AGV之间的阻塞关系建立的具有多级子节点的拓扑图；其中，引起拥堵的拥堵源AGV为根节点，每个子节点对应的AGV的路径中包含其父节点对应的AGV的位置；拥堵拓扑图中，还包括：各个子节点到达父节点的位置的时长。
在一些示例中，该拥堵拓扑图可以通过以下步骤建立：
步骤A，获得引起拥堵的拥堵源AGV及其位置作为根节点；
在一些示例中，在当前时刻，当该其他AGV中存在速度为0的AGV，则该速度为0的AGV可能是引起拥堵的AGV，上述的地面控制设备可以判断在该速度为0的AGV的行驶路径上，是否还存在速度为0的AGV，如果不存在，则说明该速度信息为0的AGV为引起拥堵的第二AGV，如果存在，则继续判断该行驶路径上，是否还存在其他速度为0的AGV。最终可以从该其他AGV中，确定出引起拥堵的AGV，将该引起拥堵的AGV确定为拥堵源AGV，进而可以确定出该拥堵源AGV所处的位置。
上述的地面控制设备在获取到拥堵源AGV及其所在位置后，可以将该拥堵源AGV及其所在位置作为根节点。
步骤B，获得拥堵源AGV的关联AGV及其位置作为根节点的子节点。
其中，拥堵源AGV的关联AGV满足以下条件：与拥堵源AGV有阻塞关系，且拥堵源AGV的关联AGV从其所在位置至拥堵源AGV的位置之间的子路径中，不包含其他与拥堵源AGV有阻塞关系的AGV，拥堵源AGV的关联AGV的路径中包含拥堵源AGV的位置。
在一些示例中，上述的地面控制设备在确定拥堵源AGV后，可以依据行驶路径是否包含该拥堵源AGV的位置，来确定其他AGV中是否存在与该拥堵源AGV有阻塞关系的各个关联AGV，如果存在，可以获取各个关联AGV在当前时刻的位置，并将该各个关联AGV及其在当前时刻的位置作为根节点的子节点。
例如，假设该其他AGV在当前时刻时的位置信息为图6a中的点K、点L、点M、点N、点P、点Q，处于点K的AGV为拥堵源AGV，假设处于点M处的AGV的路径包含处于点L处的AGV的位置，处于点N处的AGV的路径也包含处于点L处的AGV的位置，处于点P的AGV的路径也包含处于点L处的AGV的位置，处于点Q处的AGV的路径包含经过处于点K处的AGV的位置。则上述的地面控制设备可以将位于点L处的AGV及点L的位置、位于点Q处的AGV及点Q的位置确定为根节点K的子节点。
在又一些示例中，行驶路径包含该拥堵源AGV的位置的AGV，在该拥堵源AGV所在的位置可能可以并行通过，也可能不能并行通过，如果可以并行通过，则说明该拥堵源AGV并不会导致该AGV的拥堵，可以不将该AGV作为关联AGV。如果不能并行通过，则说明该拥堵源AGV会导致该AGV的拥堵，可以将该AGV作为关联AGV。
在一些示例中，可以通过以下步骤，来确定与拥堵源AGV有阻塞关系的AGV：
B1，获取拥堵源AGV的尺寸和行驶路径包含拥堵源AGV所处位置的第三AGV的尺寸。
B2，根据第三AGV所处位置至拥堵源AGV所处的位置之间的道路的第三宽度、拥堵源AGV的尺寸和第三AGV的尺寸，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV的尺寸和第三AGV并行通过；
B3，在第三AGV所处位置至拥堵源AGV所处的位置之间的道路，不支持拥堵源AGV的尺寸和第三AGV并行通过时，将第三AGV作为与拥堵源AGV有阻塞关系的关联AGV。
步骤C，对各个子节点，获得与该子节点有阻塞关系的各个关联AGV及其位置作为下一级子节点；对下一级子节点执行本步骤，直到下一级子节点没有有阻塞关系的关联AGV；各个子节点的路径中包含其父节点的位置；
同样的，这里与各个子节点有阻塞关系的关联AGV满足以下条件：与该子节点有阻塞关系，且该子节点的关联AGV从其所在位置至该子节点的位置之间的子路径中，不包含其他与该子节点有阻塞关系的AGV，该子节点的关联AGV的路径中包含该子节点的位置。
在一些示例中，可以参考B1～B3的步骤，来确定与根节点的子节点有阻塞关系的各个关联AGV。
例如，假设位于点M处的AGV、位于点N处的AGV、位于点P处的AGV为与根节点K的子节点L有阻塞关系的各个关联AGV。则可以将位于点M处的AGV及点M的位置、位于点N处的AGV及点N的位置和位于点P处的AGV及点P的位置确定为根节点K的子节点L的子节点。
对于根节点K的子节点L的下一级子节点，可以参考步骤C，来确定该下一级子节点的子节点，直到该下一级子节点没有有阻塞关系的关联AGV。
步骤D，计算各个子节点对应的AGV从其所处位置到达父节点对应的AGV所处位置的到达时长，并将各个子节点对应的到达时长添加至对应的各个子节点。
在一些示例中，当引起拥堵的拥堵源AGV处于拥堵位置时，可能会导致将要经过该拥堵位置的AGV也处于拥堵状态，即，将要经过该拥堵位置的AGV停止在当前时刻时的位置无法前行。例如，假设该拥堵源AGV为图6a中所示的位于点K处的AGV，则点K处拥堵时，可能导致点L处的AGV停止在点L处无法前行，同样的，当L处的AGV停止在点L处时，也可能导致将要经过点L处的AGV停止在点M处和/或点N处和/或点P处。
当L处不拥堵时，点M处的AGV需要到达点L的时间为点M与点L之间的距离与点M处的AGV的行驶速度的商值。
因此，上述的地面控制设备，可以依据子节点对应的AGV在当前时刻时的位置和其父节点对应的AGV在当前时刻时的位置以及该子节点AGV的速度，确定该子节点AGV到达父节点AGV的时长。
上述的地面控制设备在得到子节点AGV到达其父节点AGV的时长后，可以根据根节点，各级子节点、各个子节点对应的到达时长，建立拥堵拓扑图。
例如，以点K处的AGV及点K的位置为根节点K，以点L处的AGV及点L的位置为根节点K的子节点L，以点Q处的AGV和点Q的位置为根节点K的子节点Q，以点M处的AGV及点M的位置为子节点L的子节点M，以点N处的AGV及点N的位置为子节点L的子节点N、以点P处的AGV及点P的位置为子节点L的子节点P，将点L处的AGV到达点K的时长添加至子节点L，将点Q处的AGV到达点K的时长添加至子节点Q，将点M处的AGV到达点L的时长添加至子节点M，将点N处的AGV到达点L的时长添加至子节点N，将点P处的AGV到达点L的时长添加至子节点P，建立拥堵拓扑图，得到的拥堵拓扑图可以是如图6b所示的拥堵拓扑图。
在本发明实施例的一种实施方式中，该其他AGV中可以有多个引起拥堵的拥堵源AGV，则该地面控制设备可以建立多个拥堵拓扑图。
S230，获取拥堵拓扑图中各个节点对应的AGV的路径信息。
上述的地面控制设备在获取到拥堵拓扑图后，为了确定该相邻路径点是否为可达路径点，可以获取该拥堵拓扑图中各个节点对应的AGV的路径信息。
在一些示例中，该地面控制设备中可以保存有已规划好路径的所有AGV的路径信息，因此，可以在获取到拥堵拓扑图后，从本地获取到该拥堵拓扑图中的各个节点对应的AGV的路径信息。
S240，根据待定时间段、拥堵拓扑图和各个节点对应的AGV的路径信息，判断拥堵拓扑图中是否存在第二AGV。如果是，则执行步骤S250，如果不存在，则执行步骤S150。
其中，第二AGV满足以下条件：第二AGV从其所处位置到达其父节点对应的AGV所处位置之间的路径与待定子路径存在第二重合区域，且，第二AGV通过第二重合区域到达其父节点对应的AGV所处位置的累加时间段与待定时间段存在交集。
在一些示例中，该累加时间段为第一累加时刻与第二累加时刻之间的时间段，该第一累加时刻为该第二AGV对应的节点至根节点之间的累加时长与当前时刻之和，该第二累加时刻为该第二AGV对应的节点的父节点至根节点之间的累加时长与当前时刻之和。
例如，假设第二AGV为点M处的AGV，则该第二AGV的累加时间段为：点M处的AGV从点M的位置到达与点L的位置的时长与点L处的AGV从点L的位置到达点K的位置的时长的累加时长，与点K处的AGV位于点K时的当前时刻之和，减去当前时刻的时间段。
例如，假设子节点M从点M处到达其父节点L的时长为TLM，子节点N从点N处到达其父节点L的时长为TLN，子节点P从点P处到达其父节点L的时长为TLP，子节点L从点L处到达根节点K的时长为TLK，则该根节点至子节点M的累加时长为TLK+TLM，该根节点至子节点N的累加时长为TLK+TLN，该根节点至子节点P的累加时长为TLK+TLP，
又假设根节点K对应的AGV在点K处时的当前时刻为t1，则子节点M对应的第二累加时刻为：tM＝t1+TLK+TLM，子节点N对应的第二累加时刻为：tN＝t1+TLK+TLN，子节点N对应的第二累加时刻为：tP＝t1+TLK+TLP。子节点L对应的第一累加时刻为：t1+TLK，
因此，上述的地面控制设备可以将子节点M对应的第二累加时刻tM与第一累加时刻t1+TLK之间的时间段确定为子节点M的累加时间段，将子节点N对应的第二累加时刻tN与第一累加时刻t1+TLK之间的时间段确定为子节点N的累加时间段，将子节点P对应的第二累加时刻tP与第一累加时刻t1+TLK之间的时间段确定为子节点P的累加时间段。
上述的地面控制设备在获取到拥堵拓扑图以及各个节点对应的AGV的路径信息后，可以根据待定时间段、拥堵拓扑图和各个节点对应的AGV的路径信息，判断拥堵拓扑图中是否存在第二AGV。如果是，则执行步骤S250。
S250，根据第二AGV的尺寸、目标AGV的尺寸和第二重合区域所在道路的第二宽度，判断第二重合区域是否支持第二AGV和目标AGV并行通过；如果支持，则执行步骤S150。
在一些示例中，上述的地面控制设备在判断拥堵拓扑图中存在第二AGV时，为了确定该第二AGV与目标AGV实际是否发生碰撞，可以根据第二AGV的尺寸、目标AGV的尺寸和第二重合区域所在道路的第二宽度，判断第二重合区域是否支持第二AGV和目标AGV并行通过。
在一些示例中，当该第二AGV和目标AGV上都没有装载物体或者，各自装载的物体的宽度都小于对应的AGV的宽度时，可以将该第二AGV的宽度与该目标AGV的宽度相加，与第二重合区域对应的道路的宽度对比，来判断第二重合区域是否支持第二AGV和目标AGV并行通过。
当第二AGV的宽度与该目标AGV的宽度的总值大于该道路的宽度时，则判断第二重合区域不支持第二AGV和目标AGV并行通过，说明该目标AGV与第二AGV会发生碰撞，反之，则说明目标AGV与第二AGV不会发生碰撞。
在一些示例中，当该第二AGV上装载的物体的宽度大于该第二AGV的宽度，目标AGV上装载的物体的宽度大于该目标AGV的宽度时，则可以将该第二AGV上装载的物体的宽度与目标AGV上装载的物体的宽度相加，与第二重合区域对应的道路的第二宽度信息对比，来判断第二重合区域是否支持第二AGV和目标AGV并行通过。
在一些示例中，该第二AGV在行驶过程中，可能会行驶在道路中间，对此，当预测目标AGV与第二AGV不会发生碰撞时，上述的路径规划装置可以向该第二AGV发送通知信息，以使得该第二AGV在行驶到该第二重合区域时，调整自身在道路中的位置，以便该第二重合区域对应的道路可以同时容纳该第二AGV与目标AGV并行通过。
如果判断第二重合区域支持第二AGV和目标AGV并行通过，则执行步骤S150。
在本发明实施例的一种可能的实现方式中，在根据第三AGV所处位置至拥堵源AGV所处的位置之间的道路的第三宽度、拥堵源AGV的尺寸和第三AGV的尺寸，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV的尺寸和第三AGV并行通过时，该拥堵源AGV上可能装载有物品，第三AGV上也可能装载有物品，此时，该拥堵源AGV的尺寸包括：拥堵源AGV本体的尺寸、拥堵源AGV装载的物体的尺寸，第三AGV的尺寸包括：第三AGV本体的尺寸、第三AGV装载的物体的尺寸。
对此，上述的地面控制设备可以采用如下方式，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV的尺寸和第三AGV并行通过：
步骤B21，按照拥堵源AGV本体、拥堵源AGV装载的物体、第三AGV本体和第三AGV装载的物体从低到高的顺序，分别以拥堵源AGV本体、拥堵源AGV装载的物体、第三AGV本体和第三AGV装载的物体的最高点所在的水平面，确定高度不同的多个第一分层面。
例如，假设拥堵源AGV本体为框750，第三AGV本体为框760，拥堵源AGV上装载的物体为框710和框720，第三AGV上装载的物体为框730和框740，则上述的地面控制设备可以以框750的最高点s所在的水平面，确定第一分层面S，以框760的最高点t所在的水平面，确定第一分层面T，以框740的最高点p所在的水平面，确定第一分层面P，以框720的最高点k所在的水平面，确定第一分层面K，以框730的最高点l所在的水平面，确定第一分层面L，以框710的最高点g所在的水平面，确定第一分层面G。
步骤B22，根据各个第一分层面的高度，对拥堵源AGV的竖直尺寸和第三AGV的竖直尺寸进行分层，得到拥堵源AGV本体在每一分层的水平尺寸、拥堵源AGV装载的物体在每一分层的水平尺寸、第三AGV本体在每一分层的水平尺寸和第三AGV装载的物体在每一分层的水平尺寸。
上述的地面控制设备在得到高度不同的多个第一分层面后，可以根据各个第一分层面的高度，对拥堵源AGV的竖直尺寸和第三AGV的竖直尺寸进行分层。
例如，假设上述的地面控制设备得到的多个第一分层面为：第一分层面S、第一分层面T、第一分层面P、第一分层面K、第一分层面L、第一分层面G，则可以建立分层OS、分层ST、分层TP、分层PK、分层KL和分层LG。
进而可以以分层OS对框750的竖直尺寸进行分层，以分层OS和分层ST对框760的竖直尺寸进行分层，以分层ST、分层TP和分层PK对框720的竖直尺寸进行分层，以分层TP对框740的竖直尺寸进行分层，以分层PK和分层KL对框730的竖直尺寸进行分层，以分层KL和分层LG对框710的竖直尺寸进行分层。从而可以得到各个框在各个分层的水平尺寸。
步骤B23，针对每一分层，根据拥堵源AGV本体在该分层的水平尺寸、拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三AGV装载的物体在该分层的水平尺寸以及第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过。
在一些示例中，可以通过以下步骤判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过：
针对每一分层，基于拥堵源AGV本体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV本体在该分层的水平尺寸、第三AGV装载的物体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV装载的物体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过。
针对每一分层，可能包括拥堵源AGV本体和第三AGV本体，也可能包括拥堵源AGV本体和第三AGV装载的物体，也可能包括拥堵源AGV装载的物体和第三AGV本体，还可能包括拥堵源AGV装载的物体和第三AGV装载的物体。因此，针对上述的不同情况，可以依据步骤B23中的相应步骤来预测父节点AGV与子节点AGV是否碰撞。
在一些示例中，如果在任一分层，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，不支持拥堵源AGV和第三AGV并行通过，则说明拥堵源AGV与第三AGV会发生碰撞，则该第三AGV所处位置至拥堵源AGV所处的位置之间的道路，不支持拥堵源AGV和第三AGV并行通过。当在所有分层都判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，支持拥堵源AGV和第三AGV并行通过，则可以确定该第三AGV所处位置至拥堵源AGV所处的位置之间的道路，支持拥堵源AGV和第三AGV并行通过。
进一步的，在本发明实施例的一种实施方式中，当该第二AGV上装载的物体的宽度大于该第二AGV的宽度，目标AGV上装载的物体的宽度大于该目标AGV的宽度时，步骤S250，根据第二AGV的尺寸、目标AGV的尺寸和第二重合区域所在道路的第二宽度，判断第二重合区域是否支持第二AGV和目标AGV并行通过，具体可以包括如下步骤：
步骤E，按照第二AGV本体、第二AGV装载的物体、目标AGV本体和目标AGV装载的物体从低到高的顺序，分别以第二AGV本体、第二AGV装载的物体、目标AGV本体和目标AGV装载的物体最高点所在的水平面，确定高度不同的多个第二分层面。
步骤F，根据各个第二分层面的高度，对第二AGV的竖直尺寸和目标AGV的竖直尺寸进行分层，得到第二AGV本体在每一分层的水平尺寸、第二AGV装载的物体在每一分层的水平尺寸、目标AGV本体在每一分层的水平尺寸和目标AGV装载的物体在每一分层的水平尺寸
步骤G，针对每一分层，第二AGV本体在该分层的水平尺寸、第二AGV装载的物体在该分层的水平尺寸、目标AGV本体在该分层的水平尺寸、目标AGV装载的物体在该分层的水平尺寸以及第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过。
在一些示例中，可以通过以下步骤，判断第二重合区域是否支持目标AGV与第二AGV并行通过：
针对每一分层，基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV本体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV本体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过。
需要说明的是，在本发明实施例中，步骤A～步骤C的过程，与步骤B21～步骤B23的过程基本相似，可以参考步骤B21～步骤B23的过程，这里不再赘述。
在一些示例中，如果上述的地面控制设备判断第二重合区域不支持目标AGV与第二AGV并行通过，上述的地面控制设备可以调整该目标AGV的行驶时间，以避免与该第二AGV发生碰撞。具体的，上述的地面控制设备可以将计算得到的目标AGV通过待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段，在一些示例中，该第二固定时长大于或等于第二AGV从第二AGV所在位置到达对应的父节点AGV所在位置的时长。
这样，可以调整该目标AGV在待定子路经上行驶的时间。以期望避免与第二AGV发生碰撞。
上述的地面控制设备在调整该目标AGV在待定子路径上行驶的时间后，为了确定调整的行驶时间是否合适，可以针对第二待定时间段和拥堵拓扑图，执行步骤S240，判断拥堵拓扑图中是否存在第二AGV。
在图5所示的AGV路径规划方法的基础上，本发明实施例还提供了一种可能的实现方式，如图8所示，为本发明实施例的一种路径规划方法第五种实施方式的流程图，当第二AGV对应的父节点包括多个子节点时，在通过步骤S250，根据第二AGV的尺寸、目标AGV的尺寸和第二重合区域所在道路的第二宽度，判断第二重合区域是否支持第二AGV和目标AGV并行通过之后，如果第二重合区域不支持目标AGV与第二AGV并行通过，该方法还可以包括：
S260，针对第二AGV对应的父节点的每个子节点，获取该子节点对应的AGV从其所处位置到达其父节点对应的AGV所处位置的到达时长；
S270，将第二AGV对应的父节点的所有子节点对应的AGV的到达时长中的最大到达时长，作为第二固定时长，
S280，将计算得到的目标AGV通过待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段，并针对第二待定时间段和拥堵拓扑图，返回执行步骤S240，判断拥堵拓扑图中是否存在第二AGV。
例如，假设子节点M对应的AGV不能与目标AGV并行通过第二重合区域所在道路，会与目标AGV发生碰撞，且该子节点M对应的父节点L还具有子节点N和子节点P。则上述的地面控制设备可以获取子节点M对应的AGV从子节点M的位置到达父节点L的位置的时长TLM，获取子节点N对应的AGV从子节点N的位置到达父节点L的位置的时长TLN，获取子节点P对应的AGV从子节点P的位置到达父节点L的位置的时长TLP。
假设时长TLM＜时长TLN＜时长TLP，则上述的地面控制设备可以将子节点P对应的AGV从子节点P的位置到达父节点L的位置的时长TLP作为第二固定时长。然后该地面控制设备可以将计算得到的目标AGV通过待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段，并针对第二待定时间段和拥堵拓扑图，返回执行步骤S240，判断拥堵拓扑图中是否存在第二AGV。
这样，可以调整该目标AGV在第二重合区域上行驶的时间。使得该目标AGV避免与到达该第二AGV对应的子节点的父节点的所有AGV发生碰撞。
上述的地面控制设备在调整该目标AGV在第二重合区域上行驶的时间后，为了确定调整的行驶时间是否合适，是否会与其他AGV发生碰撞。可以执行步骤S240。
相应于上述的方法实施例，本发明实施例还提供了一种AGV路径规划装置，如图9所示，为本发明实施例的一种AGV路径规划装置的结构示意图，该路径规划装置可以应用于AGV系统中的地面控制设备，也可以应用于AGV系统中的AGV；该装置可以包括：
相邻路径点查找模块910，用于将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，并触发第一待定时间段计算模块920；
第一待定时间段计算模块920，用于将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；
第一AGV判断模块930，用于根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；如果是，触发第一并行通过判断模块940；
第一并行通过判断模块940，用于则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；如果支持，触发路径点保存模块950；
路径点保存模块950，用于将相邻路径点保存为目标AGV的可达路径点。
本发明实施例的一种AGV路径规划装置，在为目标AGV规划路径时，可以将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，然后针对当前路径点和查找到的相邻路径点执行以下处理：将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；如果是，则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；如果支持，将相邻路径点保存为目标AGV的可达路径点。这样，可以使得在路径规划时，通过AGV的尺寸信息以及道路的宽度信息来确定该道路是否会发生拥堵，可以避免对道路进行“加锁”，从而提高了道路的利用率，进而提高了AGV系统的工作效率。
可选的，该AGV路径规划装置，还可以包括：
第二相邻路径点查找模块，用于如果第一重合区域不支持第一AGV和目标AGV并行通过，则查找与当前路径点相邻的新的相邻路径点，并触发第一待定时间段计算模块920。
可选的，第一待定时间段计算模块920，具体用于：
计算目标AGV到达当前路径点的第一预估时刻和到达相邻路径点的第二预估时刻，将第一预估时刻至第二预估时刻的时间段确定为目标AGV通过待定子路径的待定时间段；
可选的，该AGV路径规划装置，还包括：
第二预估时刻保存模块，用于保存第二预估时刻。
可选的，该AGV路径规划装置，还包括：
目标路径点判断模块，用于判断相邻路径点是否为目标AGV的目标路径点，如果是，触发目标路径输出模块，如果否，则触发第三相邻路径点查找模块；
触发目标路径输出模块，用于根据已保存的目标AGV的可达路径点，输出目标AGV从起始路径点到目标路径点的路径；
第三相邻路径点查找模块，用于将相邻路径点作为新的当前路径点，查找与新的当前路径点相邻的路径点，并触发第一待定时间段计算模块。
可选的，第一AGV判断模块930，还用于在判断不存在第一AGV时，触发路径点保存模块。
可选的，第一并行通过判断模块940，还用于：如果第一重合区域不支持第一AGV和目标AGV并行通过，则触发第二待定时间段计算模块。
第二待定时间段计算模块，用于将计算得到的目标AGV通过待定子路径的待定时间段向后推延第一固定时长，得到第一待定时间段，第一固定时长大于或等于目标AGV以预设行驶速度通过待定子路径所花费的时长；并针对第一待定时间段和已保存的其他AGV的路径信息，触发第一AGV判断模块930，判断是否存在第一AGV。
可选的，该AGV路径规划装置，还包括：
当前拥堵判断模块，用于判断当前是否发生拥堵，如果否，触发第一AGV判断模块930；如果是，触发拥堵拓扑图获取模块；
拥堵拓扑图获取模块，用于获取拥堵拓扑图，其中，拥堵拓扑图为：根据引起拥堵的拥堵源AGV和各个AGV之间的阻塞关系建立的具有多级子节点的拓扑图；其中，引起拥堵的拥堵源AGV为根节点，每个子节点对应的AGV的路径中包含其父节点对应的AGV的位置；拥堵拓扑图中，还包括：各个子节点到达父节点的位置的时长；
路径信息获取模块，用于获取拥堵拓扑图中各个节点对应的AGV的路径信息；
第二AGV判断模块，用于根据待定时间段、拥堵拓扑图和各个节点对应的AGV的路径信息，判断拥堵拓扑图中是否存在第二AGV；其中，第二AGV满足以下条件：第二AGV从其所处位置到达其父节点对应的AGV所处位置之间的路径与待定子路径存在第二重合区域，且，第二AGV通过第二重合区域到达其父节点对应的AGV所处位置的累加时间段与待定时间段存在交集；如果是，触发第二并行通过判断模块；
第二并行通过判断模块，用于根据第二AGV的尺寸、目标AGV的尺寸和第二重合区域所在道路的第二宽度，判断第二重合区域是否支持第二AGV和目标AGV并行通过；如果支持，触发路径点保存模块950。
可选的，该AGV路径规划装置，还包括：
AGV位置获取模块，用于获得引起拥堵的拥堵源AGV及其位置作为根节点；
关联AGV位置获取模块，用于获得拥堵源AGV的关联AGV及其位置作为根节点的子节点；其中，拥堵源AGV的关联AGV满足以下条件：与拥堵源AGV有阻塞关系，且拥堵源AGV的关联AGV从其所在位置至拥堵源AGV的位置之间的子路径中，不包含其他与拥堵源AGV有阻塞关系的AGV，拥堵源AGV的关联AGV的路径中包含拥堵源AGV的位置；
节点关系建立模块，用于对各个子节点，获得与该子节点有阻塞关系的各个关联AGV及其位置作为下一级子节点；对下一级子节点执行本步骤，直到下一级子节点没有有阻塞关系的关联AGV；各个子节点的路径中包含其父节点的位置；
到达时长计算模块，用于计算各个子节点对应的AGV从其所处位置到达父节点对应的AGV所处位置的到达时长，并将各个子节点对应的到达时长添加至对应的各个子节点。
可选的，该AGV路径规划装置，还包括：
AGV尺寸获取模块，用于获取拥堵源AGV的尺寸和行驶路径包含拥堵源AGV所处位置的第三AGV的尺寸；
第三并行通过判断模块，用于根据第三AGV所处位置至拥堵源AGV所处的位置之间的道路的第三宽度、拥堵源AGV的尺寸和第三AGV的尺寸，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV的尺寸和第三AGV并行通过；
在第三AGV所处位置至拥堵源AGV所处的位置之间的道路，不支持拥堵源AGV的尺寸和第三AGV并行通过时，触发关联AGV确定模块；
触发关联AGV确定模块，用于将第三AGV作为与拥堵源AGV有阻塞关系的关联AGV。
可选的，拥堵源AGV的尺寸包括：拥堵源AGV本体的尺寸、拥堵源AGV装载的物体的尺寸，第三AGV的尺寸包括：第三AGV本体的尺寸、第三AGV装载的物体的尺寸；
第三并行通过判断模块，包括：
第一分层面确定子模块，用于按照拥堵源AGV本体、拥堵源AGV装载的物体、第三AGV本体和第三AGV装载的物体从低到高的顺序，分别以拥堵源AGV本体、拥堵源AGV装载的物体、第三AGV本体和第三AGV装载的物体的最高点所在的水平面，确定高度不同的多个第一分层面；
第一分层子模块，用于根据各个第一分层面的高度，对拥堵源AGV的竖直尺寸和第三AGV的竖直尺寸进行分层，得到拥堵源AGV本体在每一分层的水平尺寸、拥堵源AGV装载的物体在每一分层的水平尺寸、第三AGV本体在每一分层的水平尺寸和第三AGV装载的物体在每一分层的水平尺寸；
第三并行通过判断子模块，用于针对每一分层，根据拥堵源AGV本体在该分层的水平尺寸、拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三AGV装载的物体在该分层的水平尺寸以及第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过。
可选的，第三并行通过判断子模块，具体用于：
针对每一分层，基于拥堵源AGV本体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV本体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV本体在该分层的水平尺寸、第三AGV装载的物体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、第三AGV装载的物体在该分层的水平尺寸和第三宽度，判断第三AGV所处位置至拥堵源AGV所处的位置之间的道路，是否支持拥堵源AGV和第三AGV并行通过。
可选的，第二AGV判断模块，还用于在判断拥堵拓扑图中不存在第二AGV时，触发路径点保存模块950。
可选的，第二AGV的尺寸包括：第二AGV本体的尺寸和第二AGV装载的物体的尺寸，目标AGV的尺寸包括：目标AGV本体的尺寸和目标AGV装载的物体的尺寸；
第二并行通过判断模块，包括：
第二分层面确定子模块，用于按照第二AGV本体、第二AGV装载的物体、目标AGV本体和目标AGV装载的物体从低到高的顺序，分别以第二AGV本体、第二AGV装载的物体、目标AGV本体和目标AGV装载的物体最高点所在的水平面，确定高度不同的多个第二分层面；
第二分层子模块，用于根据各个第二分层面的高度，对第二AGV的竖直尺寸和目标AGV的竖直尺寸进行分层，得到第二AGV本体在每一分层的水平尺寸、第二AGV装载的物体在每一分层的水平尺寸、目标AGV本体在每一分层的水平尺寸和目标AGV装载的物体在每一分层的水平尺寸；
第二并行通过判断子模块，用于针对每一分层，第二AGV本体在该分层的水平尺寸、第二AGV装载的物体在该分层的水平尺寸、目标AGV本体在该分层的水平尺寸、目标AGV装载的物体在该分层的水平尺寸以及第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过。
可选的，第二并行通过判断子模块，具体用于：
针对每一分层，基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV本体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV本体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和第二重合区域所在道路的宽度，判断第二重合区域是否支持目标AGV与第二AGV并行通过。
第二并行通过判断模块，还用于：如果第二重合区域不支持目标AGV与第二AGV并行通过，则触发第三待定时间段计算模块。
第三待定时间段计算模块，用于将计算得到的目标AGV通过待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段，第二固定时长大于或等于第二AGV从第二AGV所在位置到达对应的父节点AGV所在位置的时长；并针对第二待定时间段和拥堵拓扑图，触发第二AGV判断模块，判断拥堵拓扑图中是否存在第二AGV。
可选的，当第二AGV对应的父节点包括多个子节点时，该AGV路径规划装置，还包括：
到达时长获取模块，用于针对第二AGV对应的父节点的每个子节点，获取该子节点对应的AGV从其所处位置到达其父节点对应的AGV所处位置的到达时长；
到达时长更新模块，用于将第二AGV对应的父节点的所有子节点对应的AGV的到达时长中的最大到达时长，作为第二固定时长，并触发第三待定时间段计算模块。
本发明实施例还提供了一种电子设备，如图10所示，包括处理器1010、通信接口1020、存储器1030和通信总线1040，其中，处理器1010，通信接口1020，存储器1030通过通信总线1040完成相互间的通信，
存储器1030，用于存放计算机程序；
处理器1010，用于执行存储器1030上所存放的程序时，实现上述的任一种AGV路径规划方法，例如，可以实现如下步骤：
将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，针对当前路径点和查找到的相邻路径点执行以下处理：
将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；
根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；
如果是，则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；
如果支持，将相邻路径点保存为目标AGV的可达路径点。
本发明实施例提供的一种电子设备，在为目标AGV规划路径时，可以将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，然后针对当前路径点和查找到的相邻路径点执行以下处理：将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；如果是，则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；如果支持，将相邻路径点保存为目标AGV的可达路径点。这样，可以使得在路径规划时，通过AGV的尺寸信息以及道路的宽度信息来确定该道路是否会发生拥堵，可以避免对道路进行“加锁”，从而提高了道路的利用率，进而提高了AGV系统的工作效率。
上述电子设备提到的通信总线可以是外设部件互连标准(Peripheral ComponentInterconnect，PCI)总线或扩展工业标准结构(Extended Industry StandardArchitecture，EISA)总线等。该通信总线可以分为地址总线、数据总线、控制总线等。为便于表示，图中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。
通信接口用于上述电子设备与其他设备之间的通信。
存储器可以包括随机存取存储器(Random Access Memory，RAM)，也可以包括非易失性存储器(Non-Volatile Memory，NVM)，例如至少一个磁盘存储器。可选的，存储器还可以是至少一个位于远离前述处理器的存储装置。
上述的处理器可以是通用处理器，包括中央处理器(Central Processing Unit，CPU)、网络处理器(Network Processor，NP)等；还可以是数字信号处理器(Digital SignalProcessing，DSP)、专用集成电路(Application Specific Integrated Circuit，ASIC)、现场可编程门阵列(Field-Programmable Gate Array，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。
本发明实施例还提供了一种计算机可读存储介质，计算机可读存储介质内存储有计算机程序，计算机程序被处理器执行时实现上述的任一种AGV路径规划方法，例如，可以实现如下步骤：
将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，针对当前路径点和查找到的相邻路径点执行以下处理：
将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；
根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；
如果是，则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；
如果支持，将相邻路径点保存为目标AGV的可达路径点。
本发明实施例提供的一种存储介质，在为目标AGV规划路径时，可以将目标AGV所在的起始路径点作为当前路径点，查找与当前路径点相邻的路径点，然后针对当前路径点和查找到的相邻路径点执行以下处理：将当前路径点与找到的相邻路径点之间的路径确定为待定子路径，计算目标AGV通过待定子路径的待定时间段；根据待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，第一AGV满足以下条件：第一AGV的路径与待定子路径存在第一重合区域，且第一AGV通过第一重合区域的时间段与待定时间段存在交集；如果是，则根据第一AGV的尺寸、目标AGV的尺寸和第一重合区域所在道路的第一宽度，判断第一重合区域是否支持第一AGV和目标AGV并行通过；如果支持，将相邻路径点保存为目标AGV的可达路径点。这样，可以使得在路径规划时，通过AGV的尺寸信息以及道路的宽度信息来确定该道路是否会发生拥堵，可以避免对道路进行“加锁”，从而提高了道路的利用率，进而提高了AGV系统的工作效率。
需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
本说明书中的各个实施例均采用相关的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于装置、电子设备及存储介质实施例而言，由于其基本相似于方法实施例，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。
以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等，均包含在本发明的保护范围内。

Claims (19)

1.一种AGV路径规划方法，其特征在于，所述方法包括：
将目标AGV所在的起始路径点作为当前路径点，查找与所述当前路径点相邻的路径点，针对所述当前路径点和查找到的相邻路径点执行以下处理：
将所述当前路径点与所述找到的相邻路径点之间的路径确定为待定子路径，计算所述目标AGV通过所述待定子路径的待定时间段；
根据所述待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，所述第一AGV满足以下条件：所述第一AGV的路径与所述待定子路径存在第一重合区域，且所述第一AGV通过所述第一重合区域的时间段与所述待定时间段存在交集；
如果是，则根据所述第一AGV的尺寸、所述目标AGV的尺寸和所述第一重合区域所在道路的第一宽度，判断所述第一重合区域是否支持所述第一AGV和所述目标AGV并行通过；
如果支持，将所述相邻路径点保存为所述目标AGV的可达路径点。
2.根据权利要求1所述的方法，其特征在于，在所述判断所述第一重合区域是否支持所述第一AGV和所述目标AGV并行通过之后，所述方法还包括：
如果所述第一重合区域不支持所述第一AGV和所述目标AGV并行通过，则查找与当前路径点相邻的新的相邻路径点，针对所述当前路径点和新的相邻路径点返回执行所述处理。
3.根据权利要求1所述的方法，其特征在于，所述计算所述目标AGV通过所述待定子路径的待定时间段，包括：
计算目标AGV到达所述当前路径点的第一预估时刻和到达所述相邻路径点的第二预估时刻，将所述第一预估时刻至所述第二预估时刻的时间段确定为所述目标AGV通过所述待定子路径的待定时间段；
在将相邻路径点保存为目标AGV的可达路径点之后，所述方法还包括：
保存所述第二预估时刻。
4.根据权利要求2所述的方法，其特征在于，在将所述相邻路径点保存为所述目标AGV的可达路径点之后，所述方法还包括：
判断所述相邻路径点是否为所述目标AGV的目标路径点；
如果是，则根据已保存的所述目标AGV的可达路径点，输出目标AGV从所述起始路径点到所述目标路径点的路径；
如果否，则将所述相邻路径点作为新的当前路径点，查找与所述新的当前路径点相邻的路径点，针对新的当前路径点和与所述新的当前路径点相邻的路径点返回执行所述处理。
5.根据权利要求2所述的方法，其特征在于，在所述判断是否存在第一AGV之后，所述方法还包括：
如果否，将所述相邻路径点保存为所述目标AGV的可达路径点。
6.根据权利要求4所述的方法，其特征在于，所述方法还包括：
如果所述第一重合区域不支持所述第一AGV和所述目标AGV并行通过，则将计算得到的目标AGV通过所述待定子路径的待定时间段向后推延第一固定时长，得到第一待定时间段，所述第一固定时长大于或等于所述目标AGV以预设行驶速度通过所述待定子路径所花费的时长；
针对所述第一待定时间段和所述已保存的其他AGV的路径信息，返回执行所述判断是否存在第一AGV的步骤。
7.根据权利要求1所述的方法，其特征在于，在所述根据所述待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV的步骤之前，所述方法还包括：
判断当前是否发生拥堵，如果否，执行所述根据所述待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV的步骤；
如果是，则获取拥堵拓扑图，其中，所述拥堵拓扑图为：根据引起拥堵的拥堵源AGV和各个AGV之间的阻塞关系建立的具有多级子节点的拓扑图；其中，引起拥堵的拥堵源AGV为根节点，每个子节点对应的AGV的路径中包含其父节点对应的AGV的位置；所述拥堵拓扑图中，还包括：各个子节点到达父节点的位置的时长；
获取所述拥堵拓扑图中各个节点对应的AGV的路径信息；
根据所述待定时间段、所述拥堵拓扑图和所述各个节点对应的AGV的路径信息，判断所述拥堵拓扑图中是否存在第二AGV；其中，所述第二AGV满足以下条件：所述第二AGV从其所处位置到达其父节点对应的AGV所处位置之间的路径与所述待定子路径存在第二重合区域，且，所述第二AGV通过所述第二重合区域到达其父节点对应的AGV所处位置的累加时间段与所述待定时间段存在交集；
如果是，则根据所述第二AGV的尺寸、所述目标AGV的尺寸和所述第二重合区域所在道路的第二宽度，判断所述第二重合区域是否支持所述第二AGV和所述目标AGV并行通过；
如果支持，将所述相邻路径点保存为所述目标AGV的可达路径点。
8.根据权利要求7所述的方法，其特征在于，所述拥堵拓扑图通过如下步骤建立：
获得所述引起拥堵的拥堵源AGV及其位置作为根节点；
获得所述拥堵源AGV的关联AGV及其位置作为根节点的子节点；其中，所述拥堵源AGV的关联AGV满足以下条件：与所述拥堵源AGV有阻塞关系，且所述拥堵源AGV的关联AGV从其所在位置至所述拥堵源AGV的位置之间的子路径中，不包含其他与所述拥堵源AGV有阻塞关系的AGV，所述拥堵源AGV的关联AGV的路径中包含所述拥堵源AGV的位置；
对各个子节点，获得与该子节点有阻塞关系的各个关联AGV及其位置作为下一级子节点；对下一级子节点执行本步骤，直到下一级子节点没有有阻塞关系的关联AGV；各个子节点的路径中包含其父节点的位置；
计算各个子节点对应的AGV从其所处位置到达父节点对应的AGV所处位置的到达时长，并将各个子节点对应的到达时长添加至对应的各个子节点。
9.根据权利要求8所述的方法，其特征在于，在所述获得与拥堵源AGV有阻塞关系的各个关联AGV及其位置作为根节点的子节点之前，所述方法还包括：
获取所述拥堵源AGV的尺寸和行驶路径包含所述拥堵源AGV所处位置的第三AGV的尺寸；
根据所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路的第三宽度、所述拥堵源AGV的尺寸和第三AGV的尺寸，判断所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，是否支持所述拥堵源AGV的尺寸和第三AGV并行通过；
在所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，不支持所述拥堵源AGV的尺寸和第三AGV并行通过时，将所述第三AGV作为与所述拥堵源AGV有阻塞关系的关联AGV。
10.根据权利要求9所述的方法，其特征在于，所述拥堵源AGV的尺寸包括：所述拥堵源AGV本体的尺寸、所述拥堵源AGV装载的物体的尺寸，所述第三AGV的尺寸包括：所述第三AGV本体的尺寸、所述第三AGV装载的物体的尺寸；
所述根据所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路的第三宽度、所述拥堵源AGV的尺寸和第三AGV的尺寸，判断所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，是否支持所述拥堵源AGV的尺寸和第三AGV并行通过，包括：
按照所述拥堵源AGV本体、所述拥堵源AGV装载的物体、所述第三AGV本体和所述第三AGV装载的物体从低到高的顺序，分别以所述拥堵源AGV本体、所述拥堵源AGV装载的物体、所述第三AGV本体和所述第三AGV装载的物体的最高点所在的水平面，确定高度不同的多个第一分层面；
根据各个第一分层面的高度，对所述拥堵源AGV的竖直尺寸和所述第三AGV的竖直尺寸进行分层，得到所述拥堵源AGV本体在每一分层的水平尺寸、拥堵源AGV装载的物体在所述每一分层的水平尺寸、所述第三AGV本体在所述每一分层的水平尺寸和所述第三AGV装载的物体在所述每一分层的水平尺寸；
针对所述每一分层，根据所述拥堵源AGV本体在该分层的水平尺寸、拥堵源AGV装载的物体在该分层的水平尺寸、所述第三AGV本体在该分层的水平尺寸和所述第三AGV装载的物体在该分层的水平尺寸以及所述第三宽度，判断所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，是否支持所述拥堵源AGV和第三AGV并行通过。
11.根据权利要求10所述的方法，其特征在于，所述针对每一分层，根据所述拥堵源AGV本体在该分层的水平尺寸、拥堵源AGV装载的物体在该分层的水平尺寸、所述第三AGV本体在该分层的水平尺寸和所述第三AGV装载的物体在该分层的水平尺寸以及所述第三宽度，判断所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，是否支持所述拥堵源AGV和第三AGV并行通过，包括：
针对每一分层，基于所述拥堵源AGV本体在该分层的水平尺寸、所述第三AGV本体在该分层的水平尺寸和所述第三宽度，判断所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，是否支持所述拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、所述第三AGV本体在该分层的水平尺寸和所述第三宽度，判断所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，是否支持所述拥堵源AGV和第三AGV并行通过；和/或者，
基于所述拥堵源AGV本体在该分层的水平尺寸、所述第三AGV装载的物体在该分层的水平尺寸和所述第三宽度，判断所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，是否支持所述拥堵源AGV和第三AGV并行通过；和/或者，
基于拥堵源AGV装载的物体在该分层的水平尺寸、所述第三AGV装载的物体在该分层的水平尺寸和所述第三宽度，判断所述第三AGV所处位置至所述拥堵源AGV所处的位置之间的道路，是否支持所述拥堵源AGV和第三AGV并行通过。
12.根据权利要求7～11任一项所述的方法，其特征在于，在所述判断所述拥堵拓扑图中是否存在第二AGV之后，所述方法还包括：
如果否，将所述相邻路径点保存为所述目标AGV的可达路径点。
13.根据权利要求7～11任一项所述的方法，其特征在于，所述第二AGV的尺寸包括：所述第二AGV本体的尺寸和所述第二AGV装载的物体的尺寸，所述目标AGV的尺寸包括：所述目标AGV本体的尺寸和所述目标AGV装载的物体的尺寸；
所述根据所述第二AGV的尺寸、所述目标AGV的尺寸和所述第二重合区域所在道路的第二宽度，判断所述第二重合区域是否支持所述目标AGV与所述第二AGV并行通过，包括：
按照所述第二AGV本体、所述第二AGV装载的物体、所述目标AGV本体和所述目标AGV装载的物体从低到高的顺序，分别以所述第二AGV本体、所述第二AGV装载的物体、所述目标AGV本体和所述目标AGV装载的物体最高点所在的水平面，确定高度不同的多个第二分层面；
根据各个第二分层面的高度，对所述第二AGV的竖直尺寸和所述目标AGV的竖直尺寸进行分层，得到所述第二AGV本体在每一分层的水平尺寸、所述第二AGV装载的物体在所述每一分层的水平尺寸、所述目标AGV本体在所述每一分层的水平尺寸和所述目标AGV装载的物体在所述每一分层的水平尺寸；
针对每一分层，所述第二AGV本体在该分层的水平尺寸、所述第二AGV装载的物体在该分层的水平尺寸、所述目标AGV本体在该分层的水平尺寸、所述目标AGV装载的物体在该分层的水平尺寸以及所述第二重合区域所在道路的宽度，判断所述第二重合区域是否支持所述目标AGV与所述第二AGV并行通过。
14.根据权利要求13所述的方法，其特征在于，所述针对每一分层，根据所述第二AGV在该分层的水平尺寸、所述目标AGV在该分层的水平尺寸以及所述第二重合区域所在道路的宽度，判断所述第二重合区域是否支持所述目标AGV与所述第二AGV并行通过，包括：
针对每一分层，基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV本体的水平尺寸和所述第二重合区域所在道路的宽度，判断所述第二重合区域是否支持所述目标AGV与所述第二AGV并行通过；和/或者，
基于该分层的第二AGV本体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和所述第二重合区域所在道路的宽度，判断所述第二重合区域是否支持所述目标AGV与所述第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV本体的水平尺寸和所述第二重合区域所在道路的宽度，判断所述第二重合区域是否支持所述目标AGV与所述第二AGV并行通过；和/或者，
基于该分层的第二AGV装载的物体的水平尺寸、该分层的目标AGV装载的物体的水平尺寸和所述第二重合区域所在道路的宽度，判断所述第二重合区域是否支持所述目标AGV与所述第二AGV并行通过。
15.根据权利要求7所述的方法，其特征在于，所述方法还包括：
如果所述第二重合区域不支持所述目标AGV与所述第二AGV并行通过；
将计算得到的目标AGV通过所述待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段，所述第二固定时长大于或等于所述第二AGV从所述第二AGV所在位置到达对应的父节点AGV所在位置的时长；
针对所述第二待定时间段和所述拥堵拓扑图，返回执行所述判断所述拥堵拓扑图中是否存在第二AGV的步骤。
16.根据权利要求15所述的方法，其特征在于，当所述第二AGV对应的父节点包括多个子节点时，在所述将计算得到的目标AGV通过所述待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段之前，所述方法还包括：
针对所述第二AGV对应的父节点的每个子节点，获取该子节点对应的AGV从其所处位置到达其父节点对应的AGV所处位置的到达时长；
将所述第二AGV对应的父节点的所有子节点对应的AGV的到达时长中的最大到达时长，作为所述第二固定时长，并执行所述将计算得到的目标AGV通过所述待定子路径的待定时间段向后推延第二固定时长，得到第二待定时间段的步骤。
17.一种AGV路径规划装置，其特征在于，所述装置包括：
第一相邻路径点查找模块，用于将目标AGV所在的起始路径点作为当前路径点，查找与所述当前路径点相邻的路径点，并触发第一待定时间段计算模块；
所述第一待定时间段计算模块，用于将所述当前路径点与所述找到的相邻路径点之间的路径确定为待定子路径，计算所述目标AGV通过所述待定子路径的待定时间段；
第一AGV判断模块，用于根据所述待定时间段和已保存的其他AGV的路径信息，判断是否存在第一AGV，所述第一AGV满足以下条件：所述第一AGV的路径与所述待定子路径存在第一重合区域，且所述第一AGV通过所述第一重合区域的时间段与所述待定时间段存在交集；如果是，触发第一并行通过判断模块；
所述第一并行通过判断模块，用于则根据所述第一AGV的尺寸、所述目标AGV的尺寸和所述第一重合区域所在道路的第一宽度，判断所述第一重合区域是否支持所述第一AGV和所述目标AGV并行通过；如果支持，触发路径点保存模块；
所述路径点保存模块，用于将所述相邻路径点保存为所述目标AGV的可达路径点。
18.一种电子设备，其特征在于，包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过通信总线完成相互间的通信；
存储器，用于存放计算机程序；
处理器，用于执行存储器上所存放的程序时，实现权利要求1-16任一所述的方法步骤。
19.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现权利要求1-16任一所述的方法步骤。
CN201910079511.XA 2019-01-28 2019-01-28 一种agv路径规划方法、装置、电子设备及存储介质 Active CN111487957B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201910079511.XA CN111487957B (zh) 2019-01-28 2019-01-28 一种agv路径规划方法、装置、电子设备及存储介质

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201910079511.XA CN111487957B (zh) 2019-01-28 2019-01-28 一种agv路径规划方法、装置、电子设备及存储介质

Publications (2)

Publication Number Publication Date
CN111487957A CN111487957A (zh) 2020-08-04
CN111487957B true CN111487957B (zh) 2023-05-02

Family

ID=71794170

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201910079511.XA Active CN111487957B (zh) 2019-01-28 2019-01-28 一种agv路径规划方法、装置、电子设备及存储介质

Country Status (1)

Country Link
CN (1) CN111487957B (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112633585B (zh) * 2020-12-30 2024-09-06 广州极飞科技股份有限公司 无人设备调度方法、装置、电子设备及存储介质

Citations (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH09128682A (ja) * 1995-11-02 1997-05-16 Honda Motor Co Ltd 車両用渋滞情報案内方法
US6049745A (en) * 1997-02-10 2000-04-11 Fmc Corporation Navigation system for automatic guided vehicle
JP2003004466A (ja) * 2001-06-15 2003-01-08 Denso Corp 走行状況予測装置、経路設定装置、及び、ナビゲーション装置
JP2004280213A (ja) * 2003-03-13 2004-10-07 Japan Science & Technology Agency 分散型経路計画装置及び方法、分散型経路計画プログラム
CN104457770A (zh) * 2014-08-21 2015-03-25 胡泓涛 一种拥堵预判和行驶路径规划的方法及行驶路径规划的系统
CN105810001A (zh) * 2016-05-19 2016-07-27 东华大学 一种基于车载自组网的实时动态路径规划方法
CN106020183A (zh) * 2016-05-05 2016-10-12 天津阿备默机器人科技有限公司 基于交通管制区域的agv交通调度管理实现方法
CN106595688A (zh) * 2016-12-08 2017-04-26 济南佰意兴网络科技有限公司 一种多agv导向和动态路径规划方法
CN107727099A (zh) * 2017-09-29 2018-02-23 山东大学 一种工厂内物料运输多agv调度及路径规划方法
CN108195380A (zh) * 2017-12-26 2018-06-22 广东嘉腾机器人自动化有限公司 一种基于最短路径的agv最优路径选择方法
CN108287547A (zh) * 2018-01-19 2018-07-17 广东美的智能机器人有限公司 多移动机器人的冲突管理方法及系统
CN108629438A (zh) * 2017-03-16 2018-10-09 北京京东尚科信息技术有限公司 测量agv路段拥堵的方法、装置、电子设备和可读存储介质
CN108897330A (zh) * 2018-10-15 2018-11-27 河北工业大学 一种基于交通拥堵控制的物流中心搬运机器人路径规划方法

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP6260912B2 (ja) * 2016-02-09 2018-01-17 本田技研工業株式会社 渋滞箇所情報提供のための装置、方法、及びプログラム

Patent Citations (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH09128682A (ja) * 1995-11-02 1997-05-16 Honda Motor Co Ltd 車両用渋滞情報案内方法
US6049745A (en) * 1997-02-10 2000-04-11 Fmc Corporation Navigation system for automatic guided vehicle
JP2003004466A (ja) * 2001-06-15 2003-01-08 Denso Corp 走行状況予測装置、経路設定装置、及び、ナビゲーション装置
JP2004280213A (ja) * 2003-03-13 2004-10-07 Japan Science & Technology Agency 分散型経路計画装置及び方法、分散型経路計画プログラム
CN104457770A (zh) * 2014-08-21 2015-03-25 胡泓涛 一种拥堵预判和行驶路径规划的方法及行驶路径规划的系统
CN106020183A (zh) * 2016-05-05 2016-10-12 天津阿备默机器人科技有限公司 基于交通管制区域的agv交通调度管理实现方法
CN105810001A (zh) * 2016-05-19 2016-07-27 东华大学 一种基于车载自组网的实时动态路径规划方法
CN106595688A (zh) * 2016-12-08 2017-04-26 济南佰意兴网络科技有限公司 一种多agv导向和动态路径规划方法
CN108629438A (zh) * 2017-03-16 2018-10-09 北京京东尚科信息技术有限公司 测量agv路段拥堵的方法、装置、电子设备和可读存储介质
CN107727099A (zh) * 2017-09-29 2018-02-23 山东大学 一种工厂内物料运输多agv调度及路径规划方法
CN108195380A (zh) * 2017-12-26 2018-06-22 广东嘉腾机器人自动化有限公司 一种基于最短路径的agv最优路径选择方法
CN108287547A (zh) * 2018-01-19 2018-07-17 广东美的智能机器人有限公司 多移动机器人的冲突管理方法及系统
CN108897330A (zh) * 2018-10-15 2018-11-27 河北工业大学 一种基于交通拥堵控制的物流中心搬运机器人路径规划方法

Also Published As

Publication number Publication date
CN111487957A (zh) 2020-08-04

Similar Documents

Publication Publication Date Title
CN106647734B (zh) 自动导引车、路径规划方法与装置
CN114819420B (zh) 基于冲突消解的天车运输路径规划方法
CN109115226B (zh) 基于跳点搜索的多机器人冲突避免的路径规划方法
CN114895636B (zh) 一种agv控制方法、控制系统、电子设备及存储介质
CN113387089B (zh) 一种用于库位分配的方法、入库端及机器人
CN111532641B (zh) 仓储分拣中自动引导车的并行路径规划方法
JP2022082419A (ja) 動作環境におけるルートプランを最適化するためのシステム及び方法
CN112833905A (zh) 基于改进a*算法的分布式多agv无碰撞路径规划方法
WO2020039699A1 (ja) 走行車制御装置、走行車システム、及び走行車制御方法
CN118083804B (zh) 基于降低轨道繁忙程度的路径选择方法及装置
CN116030625B (zh) 车辆调度方法、装置、设备及系统
KR101010718B1 (ko) 복수개의 자원을 점유하는 무인 반송차의 동적 주행방법
CN117308945A (zh) 基于准确交通管控的无人天车动态路径规划方法及系统
CN114415610A (zh) 机器人的调度方法、装置、电子设备及存储介质
JP2020030723A (ja) 走行車制御装置、走行車システム、及び走行車制御方法
US11705353B2 (en) Dynamic routing method and apparatus for overhead hoist transport system
Koo et al. Vehicle travel time models for AGV systems under various dispatching rules
CN111487957B (zh) 一种agv路径规划方法、装置、电子设备及存储介质
CN118466514A (zh) 一种rmfs多agv路径规划及冲突、死锁避免方法及系统
CN117908475A (zh) 调度方法和调度装置
WO2019114620A1 (zh) 移动装置导航方法及相关设备
CN116940911A (zh) 用于管理材料搬运车辆的移动的系统和方法
CN117636641A (zh) 一种用于车辆搬运机器人的车辆间协同搬运方法及装置
CN116719312B (zh) 一种单行道场景下基于折返避让的多agv解锁方法
CN118363374A (zh) Amr集群调度方法及装置、电子设备和可读存储介质

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
CB02 Change of applicant information
CB02 Change of applicant information

Address after: 310051 room 304, B / F, building 2, 399 Danfeng Road, Binjiang District, Hangzhou City, Zhejiang Province

Applicant after: Hangzhou Hikvision Robot Co.,Ltd.

Address before: 310052 5 / F, building 1, building 2, no.700 Dongliu Road, Binjiang District, Hangzhou City, Zhejiang Province

Applicant before: HANGZHOU HIKROBOT TECHNOLOGY Co.,Ltd.

GR01 Patent grant
GR01 Patent grant