[发明专利]一种基于动态时间窗的泊车系统路径规划方法

摘要

本发明公开了一种基于动态时间窗的泊车系统路径规划方法，属于路径规划技术领域，其特征在于包括以下步骤：步骤S1：采用拓扑法创建智能车库中AGV的工作环境模型；步骤S2：按照不同评价标准，分别为每台AGV和每项存取车任务设定优先级；步骤S3：采用Dijkstra算法为接受任务的AGV规划最短可行路径；步骤S4：排布可行路径时间窗；步骤S5：根据冲突类型不同，设计冲突解决策略；步骤S6：利用基于动态时间窗的泊车系统路径规划算法为AGV规划无冲突最优路径。本发明采用分时利用策略，通过将Dijkstra算法和时间窗法进行有效结合，不仅可以有效解决目前多AGV路径规划柔性差、易出现死锁、碰撞冲突等问题，而且可以为接受任务的AGV规划出一条时间最短的无冲突优化路径。除此之外，本发明还可有效提高智能立体停车系统整体运行效率，降低社会人员存、取车等待时间。

主权项

1.一种基于动态时间窗的泊车系统路径规划方法，其特征在于，包括如下步骤：步骤S1：采用拓扑法创建智能车库中AGV的工作环境模型；步骤S2：按照不同评价标准，分别为每台AGV和每项存取车任务设定优先级；步骤S3：采用Dijkstra算法为接受任务的AGV规划最短可行路径；步骤S4：排布可行路径时间窗；步骤S5：根据冲突类型不同，设计冲突解决策略；步骤S6：利用基于动态时间窗的泊车系统路径规划算法为AGV规划无冲突最优路径；所述步骤S1中，采用拓扑法创建智能车库中AGV的工作环境模型，具体步骤包括：步骤S11：对环境模型中的交通路网和AGV作如下处理：①AGV运行车道为单道双向模式，且宽度方向仅能容纳一台AGV；②系统中的AGV在同一时间段内只能接受一项存取车任务，在其执行任务期间，系统分配的其他任务则视为无效；③为避免与其他AGV发生碰撞事故，需为执行任务的AGV设定一个安全行驶区域，该安全行驶区域由AGV车体几何尺寸、运行速度以及运行车道几何尺寸来确定；④在某时刻或某一时间段内，路网中的任一交叉路口和任一行驶路段都只允许一台AGV使用；步骤S12：利用AGV自带的摄像头、雷达传感器、超声波传感器以及红外线传感器采集AGV运行环境信息，上述环境信息包括AGV的起始车位、目标车位、障碍物以及AGV待充电位置；步骤S13：以步骤S11和步骤S12操作采集的环境信息作为建模数据，采用拓扑法创建AGV在智能车库中的工作环境模型；所述步骤S2中，按照不同评价标准，分别为每台AGV和每项存取车任务设定优先级，具体内容包括：步骤S21：对于系统中AGV的优先级，则由车辆编号大小确定，且AGV优先级高低次序与车辆编号大小成负相关；步骤S22：对于系统中存取车任务的优先级，则由任务加载顺序、任务轻重缓急和距离最短评价标准综合确定；步骤S23：当发生交叉路口冲突时，对于AGV通过冲突交叉路口的先后顺序问题，则由AGV当前优先级和距离最短优先级综合确定；步骤S24：系统还规定，正在执行存取车任务的AGV的优先级高于空闲AGV的优先级；在AGV执行任务期间，地面控制系统为其分配的新的存取车任务被视为无效；所述步骤S23中，当发生交叉路口冲突时，对于AGV通过冲突交叉路口的先后顺序问题，则由AGV当前优先级和距离最短优先级综合确定的情况包括：步骤231：当两台AGV同时到达同一交叉路口时，系统首先对AGV优先级进行判断，然后按照优先级高低次序，来安排两台AGV通过交叉路口的先后顺序；当优先级高的AGV通过交叉路口且与优先级低的AGV保持一定的安全距离后，系统会呼叫优先级低的AGV继续执行任务；步骤232：当两台AGV是一前一后到达交叉路口，但两者会在交叉路口出现冲突时，此时系统在判断AGV优先级的基础上，还要根据两台AGV到交叉路口距离的长短来确定彼此通过路口的先后顺序；步骤233：当优先级相同的两台AGV同时到达交叉路口时，系统会根据两台AGV距离交叉路口的远近来决定其通过交叉路口的先后顺序；所述步骤S3中，采用Dijkstra算法为接受任务的AGV规划最短可行路径的关键在于，其必须按照步骤S2中的优先级高低次序进行；对于系统中任一项任务m_i的函数定义为：m_i(t)＝(s_i,d_i,λ_i(t),P_i(t),q_i)   (1)(1)式中，i表示任务编号；m_i(t)表示t时刻系统分配的任务；s_i表示任务m_i的起点，d_i表示任务m_i的终点，λ_i(t)表示在t时刻第i项任务所经过的一系列有序路段的集合；P_i(t)表示任务m_i的优先级，q_i表示执行任务m_i的AGV；当多AGV路径规划结束后，每项任务的参数固定不变，只有在发生冲突的情况下，优先级低的AGV才需要动态更改其运行路线，以此来避免执行任务的AGV间发生碰撞、死锁冲突和增强AGV的柔性；所述步骤S4中，排布可行路径时间窗，具体步骤包括：步骤S41：时间窗初始化；最短可行路径确定后，在理想条件即无冲突时，为接受任务的AGV排布出可行路径时间窗；由步骤S3中任务m_i找出的最短可行路径λ_i，其是由一系列运行路段组成，用有序路段集合表示，即λ_i＝{e_j,e_k,e_l,…,e_q}，e_j,e_k,e_l,…,e_q∈E，其中，E表示路网中所有可行路段的集合，e_k表示最短可行路径中某一路段，k∈1,2,3,....,q；任务m_i在路段e_k上的时间窗函数定义为：T_w,ik＝(q_i,m_i,r,t_in,k,t_out,k)式中，r表示路段e_k在可行路径λ_i上的位置；t_in,k表示车辆q_i驶入路段e_k的起始时间；t_out,k表示车辆q_i离开路段e_k的时间；对于路段e_k的时间窗，由下式计算得到：t_out,k＝t_in,k+ω_i,k式中，ω_i,k表示AGV通过路段e_k所花费的时间，由下式计算得到：式中，l_i,k表示路段e_k的长度，v表示AGV的运行速度；在实际应用中，由于可行路径的任意有序路段e_k需要被AGV分时使用，因此，有序路段e_k也是由一系列时间窗组成，用有序向量e_k^k＝{T_ω,1j,T_ω,2j,…,T_ω,mj}表示，在有序向量e_k^k中，向量维度与存取车任务数量相同，随时间变化而变化；如果任务m_i在某时刻没有使用路段e_k，则把在该路段的驶入时间t_in,k和驶出时间t_out,k都设置为0；另外，由于任务m_i的最短可行路径是由一系列有序路段组成，而每条有序路段又对应着一个时间窗，因此，任务m_i认为是由一系列时间窗组成，用集合D_i＝{e_kⁱ,e_jⁱ,e_lⁱ…,e_qⁱ}表示；按照步骤S41中所给方程式，为任务m_i的最短可行路径λ_i排布出如集合D_i所示的时间窗分布；步骤S42：时间窗更新，按照步骤S41排布出一条理想情况下的时间窗路径后，然后检查不同任务间可行路径的时间窗是否存在重叠现象；若无重叠现象，则任务m_i的路径规划过程结束；如果当前任务m_i是当前系统中优先级最高的调度任务时，则将步骤S41规划的可行路径时间窗作为任务m_i的最终时间窗，无需再次更新；若有重叠部分，则说明当前任务与其他任务规划出的最短可行路径上至少有一条路段是同时使用的；对于此种现象，则需要系统根据冲突类型，设计合理的冲突避障策略；步骤S43：时间窗的安排；将可行路径各路段对应的无冲突时间窗按照顺序排列，即完成可行路径的时间窗安排；若某一路段e_k存在多个任务的时间窗，则新加入任务在路段e_k上的时间窗的进入时间必须满足条件：①驶入该路段的时间必须大于或等于AGV从上一条路段的离开时间；②该路段的空闲时间窗的长度应大于或等于AGV通过该路段所花费的时间；所述时间窗是指执行存取车任务的AGV从开始进入到离开某个交叉路口或某个路段的整个过程所花费的时间，其主要作用是对AGV已占用的交叉路口或行驶路段进行标记；按照步骤S3和步骤S4，通过循环迭代搜索，依次为接受任务的AGV规划出无冲突最短可行路径时间窗；所述步骤S4中，地面控制系统会实时接收AGV在行使过程中上传的位置、速度及运行状态信息，并根据这些信息，判断AGV是否已经离开某条路段或某个交叉路口，驶向下一路段或交叉路口；如果AGV已经离开某条路段或某个交叉路口，则需从时间窗向量表中删除AGV在该表中注册的信息，从而释放该路段或该交叉路口资源，供其他AGV使用；所述步骤S4中，以避免在该AGV占用的时间段内，被其他AGV使用而引发死锁或碰撞冲突。