在狭窄通道环境下书库管理机器人的最优路径规划*

唐丽娜, 李 琳, 宿 浩， 郭忠文

(1. 中国海洋大学图书馆， 山东 青岛 266100； 2. 中国海洋大学信息科学与工程学院， 山东 青岛 266100)

移动机器人的路径规划问题一直是自动控制和计算机应用领域的重要研究课题。研究人员提出了许多规划方法：如人工势场法[1]、单元分解法[2]、随机路标图法[3]、快速搜索树法[4]等。目前移动机器人的路径规划算法，多数是以最短路径为指标进行研究的[5-6]。在许多情况下，移动机器人在作业范围内行驶的通道非常狭窄。例如为了充分利用图书馆的空间，书库的书架间的通道往往比较狭窄。书库管理机器人在书库中狭窄的通道中穿梭转弯或调头比较困难。因此，在通道狭窄环境下研究移动机器人的路径规划问题需要考虑动机器人的转弯或调头的代价。仅以最短路径为指标的路径规划算法不一定适合于在通道狭窄环境下研究移动机器人的路径规划问题。

近年来，随着图书馆智能化技术的不断发展，国内外已逐步将轮式机器人运用到图书馆书库的管理[7-8]。书库管理机器人在读者借阅和归还图书的过程中，一定程度代替了图书馆员，不但节省人力，还提高了读者借阅和归还图书的效率。例如，图书馆图书自动存取机器人，使得图书自动存取机器人可以在无人干预的情况下对图书进行识别、搬运和上下架[9]。又如利用射频识别(RFID)标签识别图书的定位技术逐步在各类图书馆中推广[10-11]，这一图书识别和定位技术为利用机器人自主完成图书的管理提供了方便[12]。

本文以书库管理机器人为例，研究在狭窄通道环境下自主式移动机器人的定位和路径规划问题。根据书架和图书上的射频识别(RFID)标签，利用RFID技术提出了确定书库管理机器人位置和姿态的方法。针对图书馆书库通道狭窄和可选路径固定的特点，并根据书库管理机器人原地不动、匀速直线运动、原地匀速旋转运动三种运动状态[13]，分别给出了书库管理机器人匀速直线运动和原地匀速旋转运动的用时模型。最后提出了书库管理机器人从任意起始位置和起始姿态到达任意目标位置的最小用时路径规划算法。书库管理机器人在到达目标书架取还书的过程中，根据书库的图书的RFID标签识别机器人所在位置和姿态，并按规划的最优路径到达目标书目的位置。利用最小用时路径规划算法，达到有效节省能源和提高书库管理机器人工作效率的目的。

1 问题描述

现以横向具有m排书架和纵向具有p个通道的图书馆书库为例，研究移动书库管理机器人取书和还书的路径规划问题。假设书架间的通道比较狭窄，但不存在障碍物。本文研究的问题是如何规划一条路线，使得书库管理机器人在任意的初始位置A和初始姿态(行驶方向)下，以最短的行驶时间到达确定的目标位置B。图1表示出了书库管理机器人在具有4行3列书架的书库中的行驶路线，其中位置A和B分别表示书库管理机器人的起始位置和目标位置，(i,j)表示第i行第j列书架间通道交叉点位置，虚线和点划线分别表示两种可选的书库管理机器人行驶路径。

图1 书库管理机器人行驶路线示意图

