基于Petri网的消防机器人任务分配及路径规划方法

何舟，张瑞杰，刘苗，古婵

(陕西科技大学 机电工程学院，陕西 西安 710021)

0 引 言

消防机器人作为一种具有灭火救援功能的特种机器人，可以代替人类到较为危险的环境中展开工作[1]。因此，如何规划其路径轨迹并高效协同完成相应任务已经逐渐成为机器人协同工作的研究热点。

文献[2]提出了一种有限概率状态模型，并结合Petri网采用一种在线策略随时调整偏离轨迹的机器人，适合于具有更为复杂任务的机器人系统。文献[3]采用布尔规范将多机器人任务进行描述，将布尔任务转化成整数线性规划问题来求解，最终得到满足任务的最短轨迹。现有文献主要是对单个或多个独立的机器人采用如遗传算法[4]、蚁群算法[5]和粒子群算法[6]等进行路径优化。文献[7]提出一种基于动态惯性权重的改进粒子群算法，可以在较复杂的环境下规划出一条平滑安全无碰撞路径。文献[8]在传统蚁群算法的基础上引入信息素的模糊控制更新方式，对状态转移概率函数进行改进，有效减少了迭代的次数并且得到消防机器人更优的路径。

目前，越来越多的消防机器人已应用到各种危险场合，消防机器人的广泛应用对其路径规划能力提出了更高的要求[9]。本文提出了一种基于Petri网的任务分配及最优路径规划方法。通过构建Petri网模型对消防机器人工作环境进行描述，在此基础上通过求解整数线性规划获得消防机器人协同工作时间最短的路径，确保救援的高效性。

1 Petri网基础

一个Petri网可定义为一个四元组N=(P，T，F，W)，其中:P={p1，p2，...，pn}为n个库所的集合；T={t1，t2，…，tm}为m个变迁的集合；F⊆(P×T)∪(T×P)，称为有向弧的集合;W为F→N，称为网N的权函数，N={0，1，2，…}。W(p，t)为从p到t的权值，W(t，p)为从t到p的权值。

(1)

式(1)称为Petri网的状态方程，表示标识和变迁序列中变迁出现次数的关系。

2 消防机器人协同任务分配及路径规划

2.1 工作环境建模

本文参考文献[10]的室内仿真环境，如图1所示，对其进行区域划分和调整后得到图2所示的消防机器人工作环境。各机器人既可以和中央通信也可以互相通信，图2的工作空间被划分成若干个小房间，房间与房间之间通过双向门连接，实现双向移动。这样任务分配的问题就转变成控制指定功能和数量的机器人到达指定的房间完成相应的任务。

图1 多机器人室内救援环境

图2 消防机器人工作环境

图1中存在两个机器人、障碍物以及不可通行的墙壁，其利用2个机器人同时进行扫描工作，实现对该环境的地图构建，从而指引救援人员实施救援工作。

图2的每个区域Ri被认为是一个库所，记做pi(i=1，2，…，n)；机器人从区域Ri到达区域Rj通过变迁tk(k=1，2，…，m)来表示。因此，图2的Petri网模型如图3所示。

图3 消防机器人工作的Petri网模型

2.2 消防机器人协同工作

本文将消防机器人工作环境分为：公共区域、专属区域、协同区域、避障区域和终点区域。公共区域是所有机器人都可以进行访问的区域；不同类型的机器人有各自的专属区域，该区域只能由对应机器人访问；协同区域是多机器人共同执行任务的区域；避障区域是任何机器人都无法访问的地方；终点区域是机器人最终到达的位置。

由于基本Petri网里面的资源是相同的，当某个变迁触发时，对应的具体是哪个机器人进行移动并不能很好地区分开来。如果要在基本Petri网中对资源进行区分，就需要为每一个机器人单独建立一个基本Petri网模型。当环境中的机器人数量很多时，模型的规模会大幅增加，不便于表示和分析。考虑到每个机器人的工作环境模型是相同的，本文将同一工作环境下不同种类的机器人的路径使用不同的线型进行区分，并将每种类型的机器人路径分成H步计算，以此来解决区分机器人所带来的基本Petri网规模膨胀问题。

假设图1的工作环境有3种不同类型的消防机器人，记为r1、r2、r3。现有3个专属任务和1个协同任务需要这3个机器人完成：

专属任务1：需要在p10处由r1类型的机器人独立完成。

专属任务2：需要在p30处由r2类型的机器人独立完成。

