星形多邊形搜索策略的研究

（蘭州理工大學(xué) 計算機(jī)與通信學(xué)院， 蘭州 730050）

摘 要：在自動化機(jī)器人的導(dǎo)航問題中，機(jī)器人必須在不具備全部信息或在不確定情況下反復(fù)作出決定且最終要找到未知環(huán)境中的目標(biāo)；當(dāng)機(jī)器人獲得了全部信息時問題得到解決。研究多邊形內(nèi)目標(biāo)的在線搜索問題，提出了一種用于查找星形多邊形內(nèi)未知目標(biāo)的搜索策略，這一策略具有競爭比11.18，它獨(dú)立于起始點(diǎn)和目標(biāo)點(diǎn)所在的位置。

關(guān)鍵詞：在線搜索;競爭比;搜索策略;星形多邊形

中圖分類號：TP393.04 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2009)02051803



Study on strategy to search in starshaped polygons



LIN Qiang，ZHANG Yuanping，CHEN Hua，HE Yi

(School of Computer Communication ， Lanzhou University of Technology， Lanzhou 730050， China)

Abstract:In the navigation problem of autonomous robots， the robot must repeatedly make decisions without full knowledge or under uncertainty and find a goal in an unknown environment finally; the problem is solved when the robot has gained full information.This paper studied the problem of online searching for a target inside a polygon and proposed a strategy for finding a target of unknown location in a starshaped polygon with a competitive ratio of 11.18， it was independent on the starting position of the robot and the position of the target.

Key words:online searching; competitive ratio; searching strategy; starshaped polygons

過去幾年中，在線搜索問題已成為計算機(jī)科學(xué)研究中的一個熱門領(lǐng)域[1~5]。在這些問題的所有研究成果中，一個在線搜索問題由一個代理搜索未知區(qū)域中的目標(biāo)所組成。機(jī)器人在一般區(qū)域中的搜索路徑長度通常比從初始點(diǎn)到目標(biāo)點(diǎn)之間的最短路徑長很多。搜索策略會隨著搜索區(qū)域的類型以及機(jī)器人搜索能力的不同而有所改變。假設(shè)機(jī)器人裝備有可視系統(tǒng)，它能使機(jī)器人看到當(dāng)前局部環(huán)境。機(jī)器人必須在僅掌握部分環(huán)境信息的基礎(chǔ)上作出搜索的決策，所以機(jī)器人搜索問題為在線問題。在線搜索策略的性能由機(jī)器人在這一策略下所走過的路徑長度與起始點(diǎn)s到目標(biāo)點(diǎn)t之間的最短路徑長度的比值來衡量。將機(jī)器人遍歷過的路徑長度與s到t間最短距離的比值中的最大值稱為搜索策略的競爭比（率）。

截止目前有幾類多邊形具有常數(shù)競爭比，最具代表性的是街（street）[6~8]、廣義街（gstreet）[9，10]、水平垂直街（HVstreet）及θ街（θstreet）[11]。以上多邊形搜索策略常數(shù)競爭比的存在依賴于目標(biāo)點(diǎn)所在的位置。

最早考慮的位置獨(dú)立的在線可搜索多邊形是星形多邊形，其競爭比隨著搜索策略的不同而不同。當(dāng)機(jī)器人沿著直線策略接近目標(biāo)時獲得競爭比14.5；當(dāng)沿半圓曲線策略接近目標(biāo)時獲得競爭比11.52[12]，且這種多邊形搜索策略競爭比的低界值為9[13]。借助于星形多邊中搜索所采用的方法，街多邊形成為目標(biāo)點(diǎn)和搜索者位置獨(dú)立的常數(shù)競爭比可搜索多邊形[14]。本文在文獻(xiàn)[12]的基礎(chǔ)上提出一種新的星形多邊形目標(biāo)搜索策略，這一策略具有常數(shù)競爭比且與位置獨(dú)立。

1 定義

