基于线性时序逻辑理论的仓储机器人路径规划①

禹鑫燚 陈 浩 郭永奎 程 诚 欧林林 俞 立



基于线性时序逻辑理论的仓储机器人路径规划①

禹鑫燚②陈 浩 郭永奎 程 诚 欧林林③俞 立

(浙江工业大学信息工程学院 杭州 310023)

首先根据仓储物流环境的特点构建了可灵活扩展的仓储环境模型，并制定了适合仓储物流需求的机器人运动规则，使该模型能够适用于动态的仓储物流环境；其次采用线性时序逻辑任务公式描述具体的任务需求，使其可以适用于实际应用中更加复杂的任务；继而将任务需求与环境信息相融合，构建任务可行网络拓扑，避免分段任务搜索；然后采用Dijkstra算法在任务可行网络拓扑上搜索出最优路径，确保规划所得路径的最优性；最后将任务可行网络拓扑上的最优路径映射回加权切换系统，获得环境中满足任务需求的最优路径。与目前广泛使用的A*算法相比，上述方法不仅能够满足复杂的任务需求，而且能够保证路径规划的最优性，而不是次优解。

路径规划， 线性时序逻辑(LTL)， 仓储机器人，Dijkstra算法

0 引 言

随着电子商务的飞速发展，传统的仓储物流已无法适应现代物流品种多、批量小、批次多、周期短的特点，而基于移动机器人的自动化仓储物流技术研究了基于线性时序逻辑(LTL)理论规划仓储机器人路径的方法。得到了应用和发展，目前仓储物流业已成为继汽车行业后的第二大机器人应用领域[1]。仓储物流机器人的应用可以大大提高电商仓储物流工作的效率，缓解当前仓储物流行业供不应求的现状。机器人应用的目的是提高电商的库存管理能力与配载能力，而实现这样的目的的核心技术是机器人的路径规划。路径规划是指根据当前仓储物流物品种类多、仓储面积大的特点，按照货单需求规划出合理的机器人路径，以提高仓储机器人的作业效率。本研究根据实际应用要求，提出了一种基于线性时序逻辑(lineartemporallogic,LTL)理论的仓储移动机器人路径规划方法，该方法可根据实际的仓储环境和任务需求，规划出符合环境信息的最优路径，确保机器人完成指定任务的运行路径总长度最短，提高仓储工作整体的工作效率。与传统的方法相比，本文所提出的方法在确保规划路径最优的基础上能够较好的适用于仓储物流环境。

1 相关研究

目前仓储机器人的应用研究主要集中在调度和避碰问题上，对针对具体环境和具体任务的路径规划的研究较少。文献[2]在传统的A*算法(一类启发式的路径搜索算法)中引入时间参量，将平面二维的A*算法扩展到平面空间加时间的三维时空中，同时引入暂停机制避免机器人之间发生碰撞，结合分层的路径规划算法减少了计算量；文献[3]将机器人调度与特殊规则约束下基于A*算法的路径规划相结合实现了仓储物流机器人集群的智能调度和路径规划；文献[4]采用改进的遗传算法和SHAA神经网络算法主要解决了多机器人避碰问题；文献[5]提出了一种PUSH-SWAP的方法来避免多移动机器人之间的碰撞。此外，现有的路径规划方法还有诸如人工势场法[6]、A*算法[7]、快速扩展随机树(rapiddy-exploringrandomtree,RRT)算法[8]等都是针对简单的点到点的路径规划任务。然而，上述方法仍然存在很大的瓶颈，无法很好的适用于仓储机器人这类包含多点访问等复杂任务需求的应用中。

