Issue |
JNWPU
Volume 42, Number 4, August 2024
|
|
---|---|---|
Page(s) | 716 - 725 | |
DOI | https://doi.org/10.1051/jnwpu/20244240716 | |
Published online | 08 October 2024 |
A Petri nets-based modeling method for multi robot path planning
一种基于Petri网的多机器人路径规划建模方法
1
School of Automation, Xi'an University of Posts and Telecommunications, Xi'an 710121, China
2
School of Electronic Engineering, Xi'an University of Posts and Telecommunications, Xi'an 710121, China
3
School of Astronautics, Northwestern Polytechnical University, Xi'an 710072, China
Received:
7
August
2023
The construction of lunar bases is one of the core enabling technologies in current lunar exploration and development plans of various countries. However, to eliminate the constraints of high transportation costs and limited manned space technology, a new research plan is to employ multi robot teams to build lunar bases. The key to this solution is how to achieve path planning for complex tasks for multiple robots. Therefore, this article takes the exploration and collection area, lunar soil collection, and lunar soil transportation in the lunar base construction scene as complex task inputs, and studies a multi robot path planning modeling method based on Petri net model. Firstly, a Petri net model for multi robot motion was constructed. Meanwhile, linear temporal logic(LTL) language was used to describe the related tasks of lunar base construction. Finally, simulation validation was conducted in Matlab software and compared with the modeling method using switching systems. The results show that the total modeling time required for using the Petri net model is reduced by two orders of magnitude compared to the modeling time for a single task switching system model, indicating that the established Petri net multi robot model has advantages such as avoiding dimension explosion and computational efficiency.
摘要
月球基地建设是当前各国月球探测与开发计划的核心使能技术之一。然而, 为消除高昂的运输成本和有限载人航天技术的约束, 使用多机器人团队建造月球基地的新研究方案被提出, 该方案的关键是如何实现多机器人针对复杂任务的路径规划。为此, 以月球基地建设场景中的探测采集区域、采集月壤、搬运月壤等作为复杂的任务输入, 研究了一种基于Petri网模型的多机器人路径规划建模方法。构建了多机器人运动的Petri网模型; 使用线性时序逻辑(linear temporal logic, LTL)语言描述月球基地建设的相关任务; 将Petri网模型和LTL公式结合求解得到多机器人路径; 在Matlab软件中进行仿真验证, 并与使用切换系统的建模方法进行对比。结果表明, 使用Petri网模型所需的建模总时间比切换系统模型单个任务的建模时间减少2个数量级, 说明建立的Petri网多机器人模型具有避免维度爆炸、计算高效等优势。
Key words: construction of lunar bases / Petri net model / path planning modeling / linear temporal logic
关键字 : 月球基地建设 / Petri网模型 / 路径规划建模 / 线性时序逻辑
© 2024 Journal of Northwestern Polytechnical University. All rights reserved.
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
月球是距离地球最近的天体,是人类向太空探索最天然稳定的“空间站”,也是人类向太空天体探索的“始发站”[1]。月球基地是月球资源开采和利用的试验站,可服务于后续无人月球探测和载人登月探测任务。当前,月球基地建设是我国及世界各国对月球探测和开发计划的重要目标[2–3]。建设月球基地需要消耗大量的建筑材料,而根据唐红、邢丹等[4–5]的统计,将大量建筑材料运输至月球会耗费高额的运输成本。显然,当前航天技术无法满足月球基地经济合理的建设原则,因此,国内外一些科研工作者基于真实月壤或模拟月壤开展了大量研究,提出了月壤基纤维制备技术和多种月壤成型技术[6–9]。进一步地,Pico和徐桂弘等[10–11]通过研究发现,利用月壤制备月壤基纤维,可结合3D打印技术制备各种建筑材料,是建造月球基地的良好选择。同时,当前的载人航天技术不足以将大量人力资源输送至月球,而Zhang等[12]提出了一种可扩展的多机器人3D打印和路径规划框架,该框架使机器人任务和群体规模能够适应整个建筑任务中打印几何结构的变化。
基于上述研究基础,本文的研究考虑使用智能多机器人团队进行月球基地建设的相关工作,且考虑建筑材料取材于月壤。多机器人团队需完成的月球基地建设任务较为复杂,涉及多个环节,例如:顺序探测采集区域、前往采集区域采集月壤、将月壤搬运至月球基地主建设区等。这些任务之间存在着一定的时序性和逻辑性,与传统的“由A点运动至B点并避开障碍物”的路径规划相比更为复杂。要使用多个机器人完成上述任务,就涉及到多机器人在时序逻辑任务要求下的路径规划。因此,使用多智能机器人团队执行月球基地建设相关任务的关键技术是复杂任务下多机器人的路径规划;而选择一个合适的建模分析方法是开展相关研究的关键,具有重要的现实意义。
当前,在多机器人路径规划领域,基于深度强化学习的方法、基于采样的方法、群体智能算法等[13–15]主要针对多机器人的传统路径规划,总体上缺乏针对多机器人执行复杂任务路径规划的研究。在多机器人复杂任务路径规划的建模领域,Mahulea等[16]提出了一种基于切换系统和线性时序逻辑(LTL)的多机器人路径规划方法,将环境建模成一个切换系统,用LTL语言描述包含多个访问点和障碍物的任务需求,但这种方法会产生切换系统状态的维度爆炸问题,使得建模及后续求解效率急剧下降。何舟等[17]针对多类型消防机器人协同工作的任务分配及路径规划问题,建立了能够描述消防机器人运行状态的Petri网模型,但该方法无法与具有时序逻辑性的任务相结合。此外,文献[18–20]主要针对无人机集群行为、装备体系任务和机载系统的动态可靠性进行建模,缺乏对无人机、机器人等物理实体运动的建模。
本文选用Petri网模型进行建模分析,Petri网模型作为一种图形化的离散事件模型,广泛应用于建模和分析并发系统、分布式系统等多个领域。相较于其他路径规划建模方法,Petri网模型具有易于理解和分析的优势,尤其在解决多机器人复杂任务路径规划中的维数爆炸问题时表现出色,计算速度快的特点使之成为处理复杂任务路径规划的理想选择。
为了使多机器人能够顺利执行月球基地建设的相关任务,本文针对月球基地建设的二维平面环境,提出了一种基于Petri网的多机器人路径规划建模方法。首先,构建月球基地建设环境的有向图模型,由此建立多机器人运动的Petri网模型;接着,将多机器人运动的Petri网模型与LTL公式描述的复杂任务结合,在Matlab仿真软件中进行验证;同时,通过对比切换系统模型建模的方法以证明Petri网模型在复杂系统建模和高效计算方面的优势。
1 多机器人运动建模方法
1.1 有向图建模
在进行Petri网建模之前,对于一个由任务区域(机器人需要访问的区域)和自由区域(除任务区域以外的区域)组成的月球基地建设二维平面环境,使用分割算法将该环境分割成多个离散的子区域,从而构建一个有向图。使用分割算法减小了问题规模,简化了路径规划,有助于提高多机器人协同路径规划的效率、可行性和可扩展性。下文给出了有向图模型的定义。
定义1 有向图模型
式中:C={c1, c2, …, c|C|}表示|C|个环境离散区域的集合; E⊆C×C表示C中区域之间关系的集合, (ci, cj)∈E表明ci和cj相邻, 且假定所有的ci∈C有(ci, ci)∈E; A表示邻接矩阵, A(i, j)=‖center(ci)-mid(ci, cj)‖+‖center(cj)-mid(ci, cj)‖当且仅当(ci, cj)∈E(当i=j时, A(i, j)=1), 反之A(i, j)=0, center(ci)表示ci的中心, mid(ci, cj)表示ci和cj相邻边的中点; Y={y1, y2, …, y|Y|}表示|Y|个机器人任务区域。
1.2 经典Petri网模型
一个经典的Petri网模型结构主要包括4个元素: 库所(place)、变迁(transition)、库所和变迁之间的有向弧(arc)、托肯(token)。托肯是库所中的动态对象(在本文中为机器人), 可以从一个库所移动到另一个库所。
定义2 经典Petri网模型
式中: P={p1, p2, …, p|P|}表示库所, T={t1, t2, …, t|T|}表示变迁; F⊆(P×T)∪(T×P)表示托肯流动关系; F=∪, 当且仅当(pi, tj), (tm, pn)之间存在可供托肯流动的有向弧。
经典Petri网模型Σ还需要满足以下条件:
1) P×T≠Ø
2) P∩T=Ø
3) dom(F)∪cod(F)=P∪T, 其中dom(F)={x∈P∪T|∃y∈P∪T: (x, y)∈F}, cod(F)={x∈P∪T|∃y∈P∪T: (y, x)∈F}。
在经典Petri网模型的图形化表示中, 库所P用圆圈表示, 变迁T用矩形表示, 有向弧用箭头表示, 托肯用黑色实心小正方形表示。图 1是一个经典Petri网模型的图形化表示。在图 1中, 库所集合P={p1, p2, p3, p4}, 变迁集合T={t1, t2, t3, t4}, 流动关系F={(p1, t1), (p2, t2), (p3, t3), (p4, t1), (p4, t4), (t1, p2), (t2, p3), (t3, p4), (t4, p1)}, 有一个托肯在库所p1内。根据定义2, dom(F)={(p1, t1), (p2, t2), (p3, t3), (p4, t1), (p4, t4)}表示库所到变迁的有向弧集合; cod(F)={(t1, p2), (t2, p3), (t3, p4), (t4, p1)}表示变迁到库所的有向弧集合。
定义3 输入集和输出集定义
在经典Petri网中, 对于x∈P∪T, 记
称·x为x的前集或输入集; x·为x的后集或输出集, ·x∪x·为x的外延。
在图 1中, x可以表示1个库所, 也可以表示1个变迁。例如, 对于库所p1, ·p1是p1的输入集, ·p1={t4}, p1·是p1的输出集, p1·={t1}; 对于变迁t1, ·t1是t1的输入集, ·t1={p1, p4}, t1·是t1的输出集, t1·={p2}。则p1的外延·p1∪p1·={t1, t4}, t1的外延·t1∪t1·={p1, p2, p4}。
图1 经典Petri网模型 |
1.3 多机器人运动的Petri网建模
在一个月球基地建设的二维平面环境中考虑一个包含|R|个相同的全向移动机器人的团队, 则多机器人的运动可建为多机器人运动Petri网(multi-robots motion petri nets, MRMP)模型。
定义4 多机器人运动Petri网
式中: G是有向图; Σ=(P, T, F)是经典Petri网模型中的结构, 在MRMP中, 将G中的C建模成P, 即pi=ci, |P|=|C|, P即为所有环境离散区域的集合, 对于任意变迁t, 其输入集·t和输出集t·中的元素是唯一的, 即外延·t∩t·中元素个数为2, 且2个元素不相同; M是MRMP的机器人状态标识, 其标记当前状态每个区域机器人的数量, 对于库所集合P={p1, p2, …, p|P|},M为一个列向量M=[M(p1), M(p2), …, M(p|P|)]T, 对∀pi∈P, 如果M(pi)=k, 则称pi中有k个机器人, 记M0为MRMP的初始状态标识; W是有向弧权, 对∀x, y∈P∪T且(x, y), (y, x)∈F, 记W(x, y), W(y, x)为x与y、y与x之间有向弧的弧权; h={h1, h2, …, h|R|}, 其中hi={y1, y2, …, y|Y|, O}是单机器人可能到达的任务区域和自由区域的集合, 自由区域用O表示; H=h1×h2×…×h|R|是多机器人可能到达的任务区域和自由区域所有组合的集合, , , Hj是hi中的某一个元素。
注意到MRMP中Petri网结构与经典Petri网结构的不同在于, MRMP对变迁t做出了约束, 要求每一个变迁t只能从一个库所输入, 并输出到另一个库所, 以保证多机器人在运动过程中相互不发生碰撞。以图 1为例, 假定图 1能构成一个MRMP, 现在考察变迁t1, 若区域p1和p4中均有一个机器人, 且2个机器人均要前往区域p2, 那么在实际的环境中就可能会发生碰撞, 因此图 1所示的模型不能构成MRMP。
此外, 在定义4中, h中的hi建模的是单个机器人执行任务的情况, H建模的是多机器人团队在某一时刻执行任务的情况。在后文的验证部分, h和H将被用在所使用的验证算法中。
规定MRMP的变迁发射规则为当且仅当∀p∈·t, M(p)≥W(p, t)。在MRMP中, 规定W(p, t)=1, 即变迁发射规则可阐述为区域p中至少要有一个机器人, 且变迁每发射一次只能移动一个机器人。
在MRMP模型中多机器人由区域到变迁、由变迁到区域的移动关系可用输入矩阵Pre和输出矩阵Post表示, 其中
式中:2个矩阵的大小均为|P|×|T|, 其中, 矩阵Pre的第i行代表区域pi, i=1, 2, …, |P|, pi行向量中第j个元素(j=1, 2, …, |T|)的值为1表示机器人从区域pi出发能移动至变迁tj, 为0则表示不能移动至变迁tj。矩阵Post的第i行代表区域pi。pi行向量中第j个元素的值为1表示机器人从变迁tj出发能移动至区域pi, 为0则表示不能移动至区域pi。
由输入矩阵和输出矩阵可以得到一个机器人的移动矩阵, 记作[C], [C]=Post-Pre, 该矩阵描述了机器人在MRMP下的运动关系, 具体元素的含义将在实例中做出解释。由此有MRMP的状态转移方程为
式中:[C][·, tj]表示变迁tj, 则称M是由M0经过发射变迁tj得到的可达标识, 记作M0[tj〉M。若有变迁发射序列ρ=t1, t2, …, tn使得M0[t1〉M1[t2〉…Mn-1[tn〉M成立, 则有标识M从M0可达。记σ=[σ(t1), σ(t2), …, σ(tn)]T为MRMP的变迁发射计数向量, 每个元素为变迁tn的发射次数, 由此, (1)式的另一种写法为
由(2)式可以看出, σ的意义是多机器人的路径规划, 即已知σ则可以得到多机器人运动到的具体位置。
以图 2所示的示例环境和MRMP为例, 图 2a)是一个拥有A, B, C, D 4个区域的环境, 图 2b)是该环境的MRMP模型, 初始状态下, 在A区域内有3个机器人(用圆圈表示), 则初始标识M0=[M(p1), M(p2), M(p3), M(p4)]T=[3, 0, 0, 0]T。容易看出, 单个机器人在某一时刻能到达A, B, C, D中的某一个区域, B, C, D记为任务区域, A记为自由区域(用O表示), 则hi={B, C, D, O}, i=1, 2, 3, 那么H=h1×h2×h3={(O, O, O), (B, O, O), (B, B, O), (B, B, B), (B, B, C), …, (D, D, C), (D, D, D)}。
图 2示例中MRMP模型的输入矩阵Pre和输出矩阵Post分别为
则机器人移动矩阵[C]为
[C]的含义为: 第i, k行表示区域pi, pk, 第j列表示变迁, 对于第j列向量, 第i行值为-1表示的是机器人从区域pi移动到变迁tj, 第k行值为1表示的是机器人从变迁tj移动到区域pk。
假定现在p1内的3个机器人分别要前往p2, p3和p4, 显然, 前往p2需要发射一次变迁t1, 前往p3需要发射一次变迁t2, 前往p4可以先发射一次变迁t1再发射一次变迁t4, 则变迁发射计数向量σ1=[σ(t1), σ(t2), …, σ(t8)]T=[2, 1, 0, 1, 0, 0, 0, 0]T, 由(3)式可以得到下一个状态的标识为M1=[0, 1, 1, 1]T。
在M1的基础上, 假定现在有一个变迁发射序列ρ=t4, t8, t6, t8, t6, t8, 使得MRMP从标识M1到达下一个标识M2, 则变迁发射计数向量σ2=[0, 0, 0, 1, 0, 2, 0, 3]T, 根据(4)式可以得到下一个状态的标识M2=[0, 0, 2, 1]T, 即通过发射ρ使得2个机器人在p3内, 1个机器人在p4内。
图2 示例环境与其MRMP |
2 多机器人运动建模及实例验证
本文在月球基地建设环境下, 采用多机器人运动的Petri网模型, 运用LTL公式描述月球基地建设的相关任务。通过将LTL公式与多机器人运动的Petri网模型结合, 在Matlab中构建混合整数线性规划[21], 得到了多机器人在这些路径上的行动轨迹。同时, 利用文献[16]中提出的切换系统模型和Büchi自动机相乘的方法, 在相同的环境下进行验证, 并进行了对比实验以评估Petri网模型的性能和适用性。这一整合框架为月球基地建设的相关任务中多机器人的行为描述、验证和规划提供了全面的解决方案。
2.1 实例建模
考虑一个包含多个区域的模拟月球基地建设环境(如图 3所示),该环境中存在月球基地建设区(科研站、通信站、住宅生活区)、机器人充电站和月壤采集区。
模拟月球基地建设实景图如图 4所示, 该场景由①~④这4个区域组成, 区域①为月球基地主建设区, 区域②为机器人充电站, 区域③和区域④为资源探测区, 需要机器人前往该区域探测是否存在可用于月球基地建设的月壤。将该场景映射到一个二维平面上, 如图 5所示, 其中y1~y4分别对应①~④。
图 5是一个大小为10×10的区域, 任务区域集合Y={y1, y2, y3, y4}, 其中y1是月球基地的主建设区, 包含可供航天员进行科研工作的科研站, 可使航天员与地球指挥中心进行通信的通信站, 可供航天员正常生活和休息的住宅生活区; y2是机器人充电站, 用于机器人充电; y3和y4是资源探测区。
根据定义1, 使用三角分割算法[22]将图 5分割成若干个离散区域, 如图 6所示。
由图 6可知, 环境离散区域集合C={c1, c2, …, c16}, 在任务区域中, y1={c2, c8}, y2={c5}, y3={c14}, y4={c10, c12}。现在考察3个机器人, 分别为侦察机器人、挖掘机器人和运输机器人, 其中位置①为侦察机器人r1, 位置②为挖掘机器人r2, 位置③为运输机器人r3。初始状态下3个机器人都在c5内, 坐标分别为r1: (3, 8), r2: (2, 9), r3: (1, 8)。单个机器人在某一时刻能到达任务区域和自由区域中的某一个, 即hi={y1, y2, y3, y4, O}, i=1, 2, 3, 则H=h1×h2×h3={(O, O, O), (y1, O, O), …, (y4, y4, y3), (y4, y4, y4)}。
根据图 6构建的MRMP模型如图 7所示, 其中P={p1, p2, …, p16}, T={t1, t2, …, t36}, 初始状态标识M0=[M(p1), M(p2), …, M(p16)]T=[0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]T。根据图 7,对于∀(pi, tj), (tj, pi)∈F, 机器人移动矩阵[C]∈{-1, 0, 1}16×36由(5)式确定。
图3 月球基地建设的实验室模拟环境 |
图4 月球基地建设的某一模拟实景图 |
图5 模拟月球基地的二维平面图 |
图7 多机器人运动的Petri网模型 |
2.2 结合建设任务的仿真验证
本文使用线性时序逻辑(linear temporal logic, LTL)语言描述月球基地建设任务。LTL语言的运算符主要有: 布尔运算符¬(非)、∨(或)以及∧(与), 逻辑连接符→(推断出)、⇔(等价于), 时序运算符○(下一步, 也可使用X表示)、U(直到)、◇(最后, 也可使用F表示, 在本文中使用F)和□(始终, 也可使用G表示)。任意运算符可与任意任务区域集合Y={y1, y2, y3, y4}中的元素组成LTL公式, 用ϕ表示。
下面考虑3个任务:
任务1 侦察机器人前往资源探测区探测是否存在可用于建设月球基地的月壤, 侦察完成后返回机器人充电站;
任务2 在侦察机器人返回确认存在可用月壤后, 挖掘机器人和运输机器人一同前往存在可用月壤的区域, 挖掘机器人挖掘月壤, 并装在运输机器人携带的收集桶中。
任务3 挖掘机器人挖掘完成后返回机器人充电站, 运输机器人将月壤运输至月球基地建设区之后返回机器人充电站。
2.2.1 任务1
任务1的LTL公式描述为
(6) 式表明, 侦察机器人需要按照y4→y3→y2的顺序依次访问, 其中任务区域的上标表示机器人。
将MRMP模型与(6)式结合, 在Matlab 2022b中构建混合整数线性规划(mixed integer linear programming, MILP)并利用GLPK求解器得到MRMP模型中最小的变迁发射计数向量σ1=[σ(t1), σ(t2), …, σ(t36)]T=[0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0]T, 并转换成机器人的路径, 最终得到的仿真结果如图 8所示。在图 8中, 侦察机器人r1的路径为c5, c9, c7, c10, c15, c16, c11, c14, c11, c16, c6, c3, c5。由图可知, 侦察机器人顺利地完成了侦察任务, 且假定侦察机器人确认y3区域存在可用的月壤, y4区域不存在可用的月壤。
由图 7的模型可知, 在r1经过的区域中, 需要发射的变迁有: t10, t21, t16, t24, t33, t35, t26, t31, t27, t34, t11, t5。根据(2)式可到达下一个状态的标识M1=[0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]T, MRMP如图 9所示, 当前状态下, 3个机器人都位于c5区域内。
图8 任务1仿真结果 |
图9 M1状态下的MRMP |
2.2.2 任务2
任务2的LTL公式描述为
(7) 式表明, 挖掘机器人和运输机器人需要前往y3区域。
将MRMP模型与(7)式结合, 在Matlab 2022b中构建混合整数线性规划MILP并利用GLPK求解器得到MRMP模型中最小的变迁发射计数向量σ2=[σ(t1), σ(t2), …, σ(t36)]T=[0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0]T, 并转换成机器人的路径, 最终得到的仿真结果如图 10所示。在图 10中, 挖掘机器人r2的路径为c5, c9, c7, c6, c16, c11, c14, 运输机器人r3的路径为c5, c3, c6, c16, c11, c14。由图可知, 2个机器人顺利前往y3区域。
由图 7的模型可知, 在r2经过的区域中, 需要发射的变迁有: t10, t21, t14, t13, t35, t26, 在r3经过的区域中, 需要发射的变迁有: t8, t6, t13, t35, t26。根据(2)式可到达下一个状态的标识M2=[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0]T, MRMP如图 11所示, 当前状态下, 侦察机器人r1位于c5区域内, 挖掘机器人r2和运输机器人r3位于c14区域内。
图10 任务2仿真结果 |
图11 M2状态下的MRMP |
2.2.3 任务3
任务3的LTL公式描述为
(8) 式表明, 月壤挖掘完成后, 挖掘机器人直接返回机器人充电站, 运输机器人需要先将月壤运输至月球基地建设区再返回机器人充电站。
将MRMP模型与(10)式结合, 在Matlab 2022b中构建混合整数线性规划MILP并利用GLPK求解器得到MRMP模型中最小变迁发射计数向量σ3=[σ(t1), σ(t2), …, σ(t36)]T=[1, 0, 1, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 1, 0, 0]T, 并转换成机器人的路径, 最终得到的仿真结果如图 12所示。
在图 12中, 挖掘机器人r2的路径为c14, c11, c16, c6, c3, c5, 运输机器人r3的路径为c14, c11, c13, c8, c2, c8, c1, c3, c5。由图可知, 挖掘机器人直接返回机器人充电站, 运输机器人将月壤运输至月球基地建设区并返回机器人充电站。
由图 7的模型可知, 在r2经过的区域中, 需要发射的变迁有: t31, t27, t34, t11, t5, 在r3经过的区域中, 需要发射的变迁有: t31, t25, t29, t18, t3, t17, t1, t5。根据(2)式可到达下一个状态的标识M3=[0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]T, MRMP如图 13所示, 在最终状态, 3个机器人均回到了c5内。
图12 任务3仿真结果 |
图13 M3状态下的MRMP |
2.3 仿真对比
本文记录了Petri网建模的仿真运行时间(保留6位有效数字), 如表 1所示。不难看出, 生成Petri网模型的总时间仅约为4 ms, 求解路径的时间约为0.27 s, 总的运行时间仅为0.270 348 s, 有效证明了多机器人运动Petri网建模方法具有较高的效率。
另外, 对于任务1, 将文献[16]中的基于切换系统模型的方法进行了仿真实验, 得到的结果如图 14所示。由图 14可以看出, 侦察机器人r1的路径为: c5, c9, c7, c10, c15, c16, c11, c14, c11, c16, c6, c3, c5。
从仿真结果来看,使用切换系统模型对环境进行建模的方法与Petri网模型建模得到的机器人路径基本一致。同样地,表 2记录了切换系统模型建模的仿真运行时间(保留6位有效数字)。注意到生成切换系统模型的时间约为225 ms,任务1的总用时为0.617 053 s,在相同环境和相同任务下,比使用多机器人运动Petri网模型建模的总时间还增加了2个数量级,这是因为切换系统模型会受到机器人数量以及LTL公式描述任务复杂度的影响,随着机器人数量增加,切换系统中的状态数会呈指数型暴增,因此可以看出使用Petri网模型建模的方法具有出色的效率。
基于多机器人运动Petri网的仿真时间
图14 基于切换系统模型方法任务1的仿真结果 |
基于切换系统模型方法的仿真时间
3 结论
多智能机器人团队的路径规划是月球基地建设复杂任务中的关键技术之一。本文首先采用三角分割算法对月球基地的二维平面进行离散化,并构建了有向图模型。随后,通过Petri网精准地建模了多机器人运动。接着,月球基地建设的相关任务以线性时序逻辑(LTL)公式描述。最后,通过混合整数线性规划(MILP)方法获得了多机器人团队的路径。在Matlab仿真中,对比了多机器人运动的Petri网模型和切换系统模型2种方法,结果表明,采用Petri网建模的方法能高效实现多机器人团队在月球基地建设中的任务。该建模方式不仅易于理解和分析,而且当LTL公式中命题数较多时可规避指数爆炸问题。仿真的时间记录验证了该模型具有出色的效率。这一研究的结论清晰表明,使用Petri网建模是实现月球基地建设任务的一种可行且有效的方法。
References
- YUAN Yong, ZHAO Chen, HU Zhenyu. Concept of lunar base construction plan[J]. Journal of Deep Space Exploration, 2018, 5(4): 374–381 (in Chinese) [Google Scholar]
- JIANG Mingjing, ZHANG Xinrui, SIMA Jun, et al. The application of soil based material reinforced lunar soil technology in the construction of lunar bases[J]. Journal of Suzhou University of Science and Technology, 2023, 40(3): 11–20 (in Chinese) [Google Scholar]
- WU Zhifei, OUYANG Ziyuan. In order to leave Chinese footprints on the moon[J]. International Talent Exchange, 2022(5): 30–33. [Article] (in Chinese) [Google Scholar]
- TANG Hong, WANG Shijie, LI Xiongyao, et al. Preliminary ideas for microwave sintering of lunar ilmenite to prepare structural materials for lunar bases[J]. Journal of Mineralogy, 2009, 29(2): 229–234. [Article] (in Chinese) [Google Scholar]
- XING Dan, QIAN Xiongyu, GUO Zeshi, et al. Feasibility study on preparing continuous fibers from simulated lunar soil[J]. Chinese Science: Technical Science, 2020, 50(12): 1625–1633 (in Chinese) [Google Scholar]
- LIU Jinjun, GUO Jiancheng, JIANG Zheng. On the construction and technology of lunar bases[J]. Satellites and Networks, 2021(8): 56–65 (in Chinese) [Google Scholar]
- JIANG Mingjing, LI Liqing. Development of TJ-1 simulated lunar soil[J]. Journal of Geotechnical Engineering, 2011, 33(2): 209–214 (in Chinese) [Google Scholar]
- GUO Z, XING D, XI X, et al. Production of fibres from lunar soil: feasibility, applicability and future perspectives[J]. Advanced Fiber Materials, 2022, 4(5): 923–937. [Article] [CrossRef] [Google Scholar]
- SUN Yimeng, CHEN Shenggui, HUA Kaihui, et al. Research progress on in-situ additive manufacturing technology for simulated lunar soil[J]. Materials Research and Application, 2021, 15(2): 178–185. [Article] (in Chinese) [NASA ADS] [Google Scholar]
- PICO D, LÜKING A, SEMPERE A, et al. Moon Basalt fiber-preliminary feasibility study[J/OL]. (2019-07-11)[2023-06-12]. [Article] [Google Scholar]
- XU Guihong, LI Yang, LI Rui, et al. Research progress on in-situ resource utilization technology of lunar soil[J]. Mineral Protection and Utilization, 2023, 43(4): 12–23 (in Chinese) [Google Scholar]
- ZHANG K, CHERMPRAYONG P, XIAO F, et al. Aerial additive manufacturing with multiple autonomous robots[J]. Nature, 2022, 609: 709–717. [Article] [NASA ADS] [CrossRef] [Google Scholar]
- ZHANG F, GU C, YANG F. An improved algorithm of robot path planning in complex environment based on double DQN[J]. Advances in Guidance, Navigation and Control, 2021, 644: 303–313 [CrossRef] [Google Scholar]
- NGUYEN T H, NGUYEN X T, PHAM D A, et al. A new approach for mobile robot path planning based on RRT algorithm[J]. Modern Physics Letters B, 2023, 37(18): 2340027. [Article] [CrossRef] [Google Scholar]
- XU Zhao, HU Jinwen, MA Yunhong, et al. A study on path planning algorithms of UAV collision avoidance[J]. Journal of Northwestern Polytechnical University, 2019, 37(1): 100–106. [Article] (in Chinese) [CrossRef] [EDP Sciences] [Google Scholar]
- MAHULEA C, KLOETZER M, RAMÓN G. Path planning by using transition system models[M]. Piscataway: Wiley-IEEE Press, 2020 [Google Scholar]
- HU Zhou, ZHANG Ruijie, LIU Miao, et al. Task allocation and path planning method for firefighting robots based on Petri nets[J]. Electrical Automation, 2021, 43(2): 115–118. [Article] (in Chinese) [Google Scholar]
- LU Nan, WANG Xiaodong, TANG Zheng, et al. Modeling method of unmanned aerial vehicle swarm behavior based on spatiotemporal hybrid Petri net[J]. Journal of Northwestern Polytechnical University, 2022, 40(4): 812–818. [Article] (in Chinese) [NASA ADS] [CrossRef] [EDP Sciences] [Google Scholar]
- CHEN Yuqi, XU Tingxue, ZHAO Xiaotong, et al. Modeling and analysis of mission thread of weapon system of systems based on O-PPN[J]. Journal of Northwestern Polytechnical University, 2021, 39(1): 197–207. [Article] (in Chinese) [NASA ADS] [CrossRef] [EDP Sciences] [Google Scholar]
- ZHUANG Lu, LU Zhong, ZHANG Ziwen. Dynamic reliability model for airborne systems based on stochastic petri net[J]. Journal of Northwestern Polytechnical University, 2020, 38(4): 846–854. [Article] (in Chinese) [CrossRef] [EDP Sciences] [Google Scholar]
- MAHULEA C, KLOETZER M, RAMÓN G. Path and task planning using petri net models[M]. Piscataway: Wiley-IEEE Press, 2020 [Google Scholar]
- KLEIN R. Voronoi diagrams and delaunay triangulations[J/OL]. (2015-01-05)[2023-06-12]. [Article] [Google Scholar]
All Tables
All Figures
图1 经典Petri网模型 |
|
In the text |
图2 示例环境与其MRMP |
|
In the text |
图3 月球基地建设的实验室模拟环境 |
|
In the text |
图4 月球基地建设的某一模拟实景图 |
|
In the text |
图5 模拟月球基地的二维平面图 |
|
In the text |
图6 图 5的离散化结果 |
|
In the text |
图7 多机器人运动的Petri网模型 |
|
In the text |
图8 任务1仿真结果 |
|
In the text |
图9 M1状态下的MRMP |
|
In the text |
图10 任务2仿真结果 |
|
In the text |
图11 M2状态下的MRMP |
|
In the text |
图12 任务3仿真结果 |
|
In the text |
图13 M3状态下的MRMP |
|
In the text |
图14 基于切换系统模型方法任务1的仿真结果 |
|
In the text |
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.