稱多邊形P中兩點(diǎn)p和p′相互可見，如果線段pp′完全包含在P中。若A和B是兩個點(diǎn)集，稱A從B勉強(qiáng)可見，如果A中的所有點(diǎn)從B中的某一點(diǎn)可見。

定義1 設(shè)p為多邊形P中的一點(diǎn)，點(diǎn)p在P中的可見多邊形VisP(p)是從p可見的P中點(diǎn)的子集。

定義2[15] 如果簡單多邊形P中存在一點(diǎn)p使得VisP(p)=P，則P是星形多邊形。所有VisP(p)=P的P中點(diǎn)p構(gòu)成的集合叫做P的核，記做Ker(P)。

如果機(jī)器人的起始位置不在Ker（P）中，那么P中存在機(jī)器人不可見的部分，把P\\VisP(p)稱為暗區(qū)（pockets）。暗區(qū)的邊界由P的一些邊及一條不屬于P邊界的線段組成，稱這條線段為VisP(p)的窗口（window）。一個窗口僅在其端點(diǎn)處與多邊形P的邊界相交，其中一個交點(diǎn)為多邊形P的頂點(diǎn)，稱這一點(diǎn)為暗區(qū)的入點(diǎn)（entrance）。一般而言，將一條僅在其端點(diǎn)處與P邊界相交的線段叫做P的弦（chord）。

設(shè)p和q為P中的兩個點(diǎn)，用shp(p，q)表示從p到q的最短路徑。所有從p到P頂點(diǎn)的最短路徑構(gòu)成的整體形成了一個樹狀結(jié)構(gòu)，稱這一結(jié)構(gòu)為p的最短路徑樹，用shptree(p，q)表示。通過延長最短路徑樹上從p開始的線段直到與P的邊界相交來擴(kuò)展這一種樹狀結(jié)構(gòu)，將擴(kuò)展后的這一新結(jié)構(gòu)稱為p的擴(kuò)展最短路徑樹，用shptree*(p，q)表示。延長線的終點(diǎn)也即它與P邊界的交點(diǎn)叫做p的擴(kuò)展點(diǎn)。p的擴(kuò)展最短路徑樹將P劃分成若干個三角形，每一個三角形中離p最近的點(diǎn)叫做三角形的錨點(diǎn)(anchor)。

P的一條暗區(qū)邊是P中的一條線段，它始于p且包括至少一個窗口。每一條暗區(qū)邊是shptree* (p，q)的一部分。更一般地，p的一條擴(kuò)展暗區(qū)路徑是一條從p到p的擴(kuò)展點(diǎn)之間的最短路徑。很明顯，一條擴(kuò)展暗區(qū)路徑也是shptree* (p，q)的一部分。

一個暗區(qū)被稱做是左暗區(qū)，如果它當(dāng)前位于包含其窗口的暗區(qū)射線的左側(cè)。一條暗區(qū)邊被稱為是左暗區(qū)邊，如果它定義一個左暗區(qū)。一條擴(kuò)展暗區(qū)路徑是左擴(kuò)展暗區(qū)路徑，如果它的起初部分線段與左暗區(qū)邊重合。右暗區(qū)、右暗區(qū)邊以及右擴(kuò)展暗區(qū)路徑的定義與上述類似。

例如，在圖1所示的多邊形中，L1和L2為左暗區(qū)，R為右暗區(qū)；線段v1v′1、v2v′2和v3v′3是VisP(p)的窗口；v1、v2分別為L1和L2的入點(diǎn)，v3為R的入點(diǎn)；v1、v2同時也是錨點(diǎn)；

pv1、pv2和pv3分別為兩條左暗區(qū)邊和一條右暗區(qū)邊；

pv′1、

pv′2和pv′3為擴(kuò)展暗區(qū)路徑；v′1、v′2和v′3為點(diǎn)p的擴(kuò)展點(diǎn)。

