路径规划问题是自动化移动系统研究中的一个基本问题,此问题的目的是在简单多边形环境中生成一条机器人从起始点到目标点之间的路径。如果搜索是在未知环境中进行时,即搜索环境的形状机器人事先未知且必须完成对目标的搜索时,依在线问题的定义,称这样的搜索为在线搜索。在线搜索算法(策略)的性能是由机器人在该策略下经过的路径长度与从起始点到目标点之间的最短路径长度的比值来确定的,并且称这一比值为在线搜索策略获得的竞争比。如果搜索策略竞争比的取值是一个不依赖于多边形参数(如多边形的边数、凹凸顶点的个数等)的常数,那么称此策略为常数竞争比搜索策略。更进一步地,如果常数竞争比的取值与机器人搜索时的起始位置以及目标点所在位置无关时,则称此策略为位置无关的常数竞争比搜索策略,相应地将具有位置无关常数竞争比搜索策略的多边形称为位置无关的多边形。目前,星形多边形和街多边形两类多边类属于位置无关的多边形,且星形多边形是第一个属于此类的多边形。本文首先在分析星形多边形环境及现有搜索策略的基础上,通过采用修正弦曲线做为机器人的运动轨迹,提出了星形多边形更具竞争性的在线搜索策略,这一策略具有竞争比11.18。并通过严格的数学推导确保了结果的正确性。其次,对于街多边形在线搜索,当机器人搜索起始点受限时,通过调整现有搜索策略中机器人的返回路径,并分析路径长度间的数量关系,使得新策略获得了比现有结论更优的竞争比25.68。而当起始点位置任意时,将搜索环境从中弦处划分为两部分,并在每一部分中按上述思想进行搜索,此时获得的竞争比为47.334。上述策略,尤其是街多边形搜索策略的提出,在较大程度改进了现有策略的性能,这些结果截止目前是最好的。最后,对本文的研究结论进行了总结,并提出了多边形在线搜索进一步的研究方向。