基于线性时序逻辑理论的仓储机器人路径规划-禹鑫燚.pdf

《基于线性时序逻辑理论的仓储机器人路径规划-禹鑫燚.pdf》由会员分享，可在线阅读，更多相关《基于线性时序逻辑理论的仓储机器人路径规划-禹鑫燚.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、高技术通讯2016年第26卷第1期：1623doi：103772jissn1002-0470201601003基于线性时序逻辑理论的仓储机器人路径规划禹鑫姨 陈 浩 郭永奎程诚 欧林林俞立(浙江工业大学信息工程学院 杭州310023)摘 要 首先根据仓储物流环境的特点构建了可灵活扩展的仓储环境模型，并制定了适合仓储物流需求的机器人运动规则，使该模型能够适用于动态的仓储物流环境；其次采用线性时序逻辑任务公式描述具体的任务需求，使其可以适用于实际应用中更加复杂的任务；继而将任务需求与环境信息相融合，构建任务可行网络拓扑，避免分段任务搜索；然后采用Dijkstra算法在任务可行网络拓扑上搜索出最优路

2、径，确保规划所得路径的最优性；最后将任务可行网络拓扑上的最优路径映射回加权切换系统，获得环境中满足任务需求的最优路径。与目前广泛使用的A算法相比，上述方法不仅能够满足复杂的任务需求，而且能够保证路径规划的最优性，而不是次优解。关键词路径规划，线性时序逻辑(LTL)，仓储机器人，Dijkstra算法0 引言随着电子商务的飞速发展，传统的仓储物流已无法适应现代物流品种多、批量小、批次多、周期短的特点，而基于移动机器人的自动化仓储物流技术研究了基于线性时序逻辑(LTL)理论规划仓储机器人路径的方法。得到了应用和发展，目前仓储物流业已成为继汽车行业后的第二大机器人应用领域。1。仓储物流机器人的应用可以

3、大大提高电商仓储物流工作的效率，缓解当前仓储物流行业供不应求的现状。机器人应用的目的是提高电商的库存管理能力与配载能力，而实现这样的目的的核心技术是机器人的路径规划。路径规划是指根据当前仓储物流物品种类多、仓储面积大的特点，按照货单需求规划出合理的机器人路径，以提高仓储机器人的作业效率。本研究根据实际应用要求，提出了一种基于线性时序逻辑(1inear temporal logic，LTL)理论的仓储移动机器人路径规划方法，该方法可根据实际的仓储环境和任务需求，规划出符合环境信息的最优路径，确保机器人完成指定任务的运行路径总长度最短，提高仓储工作整体的工作效率。与传统的方法相比，本文所提出的方法

4、在确保规划路径最优的基础上能够较好的适用于仓储物流环境。1 相关研究目前仓储机器人的应用研究主要集中在调度和避碰问题上，对针对具体环境和具体任务的路径规划的研究较少。文献2在传统的A+算法(一类启发式的路径搜索算法)中引人时间参量，将平面二维的A+算法扩展到平面空间加时间的三维时空中，同时引入暂停机制避免机器人之间发生碰撞，结合分层的路径规划算法减少了计算量；文献3将机器人调度与特殊规则约束下基于A算法的路径规划相结合实现了仓储物流机器人集群的智能调度和路径规划；文献4采用改进的遗传算法和SHAA神经网络算法主要解决了多机器人避碰问题；文国家自然科学基金(61273116)，863计划(201

5、4AA041601-05)和浙江省自然科学基金(LYl5F030015)资助项目。男，1979年生，博士(后)；研究方向：机器人控制与规划；E-mail：yuxinyinet163tomE-mail：linlinouzjteducn(收稿13期：2015-1010)一16一万方数据禹鑫皴等：基于线性时序逻辑理论的仓储机器人路径规划献5提出了一种PUSHSWAP的方法来避免多移动机器人之间的碰撞。此外，现有的路径规划方法还有诸如人工势场法旧J、A+算法。卜、快速扩展随机树(rapiddyexploring random tree，RRT)算法。副等都是针对简单的点到点的路径规划任务。然而，上述方