专属任务3：需要在p19处由r3类型的机器人独立完成。

协同任务：需要在p12处由r2和r3类型的机器人共同完成。

机器人从一个区域移动到另一个区域记作一步，且所有机器人的初始位置均在区域R1中。假设机器人从R1出发，移动到终点区域共需要H步。r1、r2、r3的公共区域是R3、R4和R28,避障区域是R5和R9，终点区域是R29、R32。由于消防机器人工作的特殊性，到达R12的机器人的时间应该一致。

3 整数线性规划模型的建立

3.1 模型的条件

(1)消防机器人总数量为K。

(2)机器人完成任务的最大步数为H。

(3)消防机器人的公共区域为Ic，专属区域为Ie，协同工作区域是Ix，终点区域是If，禁行区域是Ia。

(4)消防机器人在专属区域工作的机器人集合为Eti即完成专属任务i的机器人集合，其中：i=1，2，…，n。协同区域的机器人集合为Ex。

(5)消防机器人的运行环境较为宽松，允许多个机器人在一个房间中。

3.2 模型的建立过程

为实现高效救援工作，本文以消防机器人的工作时间最短为优化目标。在Petri网中，令f=[f(t1)，f(t2)，…，f(tm)]∈Nm，给每个变迁赋值一定的时间。优化目标函数式(2)使所有机器人工作总时间最短：

(2)

消防机器人r在第h步的位置变化可由状态方程(1)得式(3)：

(3)

消防机器人r在第h步变迁使能后库所内的托肯数非负，则有式(4)：

(4)

机器人r第h步只能到达一个位置，即第h步最多只会触发一个变迁，则有式(5)：

(5)

公共区域作为所有消防机器人都可以访问的区域，应保证至少有一个机器人对其进行访问，则有式(6)和式(7)：

(6)

(7)

式中：vRj=[vRj(p1)，…，vRj(pn)]是一个包含n个元素的向量，每个元素vRj(pi)是一个0～1变量。当机器人访问区域Rj的时候，该向量只有第j个元素为1，即：

(8)

消防机器人的专属区域只能由对应类型的机器人进行访问和工作，其他类型机器人不能到达该区域，应满足式(9)和式(10)。

(9)

(10)

消防机器人的协同区域，除了对应的机器人进行访问外，其他机器人不能到达该区域，应满足式(11)和式(12)：

(11)

(12)

消防机器人至少会到达一个停止区域，式(13)到式(16)满足该目标。

vRj×Mr,H-1≤zj,r×H,∀Rj∈If

(13)

1-vRj×Mr,H≤zj,r×H,∀Rj∈If

(14)

zj,1+zj,2+…+zj,k≤K,∀Rj∈If

(15)

(16)

式中：H为一个足够大的数；zj，r(r=1，…，K)为一个0-1变量，表示机器人r是否访问区域Rj，即：

(17)

消防机器人应避免到达障碍区域，应满足式(18)：

(18)

消防机器人的时刻描述：

(19)

τr,0=0

(20)

式中：τr，0为机器人的初始时刻；τr，h为机器人第h步的时刻。

4 试验结果

基于3.2小节所建立的模型，其中，K=3，H=10，f=1，Ic={R3，R4，R28}；If={R29，R32}；Ie={R10，R30，R19}；Ia={R5，R9}；Ix={R12}；Ex={r2，r3}；Et1={r1}；Et2={r2}；Et3={r3}。MATLAB仿真得到如下结果：

r1轨迹：R1→R3→R4→R10→R11→R14→R18→R26→R27→R28→R32

r2轨迹：R1→R3→R11→R12→R13→R14→R18→R26→R30→R29

r3轨迹：R1→R3→R11→R12→R13→R14→R19→R22→R25→R29

满足所有消防机器人完成对应任务的路径如图4所示，且工作时间最短为28 s。

图4 消防机器人最优路径

5 结束语

结合消防机器人工作环境的Petri网模型，本文提出了一种基于Petri网特性的整数线性规划方法。通过将消防机器人的工作环境划分为公共区域、专属区域、协同区域、避障区域和终点区域，实现了机器人的任务分配。在此基础上，本文将对应的任务需求转换为具有Petri网特性的整数线性规划模型，然后利用MATLAB仿真获得消防机器人工作效率最高的最优路径。经验证，本文提出的整数线性规划方法具有可行性且计算效率高，能够获得消防机器人完成救援工作的全局最优路径，确保了救援的高效性。