在狹窄通道環(huán)境下書(shū)庫(kù)管理機(jī)器人的最優(yōu)路徑規(guī)劃*

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

(1. 中國(guó)海洋大學(xué)圖書(shū)館， 山東 青島 266100； 2. 中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院， 山東 青島 266100)

移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題一直是自動(dòng)控制和計(jì)算機(jī)應(yīng)用領(lǐng)域的重要研究課題。研究人員提出了許多規(guī)劃方法：如人工勢(shì)場(chǎng)法[1]、單元分解法[2]、隨機(jī)路標(biāo)圖法[3]、快速搜索樹(shù)法[4]等。目前移動(dòng)機(jī)器人的路徑規(guī)劃算法，多數(shù)是以最短路徑為指標(biāo)進(jìn)行研究的[5-6]。在許多情況下，移動(dòng)機(jī)器人在作業(yè)范圍內(nèi)行駛的通道非常狹窄。例如為了充分利用圖書(shū)館的空間，書(shū)庫(kù)的書(shū)架間的通道往往比較狹窄。書(shū)庫(kù)管理機(jī)器人在書(shū)庫(kù)中狹窄的通道中穿梭轉(zhuǎn)彎或調(diào)頭比較困難。因此，在通道狹窄環(huán)境下研究移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題需要考慮動(dòng)機(jī)器人的轉(zhuǎn)彎或調(diào)頭的代價(jià)。僅以最短路徑為指標(biāo)的路徑規(guī)劃算法不一定適合于在通道狹窄環(huán)境下研究移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題。

近年來(lái)，隨著圖書(shū)館智能化技術(shù)的不斷發(fā)展，國(guó)內(nèi)外已逐步將輪式機(jī)器人運(yùn)用到圖書(shū)館書(shū)庫(kù)的管理[7-8]。書(shū)庫(kù)管理機(jī)器人在讀者借閱和歸還圖書(shū)的過(guò)程中，一定程度代替了圖書(shū)館員，不但節(jié)省人力，還提高了讀者借閱和歸還圖書(shū)的效率。例如，圖書(shū)館圖書(shū)自動(dòng)存取機(jī)器人，使得圖書(shū)自動(dòng)存取機(jī)器人可以在無(wú)人干預(yù)的情況下對(duì)圖書(shū)進(jìn)行識(shí)別、搬運(yùn)和上下架[9]。又如利用射頻識(shí)別(RFID)標(biāo)簽識(shí)別圖書(shū)的定位技術(shù)逐步在各類(lèi)圖書(shū)館中推廣[10-11]，這一圖書(shū)識(shí)別和定位技術(shù)為利用機(jī)器人自主完成圖書(shū)的管理提供了方便[12]。

本文以書(shū)庫(kù)管理機(jī)器人為例，研究在狹窄通道環(huán)境下自主式移動(dòng)機(jī)器人的定位和路徑規(guī)劃問(wèn)題。根據(jù)書(shū)架和圖書(shū)上的射頻識(shí)別(RFID)標(biāo)簽，利用RFID技術(shù)提出了確定書(shū)庫(kù)管理機(jī)器人位置和姿態(tài)的方法。針對(duì)圖書(shū)館書(shū)庫(kù)通道狹窄和可選路徑固定的特點(diǎn)，并根據(jù)書(shū)庫(kù)管理機(jī)器人原地不動(dòng)、勻速直線運(yùn)動(dòng)、原地勻速旋轉(zhuǎn)運(yùn)動(dòng)三種運(yùn)動(dòng)狀態(tài)[13]，分別給出了書(shū)庫(kù)管理機(jī)器人勻速直線運(yùn)動(dòng)和原地勻速旋轉(zhuǎn)運(yùn)動(dòng)的用時(shí)模型。最后提出了書(shū)庫(kù)管理機(jī)器人從任意起始位置和起始姿態(tài)到達(dá)任意目標(biāo)位置的最小用時(shí)路徑規(guī)劃算法。書(shū)庫(kù)管理機(jī)器人在到達(dá)目標(biāo)書(shū)架取還書(shū)的過(guò)程中，根據(jù)書(shū)庫(kù)的圖書(shū)的RFID標(biāo)簽識(shí)別機(jī)器人所在位置和姿態(tài)，并按規(guī)劃的最優(yōu)路徑到達(dá)目標(biāo)書(shū)目的位置。利用最小用時(shí)路徑規(guī)劃算法，達(dá)到有效節(jié)省能源和提高書(shū)庫(kù)管理機(jī)器人工作效率的目的。