6、法仍然存在很大的瓶颈，无法很好的适用于仓储机器人这类包含多点访问等复杂任务需求的应用中。线性时序逻辑(m)语言一1可以描述仓储物流机器人实际应用中较为复杂的任务需求，诸如在仓库环境中从起点出发先后到若干个货架取货后回到指定点，途中规避某些区域等。目前，基于LTL理论的路径规划方法的研究主要集中在解决旅行商(TSP)问题上，文献10，11采用了最小瓶颈环法解决了单机器人多点巡回的问题；文献12针对传统方法无法直接解决多点最优巡回问题，采用基于扩展乘积自动机的最优巡回算法寻优路径；文献13在传统方法的基础上加入了时序要求，针对两机器人同时巡回某些点的问题，采用了同步序列法生成同步路径以保证两机器人

7、的同时性；文献14将基于LTL理论的路径规划方法扩展到有时间限制的动态环境中。然而，上述方法由于无法灵活的应用于动态的仓储环境、无法保证最优性、计算量大、路径寻优时间长等不足，都无法满足仓储物流机器人的应用需求。2 问题描述机器人的效率与仓储物流系统的运作效率直接相关。因此，需要为仓储机器人设计一种有效的算法来控制机器人按指定任务在仓库中运行，并且能实现路径最优，从而最大限度地提高仓储物流系统的整体运作效率。传统的路径规划方法，诸如A+算法、人工势场法、RRT算法等都需要根据任务节点顺序，按序分段进行规划，规划所得路径受任务节点的数目和顺序影响，无法保证规划所得路径的最优性。本文所采用的基于线

8、性时序逻辑的路径规划方法将环境信息与任务需求相融合，构建任务可行网络拓扑确保了寻优所得路径不受任务节点顺序的影响；此外，采用Dijkstra算法来搜索路径保证了规划所得路径的最优性。3 基于LTL理论的路径规划方法本文采用基于线性时序逻辑理论的路径规划方法寻优路径，其具体算法流程图如图l所示，主要分为环境建模与任务描述和路径寻优两个部分。首先，将机器人运行环境构建为可扩展的加权切换系统；然后，采用线性时序任务公式描述任务需求，并通过LTL2BA工具包将其转换为图表形式(Biichi自动机)15。；接着，将加权切换系统与Btichi自动机作笛卡尔乘积构成任务可行网络拓扑(Product自动机)_

9、6|；之后，采用Dijkstra算法。17。在任务可行网络拓扑上所搜出最优路径；最后，将任务可行网络拓扑上寻优所得路径映射回加权切换系统得到环境中对应的最优路径。路径寻优图l 基于LTL的路径规划方法流程图31环境建模与任务描述由于实际的仓储环境中货架数量非常多，在构一17一万方数据高技术通讯2016年1月第26卷第1期建环境模型时若把所有的货架信息都包含进去，会导致环境模型太过复杂，增加路径规划的计算量。因此，本文构建了一个可灵活扩展的环境模型，选取环境中固定的路径节点构建环境模型，当选定任务货架后再对环境模型进行扩展，以此降低环境模型的复杂度，从而降低计算量。另外，传统的路径规划方法只能针

10、对点到点的路径规划，无法很好地描述仓储物流应用中诸如连续多点访问等复杂任务需求，因而本文采用线性时序任务公式对仓储环境中的任务进行描述，使其能够适用于实际应用中各类复杂的任务需求。假设仓储环境如图2所示，其中带箭头矩形代表机器人，浅灰色矩形代表存放不同货物的各个货架，左上角为仓储机器人起点和出货的柜台，当柜台接到取货单时需要规划出最优的取货路径，然后让机器人按指定路径去取货，如图2所示深灰色矩形为货单上货物对应的货架。 机爹ll黑-_-l_l_目标赞架 目标货架一一图2模拟仓库环境示意图本文将机器人在环境当中的运动建立成一个可灵活扩展的加权切换系统模型。加权切换系统模型一博1是一种图表，它以环

11、境中的关键位置为节点，如果机器人能从一个位置行驶至另一个位置，则这两个节点问有边相连。每条边都标有相应的权值，表示机器人从一个节点行驶至另一个节点的成本。本文用一个元组T=(Q，q。，R，兀，f，) (1)来表示机器人运行环境对应的加权切换系统模型。其中，Q为一个有限状态集，其每一个状态代表环境中道路网络的一个节点；q。Q代表初始状态，即机器人在环境中所处的初始节点；RQQ代表切换关系，即环境中节点问的连通状态；H为一个原子命题集合；f：Q一2Il是状态的命题函数；甜：RR，。代表切换权重，代表机器人在环境中从一1 R一一个节点切换到另一节点所需的成本(如运行时间、路径长度等)。以图3所示的模