线性时序逻辑(LTL)语言[9]可以描述仓储物流机器人实际应用中较为复杂的任务需求，诸如在仓库环境中从起点出发先后到若干个货架取货后回到指定点，途中规避某些区域等。目前，基于LTL理论的路径规划方法的研究主要集中在解决旅行商(TSP)问题上，文献[10,11]采用了最小瓶颈环法解决了单机器人多点巡回的问题；文献[12]针对传统方法无法直接解决多点最优巡回问题，采用基于扩展乘积自动机的最优巡回算法寻优路径；文献[13]在传统方法的基础上加入了时序要求，针对两机器人同时巡回某些点的问题，采用了同步序列法生成同步路径以保证两机器人的同时性；文献[14]将基于LTL理论的路径规划方法扩展到有时间限制的动态环境中。然而，上述方法由于无法灵活的应用于动态的仓储环境、无法保证最优性、计算量大、路径寻优时间长等不足，都无法满足仓储物流机器人的应用需求。

2 问题描述

机器人的效率与仓储物流系统的运作效率直接相关。因此，需要为仓储机器人设计一种有效的算法来控制机器人按指定任务在仓库中运行，并且能实现路径最优，从而最大限度地提高仓储物流系统的整体运作效率。

传统的路径规划方法，诸如A*算法、人工势场法、RRT算法等都需要根据任务节点顺序，按序分段进行规划，规划所得路径受任务节点的数目和顺序影响，无法保证规划所得路径的最优性。本文所采用的基于线性时序逻辑的路径规划方法将环境信息与任务需求相融合，构建任务可行网络拓扑确保了寻优所得路径不受任务节点顺序的影响；此外，采用Dijkstra算法来搜索路径保证了规划所得路径的最优性。

3 基于LTL理论的路径规划方法

本文采用基于线性时序逻辑理论的路径规划方法寻优路径，其具体算法流程图如图1所示，主要分为环境建模与任务描述和路径寻优两个部分。首先，将机器人运行环境构建为可扩展的加权切换系统；然后，采用线性时序任务公式描述任务需求，并通过LTL2BA工具包将其转换为图表形式(Büchi自动机)[15]；接着，将加权切换系统与Büchi自动机作笛卡尔乘积构成任务可行网络拓扑(Product自动机)[16]；之后，采用Dijkstra算法[17]在任务可行网络拓扑上所搜出最优路径；最后，将任务可行网络拓扑上寻优所得路径映射回加权切换系统得到环境中对应的最优路径。

图1 基于LTL的路径规划方法流程图

3.1 环境建模与任务描述

由于实际的仓储环境中货架数量非常多，在构建环境模型时若把所有的货架信息都包含进去，会导致环境模型太过复杂，增加路径规划的计算量。因此，本文构建了一个可灵活扩展的环境模型，选取环境中固定的路径节点构建环境模型，当选定任务货架后再对环境模型进行扩展，以此降低环境模型的复杂度，从而降低计算量。另外，传统的路径规划方法只能针对点到点的路径规划，无法很好地描述仓储物流应用中诸如连续多点访问等复杂任务需求，因而本文采用线性时序任务公式对仓储环境中的任务进行描述，使其能够适用于实际应用中各类复杂的任务需求。

假设仓储环境如图2所示，其中带箭头矩形代表机器人，浅灰色矩形代表存放不同货物的各个货架，左上角为仓储机器人起点和出货的柜台，当柜台接到取货单时需要规划出最优的取货路径，然后让机器人按指定路径去取货，如图2所示深灰色矩形为货单上货物对应的货架。

图2 模拟仓库环境示意图

本文将机器人在环境当中的运动建立成一个可灵活扩展的加权切换系统模型。加权切换系统模型[18]是一种图表，它以环境中的关键位置为节点，如果机器人能从一个位置行驶至另一个位置，则这两个节点间有边相连。每条边都标有相应的权值，表示机器人从一个节点行驶至另一个节点的成本。本文用一个元组

T=(Q,q0,R, ∏,ζ,ω)

(1)

来表示机器人运行环境对应的加权切换系统模型。其中，Q为一个有限状态集，其每一个状态代表环境中道路网络的一个节点；q0∈Q代表初始状态，即机器人在环境中所处的初始节点；R⊆Q×Q代表切换关系，即环境中节点间的连通状态；∏为一个原子命题集合；ζ:Q→2∏是状态的命题函数；ω:R→>0代表切换权重，代表机器人在环境中从一个节点切换到另一节点所需的成本(如运行时间、路径长度等)。

