CN107036618A一种基于最短路径深度优化算法的agv路径规划方法

著录项

申请号CN201710376356.9
申请日20170524
公开号CN107036618A
公开日20170811
申请（专利权）人合肥工业大学（马鞍山）高新技术研究院;合肥工业大学
发明人吴焱明;王吉祥;王浩;赵韩;杨少锋;杨强;朱家诚
主分类号G01C21/34
分类号G01C21/34 G05D1/02
地址安徽省马鞍山市开发区太白大道578号
国省代码安徽(34)
代理机构合肥天明专利事务所（普通合伙）
代理人奚华保

1.一种基于最短路径深度优化算法的AGV路径规划方法，其特征在于：该方法包括下列顺序的步骤：

(1)初始化AGV调度管理系统，PC机调度系统读取数据库中已经建立的路径地图模型，提取地图中的关键节点P和路段L的信息，并采用优化存储方式对节点信息进行存储,同时 PC机调度系统读取激光导航系统反馈的全部AGV状态信息，对AGV进行监控定位，同时车机监控管理系统实时接收系统中不同加工点的货物输送的任务请求，PC机调度系统接收任务请求并将请求信息发送至每台AGV车载监控管理系统；

(2)AGV车载监控管理系统接收任务请求信息后，读取当前AGV运行状态，判断当前AGV 是否处于空闲状态：若非处于空闲状态，则反馈当前AGV处于工作状态，不接收任务请求；若处于空闲状态，读取AGV当前位置坐标信息，将AGV的位置坐标信息反馈至PC机调度系统；PC 机调度系统通过请求任务的位置坐标和AGV坐标位置计算AGV执行任务路径的运送时长的权值，根据AGV执行任务路径的运送时长的权值大小设定AGV的优先级顺序，选取优先级最高的AGV执行任务,AGV车载监控管理系统将执行任务AGV的位置信息和任务请求的位置信息传递至路径优化系统；

(3)路径优化系统接收AGV的位置信息后，初始化并更新数据库中路径地图模型的信息，将AGV当前位置记为起始节点P 0，有任务请求的加工工位位置记为终止节点Pn，路径优化系统读取路径地图模型中节点和路段信息,采用基于最短运送时长的最优路径算法即 Dijkstra算法，Dijkstra算法根据起始节点P 0、终止节点Pn和路径节点的占用信息计算出节点之间的可行路径，并根据评估函数评估可行路径并从中选取最优路径，路径优化系统将最优路径的信息反馈至PC机调度系统中；

(4)PC机调度系统接收到路径优化系统反馈的最优路径信息后，将最优路径转化为车载工控机能够识别的运动控制指令，根据任务的优先级顺序的大小，依次将任务路径的运动控制指令发送至车载控制系统中，车载控制系统接收运动指令后执行动作,并将动作执行的信息反馈至车机监控管理系统,车机监控管理系统读取激光导航系统中AGV的实际位置信息,并比较与车载控制系统反馈的动作位置信息差值,对反馈的动作位置与AGV实际位置之间的差值采取线性插补策略,对AGV的运动轨迹进行模糊控制,通过调节模糊控制器的控制参数(k α,k β,k γ)，其中k β为比例因子、k α和k γ为量化因子；AGV完成任务后，将任务完成信息反馈至PC机调度系统；

(5)PC机调度系统接收任务完成信息后，为AGV设定固定的等待时间值，在等待时间到达之后，若有新任务分配时，AGV接收任务并完成；若无新任务分配时，AGV自动启动自动回仓程序，为其分配最优的回仓路径，AGV将自动启动并返回至仓库，并释放路径中节点和路段的资源。

2.根据权利要求1所述的基于最短路径深度优化算法的AGV路径规划方法，其特征在于：在步骤(1)中，针对物流车间的实际工作环境建立与之相对应的关键节点P和路段L，在保留关键的运送流程的基础之上,简化地图模型中的关键节点P和路段L，建立较为疏散的无向地图模型G(P’,L’)，其中P’＝{1,2,3……，n}为节点的集合即节点集，L’为节点之间的弧集即路段集，根据P’和L’的信息建立无向地图的距离矩阵D＝(d ij) n*n，其中，

其中，L ij表示节点P i与节点P j之间的距离值；+∞表示节点P i与节点P j节之间不相邻，距离是无穷大；0表示节点P i与节点P j重合。