1 問(wèn)題描述

現(xiàn)以橫向具有m排書(shū)架和縱向具有p個(gè)通道的圖書(shū)館書(shū)庫(kù)為例，研究移動(dòng)書(shū)庫(kù)管理機(jī)器人取書(shū)和還書(shū)的路徑規(guī)劃問(wèn)題。假設(shè)書(shū)架間的通道比較狹窄，但不存在障礙物。本文研究的問(wèn)題是如何規(guī)劃一條路線，使得書(shū)庫(kù)管理機(jī)器人在任意的初始位置A和初始姿態(tài)(行駛方向)下，以最短的行駛時(shí)間到達(dá)確定的目標(biāo)位置B。圖1表示出了書(shū)庫(kù)管理機(jī)器人在具有4行3列書(shū)架的書(shū)庫(kù)中的行駛路線，其中位置A和B分別表示書(shū)庫(kù)管理機(jī)器人的起始位置和目標(biāo)位置，(i,j)表示第i行第j列書(shū)架間通道交叉點(diǎn)位置，虛線和點(diǎn)劃線分別表示兩種可選的書(shū)庫(kù)管理機(jī)器人行駛路徑。

圖1 書(shū)庫(kù)管理機(jī)器人行駛路線示意圖

由于書(shū)架間的通道比較狹窄，假設(shè)書(shū)庫(kù)管理機(jī)器人只有三種運(yùn)動(dòng)狀態(tài)：原地不動(dòng)、速度為v(m/s)的勻速直線運(yùn)動(dòng)和角速度為ω(rad/s)(或-ω(rad/s)的原地勻速旋轉(zhuǎn)運(yùn)動(dòng)，其示意圖見(jiàn)圖2。

圖2 書(shū)庫(kù)管理機(jī)器人行駛示意圖

通常，書(shū)庫(kù)管理機(jī)器人在沒(méi)有接收到工作指令前，可以停止在如圖1所示的通道的任意起始位置A。本文的研究目的是書(shū)庫(kù)管理機(jī)器人在任意起始位置A接收到到達(dá)指定的目標(biāo)位置B的工作指令后，如何規(guī)劃一條路徑，使得到達(dá)目標(biāo)位置B的用時(shí)最少。

2 書(shū)庫(kù)管理機(jī)器人的定位方法

在實(shí)現(xiàn)書(shū)庫(kù)管理機(jī)器人的導(dǎo)航時(shí)，首先要知道機(jī)器人的起始位置和目標(biāo)位置。傳統(tǒng)的路徑導(dǎo)航的機(jī)器人的定位常常采用衛(wèi)星導(dǎo)航或聲光傳感器等技術(shù)確定機(jī)器人在電子地圖中的起始位置。這些定位方法雖然有效，但增加了定位系統(tǒng)的復(fù)雜性和增加了定位系統(tǒng)的制造成本和運(yùn)營(yíng)成本。本文根據(jù)智能化圖書(shū)館的現(xiàn)有環(huán)境資源，設(shè)計(jì)了機(jī)器人掃描書(shū)上的 RFID 標(biāo)簽來(lái)確定機(jī)器人的起始位置、起始姿態(tài)和目標(biāo)位置的書(shū)庫(kù)管理機(jī)器人的定位方法。隨著智能化圖書(shū)館的發(fā)展，利用RFID 標(biāo)識(shí)圖書(shū)的信息已經(jīng)成為發(fā)展趨勢(shì)。在RFID用于智能化圖書(shū)館的研究方面，已經(jīng)取得了很好的研究成果，近年來(lái)，中國(guó)的科技工作者開(kāi)始研究中國(guó)圖書(shū)館RFID應(yīng)用標(biāo)準(zhǔn)化問(wèn)題[14]。

為了利用RFID技術(shù)既能得到移動(dòng)機(jī)器人的定位信息又能得到移動(dòng)機(jī)器人的姿態(tài)信息，本文提出了將RFID閱讀器安裝于書(shū)庫(kù)管理機(jī)器人的側(cè)面的方案。不失一般性，我們以將RFID閱讀器安裝于機(jī)器人的左側(cè)為例，研究書(shū)庫(kù)管理機(jī)器人的起始位置、起始姿態(tài)和目標(biāo)位置的書(shū)庫(kù)管理機(jī)器人的定位方法。假定所有圖書(shū)的位置信息都存儲(chǔ)于圖書(shū)館信息管理系統(tǒng)中。如圖3所示，機(jī)器人在接收到從目前位置移動(dòng)到指定的目標(biāo)位置的指令后，首先讀取初始位置處圖書(shū)的RFID標(biāo)簽。以讀取的圖書(shū)編號(hào)確定機(jī)器人的當(dāng)前位置。如果讀取的圖書(shū)編號(hào)為奇數(shù)，則說(shuō)明機(jī)器人的姿態(tài)角θ(行駛方向與x軸夾角)為θ=0°。如果讀取的圖書(shū)編號(hào)為偶數(shù)，則說(shuō)明機(jī)器人的姿態(tài)角θ為θ=180°。

圖3 機(jī)器識(shí)別位置和姿態(tài)示意圖

本文提出的機(jī)器人的位置和姿態(tài)定位方法，不需要增加系統(tǒng)的硬件成本，只需要在機(jī)器人的控制器(ECU)中的控制軟件中增加機(jī)器人位置和姿態(tài)定位算法，在器上位機(jī)(圖書(shū)館信息管理系統(tǒng))中增加由圖書(shū)的RFID標(biāo)簽信息構(gòu)成的書(shū)庫(kù)電子地圖，并在圖書(shū)館員或讀者的手機(jī)等終端設(shè)備中安裝一個(gè)圖書(shū)館圖書(shū)檢索和借還的APP軟件，就可以方便地對(duì)書(shū)庫(kù)管理機(jī)器人進(jìn)行操控。

3 最優(yōu)路徑規(guī)劃算法設(shè)計(jì)

如圖1所示，假設(shè)點(diǎn)(i,j)到點(diǎn)(i,j+1)的距離為d1,點(diǎn)(i,j)到點(diǎn)(i+1,j)的距離為d2。則書(shū)庫(kù)管理機(jī)器人自左向右行駛時(shí)，從點(diǎn)(i,j)到點(diǎn)(i,j+1)(或書(shū)庫(kù)管理機(jī)器人自右向左行駛時(shí)，從點(diǎn)(i,j)到點(diǎn)(i,j-1))的用時(shí)為：

(1)

書(shū)庫(kù)管理機(jī)器人自下向上行駛時(shí)，從點(diǎn)(i,j)到點(diǎn)(i+1,j)(或書(shū)庫(kù)管理機(jī)器人自上向下行駛時(shí)，從點(diǎn)(i,j)到點(diǎn)(i-1,j))的用時(shí)為：

(2)

書(shū)庫(kù)管理機(jī)器人原地轉(zhuǎn)90°(或-90°)的用時(shí)為：

(3)

假設(shè)書(shū)庫(kù)管理機(jī)器人的起始位置A在點(diǎn)(i,j)和點(diǎn)(i,j+1)之間，位置A和點(diǎn)(i,j)的距離為a，位置A和點(diǎn)(i,j+1)的距離為d1-a。目標(biāo)位置B位于(k,m)和(k,m+1)之間，位置B和(k,m)的距離為b，位置B和(k,m+1)的距離為d2-b。書(shū)庫(kù)管理機(jī)器人的起始姿態(tài)角θ(行駛方向與x軸夾角)為θ=0°或θ=180°。

我們分4種情形討論書(shū)庫(kù)管理機(jī)器人在起始位置A到達(dá)目標(biāo)位置B的路徑規(guī)劃問(wèn)題。

情形1i=k,j=m

當(dāng)a>b,θ=180°或a

(4)

當(dāng)a>b,θ=0°或a

(5)

情形2i=k,j≠m

當(dāng)j>m,θ=180°或j

(6)

當(dāng)j>m,θ=0°或j

(7)

情形3i≠k,j=m

(i)當(dāng)a+b>d1,θ=0°時(shí)，書(shū)庫(kù)管理機(jī)器人用時(shí)最少最佳路徑是先由起始位置A直行到達(dá)點(diǎn)(i,j+1)，原地轉(zhuǎn)90°后，再由點(diǎn)(i,j+1)直行到達(dá)點(diǎn)(k,j+1), 再原地轉(zhuǎn)90°后，由點(diǎn)(k,j+1)直行到達(dá)目標(biāo)位置B。最少用時(shí)為：

(8)

(ii)當(dāng)a+b

(9)

(iii)當(dāng)a+b>d1,θ=180°時(shí)，書(shū)庫(kù)管理機(jī)器人用時(shí)最少最佳路徑是以下兩條路徑用時(shí)最少的路徑。第一種路徑為：先由起始位置A直行到達(dá)點(diǎn)(i,j)，原地轉(zhuǎn)90°后，再由點(diǎn)(i,j)直行到達(dá)點(diǎn)(k,j), 再原地轉(zhuǎn)90°后，由點(diǎn)(k,j)直行到達(dá)目標(biāo)位置B。用時(shí)為：

(10)

第二種路徑為：先在起始位置A原地轉(zhuǎn)180°，后由起始位置A直行到達(dá)點(diǎn)(i,j+1)，原地轉(zhuǎn)90°后，再由點(diǎn)(i,j+1)直行到達(dá)點(diǎn)(k,j+1), 再原地轉(zhuǎn)90°后，由點(diǎn)(k,j+1)直行到達(dá)目標(biāo)位置B。用時(shí)為：

(11)

兩種方案用時(shí)最少的路徑即為最佳路徑。最少用時(shí)為：

Tmin=min(T1,T2)。

(12)

(iv)當(dāng)a+b

(13)

第二種路徑為：先在起始位置A原地轉(zhuǎn)180°，后由起始位置A直行到達(dá)點(diǎn)(i,j)，原地轉(zhuǎn)90°后，再由點(diǎn)(i,j)直行到達(dá)點(diǎn)(k,j), 再原地轉(zhuǎn)90°后，由點(diǎn)(k,j)直行到達(dá)目標(biāo)位置B。用時(shí)為：

(14)

兩種方案用時(shí)最少的路徑即為最佳路徑。最少用時(shí)為：

Tmin=min(T3,T4)。

(15)

情形4i≠k,j≠m

(i)當(dāng)j

(16)

(ii)當(dāng)j>m,θ=180°時(shí)，書(shū)庫(kù)管理機(jī)器人用時(shí)最少最佳路徑是先由起始位置A直行到達(dá)點(diǎn)(i,m+1)，原地轉(zhuǎn)90°后，再由點(diǎn)(i,m+1)直行到達(dá)點(diǎn)(k,m+1), 再原地轉(zhuǎn)90°后，由點(diǎn)(k,m+1)直行到達(dá)目標(biāo)位置B。最少用時(shí)為：

(17)

(iii)當(dāng)j

(18)

第二種路徑為：先在起始位置A原地轉(zhuǎn)180°，后由起始位置A直行到達(dá)點(diǎn)(i,j+1)，原地轉(zhuǎn)90°后，再由點(diǎn)(i,j+1)直行到達(dá)點(diǎn)(k,j+1), 再原地轉(zhuǎn)90°后，由點(diǎn)(k,j+1)直行到達(dá)目標(biāo)位置B。用時(shí)為：

(19)

兩種方案用時(shí)最少的路徑即為最佳路徑。最少用時(shí)為：

Tmin=min(T5,T6)。

(20)

(iv)當(dāng)j>m,θ=0°時(shí)，書(shū)庫(kù)管理機(jī)器人用時(shí)最少最佳路徑是以下兩條路徑用時(shí)最少的路徑。第一種路徑為：先由起始位置A直行到達(dá)點(diǎn)(i,j+1)，原地轉(zhuǎn)90°后，再由點(diǎn)(i,j+1)直行到達(dá)點(diǎn)(k,j+1), 再原地轉(zhuǎn)90°后，由點(diǎn)(k,j+1)直行到達(dá)目標(biāo)位置B。用時(shí)為：

(21)

第二種路徑為：先在起始位置A原地轉(zhuǎn)180°，后由起始位置A直行到達(dá)點(diǎn)(i,j)，原地轉(zhuǎn)90°后，再由點(diǎn)(i,j)直行到達(dá)點(diǎn)(k,j), 再原地轉(zhuǎn)90°后，由點(diǎn)(k,j)直行到達(dá)目標(biāo)位置B。用時(shí)為：

(22)

兩種方案用時(shí)最少的路徑即為最佳路徑。最少用時(shí)為：

Tmin=min(T7,T8)。

(23)

在圖書(shū)館員或讀者利用手機(jī)APP等終端設(shè)備發(fā)出需借還的目標(biāo)書(shū)目信息后，機(jī)器人可以按本文提出的機(jī)器人定位方法和最優(yōu)路徑規(guī)劃算法，從初始位置出發(fā)在最短的時(shí)間內(nèi)到達(dá)目標(biāo)位置。

4 數(shù)字仿真

以圖1所示的書(shū)庫(kù)管理機(jī)器人的路徑規(guī)劃問(wèn)題為例，其中位置A和B分別為移動(dòng)機(jī)器人的初始位置和目標(biāo)位置。我們規(guī)定機(jī)器人在最靠近目標(biāo)位置的十字路口轉(zhuǎn)彎。在本例中如果規(guī)劃的路徑為從初始位置A向右行駛，則機(jī)器人在點(diǎn)(1,2)向左轉(zhuǎn)彎。然后從點(diǎn)(1,2)向上行駛，機(jī)器人在點(diǎn)(3,2)向右轉(zhuǎn)彎。此規(guī)定避免了機(jī)器人在點(diǎn)(1,1)向左轉(zhuǎn)彎，在點(diǎn)(2,1)向右轉(zhuǎn)彎，在點(diǎn)(2,2)向左轉(zhuǎn)彎，再在點(diǎn)(3,2)向右轉(zhuǎn)彎的不合理的路徑規(guī)劃。

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

以下分兩種情形研究路徑規(guī)劃問(wèn)題。

(1) 機(jī)器人的初始姿態(tài)角θ=0°

由情形4(i)知，最優(yōu)路徑為：

(a) 從初始位置A向右行駛至點(diǎn)(1,2)。

(c) 從點(diǎn)(1,2)向上行駛至點(diǎn)(3,2)。

(e) 從點(diǎn)(1,2)向右行駛至目標(biāo)位置B。

由式(16)得從初始位置A到目標(biāo)位置B的最少用時(shí)為：

(2) 機(jī)器人的初始姿態(tài)角θ=180°

由情形4(i)知，待選的最優(yōu)路徑有兩條，如圖1虛線所示路徑。由式(18)得第一種路徑的用時(shí)為：

由式(19)得第二種路徑的用時(shí)為：

由式(20)得最少用時(shí)為：

Tmin=T5=23。

從而得第一種路徑為最優(yōu)路徑，即最優(yōu)路徑為：

(a) 從初始位置A向右行駛至點(diǎn)(1,0)。

(c) 從點(diǎn)(1,0)向上行駛至點(diǎn)(3,0)。

(e) 從點(diǎn)(3,0)向右行駛至目標(biāo)位置B。

5 結(jié)語(yǔ)

本文針對(duì)圖書(shū)館書(shū)庫(kù)通道狹窄和可選路徑固定的特點(diǎn)，研究移動(dòng)機(jī)器人最優(yōu)路徑規(guī)劃問(wèn)題。提出了利用讀取圖書(shū)的RFID標(biāo)簽信息確定機(jī)器人當(dāng)前的位置和姿態(tài)方案，并給出了移動(dòng)機(jī)器人從起始位置到目標(biāo)位置的最小用時(shí)路徑規(guī)劃算法。利用最小用時(shí)路徑規(guī)劃算法，可有效的節(jié)省系統(tǒng)的硬件成本、節(jié)省能源和提高移動(dòng)機(jī)器人的工作效率。