以图3所示的模拟仓库环境模型为例，其中p1为起点，p2为终点，空白矩形代表各个存放不同货物的货架。仓储机器人需要从起点出发，到指定货架取货后将货物送回到终点。本文选取仓库环境中的22个关键节点作为路径节点，其中节点p1和p2分别表示机器人的起点和终点，即仓库接单和出货的柜台。通过一个22×22的邻接矩阵T.adj来描述各节点间的连通情况，以及任意两节点间的切换成本，即机器人需要运行的距离，其中T.adj的每一行都代表该行对应节点与其他节点的连通情况即切换成本。如T.adj的第一行第二列代表节点p1到节点p2的连通情况和切换成本，第二行第三列代表节点p2到节点p3的连通情况和切换成本，依此类推。

图3 模拟仓库环境模型

然后，当仓库接到货单时，根据货单上的货物所在的货架选取对应的货架节点，选定目标货架后的环境模型如图4所示，深灰色货架即为机器人需要取货的货架，浅灰色节点即为货架对应的路径节点。

图4 选定目标货架后的环境模型

根据任务货架节点数量扩展邻接矩阵T.adj，以图4所示的任务为例，需要将T.adj扩展为25×25的方阵。

同时，当仓库接到货单选定任务货架后，需要对任务进行描述。本文采用线性时序逻辑(LTL)公式来描述仓储物流机器人需要完成的复杂任务需求。线性时序逻辑公式φ是由原子命题∏的子集组成的表达式，其中还包含了布尔算子(非)、∧(与)、∨(或)，以及时序逻辑算子G(始终)、F(最终)、X(接下来)和U(直到)。例如，Gp1表示T中状态p1始终为真；Fp1表示最终达到T中的状态p1；Xp1表示接下来到达T中的状态p1；公式p1Up2表示当到达p1状态时，必须到达状态p2才能前往下一个状态。将这些时序和布尔算子组合可以描述更为复杂的任务需求。

以图4为例，任务需求：“机器人从p1节点出发，先后到p23、p24和p25这三个节点取货，然后回到p2节点将取回的货物打包出仓”。采用线性时序逻辑任务公式可以描述为

Fp1&Fp23&Fp24&Fp25&GFp2

(2)

其中，起点T.q0=p1。

3.2 路径寻优

在得到式(2)所示的任务公式后，首先，采用LTL2BA工具包将其转换为图表的形式(Büchi自动机)。由于任务式(2)转换后的图表较为复杂，这里以任务公式

Fp1&Fp2&GFp3

(3)

为例。假设机器人从p1出发，到p2取货后最终回到p3。图5即为式(3)转换后的结果。环境模型以图6所示的加权切换系统图为例，可以用一个4×4的邻接矩阵来描述各节点间的连通情况，以及任意两节点间的切换成本。

然后，将转换所得Büchi自动机与加权切换系统作笛卡尔乘积，得到任务可行网络拓扑(Product自动机)。图7所示即为图6所示加权切换系统与图5所示Büchi自动机作笛卡尔乘积后所得的任务可行网络拓扑，该拓扑包含了环境信息和任务需求。其中，第一行包含S0的状态为初始状态，最后一行包含S4的状态为最终的接收状态。

图5 式(2)对应的Büchi自动机

图6 加权切换系统例图

图7 任务可行网络拓扑

接着，采用Dijkstra算法在任务可行网络拓扑上搜索出从起始状态到接收状态的最优路径。如图7中实线箭头所示路径即为采用Dijkstra算法在任务可行网络拓扑上搜索从初始状态到最终状态实验所得路径结果，即(p0,s0)→(p2,s0)→(p1,s1)→(p3,s3)，其中状态S3与状态S4之间的切换为式(3)中GFp3部分的自循环，所以可以忽略不计。从图中可以看出该路径的总权重值是最小的，且路径节点数是最少的，因此规划所得路径是最优的。由于Dijkstra算法实质是广度优先搜索，因此可以确保路径的最优性。