由于书架间的通道比较狭窄，假设书库管理机器人只有三种运动状态：原地不动、速度为v(m/s)的匀速直线运动和角速度为ω(rad/s)(或-ω(rad/s)的原地匀速旋转运动，其示意图见图2。

图2 书库管理机器人行驶示意图

通常，书库管理机器人在没有接收到工作指令前，可以停止在如图1所示的通道的任意起始位置A。本文的研究目的是书库管理机器人在任意起始位置A接收到到达指定的目标位置B的工作指令后，如何规划一条路径，使得到达目标位置B的用时最少。

2 书库管理机器人的定位方法

在实现书库管理机器人的导航时，首先要知道机器人的起始位置和目标位置。传统的路径导航的机器人的定位常常采用卫星导航或声光传感器等技术确定机器人在电子地图中的起始位置。这些定位方法虽然有效，但增加了定位系统的复杂性和增加了定位系统的制造成本和运营成本。本文根据智能化图书馆的现有环境资源，设计了机器人扫描书上的 RFID 标签来确定机器人的起始位置、起始姿态和目标位置的书库管理机器人的定位方法。随着智能化图书馆的发展，利用RFID 标识图书的信息已经成为发展趋势。在RFID用于智能化图书馆的研究方面，已经取得了很好的研究成果，近年来，中国的科技工作者开始研究中国图书馆RFID应用标准化问题[14]。

为了利用RFID技术既能得到移动机器人的定位信息又能得到移动机器人的姿态信息，本文提出了将RFID阅读器安装于书库管理机器人的侧面的方案。不失一般性，我们以将RFID阅读器安装于机器人的左侧为例，研究书库管理机器人的起始位置、起始姿态和目标位置的书库管理机器人的定位方法。假定所有图书的位置信息都存储于图书馆信息管理系统中。如图3所示，机器人在接收到从目前位置移动到指定的目标位置的指令后，首先读取初始位置处图书的RFID标签。以读取的图书编号确定机器人的当前位置。如果读取的图书编号为奇数，则说明机器人的姿态角θ(行驶方向与x轴夹角)为θ=0°。如果读取的图书编号为偶数，则说明机器人的姿态角θ为θ=180°。

图3 机器识别位置和姿态示意图

本文提出的机器人的位置和姿态定位方法，不需要增加系统的硬件成本，只需要在机器人的控制器(ECU)中的控制软件中增加机器人位置和姿态定位算法，在器上位机(图书馆信息管理系统)中增加由图书的RFID标签信息构成的书库电子地图，并在图书馆员或读者的手机等终端设备中安装一个图书馆图书检索和借还的APP软件，就可以方便地对书库管理机器人进行操控。

3 最优路径规划算法设计

如图1所示，假设点(i,j)到点(i,j+1)的距离为d1,点(i,j)到点(i+1,j)的距离为d2。则书库管理机器人自左向右行驶时，从点(i,j)到点(i,j+1)(或书库管理机器人自右向左行驶时，从点(i,j)到点(i,j-1))的用时为：

(1)

书库管理机器人自下向上行驶时，从点(i,j)到点(i+1,j)(或书库管理机器人自上向下行驶时，从点(i,j)到点(i-1,j))的用时为：

(2)

书库管理机器人原地转90°(或-90°)的用时为：

(3)

假设书库管理机器人的起始位置A在点(i,j)和点(i,j+1)之间，位置A和点(i,j)的距离为a，位置A和点(i,j+1)的距离为d1-a。目标位置B位于(k,m)和(k,m+1)之间，位置B和(k,m)的距离为b，位置B和(k,m+1)的距离为d2-b。书库管理机器人的起始姿态角θ(行驶方向与x轴夹角)为θ=0°或θ=180°。

我们分4种情形讨论书库管理机器人在起始位置A到达目标位置B的路径规划问题。

情形1i=k,j=m

当a>b,θ=180°或a

(4)

当a>b,θ=0°或a

(5)

情形2i=k,j≠m

当j>m,θ=180°或j

(6)

当j>m,θ=0°或j

(7)

情形3i≠k,j=m

(i)当a+b>d1,θ=0°时，书库管理机器人用时最少最佳路径是先由起始位置A直行到达点(i,j+1)，原地转90°后，再由点(i,j+1)直行到达点(k,j+1), 再原地转90°后，由点(k,j+1)直行到达目标位置B。最少用时为：

(8)

(ii)当a+b

(9)

(iii)当a+b>d1,θ=180°时，书库管理机器人用时最少最佳路径是以下两条路径用时最少的路径。第一种路径为：先由起始位置A直行到达点(i,j)，原地转90°后，再由点(i,j)直行到达点(k,j), 再原地转90°后，由点(k,j)直行到达目标位置B。用时为：

(10)

第二种路径为：先在起始位置A原地转180°，后由起始位置A直行到达点(i,j+1)，原地转90°后，再由点(i,j+1)直行到达点(k,j+1), 再原地转90°后，由点(k,j+1)直行到达目标位置B。用时为：

(11)

两种方案用时最少的路径即为最佳路径。最少用时为：

Tmin=min(T1,T2)。

(12)

(iv)当a+b

(13)

第二种路径为：先在起始位置A原地转180°，后由起始位置A直行到达点(i,j)，原地转90°后，再由点(i,j)直行到达点(k,j), 再原地转90°后，由点(k,j)直行到达目标位置B。用时为：

(14)

两种方案用时最少的路径即为最佳路径。最少用时为：

Tmin=min(T3,T4)。

(15)

情形4i≠k,j≠m

(i)当j

(16)

(ii)当j>m,θ=180°时，书库管理机器人用时最少最佳路径是先由起始位置A直行到达点(i,m+1)，原地转90°后，再由点(i,m+1)直行到达点(k,m+1), 再原地转90°后，由点(k,m+1)直行到达目标位置B。最少用时为：

(17)

(iii)当j

(18)

第二种路径为：先在起始位置A原地转180°，后由起始位置A直行到达点(i,j+1)，原地转90°后，再由点(i,j+1)直行到达点(k,j+1), 再原地转90°后，由点(k,j+1)直行到达目标位置B。用时为：

(19)

两种方案用时最少的路径即为最佳路径。最少用时为：

Tmin=min(T5,T6)。

(20)

(iv)当j>m,θ=0°时，书库管理机器人用时最少最佳路径是以下两条路径用时最少的路径。第一种路径为：先由起始位置A直行到达点(i,j+1)，原地转90°后，再由点(i,j+1)直行到达点(k,j+1), 再原地转90°后，由点(k,j+1)直行到达目标位置B。用时为：

(21)

第二种路径为：先在起始位置A原地转180°，后由起始位置A直行到达点(i,j)，原地转90°后，再由点(i,j)直行到达点(k,j), 再原地转90°后，由点(k,j)直行到达目标位置B。用时为：

(22)

两种方案用时最少的路径即为最佳路径。最少用时为：

Tmin=min(T7,T8)。

(23)

在图书馆员或读者利用手机APP等终端设备发出需借还的目标书目信息后，机器人可以按本文提出的机器人定位方法和最优路径规划算法，从初始位置出发在最短的时间内到达目标位置。

4 数字仿真

以图1所示的书库管理机器人的路径规划问题为例，其中位置A和B分别为移动机器人的初始位置和目标位置。我们规定机器人在最靠近目标位置的十字路口转弯。在本例中如果规划的路径为从初始位置A向右行驶，则机器人在点(1,2)向左转弯。然后从点(1,2)向上行驶，机器人在点(3,2)向右转弯。此规定避免了机器人在点(1,1)向左转弯，在点(2,1)向右转弯，在点(2,2)向左转弯，再在点(3,2)向右转弯的不合理的路径规划。

由图1知，i=1,j=0，k=3,m=2，即i

以下分两种情形研究路径规划问题。

(1) 机器人的初始姿态角θ=0°

由情形4(i)知，最优路径为：

(a) 从初始位置A向右行驶至点(1,2)。

(c) 从点(1,2)向上行驶至点(3,2)。

(e) 从点(1,2)向右行驶至目标位置B。

由式(16)得从初始位置A到目标位置B的最少用时为：

(2) 机器人的初始姿态角θ=180°

由情形4(i)知，待选的最优路径有两条，如图1虚线所示路径。由式(18)得第一种路径的用时为：

由式(19)得第二种路径的用时为：

由式(20)得最少用时为：

Tmin=T5=23。

从而得第一种路径为最优路径，即最优路径为：

(a) 从初始位置A向右行驶至点(1,0)。

(c) 从点(1,0)向上行驶至点(3,0)。

(e) 从点(3,0)向右行驶至目标位置B。

5 结语

本文针对图书馆书库通道狭窄和可选路径固定的特点，研究移动机器人最优路径规划问题。提出了利用读取图书的RFID标签信息确定机器人当前的位置和姿态方案，并给出了移动机器人从起始位置到目标位置的最小用时路径规划算法。利用最小用时路径规划算法，可有效的节省系统的硬件成本、节省能源和提高移动机器人的工作效率。