3.根据权利要求1所述的基于最短路径深度优化算法的AGV路径规划方法，其特征在于：在步骤(1)中，所述优化存储方式是指采用邻接链表的存储方式进行存储以减少无用矩阵的存储，对路径地图模型中的每个节点建立一个邻接关系的单链表，并将其表头指针用向量的形式进行存储；关键节点P的存储设计包含四个域：一是节点的序列号ID，二是邻接点域AdjacentP，用于存储于节点P相邻的节点，三是权值域WeightP，用于存储节点P与相邻节点之间的距离权值，四是邻接域NextP，用于链接节点P的邻接表中的下一个节点。

4.根据权利要求1所述的基于最短路径深度优化算法的AGV路径规划方法，其特征在于：在步骤(3)中，初始化地图模型中的所有节点，其中邻接节点集合记为集合M，已求出最优路径中已标记的节点集合记为集合N，初始化时集合N中仅包含路径节点中的起始节点 P 0，在邻接节点集合M中等待排序的存储节点集合记为集合R，对于集合R中无序序列的待存储节点，即未确定最优路径的节点，假设有n个无序序列的节点，将n个无序序列的节点采用堆排序优化存储得到小顶堆，新建一个一维数组A[]存放n个无序序列节点，并对其进行最小化堆排序，其中每个节点均是以完全二叉树的存储顺序的存储方式进行存储，树的顶点存放的是已经调整后的堆顶节点，以堆顶节点作为中间节点，并以此中间节点计算从起始节点P 0至已标记的节点的集合N的补集中的各个节点经过中间节点可达的最优路径的长度权值，依次类推，多次反复迭代至邻接节点的集合M中的全部节点均添加至已标记节点的集合N中，从而可以得到起始节点P 0至邻接节点的集合M中的任何一个节点P k的最短路径集合，并从得到的最短路径集合中选择以P 0作为起始节点，P n作为终止节点的路径作为AGV执行任务的路径。

5.根据权利要求1所述的基于最短路径深度优化算法的AGV路径规划方法，其特征在于：在步骤(3)中，所述评估基于最小运送时长的距离评估函数的公式为：

f(n)＝∑ω ij+∑(f(θ ij)+μ)

其中，θ ij是路径中AGV在节点i与节点j之间的转弯角度，f(θ ij)是转弯角度的转弯时长代价函数，μ是转弯的代价系数；路径行走的评估指标为∑ω ij，ω ij是节点i与节点j之间的距离权值。

6.根据权利要求1所述的基于最短路径深度优化算法的AGV路径规划方法，其特征在于：在步骤(3)中，所述根据Dijkstra算法选取最优路径包括以下步骤:

(6a)初始化，其中最优路径节点集合N’中仅包含起始节点P 0，未经排序的节点集合R’中包含邻接节点集合M’中除去集合N’之外的所有节点；且任意两个节点之间的相邻关系和距离权值已知，并初始化系统中地图模型的无向图和距离链表；

(6b)在未经排序的节点集合R’中，对与起始节点P 0相邻的待排序节点进行最小堆排序，并选取距离权值最小的节点P i作为堆顶点，起始节点P 0和节点P i之间的距离权值即最短路径的距离权值，将节点P i放至集合M’中，节点P 0到节点P i的最优路径的距离权值大小即运送的时长，最短路径即是P 0->P i；

(6c)以节点P i为新的中间节点，从未经排序的节点集合R’中选取与中间节点P i相邻关系的节点，若从起始节点P 0到集合R’中节点的距离权值比原先路径的距离权值小，则修改未经排序的节点集合集合R’中已经计算经过中间节点P i的路径，其中修改过后的路径权值为经过新的中间节点P i的路径权值；

(6d)重复执行步骤(6b)与(6c)，不停的迭代处理，遍历搜索未经排序的节点集合R’中未经排序的节点，直至将集合R’中所有的节点全部包含到最优路径节点集合N’中或者直至起始节点P 0与终止节点P n之间找到最优的路径为止。

7.根据权利要求1所述的基于最短路径深度优化算法的AGV路径规划方法，其特征在于：在步骤(4)中，所述车载工控机即是AGV车上搭载的工控机，所述车载控制系统包含以工控机为上位机、ABB控制器为下位机、闭环伺服系统为执行模块的运动控制系统，用于控制 AGV的转向、倒车、出入库。

8.根据权利要求1所述的基于最短路径深度优化算法的AGV路径规划方法，其特征在于：在步骤(5)中，AGV完成输送的任务、反馈任务完成信息之后，为避免占用节点和路段的资源，在等待时间到达后：若无任务分配，AGV将启动自动回仓程序，PC机调度系统将AGV当前位置设为起始节点P’ 0，仓库空闲的位置设为P’ n，PC机调度系统为这台AGV规划返回仓库的最短路径，使其自动返回至停车库；完成后，AGV释放占用的节点和路段资源；若有任务分配，则AGV接受任务。