最后，在得到任务可行网络拓扑上的最优路径后，还需将其映射回初始的加权切换系统中，得到仓库环境中完成指定任务的最优路径，于是引入如下引理：

引理1 (Product自动机路径映射)[19]对于任务可行网络拓扑上的任意路径rP=(p0,s0)(p1,s1)(p2,s2)…，路径序列rT=p0p1p2…为加权切换系统中对应的满足任务需求的路径，且rP和rT所对应的权重相等。

根据引理1，路径p0→p2→p1→p3即为图7所示的任务可行网络拓扑上最优路径映射回图6所示的加权切换系统后所得路径，即图6所示的环境模型中满足任务公式(3)的最优路径。

其具体算法如下：

输入：仓储环境对应的加权切换系统模型T；

输出：仓库环境中满足任务需求的最优路径rT；

1) 选定任务货架；

2) 根据选取的目标货架扩展加权切换系统模型T，用线性时序任务公式φ描述任务需求；

3) 将线性时序任务公式φ转换为图表的形式，即Büchi自动机B=LTL2BA(φ)；

4) 构建任务可行网络拓扑P=T⊗B；

5) 采用Dijkatra算法在任务可行网络拓扑P上搜索出一条从初始状态到最终状态的最优路径rP；

6) 将P上寻优所得路径rP映射回加权切换系统，得到仓库环境中满足任务需求的最优路径rT。

4 仿真实验

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

图8 仿真程序操作界面示意图

在图3所示的仓储环境模型中，任意指定7个任务货架，如图9中深灰色矩形所示，选取的顺序为从上到下，从左到右。机器人需要从p1节点出发，分别到p23、p24、p25、p26、p27、p28和p29这7个节点对应的货架取货，然后将货物送回到p2。

首先，将图3所示的包含22节点的仓储环境模型扩展到29节点，对应的22×22的邻接矩阵T.adj也扩展为29×29的方阵；其次，采用线性时序任务公式描述给定的任务需求，如下式所示：

Fp1&Fp23&Fp24&Fp25&Fp26&

Fp27&Fp28&Fp29&GFp2

(4)

然后，将式(4)转换为Büchi自动机B；接着，将环境对应的加权切换系统T与B作笛卡尔乘积，构建任务可行网络拓扑P；然后，采用Dijkstra算法在P上搜索出最优路径；最后，将P上寻优所得路径映射回加权切换系统，获得环境中对应的最优路径。图9中深灰色直线即为寻优所得路径。从图中可以看出基于线性时序逻辑理论的仓储机器人路径规划方法能够规划出既符合环境信息，又满足任务需求的最优路径。

图9 本文方法规划所得路径

接下来，本文将上述方法与传统方法做进一步的仿真比较。目前已有的路径规划方法有很多，但基本都针对“从a点到b点，途中避开障碍物”这类简单的任务，对于仓储机器人这类需要从起点出发，到多点取货后回到终点的复杂需求还无法得到很好的解决。本文以目前应用较为普遍的A*算法为例。

A*算法是一类启发式的路径搜索算法，从起点开始逐渐向目标点靠近，它在Dijkstra算法的基础上引入启发函数来筛选访问节点，从而降低了计算量，提高了搜索效率。但是启发函数选取好坏直接关系到A*算法的搜索速度和搜索精度。本文取A*算法的代价函数如公式

fn=gn+hn

(5)

所示，其中fn为机器人从起点经过节点n到达目标节点的估价函数，gn为起点到节点n的实际成本，hn为节点n到目标节点的启发式评估代价。本文使用公式

hn=abs(n.x-target.x)+abs(n.y-target.y)

(6)

所示的曼哈顿距离作为hn，其中(n.x,n.y)表示节点n的横纵坐标，(target.x,target.y)表示目标节点的横纵坐标，abs表示求绝对值的函数。

针对图9所示任务，同样按照从上到下，从左到右的顺序选取任务货架，采用A*算法规划所得路径如图10所示。当选取货架的顺序发生变化时，采用A*算法规划的路径也会随之变化。对比图9和图10可以看出，基于LTL理论的仓储机器人路径规划方法寻优所得路径明显优于A*算法规划所得路径，且基于LTL理论的仓储机器人路径规划方法与任务顺序无关，始终能够确保规划所得路径的最优性。

