兼顾路径长度和充电站位置的移动机器人路径规划*

张延年,吴 昊,张 云

(南京交通职业技术学院电子信息工程学院,南京 211188)

0 引言

因自动化程度高、柔性强等,移动机器人已在工业、农业、医疗业等领域广泛应用。例如,在工厂,移动机器人能够自动地搬运物料[1],其已成为智能制造车间的主要运载工具。如何使移动机器人有序移动,并快速地完成任务是当前移动机器人领域的核心问题之一。而规划移动机器人的路径是解决该问题的关键因素。

在基于移动机器人的应用中,移动机器人需要完成特定任务[2-3]。这些任务分布在特定的位置上,本文将这些位置称为任务点。由于移动机器人有一定的视觉或者感测能力,其可能需要移动至特定的位置点(以下简称服务点),才能使这些任务点在其感测范围内,进而才能完成这些任务。因此,移动机器人的路径是由这些服务点构成。移动机器人通过遍历至每个服务点,使任务点在其覆盖范围内,进而完成预定的任务。

然而,在给定任务点的前提下,建立服务点,进而规划路径是一项挑战性工作。规划路径时必须要考虑到路径长度。路径长度直接影响了移动机器人完成任务的时间,即工作效率问题。因此,路径规划问题成为移动机器人领域的研究热点,促使了研究人员对其深入研究。解瑞云等[4]提出基于多策略改进鼠群算法的路径规划算法,其利用改进的鼠群优化算法求解最短路径。

除了考虑路径长度外,规划路径时还需考虑移动机器人的能效问题[5]。在真实应用环境中,多数移动机器人是依电池供电工作。移动机器人移动一定距离后,需充电,否则无法工作。因此,如果路径中两个服务点间距离超过续航距离,则移动机器人必须充电后才能完成下一个任务。而现有的多数文献在规划移动机器人路径时,并没有考虑到移动机器人的充电问题,也没有考虑充电站的位置。

为了弥补上述不足,提出基于任务点全覆盖的能效路径规划(full coverage of mission location-based energy efficiency path planning,FCPP)算法。FCPP算法在规划移动机器人路径时不仅考虑路径长度,还考虑了充电站位置,使机器人能快速地完成各任务。仿真结果表明,提出的FCPP算法缩短了路径,减少了移动机器人完成工作的时间。

1 系统模型及问题概述

1.1 系统模型

在方形环境区域Θ=×内部署n个任务点,它们构成任务集K={pi|1≤i≤n}。以图1为例,图1中的红色方形表示任务点。移动机器人装备了传感器,其感测半径r。移动机器人依据特定路线服务这些任务点。如果某个任务点在移动机器人当前位置的感测范围内,移动机器人就在当前位置为执行该任务[6]。此外,某些任务点可能有多次被移动机器人服务的机会。

图1 系统模型

考虑到真实的应用场景,移动机器人需在特定的位置开始(始点)移动,为n个任务点服务后,又返回至始点。因此,移动机器人的每条路径都是首尾相接的闭合曲线。用s表示始点,以图1为例。图1中黑颜色的折线表示移动机器人的路径,其从s开始,至s结束。

移动机器人由电池供电。每次充满电后,续航距离为B。因此,移动机器人完成移动了距离B后,需移动至充电站充电。据此,假定在区域内存在k个充电站,它们充电站集C={ci|1≤i≤k}。图1标记“×”表示充电站。移动机器人依据其充电需要,可以反复、多次充电。此外,本文不考虑移动机器人的充电时间。

为了服务这些任务点,移动机器人需要移动到多个特定的位置点。将这些点称为服务点。每条路径都遍历这些服务点。令L表示这些服务点集,它们构成服务点集L={vi|1≤i≤m},其中m表示服务点数。仍以图1为例,图1中的黑颜色实心圆点表示服务点。当两个连续服务点间距离大于B时,移动机器人就需在途中充电。

1.2 问题概述

对于任意一条路径T,路径从始点s开始,遍布L中每个点再返回始点s,且路径T中连续的两个服务点间距离不超过B,使保持移动机器人的电量不耗尽。本文需要解决的问题是:在满足两个条件的基础上,最小化中路径T的长度|T|。这两个条件是:①移动机器人完成所有任务;②两个连续服务点间距离不超过B。

路径长度等于路径中每连续两个服务点间欧式距离之和。|T|越小表明移动机器人所移动距离越短,所消耗的能量就越少。

因此,FCPP算法需要解决的问题就是:①如何依据任务点构建服务点。所构建的服务点必保证每个任务点都被服务;②构建移动机器人路径,使路径最短,且路径中任意两个连续的服务点间距离不超过B。

2 FCPP算法

FCPP算法旨在保证每个任务点被服务的基础上,寻找服务点;然后再依据这些服务点构建能耗最低的路径。

2.1 基于区域覆盖法的服务点的构建

区域覆盖(geometric covering,GC)法是利用最少的全等副本(congruent copy,CC)覆盖给定的区域目标。令X表示区域目标集。Q表示CC的形状。当利用GC法构建服务点时,则X←K,且Q则是半径为r的圆盘(移动机器人的感测区域)。当移动机器人位于圆盘中心,其能够为圆盘内所有点服务。

因此,利用GC法构建服务点等价于寻找最少数量的圆盘,使这些圆盘联合覆盖K集内每个任务点。该问题属典型的单圆盘覆盖问题(unit disk cover,UDC)[7]。UDC问题假定r=1,即一个单位。由于很容易对r进行扩展,设置r=1并不影响求解UDC问题。

图2 网格化示例

最后,将所构建的圆盘的中心点作为服务点,将这些点加入L,进而构成L集。利用区域覆盖法构建服务点的过程如算法1所示。

