(兰州理工大学 计算机与通信学院, 兰州 730050)
摘 要:在自动化机器人的导航问题中,机器人必须在不具备全部信息或在不确定情况下反复作出决定且最终要找到未知环境中的目标;当机器人获得了全部信息时问题得到解决。研究多边形内目标的在线搜索问题,提出了一种用于查找星形多边形内未知目标的搜索策略,这一策略具有竞争比11.18,它独立于起始点和目标点所在的位置。
关键词:在线搜索;竞争比;搜索策略;星形多边形
中图分类号:TP393.04 文献标志码:A
文章编号:10013695(2009)02051803
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
过去几年中,在线搜索问题已成为计算机科学研究中的一个热门领域[1~5]。在这些问题的所有研究成果中,一个在线搜索问题由一个代理搜索未知区域中的目标所组成。机器人在一般区域中的搜索路径长度通常比从初始点到目标点之间的最短路径长很多。搜索策略会随着搜索区域的类型以及机器人搜索能力的不同而有所改变。假设机器人装备有可视系统,它能使机器人看到当前局部环境。机器人必须在仅掌握部分环境信息的基础上作出搜索的决策,所以机器人搜索问题为在线问题。在线搜索策略的性能由机器人在这一策略下所走过的路径长度与起始点s到目标点t之间的最短路径长度的比值来衡量。将机器人遍历过的路径长度与s到t间最短距离的比值中的最大值称为搜索策略的竞争比(率)。
截止目前有几类多边形具有常数竞争比,最具代表性的是街(street)[6~8]、广义街(gstreet)[9,10]、水*垂直街(HVstreet)及θ街(θstreet)[11]。以上多边形搜索策略常数竞争比的存在依赖于目标点所在的位置。
最早考虑的位置独立的在线可搜索多边形是星形多边形,其竞争比随着搜索策略的不同而不同。当机器人沿着直线策略接*目标时获得竞争比14.5;当沿半圆曲线策略接*目标时获得竞争比11.52[12],且这种多边形搜索策略竞争比的低界值为9[13]。借助于星形多边中搜索所采用的方法,街多边形成为目标点和搜索者位置独立的常数竞争比可搜索多边形[14]。本文在文献[12]的基础上提出一种新的星形多边形目标搜索策略,这一策略具有常数竞争比且与位置独立。
1 定义
称多边形P中两点p和p′相互可见,如果线段pp′完全包含在P中。若A和B是两个点集,称A从B勉强可见,如果A中的所有点从B中的某一点可见。
定义1 设p为多边形P中的一点,点p在P中的可见多边形VisP(p)是从p可见的P中点的子集。
定义2[15] 如果简单多边形P中存在一点p使得VisP(p)=P,则P是星形多边形。所有VisP(p)=P的P中点p构成的集合叫做P的核,记做Ker(P)。
定理 存在一种用于搜索星形多边形内目标的新策略,这一策略具有竞争比至多为11.18。
3 结束语
本文以文献[12]的结论为基础,提出了一种用于在线搜索星形多边形的新策略。这一策略使竞争比从原来的11.52降低到11.18,且它独立于机器人起始点及目标点所在的位置,这一结果迄今为止是最好的。可否通过选用其他曲线来构造不同的策略以实现竞争比的降低也是一个值得考虑的问题;同时,能否将这一策略应用到其他类型的多边形(如街多边形)有待进一步研究。
参考文献:
[1]
BAEZAYATES R,CULBERSON J,RAWLINS G.Searching in the plane[J].Information and Computation,1993,106(2):234252.
[2]BERMAN P,BLUM A,FIAT A,et al.Randomized robot navigation algorithms[C]//Proc of the 7th ACMSIAM Symposium on Discrete Algorithms.Philadelphia:SIAM,1996:7584.
[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:495504.
[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:441447.
[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:304313.
[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.
如果机器人的起始位置不在Ker(P)中,那么P中存在机器人不可见的部分,把P\VisP(p)称为暗区(pockets)。暗区的边界由P的一些边及一条不属于P边界的线段组成,称这条线段为VisP(p)的窗口(window)。一个窗口仅在其端点处与多边形P的边界相交,其中一个交点为多边形P的顶点,称这一点为暗区的入点(entrance)。一般而言,将一条仅在其端点处与P边界相交的线段叫做P的弦(chord)。
设p和q为P中的两个点,用shp(p,q)表示从p到q的最短路径。所有从p到P顶点的最短路径构成的整体形成了一个树状结构,称这一结构为p的最短路径树,用shptree(p,q)表示。通过延长最短路径树上从p开始的线段直到与P的边界相交来扩展这一种树状结构,将扩展后的这一新结构称为p的扩展最短路径树,用shptree*(p,q)表示。延长线的终点也即它与P边界的交点叫做p的扩展点。p的扩展最短路径树将P划分成若干个三角形,每一个三角形中离p最*的点叫做三角形的锚点(anchor)。
P的一条暗区边是P中的一条线段,它始于p且包括至少一个窗口。每一条暗区边是shptree* (p,q)的一部分。更一般地,p的一条扩展暗区路径是一条从p到p的扩展点之间的最短路径。很明显,一条扩展暗区路径也是shptree* (p,q)的一部分。
一个暗区被称做是左暗区,如果它当前位于包含其窗口的暗区射线的左侧。一条暗区边被称为是左暗区边,如果它定义一个左暗区。一条扩展暗区路径是左扩展暗区路径,如果它的起初部分线段与左暗区边重合。右暗区、右暗区边以及右扩展暗区路径的定义与上述类似。
例如,在图1所示的多边形中,L1和L2为左暗区,R为右暗区;线段v1v′1、v2v′2和v3v′3是VisP(p)的窗口;v1、v2分别为L1和L2的入点,v3为R的入点;v1、v2同时也是锚点;
pv1、pv2和pv3分别为两条左暗区边和一条右暗区边;
pv′1、
pv′2和pv′3为扩展暗区路径;v′1、v′2和v′3为点p的扩展点。
令V为P的所有反射点和p的扩展点构成的集合, v∈V为左扩展暗区路径Ev上的一点,类似地,令v′∈Ev′,这里Ev≠Ev′。称shp(p,v)在shp(p, v′)的右侧,如果shp(p,v)包括shp(p, v′)或者Ev在Ev′的右侧。用Edleftt表示一条最右侧的左扩展暗区路径,其中d为给定的最大距离。定义Edleftt的目的在于如果要走向距离为d的位置,尽可能多地封锁Edleftt左侧的部分。用shp(p,v)表示长度至多为d的最右侧的最短路径,如果这样的路径存在,那么Edleftt就由shp(p,v)连同shp(p,v)末端线段的延长线定义;否则,可任意定义Edleftt为最右侧的扩展暗区路径。最左侧的右扩展暗区路径Edright的定义与Edleftt类似。
因为Ker(P)中的任意一点可看到P中的所有点,特别地,对于p而言,VisP(p)的一个暗区不会与Ker(P)相交,这意味着有下面的引理。
引理 Ker(P)位于所有左暗区边的右侧,所有右暗区的左侧。
例如,在图1所示的多边形中,若存在核,那么它位于暗区边pv1、pv2的右侧和pv3的左侧。
上述引理意味着,在一个星形多边形中,当顺时针扫描多边形边界时所有左暗区边连续出现;同理,当逆时针扫描多边形边界时所有右暗区边连续出现。特别地,在交换左右暗区边之前顺时针排列左暗区边,逆时针排列右暗区边,反之亦然。因此,存在一个最顺时针(最右侧)的左暗区边,记为El;存在一个最逆时针(最左侧)的右暗区边,记为Er。这样核就位于El和Er之间。本文将在星形多边形搜索算法中使用这种排列,当然也可以将这种排列应用到扩展暗区路径中。
2 星形多边形中的目标搜索
2.1 搜索算法
SPS算法(星形多边形搜索算法)
输入:星形多边形P和起始点s
输出:目标点t的位置
令p0为离s最*的入点,E0为相对于p0的暗区边
d0←d(p0,s),i←0
if E0是左暗区边
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
上述算法的主要思想在于机器人交替地搜索以s为起点(经合理选择的)的左右扩展暗区路径,且将每次搜索的深度乘以常数c。c是相邻搜索步长的倍数,即di+1=c×di,它的值在竞争比分析中确定;d(p0,s)表示点p0到点s间的欧氏距离;定义┐left=right,┐right=left。
事实上,对于上述算法而言,不可能通过对步长di取值的选择来降低竞争比[1,16]。本文目的在于通过对搜索的改进来降低竞争比,以提高竞争性。
2.2 新的搜索策略
2.2.1 策略描述
令qi为在第i步探索Ei时的终点,当∠qi-2sqi接**角时最坏情况发生。在这种情况下当机器人沿着图2所示的曲线前进而不是沿sq1直线前进时,目标点会被提前发现。所以在策略中机器人前进的路径由fl生成的正弦曲线的一半(以下简称正弦弧)Sl代替属于Ei的弦fl=vlvl+1。
Sl的构造如下(图3):
a)构造通过点vl和vl+1且中心点(正弦曲线最高点所对应的横标上的点)在fl上的正弦曲线的一半(以下简称正弦弧)S(1);
b)若S(1)已经到达vl+1,则完成对Sl的构造,否则转到c);
c)找出从vl可见的P边界上的一点q(1),构造通过点vl和q(1)且中心在fl上的正弦弧S(1),S(1)上从vl到q(1)的部分便是Sl的第一部分,以下类似;
d)找出P边界上从vl可见的另一点q(2),构造通过点q(1)和q(2)且中心在fl上的正弦弧S(2);
e)假设Sl的构造已经到达q(j)阶段,1≤j≤kl-1,则S(j+1)由通过点q(j)及vl+1且中心在fl上的正弦弧构造。
为了保证机器人能尽早地发现目标,但同时又考虑到使机器人总的路径长度较短,选择sin(1.57x)且x∈[0,1]为策略中用到的曲线弧;同时,每个S(j)的中心在fl上且s(j+1)在s(j)的右侧,1≤j≤kl-1。
2.2.2 竞争比分析
s为起始点,t为目标点,最后一条简单路径En由q1qr定义(图4)。t点当前所在位置是机器人发现目标的最坏情况,也即机器人不论沿着哪条路径(半圆曲线或正弦弧)前进,只有到达点q1时才能发现目标。机器人在最后一步所经过的路径长度至多是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
因为d(s,t)≥cn-2d0且机器人到点qi及返回所走过的距离由(1+0.931 7(π-θ)/sin θ)di界定,取θ值为2.152,当c=2时上述表达式值最小,所获得的竞争比为2.77+(1+0.931 7×1.184 1)×4≈11.18。值得注意的是,当在第i步离s的距离为 di-2处发现目标时,最坏情况依然发生。的确,在这种情况下,机器人前i-1步的遍历全部返回到起始点s,第i步遍历的任何距离只会使竞争比变大。
在上面的分析中假设En是一条简单暗区边。如果En不是一条简单暗区边则机器人分别对En的每一条暗区边分离地构造Sl。
[10]LPEZORTIZ A,SCHUIERER S.Generalized streets revisited[C]//Proc of the 4th European Symposium on Algorithms.London:SpringerVerlag,1996:546558.
[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:3241.
[12]LPEZORTIZ A,SCHUIERER S.Searching and online recognition of starshaped polygons[J].Information and Computation,2003,185(1):6688.
[13]LPEZORTIZ 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:284296.
[14]BRCKER C H,LPEZORTIZ A.Positionindependent street searching[C]//Proc of the 6th International Workshop on Algorithm and Data Structures.London:SpringerVerlag,1999:241252.
[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.