图10 A*算法规划所得路径

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

如图4所示的环境和任务，当节点14畅通时采用基于线性时序逻辑路径规划方法规划所得路径和采用A*算法规划所得路径相同，结果如图11所示。但当节点p14出现突发状况(节点p14所示区域遇堵等)机器人无法通过时，采用A*算法进行规划时需要将环境模型中节点p14标记为障碍物，对原有的环境模型进行修改；而采用基于LTL的路径规划方法则只需要在选取任务货架的同时将节点p14标记为障碍物，则对应生成的任务公式为

Fp1&Fp23&Fp24&Fp25&GFp2&Gp14

(7)

其规划所得路径如图12所示，绕开了无法通过的节点p14，仍然可以确保规划所得路径的最优性。

图11 节点p14畅通规划结果

图12 节点p14遇阻规划结果

其它仓储机器人路径规划算法在上述的对比实验中与A*算法类似，需要对任务进行分段路径寻优，规划所得路径与任务节点顺序有关，无法保证最优性；当环境发生变化时需要根据当前环境对原有的环境模型进行修改，相比之下本文所提出的方法能够更好地适用于仓储机器人的应用。

5 结 论

随着电子商务的飞速发展，各大电商对基于移动机器人的自动化仓储物流技术的需求越来越迫切。本文对仓储物流机器人路径规划方法的研究与应用进行了探索：建立了一个可灵活扩展的仓储环境模型，有效地描述了仓储物流应用中的各类任务需求，并将仓储环境信息与任务需求相融合，从而规划出既满足任务需求又符合环境信息的最优路径。实验结果表明，与传统方法相比，本文的方法不仅可以灵活地扩展环境模型，而且能够更好地适应实际应用中较为复杂的任务，较传统的路径规划方法的适用性更强，适用范围更广；此外，本文所提出的方法无需对任务进行分段的点到点规划，与任务节点的顺序无关，保证了规划所得路径的最优性。因此，基于LTL理论的仓储机器人路径规划方法能够满足实际的应用需求，大大提高仓储物流机器人的工作效率。

本文主要探究了仓储物流机器人的路径规划问题，未来还可以拓展到多机器人领域，实现一套高度自动化的仓储物流机器人系统，更好地将机器人应用到仓储物流领域中去。

[ 1] 邹爽心. 仓储机器人的应用现状与发展战略探讨. 物流工程与管理, 2013, 35(6): 171-172

[ 2] 王勇. 智能仓库系统多移动机器人路径规划研究: [硕士学位论文]. 哈尔滨: 哈尔滨工业大学, 2010

[ 3] 沈博闻, 于宁波, 刘景泰. 仓储物流机器人集群的智能调度和路径规划. 智能系统学报, 2014, 6(9): 659-664

[ 4] 王戌. 智能仓库多移动机器人的路径规划研究: [硕士学位论文]. 大连: 大连交通大学, 2014

[ 5]LunaR,BekrisKE.Efficientandcompletecentralizedmulti-robotpathplanning.In:Proceedingsofthe2011IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems(IROS),SanFrancisco,USA, 2011. 3268-3275

[ 6]LeeMC,ParkMG.Artificialpotentialfieldbasedpathplanningformobilerobotsusingavirtualobstacleconcept.In:Proceedingsofthe2003IEEE/ASMEIntelligentConferenceonAdvancedIntelligentMechatronics,PortIsland,Kobe,Japan, 2003. 735-740

[ 7]ZhangSP,WangXK,DuanJ.Applicationofa-staralgorithminmobilerobotpathplanning.MechanicalEngineering&Automation, 2012, 6: 059

[ 8]LavalleSM.Rapidly-exploringrandomtrees:anewtoolforpathplanning.Algorithmic&ComputationalRoboticsNewDirections, 1998: 293-308