令D表示建立的圆盘集。最初集D为空集,即D=∅。对于K中任意一点p,先估计其属哪个网格,如表1所示。

表1 基于区域覆盖法的服务点构建算法

然后,再确认已建立的圆盘{D(i-1,j),D(i+1,j),D(i,j-1),D(i,j+1)}是否已覆盖点p。如果已覆盖,就继续为下一点构建圆盘。否则,就用D(i,j)覆盖点p,即将D(i,j)加入D中,如步骤4所示。

再进入步骤5,计算D中每个圆盘的中心,并将圆心作为移动机器人的服务点,即L=L∪O(i,j),其中O(i,j)表示D(i,j)的中心。

2.2 基于Christofides算法的路径构建

依据2.1节所述,利用算法1构建服务点,完成服务点集L的构建。接下来,需要解决的问题是:依据这些服务点和始点,形成最小权重的闭合路径。每条路径从始点s开始,遍历L中每个服务点且只遍历一次,然后再返至始点s。换而言之,在L∪{s}上建立最小权重路径。这属典型的行商问题(traveling salesman problem,TSP)[8-9]。

TSP问题的输入图G是完备的。该图G是依据输入点集构建的。此外,图G中的边满足三角不等式规则,即对于G中任意3条边(u,v),(v,w),(u,w),它们的权重满足:

weight[(u,v)]+weight[(v,w)]>weight[(u,w)]

(1)

式中:weight[·]表示边的权重。

本文中输入图G是在L∪{s}上构建的完备图,边(u,v)的权重等于节点u,v间的欧式距离,其中点u,v属于L∪{s},即u,v∈L∪{s}。

由于TSP问题是NP问题[10]。本文采用Christofides算法求解[11]。Christofides算法主要是由求解最小生成树(minimum spanning tree,MST)、最小完美匹配和形成欧拉回路3个阶段构成。在求解时,先生成最小生成树,然后,Christofides算法再使用最小完美匹配法得到最小匹配图,最后利用欧拉回路法构建一条TSP问题的近似解。求解步骤如表2所示。

表2 基于Christofides算法

2.3 基于启发式A*的能效路径的建立

从第2.2节可知,2.2节在构建路径时,并没有考虑移动机器人的充电站位置,也没有考虑到充电点。为了保证移动机器人在移动过程不耗尽电量,在构建路径时考虑充电点位置。即路径中连续的两个点间距离不超过B。具体而言,假定u,v表示路径T中连续的两个点,从点u至点v间距离可能超过B,移动机器人可能需要往返充电点。

利用文献[12]所述的启发式A*法在图Ge上构建路径,使路径T中两个连续点间距离不超过B。具体过程如表3所示。启发式A*法的具体过程可参见文献[12-13]。令Te表示由算法3输出的路径,其表示满足路径中连续两个点间距离不超过B的约束条件。

表3 Compute-ETOUR算法

3 性能分析

3.1 仿真环境

3.2 构建服务点集L所需的运行时间

图3给出了利用算法1构建服务点集L所需的运行时间和产生的圆盘数,其中n从100至1000变化。

(a) 运行时间 (b) 圆盘数图3 构建服务点集所需的运行时间和产生的圆盘数

从图3a可知,运行时间随服务点数n增加而上升,且呈近似线性关系。这符合逻辑。服务点数越多,所需的圆盘数越多,如图3b所示。图3b证实了圆盘数随服务点数n增加而上升的结果。例如,当n=400时,产生的圆盘数约240个。当n增加至800时,产生的圆盘数上升至360个。

3.3 构建能效路径所消耗的时间

图4 构建能效路径所消耗的时间

观察图4可得3条结论:①不论B值为何值和多少个充电站数,消耗时间均随n值增加而上升;②在同等条件下,充电站数越多,消耗时间越多;③B值越大,消耗时间也越多。

出现结论①的原因在于:n值越大,所产生的圆盘数越多(可见图3b)。因此,所产生的服务点数也增加,即|L|值变大,利用启发式A*法构建Te时所需计算的位置点就随之增加,这就提升了运算时间,最终增加了消耗时间。

出现结论②的原因在于:充电站数越多,图Ge的尺寸就越大。利用启发式A*法构建Te时所需考虑的点数和边数就越多,最终也增加了运算时间。

出现结论③的原因在于:B值越大,图Ge中共享边中的点数越多,使Ge越密集,最终也增加了运算时间。

3.4 路径长度

图5 路径长度

此外,B值越大,路径长度随|C|变化的波动更小。同时,观察图5可知,当n值越大时,|C|=5%×n与|C|=7%×n间的路径长度的差距越小。原因在于:n值越大,所需的圆盘数越多,参与构建能效路径的点就越多。由于服务点为均匀分布,能效路径中两个连续点间的距离就缩小,最终导致路径变短,它们受充电站数的影响就变小。

4 结束语

本文提出一种任务点全覆盖的能效路径规划算法。该算法假定移动机器人具有固定的感测范围。移动机器人以遍历最少的服务点覆盖所有任务点。FCPP算法依据任务点,并利用区域覆盖法构建圆盘,再将圆盘的中心作为移动机器人的服务点。然后,再利用Christofides算法建立路径。考虑到移动机器人是由电池供电,其电量有限。移动机器人在沿着路径移动中可能需要充电。为了使移动机器人的电量不耗尽,路径中任意两个连续服务点间距离不超过续航距离。仿真结果表明,提出的FCPP算法能够快速地覆盖所有任务点。这说明利用GC法构建服务点集,再通过Christofides算法规划路径,可有效地缩短移动路径,提高了完成任务效率。