12、拟仓库环境模型为例，其中pl为起点，p2为终点，空白矩形代表各个存放不同货物的货架。仓储机器人需要从起点出发，到指定货架取货后将货物送回到终点。本文选取仓库环境中的22个关键节点作为路径节点，其中节点pl和p2分别表示机器人的起点和终点，即仓库接单和出货的柜台。通过一个2222的邻接矩阵z n巧来描述各节点间的连通情况，以及任意两节点间的切换成本，即机器人需要运行的距离，其中z a,j的每一行都代表该行对应节点与其他节点的连通情况即切换成本。如r口孝的第一行第二列代表节点pl到节点p2的连通情况和切换成本，第二行第_-y0代表节点p2到节点p3的连通情况和切换成本，依此类推。7p3、，卜一一p

13、8、皤_-一川3卜_名l手工口口口口口：I口口口口口军口口口口口L一 !口口口口口!口口口口口主口口口口口，IPI卜一p4一爿碍，i口口口口口口口口口口i口口口口口：!口口口口口夏口口口口口主口口口口口叟ip5，I、P10一一P15崎一0恐口口ooo奉口口口口口罩口口口口口，口口UUU主口口口口口叟口口口口口，p乏+ip6：|一ll_p1分I一一如2l，口口口口口I口口口口口五口口口口口_!口口口口0毫口口口口口主口口口口口叟j芝一 y哆_ 一型一 巴图3模拟仓库环境模型然后，当仓库接到货单时，根据货单上的货物所在的货架选取对应的货架节点，选定目标货架后的环境模型如图4所示，深灰色货架即为机器

14、人需要取货的货架，浅灰色节点即为货架对应的路径节点。；l匐口口口口￥口口口口主“p19、口口口口萃麟口口口口士一；2订口口口口萃口口口口司图4选定目标货架后的环境模型卜璺攀万方数据禹鑫皴等：基于线性时序逻辑理论的仓储机器人路径规划根据任务货架节点数量扩展邻接矩阵r o巧，以图4所示的任务为例，需要将r西扩展为2525的方阵。同时，当仓库接到货单选定任务货架后，需要对任务进行描述。本文采用线性时序逻辑(LTL)公式来描述仓储物流机器人需要完成的复杂任务需求。线性时序逻辑公式咖是由原子命题兀的子集组成的表达式，其中还包含了布尔算子，(非)、八(与)、V(或)，以及时序逻辑算子G(始终)、F(最终)

15、、x(接下来)和u(直到)。例如，G P。表示71中状态P。始终为真；FP。表示最终达到丁中的状态P，；xP。表示接下来到达丁中的状态P；公式P。UP：表示当到达P。状态时，必须到达状态P：才能前往下一个状态。将这些时序和布尔算子组合可以描述更为复杂的任务需求。以图4为例，任务需求：“机器人从pl节点出发，先后到p23、p24和p25这三个节点取货，然后回到p2节点将取回的货物打包出仓”。采用线性时序逻辑任务公式可以描述为即1&Fp23&Fp24&Fp25&GFp2 (2)其中，起点TqO=pl。32路径寻优在得到式(2)所示的任务公式后，首先，采用LTL2BA工具包将其转换为图表的形式(Bi

16、ichi自动机)。由于任务式(2)转换后的图表较为复杂，这里以任务公式唧l&Fp2&GFp3 (3)为例。假设机器人从pl出发，到p2取货后最终回到p3。图5即为式(3)转换后的结果。环境模型以图6所示的加权切换系统图为例，可以用一个4 X4的邻接矩阵来描述各节点间的连通情况，以及任意两节点间的切换成本。然后，将转换所得Btichi自动机与加权切换系统作笛卡尔乘积，得到任务可行网络拓扑(Product自动机)。图7所示即为图6所示加权切换系统与图5所示Btichi自动机作笛卡尔乘积后所得的任务可行网络拓扑，该拓扑包含了环境信息和任务需求。其中，第一行包含s。的状态为初始状态，最后一行包含S。的

17、状态为最终的接收状态。图5式(2)对应的Biichi自动机图6加权切换系统例图图7任务可行网络拓扑一19一天鲜万方数据高技术通讯2016年1月第26卷第1期接着，采用Dijkstra算法在任务可行网络拓扑上搜索出从起始状态到接收状态的最优路径。如图7中实线箭头所示路径即为采用Dijkstra算法在任务可行网络拓扑上搜索从初始状态到最终状态实验所得路径结果，即(P。，s。)一(P：，s。)一(P。，s，)_(P，s，)，其中状态S，与状态S。之间的切换为式(3)中G即3部分的自循环，所以可以忽略不计。从图中可以看出该路径的总权重值是最小的，且路径节点数是最少的，因此规划所得路径是最优的。由于DO