[ 9]FainekosGE,Kress-GazitH,PappasGJ.Temporallogicmotionplanningformobilerobots.In:Proceedingsofthe2005IEEEInternationalConferenceonRoboticsandAutomation,Baecelona,Spain, 2005. 2020-2025

[10]SmithS,TumovaJ,BeltaC,etal.Optimalpathplanningforsurveillancewithtemporallogicconstraints.TheInternationalJournalofRoboticsResearch, 2011, 30(14): 695-1708

[11]SmithS,TumovaJ,BeltaC,etal.Optimalpathplanningundertemporallogicconstraints.In:ProceedingsofInternationalConferenceonIntelligentRobotsandSystems,Taipei,China, 2010. 3288-3293

[12] 肖云涛, 欧林林, 俞立. 基于线性时序逻辑的最优巡回路径规划. 自动化学报, 2014, 10(10): 2126-2133

[13]UlusoyA,SmithSL,DingXC,etal.Optimalityandrobustnessinmulti-robotpathplanningwithtemporallogicconstraints.InternationalJournalofRoboticsResearch, 2013, 32(8): 889-911

[14]MaityD,BarasJS.Motionplanningindynamicenvironmentswithboundedtimetemporallogicspecifications.In:Proceedignsofthe23thMediterraneanConferenceonControlandAutomation(MED),Torremolinos,Spain, 2015. 940-946

[15]GastinP,OddouxD.FastLTLtoBüchiAutomataTranslation.In:ComputerAidedVerification,Heidelberg,Germany:SpringerBerlin, 2001. 53-65

[16]KloetzerM,BeltaC.Afullyautomatedframeworkforcontroloflinearsystemsfromtemporallogicspecications.IEEETransactionsonAutomaticControl, 2008, 53(1): 287-297

[17]YangY.AnefficientimplementationofshortestpathalgorithmbasedonDijkstraAlgorithm.JournalofWuhanTechnicalUniversityofSurveying&Mapping, 1999, 24(3): 209-212

[18]BeltaC,IslerV,PappasGJ.Discreteabstractionsforrobotmotionplanningandcontrolinpolygonalenvironments.IEEETransactionsonRobotics, 2005, 21(5): 864-874

Path planing of warehouse robots based on linear temporal logic

YuXinyi,ChenHao,GuoYongkui,ChengCheng,OuLinlin,YuLi

(CollegeofInformationEngineering,ZhejiangUniversityofTechnology,Hangzhou310023)

Thepathplanningforwarehouserobotsbasedonthelineartemporallogic(LTL)theorywasstudied.Firstly,anextensiblewarehousemodelwasbuiltupaccordingtowarehouseenvironmentalcharacteristics,andasetofrulesforgoverningrobotmovementsweredefinedtomakethemodeladaptdynamicwarehouseenvironments.Secondly,theLTLformulawasusedtodescribetaskrequirementstomakeitsuitableformorecomplicatedtasksinpracticalapplications.Thirdly,thetask-feasiblenetworktopologywasbuiltbycombiningtaskrequirementsandenvironmentalinformationtoavoidpiecewisepathsearching.Then,theDijkstraalgorithmwasutilizedtosearchtheglobaloptimalpathonthetask-feasiblenetworktopologytoensuretheoptimalityofthepathplanningresult.Finally,theoptimizedpathwasobtainedbymappingtheoptimalpathonthetaskfeasiblenetworktopologybacktothewarehousemodel.Theabove-mentionedmethodcannotonlysatisfycomplextaskrequirements,butalsocanensuretheoptimalityofthepathplanningresult,ratherthanasuboptimalsolution,comparedwiththecurrentwidelyusedA*algorithm.

pathplanning,lineartemporallogic(LTL),warehouserobot,Dijkstraalgorithm

国家自然科学基金(61273116)，863计划(2014AA041601-05)和浙江省自然科学基金(LY15F030015)资助项目。

u@zjut.edu.cn(

2015-10-10)

10.3772/j.issn.1002-0470.2016.01.004

男，1979年生，博士(后)；研究方向：机器人控制与规划；E-mail: yuxinyinet@163.com