令V為P的所有反射點(diǎn)和p的擴(kuò)展點(diǎn)構(gòu)成的集合， v∈V為左擴(kuò)展暗區(qū)路徑Ev上的一點(diǎn)，類似地，令v′∈Ev′，這里Ev≠Ev′。稱shp(p，v)在shp(p， v′)的右側(cè)，如果shp(p，v)包括shp(p， v′)或者Ev在Ev′的右側(cè)。用Edleftt表示一條最右側(cè)的左擴(kuò)展暗區(qū)路徑，其中d為給定的最大距離。定義Edleftt的目的在于如果要走向距離為d的位置，盡可能多地封鎖Edleftt左側(cè)的部分。用shp(p，v)表示長度至多為d的最右側(cè)的最短路徑，如果這樣的路徑存在，那么Edleftt就由shp(p，v)連同shp(p，v)末端線段的延長線定義；否則，可任意定義Edleftt為最右側(cè)的擴(kuò)展暗區(qū)路徑。最左側(cè)的右擴(kuò)展暗區(qū)路徑Edright的定義與Edleftt類似。

因?yàn)镵er(P)中的任意一點(diǎn)可看到P中的所有點(diǎn)，特別地，對于p而言，VisP(p)的一個暗區(qū)不會與Ker(P)相交，這意味著有下面的引理。

引理 Ker(P)位于所有左暗區(qū)邊的右側(cè)，所有右暗區(qū)的左側(cè)。

例如，在圖1所示的多邊形中，若存在核，那么它位于暗區(qū)邊pv1、pv2的右側(cè)和pv3的左側(cè)。

上述引理意味著，在一個星形多邊形中，當(dāng)順時針掃描多邊形邊界時所有左暗區(qū)邊連續(xù)出現(xiàn)；同理，當(dāng)逆時針掃描多邊形邊界時所有右暗區(qū)邊連續(xù)出現(xiàn)。特別地，在交換左右暗區(qū)邊之前順時針排列左暗區(qū)邊，逆時針排列右暗區(qū)邊，反之亦然。因此，存在一個最順時針（最右側(cè)）的左暗區(qū)邊，記為El；存在一個最逆時針（最左側(cè)）的右暗區(qū)邊，記為Er。這樣核就位于El和Er之間。本文將在星形多邊形搜索算法中使用這種排列，當(dāng)然也可以將這種排列應(yīng)用到擴(kuò)展暗區(qū)路徑中。

2 星形多邊形中的目標(biāo)搜索

2.1 搜索算法

SPS算法(星形多邊形搜索算法)

輸入:星形多邊形P和起始點(diǎn)s

輸出:目標(biāo)點(diǎn)t的位置

令p0為離s最近的入點(diǎn)，E0為相對于p0的暗區(qū)邊

d0←d(p0，s)，i←0

if E0是左暗區(qū)邊

thenside←letf

elseside←right

loop

從s開始在Ei上遍歷di長度

if t已被看到 then exit loop

di+1←c×di

返回到s

side← ┐side

Ei+1←Edleftt

i←i+1

if t被看見then走向t

上述算法的主要思想在于機(jī)器人交替地搜索以s為起點(diǎn)（經(jīng)合理選擇的）的左右擴(kuò)展暗區(qū)路徑，且將每次搜索的深度乘以常數(shù)c。c是相鄰搜索步長的倍數(shù)，即di+1=c×di，它的值在競爭比分析中確定；d(p0，s)表示點(diǎn)p0到點(diǎn)s間的歐氏距離；定義┐left=right，┐right=left。

事實(shí)上，對于上述算法而言，不可能通過對步長di取值的選擇來降低競爭比[1，16]。本文目的在于通過對搜索的改進(jìn)來降低競爭比，以提高競爭性。

2.2 新的搜索策略

2.2.1 策略描述