18、kstra算法实质是广度优先搜索，因此可以确保路径的最优性。最后，在得到任务可行网络拓扑上的最优路径后，还需将其映射回初始的加权切换系统中，得到仓库环境中完成指定任务的最优路径，于是引入如下引理：引理l(Product自动机路径映射)H列对于任务可行网络拓扑上的任意路径rP=(P。，s。)(P。，s。)(P：，s：)，路径序列r，=PoP。P：为加权切换系统中对应的满足任务需求的路径，且r，和r，所对应的权重相等。根据引理l，路径po_p：一p。_p，即为图7所示的任务可行网络拓扑上最优路径映射回图6所示的加权切换系统后所得路径，即图6所示的环境模型中满足任务公式(3)的最优路径。其具体算法如

19、下：输入：仓储环境对应的加权切换系统模型r；输出：仓库环境中满足任务需求的最优路径r，；1)选定任务货架；2)根据选取的目标货架扩展加权切换系统模型r，用线性时序任务公式西描述任务需求；3)将线性时序任务公式中转换为图表的形式，即Bfichi自动机B=LTL2BA(咖)；4)构建任务可行网络拓扑P=T o B；5)采用Dijkatra算法在任务可行网络拓扑P上搜索出一条从初始状态到最终状态的最优路径r尸；6)将P上寻优所得路径。映射回加权切换系统，得到仓库环境中满足任务需求的最优路径r，。一204 仿真实验为了验证上述方法的可行性与有效性，本文在MATLAB中采用GUI编程对上述方法进行了仿真

20、验证，其程序操作界面如图8所示，图中的模拟仓库环境对应的模拟仓库环境模型如图3所示。其中，起点代表仓储机器人的起始位置，对应图3中的p1节点；终点代表仓储机器人完成取货后需要到达的最终位置，对应图3中的p2节点；界面中的小正方形代表仓库中存放货物的货架，仓储机器人需要按照需求到指定的货架取货，若需要仓储机器人到该货架取货则用鼠标左键单击选中对应货架；若环境中某一路径节点发生变化无法继续通行，则用鼠标右键单击对应位置，将其标记为障碍物；在选取好任务货架和障碍物节点后点击“规划路径”按键进行路径寻优一图8仿真程序操作界面示意图在图3所示的仓储环境模型中，任意指定7个任务货架，如图9中深灰色矩形所示

21、，选取的顺序为从上到下，从左到右。机器人需要从pl节点出发，分别到p23、p24、p25、p26、p27、p28和p29这7个节点对应的货架取货，然后将货物送回到p2。首先，将图3所示的包含22节点的仓储环境模型扩展到29节点，对应的2222的邻接矩阵r口巧也扩展为2929的方阵；其次，采用线性时序任务公式描述给定的任务需求，如下式所示：Fpl&Fp23&Fp24&Fp25&Fp26&Fp27&Fp28&Fp29&GFp2 (4)万方数据禹鑫皴等：基于线性时序逻辑理论的仓储机器人路径规划然后，将式(4)转换为Btichi自动机B；接着，将环境对应的加权切换系统T与B作笛卡尔乘积，构建任务可行网

22、络拓扑P；然后，采用Dijkstra算法在P上搜索出最优路径；最后，将P上寻优所得路径映射回加权切换系统，获得环境中对应的最优路径。图9中深灰色直线即为寻优所得路径。从图中可以看出基于线性时序逻辑理论的仓储机器人路径规划方法能够规划出既符合环境信息，又满足任务需求的最优路径。口口口口口 。ooJoo、 口口loo卿oo 口口口口口 口口f、 ， 、 、 旦固篓固口口口口口口 口口I口口口口口口口口口口 口口i9七29 )l口口口口口口口口口 口口l口口口口口口口口口口 口口Iv r一7 v 、口口口口口口口口口 口口【口口口口口口口口口口 口口l图9本文方法规划所得路径接下来，本文将上述方法与

