(12)发明专利申请
(10)申请公布号 CN 111798041 A(43)申请公布日 2020.10.20
(21)申请号 202010560493.X(22)申请日 2020.06.18
(71)申请人 北京卫星制造厂有限公司
地址 100190 北京市海淀区知春路63号(72)发明人 李光 于荣荣 林晓青 刘净瑜
王颜 徐建萍 殷宇航 张加波 (74)专利代理机构 中国航天科技专利中心
11009
代理人 陈鹏(51)Int.Cl.
G06Q 10/04(2012.01)G06Q 10/06(2012.01)G06Q 10/08(2012.01)G06Q 50/04(2012.01)
权利要求书2页 说明书6页 附图1页
(54)发明名称
一种基于时间窗的AGV智能调度方法(57)摘要
一种基于时间窗的AGV智能调度方法，通过采用高优先级及时间优先原则下的时间窗计算方法进行路径预先占用，实现多AGV对同一路段的分时使用和自动避让，并根据现场运行环境的虚拟映射进行各路径节点的灵活设置以及任务的优先级分类及排序，解决了生产现场多AGV设备难以同时运行、容易出现路径容量不足、多车冲突、路径交叉、环路死锁等情况的问题，有效提高了运行效率和运行安全性。
CN 111798041 ACN 111798041 A
权 利 要 求 书
1/2页
1.一种基于时间窗的AGV智能调度方法，其特征在于步骤如下：(1)根据现场环境特点及调度任务需求，建立激光导航坐标系，构建现场地图，并规划构建自动导引运输车AGV的运行路径节点，对激光导航坐标系内各运行路径节点的坐标、类型、定位方式及路径方向进行确定，根据上述现场地图信息生成现场地图文件；
(2)根据调度任务需求，对AGV设备类型、设备编号、通讯MAC地址、运行状态于数据库中进行存储；
(3)利用AGV调度系统读取现场地图文件，并对现场地图信息进行动态存储，于AGV调度系统中进行虚拟映射；
所述AGV调度系统通过读取现场地图文件及数据库中的AGV设备信息及任务信息实现AGV调度及管理；
(4)利用AGV调度系统于数据库中读取AGV设备信息，获取现场地图中可用AGV设备信息，存储可用AGV设备信息，对所选AGV设备进行初始化；
(5)建立AGV调度系统与所有可用AGV设备的通讯链路；(6)获取各AGV设备的当前位置坐标，根据现场地图信息对各AGV设备进行位置检测，查找与各AGV设备的当前位置距离最近的运行路径节点，并根据运行路径节点与各AGV设备的当前位置距离判断AGV设备是否在导航区域内，若在导航区域内，则将该AGV设备添加至空闲状态AGV列表中，否则AGV设备超出导航范围，将所有AGV设备位置检测完毕后，根据检测结果对数据库数据进行更新；
(7)通过AGV调度系统读取上层系统内的任务需求，对未开始执行的待执行任务按紧急程度、任务创建时间进行优先级分类及排序；
所述待执行任务包括任务模型、起始位置、目标位置、任务优先级、任务创建时间，所述任务模型包括起始位置处AGV设备动作、目标位置处AGV设备动作、待执行任务AGV设备类型；
(8)根据优先级分类及排序后的待执行任务顺序执行任务，根据当前待执行任务信息进行AGV设备指派；
(9)于当前待执行任务进行指派后，对指派AGV设备进行实时路径规划，于任务执行过程中实现其他AGV设备自动避让，实时更新数据库中当前任务的执行状态、指派AGV运行状态、当前AGV位置坐标及剩余运行路径节点信息；
(10)任务执行完成后，更新数据库中该任务状态为执行完成，同时将任务完成后所选AGV设备状态更新为空闲状态，为后续执行其他任务进行准备。
2.根据权利要求1所述的一种基于时间窗的AGV智能调度方法，其特征在于：所述运行路径节点中需要进行视觉导航及视觉精确定位处设置有矩阵码。
3.根据权利要求1所述的一种基于时间窗的AGV智能调度方法，其特征在于：所述步骤(6)中，对各AGV设备进行位置检测前，利用AGV调度系统，根据待检测AGV设备编号及网络地址，进行点对点定向通讯以获取各AGV设备的当前位置坐标。
4.根据权利要求1所述的一种基于时间窗的AGV智能调度方法，其特征在于：所述步骤(7)中，所述上层系统包括MES系统及智能仓储系统，优先级分类及排序具体为：根据待执行任务优先级紧急程度进行首先排序，对优先级相同的待执行任务，按照任务的创建时间先后顺序排序。
2
CN 111798041 A
权 利 要 求 书
2/2页
5.根据权利要求4所述的一种基于时间窗的AGV智能调度方法，其特征在于：所述AGV调度系统读取上层系统内的任务需求的时间间隔为500ms。
6.根据权利要求1所述的一种基于时间窗的AGV智能调度方法，其特征在于：所述步骤(8)中，根据当前待执行任务信息中的待执行任务AGV设备类型选取对应类型的所有AGV设备，其中：
若当前待执行任务信息内无待执行任务，对应类型的AGV设备继续执行原任务或待命；若当前待执行任务信息内有待执行任务，判断任务信息内是否有指定AGV设备编号，若存在指定AGV设备编号，该AGV设备处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态，则为该AGV设备指派当前待执行任务信息；
若不存在指定AGV设备编号，根据任务信息中待执行任务AGV设备类型，判断同类型中是否有处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态的AGV设备，若空闲AGV设备数量为1，则直接对该AGV设备进行指派；若空闲AGV设备数量大于1，获取每个空闲AGV设备由当前位置至任务起始位置的所有路径，计算各路径的占用时间，选取所有空闲AGV设备的所有路径中占用时间最短的路径作为备选路径，判断所选备选路径内所有运行路径节点的占用时间窗是否与其他AGV设备冲突，若存在冲突的占用时间窗，则根据占用时间排序选取占用时间仅大于备选路径的新路径重新进行占用时间窗判断，直至选取出占用时间窗与其他AGV设备不冲突的新路径作为最优路径，选取该路径对应的AGV设备作为当前待执行任务的指派AGV设备；若空闲AGV设备数量为0，则不进行指派，等待处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态的AGV设备。
7.根据权利要求6所述的一种基于时间窗的AGV智能调度方法，其特征在于：所述每个空闲AGV设备由当前位置至任务起始位置的所有路径通过dijkstra算法进行计算。
3
CN 111798041 A
说 明 书
一种基于时间窗的AGV智能调度方法
1/6页
技术领域
[0001]本发明涉及一种基于时间窗的AGV智能调度方法，属于智能调度技术领域。背景技术
[0002]AGV是柔性制造系统的重要组成部分，在生产过程自动化和智能化方面有着缺一不可的重要作用，尤其是在离散制造型企业，完成多线路间不定点多个工位的即时自动搬运，实现制造业的自动化，进行加工、装配等。AGV是提高生产制造效率的重要工具，有利于实现工厂、车间、生产线等的智能化、现代化制造，尤其是在加工、运输等工业技术中具有广泛的应用。而AGV调度系统完成对多AGV的管理、路径规划、任务分配、状态监控等，调度系统性能的优劣直接影响转运效率，从而影响生产效率和成本等。[0003]目前由于生产现场路径容量有限，但多AGV需同时运行，易发生路径容量不足、多车冲突、路径交叉、环路死锁等问题，无法满足精密制造、装配等领域对多AGV自动、无碰撞、无死锁、高效运行的要求。发明内容
[0004]本发明解决的技术问题是：针对目前现有技术中，生产现场多AGV设备难以同时运行、容易出现路径容量不足、多车冲突、路径交叉、环路死锁等情况的问题，提出了一种基于时间窗的AGV智能调度方法。
[0005]本发明解决上述技术问题是通过如下技术方案予以实现的：[0006]一种基于时间窗的AGV智能调度方法，步骤如下：[0007](1)根据现场环境特点及调度任务需求，建立激光导航坐标系，构建现场地图，并规划构建自动导引运输车AGV的运行路径节点，对激光导航坐标系内各运行路径节点的坐标、类型、定位方式及路径方向进行确定，根据上述现场地图信息生成现场地图文件；[0008](2)根据调度任务需求，对AGV设备类型、设备编号、通讯MAC地址、运行状态于数据库中进行存储；[0009](3)利用AGV调度系统读取现场地图文件，并对现场地图信息进行动态存储，于AGV调度系统中进行虚拟映射；
[0010]所述AGV调度系统通过读取现场地图文件及数据库中的AGV设备信息及任务信息实现AGV调度及管理；[0011](4)利用AGV调度系统于数据库中读取AGV设备信息，获取现场地图中可用AGV设备信息，存储可用AGV设备信息，对所选AGV设备进行初始化；[0012](5)建立AGV调度系统与所有可用AGV设备的通讯链路；[0013](6)获取各AGV设备的当前位置坐标，根据现场地图信息对各AGV设备进行位置检测，查找与各AGV设备的当前位置距离最近的运行路径节点，并根据运行路径节点与各AGV设备的当前位置距离判断AGV设备是否在导航区域内，若在导航区域内，则将该AGV设备添加至空闲状态AGV列表中，否则AGV设备超出导航范围，将所有AGV设备位置检测完毕后，根
4
CN 111798041 A
说 明 书
2/6页
据检测结果对数据库数据进行更新；[0014](7)通过AGV调度系统读取上层系统内的任务需求，对未开始执行的待执行任务按紧急程度、任务创建时间进行优先级分类及排序；[0015]所述待执行任务包括任务模型、起始位置、目标位置、任务优先级、任务创建时间，所述任务模型包括起始位置处AGV设备动作、目标位置处AGV设备动作、待执行任务AGV设备类型；[0016](8)根据优先级分类及排序后的待执行任务顺序执行任务，根据当前待执行任务信息进行AGV设备指派；[0017](9)于当前待执行任务进行指派后，对指派AGV设备进行实时路径规划，于任务执行过程中实现其他AGV设备自动避让，实时更新数据库中当前任务的执行状态、指派AGV运行状态、当前AGV位置坐标及剩余运行路径节点信息；[0018](10)任务执行完成后，更新数据库中该任务状态为执行完成，同时将任务完成后所选AGV设备状态更新为空闲状态，为后续执行其他任务进行准备。
[0019]所述运行路径节点中需要进行视觉导航及视觉精确定位处设置有矩阵码。[0020]所述步骤(6)中，对各AGV设备进行位置检测前，利用AGV调度系统，根据待检测AGV设备编号及网络地址，进行点对点定向通讯以获取各AGV设备的当前位置坐标。[0021]所述步骤(7)中，所述上层系统包括MES系统及智能仓储系统，优先级分类及排序具体为：根据待执行任务优先级紧急程度进行首先排序，对优先级相同的待执行任务，按照任务的创建时间先后顺序排序。
[0022]所述AGV调度系统读取上层系统内的任务需求的时间间隔为500ms。[0023]所述步骤(8)中，根据当前待执行任务信息中的待执行任务AGV设备类型选取对应类型的所有AGV设备，其中：
[0024]若当前待执行任务信息内无待执行任务，对应类型的AGV设备继续执行原任务或待命；
[0025]若当前待执行任务信息内有待执行任务，判断任务信息内是否有指定AGV设备编号，若存在指定AGV设备编号，该AGV设备处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态，则为该AGV设备指派当前待执行任务信息；[0026]若不存在指定AGV设备编号，根据任务信息中待执行任务AGV设备类型，判断同类型中是否有处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态的AGV设备，若空闲AGV设备数量为1，则直接对该AGV设备进行指派；若空闲AGV设备数量大于1，获取每个空闲AGV设备由当前位置至任务起始位置的所有路径，计算各路径的占用时间，选取所有空闲AGV设备的所有路径中占用时间最短的路径作为备选路径，判断所选备选路径内所有运行路径节点的占用时间窗是否与其他AGV设备冲突，若存在冲突的占用时间窗，则根据占用时间排序选取占用时间仅大于备选路径的新路径重新进行占用时间窗判断，直至选取出占用时间窗与其他AGV设备不冲突的新路径作为最优路径，选取该路径对应的AGV设备作为当前待执行任务的指派AGV设备；若空闲AGV设备数量为0，则不进行指派，等待处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态的AGV设备。
[0027]所述每个空闲AGV设备由当前位置至任务起始位置的所有路径通过dijkstra算法进行计算。
5
CN 111798041 A[0028]
说 明 书
3/6页
本发明与现有技术相比的优点在于：
[0029](1)本发明提供的一种基于时间窗的AGV智能调度方法，根据AGV现场运行环境提前规划路径节点并预先保存在数据库中，建立调度系统中的电子地图对现场环境的虚拟映射，并可根据实际需要灵活多变地设置各路径节点，提高自动加工或装配等流水线的布置和更改的灵活性，将任务按照任务执行状态、优先级、下发时间进行分类和排序，有利于对于紧急任务的优先处理，方便用户对AGV任务的管理与实时处理AGV状态信息；[0030](2)本发明采用的对同一路径节点，采用时间优先原则下的时间窗计算方法进行路径预先占用实现多AGV对同一路段的分时使用和自动避让，防止多车冲突、路径交叉、环路死锁等问题，有效提高了运行效率和运行安全性。附图说明
[0031]图1为发明提供的智能调度方法流程示意图；
具体实施方式
[0032]一种基于时间窗的AGV智能调度方法，通过预先判断运行路径节点状态和对空闲节点基于时间窗的预先占用及对被占用节点的自动避让，实现多AGV同区域内同时运行时的自动避让，提高运行效率和运行安全性，如图1所示，具体步骤为：[0033](1)根据现场环境特点及调度任务需求，建立激光导航坐标系，构建现场地图，并规划构建自动导引运输车AGV的运行路径节点，对激光导航坐标系内各运行路径节点的坐标、类型、定位方式及路径方向进行确定，根据上述现场地图信息生成现场地图文件；运行路径节点中需要进行视觉导航及视觉精确定位处设置有矩阵码，矩阵码的坐标方向与激光导航坐标系相同；[0034]其中，运行路径节点类型包括加减速点、工位点、停车点、充电点等，定位方式包括视觉定位、激光定位、PSD定位等，路径方向包括正向、反向、双向，同时还要判断该运行路径节点处是否允许AGV旋转、导航方式、是否允许横移等信息存储在电子地图中，最终根据上述属性生成json地图文件，即现场地图文件；[0035]AGV设备可采用视觉、激光等多种导航方式进行自主导航，具有巡线行走、可识别矩阵码编号或根据现场特征匹配识别自身坐标的特点；根据现场环境中存在多个固定障碍物及AGV设备自身体积及载荷体积较大的特点，AGV设备的可运行路线受限；在现场环境中设置加减速点、停车点、旋转点和工位点等不同属性的特征点，测量各点对应的坐标，构建现场二维地图；调度系统中的电子地图模块将上述点、路段的属性信息存储在json文件中，实现对现场环境的数字化建模；json文件是一种轻量级的数据交换格式，易于人阅读和编写，同时也易于机器生成和解析；[0036](2)根据调度任务需求，对AGV设备类型、设备编号、通讯MAC地址、运行状态于数据库中进行存储；[0037](3)利用AGV调度系统读取现场地图文件，并对现场地图信息进行动态存储，于AGV调度系统中进行虚拟映射；
[0038]所述AGV调度系统通过读取现场地图文件及数据库中的AGV设备信息及任务信息实现AGV调度及管理；
6
CN 111798041 A[0039]
说 明 书
4/6页
在AGV调度系统中，设备管理人员根据实际设备情况，通过操作调度系统的设备管
理模块，将所有AGV设备信息一次性存储在数据库的AGV信息表中，以便调度系统对多AGV进行调度和管理，后续若增加或删除AGV设备，可在界面中操作，调度系统自动更新数据库；否则调度系统可自主管理已录入信息的AGV设备，并根据其运行状态等自动更新；[0040](4)利用AGV调度系统于数据库中读取AGV设备信息，获取现场地图中可用AGV设备信息，存储可用AGV设备信息，对所选AGV设备进行初始化；[0041](5)建立AGV调度系统与所有可用AGV设备的通讯链路；[0042]设置通讯链路，需要AGV调度系统自动检测可用的通讯链路的端口，能够默认或更改所选端口，并设置波特率、数据位、停止位的参数，设置完成后，自动打开通讯链路的端口，并通过无线通讯模块实现调度系统与AGV设备之间的无线通讯，建立调度系统与AGV设备之间的通讯链路；[0043](6)获取各AGV设备的当前位置坐标，根据现场地图信息对各AGV设备进行位置检测，查找与各AGV设备的当前位置距离最近的运行路径节点，并根据运行路径节点与各AGV设备的当前位置距离判断AGV设备是否在导航区域内，若在导航区域内，则将该AGV设备添加至空闲状态AGV列表中，否则AGV设备超出导航范围，将所有AGV设备位置检测完毕后，根据检测结果对数据库数据进行更新；[0044]其中，所述导航区域通过现场地图信息中存储的数据、AGV的设备信息共同确定，若AGV的当前位置与与之距离最近的路径节点的距离>AGV自身长度的2倍，则认为AGV所在位置超出导航区域；对各AGV设备进行位置检测前，利用AGV调度系统，根据待检测AGV设备编号及网络地址，进行点对点定向通讯以获取各AGV设备的当前位置坐标；[0045](7)通过AGV调度系统读取上层系统内的任务需求，对未开始执行的待执行任务按紧急程度、任务创建时间进行优先级分类及排序；[0046]所述待执行任务包括任务模型、起始位置、目标位置、任务优先级、任务创建时间，所述任务模型包括起始位置处AGV设备动作、目标位置处AGV设备动作、待执行任务AGV设备类型；
[0047]上层系统包括MES系统及智能仓储系统等，优先级分类及排序具体为：根据待执行任务优先级紧急程度进行首先排序，对优先级相同的待执行任务，按照任务的创建时间先后顺序排序，AGV调度系统读取上层系统内的任务需求的时间间隔为500ms；[0048](8)根据优先级分类及排序后的待执行任务顺序执行任务，根据当前待执行任务信息进行AGV设备指派；[0049]其中，根据当前待执行任务信息中的待执行任务AGV设备类型选取对应类型的所有AGV设备，具体为：
[0050]若当前待执行任务信息内无待执行任务，对应类型的AGV设备继续执行原任务或待命；
[0051]若当前待执行任务信息内有待执行任务，判断任务信息内是否有指定AGV设备编号，若存在指定AGV设备编号，该AGV设备处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态，则为该AGV设备指派当前待执行任务信息；[0052]若不存在指定AGV设备编号，根据任务信息中待执行任务AGV设备类型，判断同类型中是否有处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态的AGV设
7
CN 111798041 A
说 明 书
5/6页
备，若空闲AGV设备数量为1，则直接对该AGV设备进行指派；若空闲AGV设备数量大于1，获取每个空闲AGV设备由当前位置至任务起始位置的所有路径，计算各路径的占用时间，选取所有空闲AGV设备的所有路径中占用时间最短的路径作为备选路径，判断所选备选路径内所有运行路径节点的占用时间窗是否与其他AGV设备冲突，若存在冲突的占用时间窗，则根据占用时间排序选取占用时间仅大于备选路径的新路径重新进行占用时间窗判断，直至选取出占用时间窗与其他AGV设备不冲突的新路径作为最优路径，选取该路径对应的AGV设备作为当前待执行任务的指派AGV设备；若空闲AGV设备数量为0，则不进行指派，等待处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态的AGV设备；
[0053]每个空闲AGV设备由当前位置至任务起始位置的所有路径通过dijkstra算法进行计算；[0054](9)于当前待执行任务进行指派后，对指派AGV设备进行实时路径规划，于任务执行过程中实现其他AGV设备自动避让，实时更新数据库中当前任务的执行状态、指派AGV运行状态、当前AGV位置坐标及剩余运行路径节点信息；
[0055]时间窗是指执行任务的AGV从开始进入到离开某个交叉路口或某个路段的整个过程所花费的时间，其主要作用是对AGV已占用的交叉路口或行驶路段进行标记，以避免该路口或路段在该AGV占用的时间段内，其他AGV驶入而发生死锁或者碰撞。
[0056]为避免执行任务的AGV与其他AGV因争夺路径资源而引发死锁或碰撞冲突，系统利用时间窗算法为该可行路径上的各有序路段插入合理、连续的时间窗；[0057](10)任务执行完成后，更新数据库中任务的状态和当前AGV的空闲状态，为后续执行新的任务做准备。将执行该任务的AGV标为空闲状态，将数据库中相应的执行完的任务标为执行完成，防止同一任务重复执行。则空闲的AGV可执行新的任务。[0058]下面结合具体实施例进行进一步说明：[0059]在本实施例中，建立激光导航坐标系，构建现场地图后，构建自动导引运输车AGV的运行路径节点，对激光导航坐标系内各运行路径节点的属性信息进行确定，生成现场地图文件的json地图文件；
[0060]对AGV设备信息进行确认，于数据库中进行存储，利用AGV调度系统读取现场地图文件，并对现场地图信息进行动态存储，于AGV调度系统中进行虚拟映射，利用AGV调度系统于数据库中读取AGV设备信息，获取现场地图中可用AGV设备信息，存储可用AGV设备信息；[0061]建立AGV调度系统与所有可用AGV设备的通讯链路，获取各AGV设备的当前位置坐标，根据现场地图信息对各AGV设备进行位置检测，确定所有AGV设备当前位置均位于导航区域内，通过AGV调度系统读取上层系统内的任务需求，对未开始执行的待执行任务按紧急程度、任务创建时间进行优先级分类及排序，确定当前待执行任务信息；[0062]根据任务信息选取对应类型的所有AGV设备，当前待执行任务信息内有待执行任务，但不存在指定AGV设备编号，因此需要进行判断，根据任务信息中待执行任务AGV设备类型，判断同类型中是否有处于调度系统控制且非通讯中断状态且在导航区域内且为空闲状态的AGV设备数量大于1，此时获取每个空闲AGV设备由当前位置至任务起始位置的所有路径，通过dijkstra算法进行计算各路径的占用时间，时间最短的路径作为备选路径，对该路径内所有运行路径节点的占用时间窗冲突情况进行判断，发现存在冲突的占用时间窗，则根据占用时间排序选取占用时间仅大于备选路径的新路径重新进行占用时间窗判断，根据
8
CN 111798041 A
说 明 书
6/6页
新一轮的判断发现占用时间由短至长的第三条路径中，占用时间窗与其他AGV设备不冲突，则以该路径作为最优路径，选取该路径对应的AGV设备作为当前待执行任务的指派AGV设备；
[0063]对指派AGV设备进行实时路径规划，于任务执行过程中实现其他AGV设备自动避让，实时更新数据库中当前任务的执行状态、指派AGV运行状态、当前AGV位置坐标及剩余运行路径节点信息，任务执行完成后，更新数据库中任务的状态和当前AGV的空闲状态，为后续执行新的任务做准备。将执行该任务的AGV标为空闲状态，将数据库中相应的执行完的任务标为执行完成，防止同一任务重复执行。则空闲的AGV可执行新的任务。[0064]尽管本发明的内容已经通过上述优选实施例作了详细介绍，但应当认识到上述的描述不应被认为是对本发明的限制。在本领域技术人员阅读了上述内容后，对于本发明的多种修改和替代都将是显而易见的。因此，本发明的保护范围应由所附的权利要求来限定。
9
CN 111798041 A
说 明 书 附 图
1/1页
图1
10
因篇幅问题不能全部显示，请点此查看更多更全内容