令qi為在第i步探索Ei時的終點(diǎn)，當(dāng)∠qi-2sqi接近平角時最壞情況發(fā)生。在這種情況下當(dāng)機(jī)器人沿著圖2所示的曲線前進(jìn)而不是沿sq1直線前進(jìn)時，目標(biāo)點(diǎn)會被提前發(fā)現(xiàn)。所以在策略中機(jī)器人前進(jìn)的路徑由fl生成的正弦曲線的一半（以下簡稱正弦弧）Sl代替屬于Ei的弦fl=vlvl+1。

Sl的構(gòu)造如下（圖3）:

a）構(gòu)造通過點(diǎn)vl和vl+1且中心點(diǎn)(正弦曲線最高點(diǎn)所對應(yīng)的橫標(biāo)上的點(diǎn))在fl上的正弦曲線的一半(以下簡稱正弦弧)S(1)；

b)若S(1)已經(jīng)到達(dá)vl+1，則完成對Sl的構(gòu)造，否則轉(zhuǎn)到c)；

c)找出從vl可見的P邊界上的一點(diǎn)q(1)，構(gòu)造通過點(diǎn)vl和q(1)且中心在fl上的正弦弧S(1)，S(1)上從vl到q(1)的部分便是Sl的第一部分，以下類似；

d）找出P邊界上從vl可見的另一點(diǎn)q(2)，構(gòu)造通過點(diǎn)q(1)和q(2)且中心在fl上的正弦弧S(2)；

e)假設(shè)Sl的構(gòu)造已經(jīng)到達(dá)q(j)階段，1≤j≤kl-1，則S(j+1)由通過點(diǎn)q(j)及vl+1且中心在fl上的正弦弧構(gòu)造。

為了保證機(jī)器人能盡早地發(fā)現(xiàn)目標(biāo)，但同時又考慮到使機(jī)器人總的路徑長度較短，選擇sin(1.57x)且x∈[0，1]為策略中用到的曲線弧；同時，每個S(j)的中心在fl上且s(j+1)在s(j)的右側(cè)，1≤j≤kl-1。

2.2.2 競爭比分析

s為起始點(diǎn)，t為目標(biāo)點(diǎn)，最后一條簡單路徑En由q1qr定義(圖4)。t點(diǎn)當(dāng)前所在位置是機(jī)器人發(fā)現(xiàn)目標(biāo)的最壞情況，也即機(jī)器人不論沿著哪條路徑（半圓曲線或正弦弧）前進(jìn)，只有到達(dá)點(diǎn)q1時才能發(fā)現(xiàn)目標(biāo)。機(jī)器人在最后一步所經(jīng)過的路徑長度至多是d(s，t)的2.5882+1倍且線段sq1所對半圓的長度是d(s，q1)的（π-θ）/sin θ倍[12]，而線段sq1所對的正弦弧長與半圓長度的比值約為0.931 7(這里假定半徑為1)。這樣競爭比由下式界定： 

[（1+0.931 7(π-θ)/sin θ)n-1i=0cid0+

(2.5882+1)d(s，t)]/d(s，t)≤

(1+0.931 7(π-θ)/sin θ)c2/(c-1)+2.77

因?yàn)閐(s，t)≥cn-2d0且機(jī)器人到點(diǎn)qi及返回所走過的距離由(1+0.931 7(π-θ)/sin θ)di界定，取θ值為2.152，當(dāng)c=2時上述表達(dá)式值最小，所獲得的競爭比為2.77+(1+0.931 7×1.184 1)×4≈11.18。值得注意的是，當(dāng)在第i步離s的距離為 di-2處發(fā)現(xiàn)目標(biāo)時，最壞情況依然發(fā)生。的確，在這種情況下，機(jī)器人前i-1步的遍歷全部返回到起始點(diǎn)s，第i步遍歷的任何距離只會使競爭比變大。

在上面的分析中假設(shè)En是一條簡單暗區(qū)邊。如果En不是一條簡單暗區(qū)邊則機(jī)器人分別對En的每一條暗區(qū)邊分離地構(gòu)造Sl。