23、传统方法做进一步的仿真比较。目前已有的路径规划方法有很多，但基本都针对“从a点到b点，途中避开障碍物”这类简单的任务，对于仓储机器人这类需要从起点出发，到多点取货后回到终点的复杂需求还无法得到很好的解决。本文以目前应用较为普遍的A+算法为例。A+算法是一类启发式的路径搜索算法，从起点开始逐渐向目标点靠近，它在Dijkstra算法的基础上引入启发函数来筛选访问节点，从而降低了计算量，提高了搜索效率。但是启发函数选取好坏直接关系到A算法的搜索速度和搜索精度。本文取A算法的代价函数如公式fo=g。+h，。 (5)所示，其中工为机器人从起点经过节点I1到达目标节点的估价函数，g。为起点到节点n的实际成

24、本，h。为节点n到目标节点的启发式评估代价。本文使用公式h。=abs(n石一targetz)+abs(ItYtargetY)(6)所示的曼哈顿距离作为h。，其中(Itz，nY)表示节点n的横纵坐标，(target戈，targetY)表示目标节点的横纵坐标，abs表示求绝对值的函数。针对图9所示任务，同样按照从上到下，从左到右的顺序选取任务货架，采用A+算法规划所得路径如图10所示。当选取货架的顺序发生变化时，采用A+算法规划的路径也会随之变化。对比图9和图10可以看出，基于LTL理论的仓储机器人路径规划方法寻优所得路径明显优于A算法规划所得路径，且基于LTL理论的仓储机器人路径规划方法与任务顺

25、序无关，始终能够确保规划所得路径的最优性。图10 A 4算法规划所得路径此外，A算法只能针对“从a点到b点，途中避开障碍物”等这类简单任务，且当原有的已知环境中出现障碍物时需要对环境模型作相应的修改，实现起来较为繁琐。而基于LTL理论的路径规划方法可以很好地描述实际应用中较为复杂的任务需求，诸如始终保持一定的范围之内(安全性)，按序访问某几个点(保证性)后，巡回访问某几个点(循环性)，图中避开某些点(避障)，到达某些点后必须到达另外一些点才能继续任务(反应性)等。如图4所示的环境和任务，当节点14畅通时采用基于线性时序逻辑路径规划方法规划所得路径和采用A算法规划所得路径相同，结果如图11所示。

26、但当节点p14出现突发状况(节点p14所示区域遇堵等)机器人无法通过时，采用A+算法进行规划时需要将环境模型中节点p14标记为障碍物，对原有的环境模型进行修改；而采用基于LTL的路径规划方法则只需要在选取任务货架的同时将节点p14标一21万方数据高技术通讯2016年1月第26卷第1期记为障碍物，则对应生成的任务公式为唧1&Fp23&Fe24&Fp25&GFp2&G-,p14 (7)其规划所得路径如图12所示，绕开了无法通过的节点p14，仍然可以确保规划所得路径的最优性。图ll 节点p14畅通规划结果图12节点p14遇阻规划结果其它仓储机器人路径规划算法在上述的对比实验中与A+算法类似，需要对任

27、务进行分段路径寻优，规划所得路径与任务节点顺序有关，无法保证最优性；当环境发生变化时需要根据当前环境对原有的环境模型进行修改，相比之下本文所提出的方法能够更好地适用于仓储机器人的应用。5 结论随着电子商务的飞速发展，各大电商对基于移动机器人的自动化仓储物流技术的需求越来越迫切。本文对仓储物流机器人路径规划方法的研究与应用进行了探索：建立了一个可灵活扩展的仓储环境模型，有效地描述了仓储物流应用中的各类任务需求，并将仓储环境信息与任务需求相融合，从而规一22一划出既满足任务需求又符合环境信息的最优路径。实验结果表明，与传统方法相比，本文的方法不仅可以灵活地扩展环境模型，而且能够更好地适应实际应用中

28、较为复杂的任务，较传统的路径规划方法的适用性更强，适用范围更广；此外，本文所提出的方法无需对任务进行分段的点到点规划，与任务节点的顺序无关，保证了规划所得路径的最优性。因此，基于LTL理论的仓储机器人路径规划方法能够满足实际的应用需求，大大提高仓储物流机器人的工作效率。本文主要探究了仓储物流机器人的路径规划问题，未来还可以拓展到多机器人领域，实现一套高度自动化的仓储物流机器人系统，更好地将机器人应用到仓储物流领域中去。参考文献1邹爽心仓储机器人的应用现状与发展战略探讨物流工程与管理，2013，35(6)：171-1722王勇智能仓库系统多移动机器人路径规划研究：硕士学位论文哈尔滨：哈尔滨工业大

29、学，20103沈博闻，于宁波，刘景泰仓储物流机器人集群的智能调度和路径规划智能系统学报，2014，6(9)：659-6644王戌智能仓库多移动机器人的路径规划研究：硕士学位论文大连：大连交通大学，20145LLula R，Bekris K EEfficient and complete centralizedmultirobot path planningIn：Proceedings of the 201 lIEEERSJ Intemational Conference on Intelligent Robotsand Systems(IROS)，San Francisco，USA，201 1

30、3268-32756Lee M C，Park M GArtificial potential field based pathplanning for mobile robots using a virtual obstacle COIlceptIn：Proceedings of the 2003 IEEEASME Intelli-gent Conference on Advanced Intelligent Mechatronics，Port Island，Kobe，Japan，2003735-7407Zhang S P，Wang X K，Duan JApplication of astar

31、 algorithm in mobile robot path planningMechanical EngineeringAutomation，20126：0598Lavalle S MRapidlyexploring random trees：a new toolfor path planningAlgorithmic&Computational RobotwsNew Directions，1998：293-3089Fmnekos G E，Kress-Gazit H，Pappas G JTemporal log万方数据 禹鑫皴等：基于线性时序逻辑理论的仓储机器人路径规划ic motion

32、planning for mobile robotsIn：Proceedings ofthe 2005 IEEE International Conference on Robotics andAutomation，Baecelona，Spain，20052020-202510Smith S，Tumova J，Beha C，et a1Optimal path planning for surveillance with temporal logic constraintsTheInternational Journal of Robotics Research201 l，30(14)：695-

33、170811Smith S，Tumova J，Beha C，et a1Optimal path planning under temporal logic constraintsIn：Proceedings ofInternational Conference on Intelligent Robots and Sys-tems，Taipei，China，20103288-329312肖云涛，欧林林，俞立基于线性时序逻辑的最优巡回路径规划自动化学报，2014，10(10)：2126-213313Ulusoy A，Smith S L，Ding X C，et a1Optimality androb

34、ustness in multirobot path planning with temporal log-ic constraintsInternational Journal of Robotics Research，2013，32(8)：889-91114Maity D，Baras J SMotion planning in dynamic environments with bounded time temporal logic specificationsIn：Proeeedigns of the 23th Mediterranean Conference onControl and

35、 Automation(MED)，Torremohnos，Spain，2015940-94615Gastin P，Oddoux DFast LTL to Btichi Automata TranslationIn：Computer Aided Verification，Heidelberg，Germany：Springer Berlin，200153-6516Kloetzer M，Beha CA fully automated framework forcontrol of linear systems from temporal logic specicationsIEEE Transact

36、ions On Automatic Controf，2008，53(1)：28729717Yang YAn efficient implementation of shortest path algorithm based on Dijkstra AlgorithmJournal of WuhanTechnical University of Surveying&Mapping，1 999，24(3)：209-21218Belta C，lsler V，Pappas G JDiscrete abstractions forrobot motion planning and control in

37、polygonal environmentsIEEE Transactions on Robotics，2005，21(5)：86487419Smith S L，Tumov6 J，Beha C，et a1Optimal path planning for surveillance with temporal-logic constraintsTheInternational Journal of Robotics Research，201 1，30(14)：16951708Path planing of warehouse robots based on linear temporal log

38、icYu Xinyi，Chen Hao，Guo Yongkui，Cheng Cheng，Ou Linlin，Yu Li(College of Information Engineering，Zhejiang University of Technology，Hangzhou 3 10023)AbstractThe path planning for warehouse robots based on the linear temporal logic(LTL)theory was studiedFirstly，an extensible warehouse model was built up

39、 according to warehouse environmental characteristics，and a set of rulesfor governing robot movements were defined to make the model adapt dynamic warehouse environmentsSecondly，the LTL formula was used to describe task requirements to make it suitable for more complicated tasks in practicalapplicat

40、ionsThirdly，the task-feasible network topology was built by combining task requirements and environmental information to avoid piecewise path searchingThen，the Dijkstra algorithm was utilized to search the global op-timal path on the taskfeasible network topology to ensure the optimality of the path

41、 planning resultFinally，theoptimized path was obtained by mapping the optimal path on the task feasible network topology back to the warehouse modelThe above-mentioned method can not only satisfy complex task requirements，but also can ensure theoptimality of the path planning result，rather than a suboptimal solution，compared with the current widely used A+algorithmKey words：path planning，linear temporal logic(U1L)，warehouse robot，Dijkstra algorithm一23万方数据