定理 存在一種用于搜索星形多邊形內(nèi)目標(biāo)的新策略，這一策略具有競爭比至多為11.18。

3 結(jié)束語

本文以文獻(xiàn)[12]的結(jié)論為基礎(chǔ)，提出了一種用于在線搜索星形多邊形的新策略。這一策略使競爭比從原來的11.52降低到11.18，且它獨(dú)立于機(jī)器人起始點(diǎn)及目標(biāo)點(diǎn)所在的位置，這一結(jié)果迄今為止是最好的。可否通過選用其他曲線來構(gòu)造不同的策略以實(shí)現(xiàn)競爭比的降低也是一個值得考慮的問題；同時，能否將這一策略應(yīng)用到其他類型的多邊形（如街多邊形）有待進(jìn)一步研究。

參考文獻(xiàn)：

［1］

BAEZAYATES R，CULBERSON J，RAWLINS G.Searching in the plane[J].Information and Computation，1993，106（2）:234252.

[2]BERMAN P，BLUM A，F(xiàn)IAT A，et al.Randomized robot navigation algorithms[C]//Proc of the 7th ACMSIAM Symposium on Discrete Algorithms.Philadelphia:SIAM，1996:7584.

[3]BLUM A，RAGHAVAN P，SCHIEBER B.Navigating in unfamiliar geometric terrain[C]//Proc of the 23rd ACM Symposium on Theory of Computing.New York:ACM，1991:495504.

[4]KAO M Y，REIF J H，TATE S R.Searching in an unknown environment:an optimal randomized algorithm for the cowpath problem[C]//Proc of the 4th ACMSIAM Symposium on Discrete Algorithms.Philadelphia:SIAM，1992:441447.

[5]KLEINBERG J.Online search in a simple polygon[C]//Proc of the 5th ACMSIAM Symposium on Discrete Algorithms.Philadelphia:SIAM，1994:815.

[6]ICKING C H，KLEIN R，LANGETEPE E.An optimal competitive strategy for walking in strees[C]//Proc of the 16th Symposium on Theoretical Aspects of Computer Science.Berlin:Springer，1999:110120.

[7]KLEIN R.Walking an unknown street with bounded detour[C]//Proc of the 32nd Annual Symposium on Foundations of Computer Science.1991:304313.

[8]SCHUIERER S，SEMRAU I.An optimal strategy for searching in unknown streets[C]//Proc of the 16th Symposium on Theoretical Aspects of Computer Science.Berlin:Springer ，1999:121131.

[9]DATTA A，ICKING C H.Competitive searching in a generalized street[C]//Proc of the 10th ACM Symposium on Computational Geometry.New York:ACM，1994:175182. 

[10]LPEZORTIZ A，SCHUIERER S.Generalized streets revisited[C]//Proc of the 4th European Symposium on Algorithms.London:SpringerVerlag，1996:546558. 

[11]DATTA A，HIPKE C H，SCHUIERER S.Competitive searching in polygonsbeyond generalized streets[C]//Proc of the 6th Annual International Symposium on Algorithms and Computation.London:SpringerVerlag，1995:3241. 

[12]LPEZORTIZ A，SCHUIERER S.Searching and online recognition of starshaped polygons［J］.Information and Computation，2003，185(1):6688. 

[13]LPEZORTIZ A，SCHUIERER S.Positionindependent near optimal searching and online recognition in star polygons[C]//Proc of the 5th Workshop on Algorithms and Data Structures.London:SpringerVerlag，1997:284296. 

[14]BRCKER C H，LPEZORTIZ A.Positionindependent street searching[C]//Proc of the 6th International Workshop on Algorithm and Data Structures.London:SpringerVerlag，1999:241252.

[15]PREPARATA F P，SHAMOS M I.Computational geometry［M］.New York:SpringerVerlag，1985.

[16]GAL S.Search games［M］. New York:Academic Press，1980.