Path planning for moving a point object amidst unknown obstacles in a plane: the universal lower bound on the worst path lengths and a classification of algorithms
Path planning for moving a point object amidst unknown obstacles in a plane: the universal lower bound on the worst path lengths and a classification of algorithms
复制标题
在平面中未知障碍物中移动点对象的路径规划：最差路径长度的通用下界和算法分类
DOI：
10.1109/robot.1991.131871
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
M. Vidyasagar
中科院分区：
文献类型：
--
作者：
A. Sankaranarayanan;M. Vidyasagar
讨论了在充满任意形状未知障碍物的二维平面上，点物体任意两点间路径的生成问题。这个问题叫做P1。最坏情况路径长度的问题是在一般情况下分析的，独立于任何特定的算法。结果表明，求解P1有两种不同的方法，将求解P1的所有可能算法的集合划分为两个不相交的类。确定每一类中可能的最小最坏情况路径长度，并找到任何算法的最坏情况路径长度的通用下界。这些结果被证明对开发算法和更一般的问题模型是有用的
The problem of generating a path between any two points for a point object in a 2D plane filled with unknown obstacles of arbitrary shapes is discussed. This problem is termed P1. The issue of worst-case path lengths is analysed in a general setting, independent of any particular algorithm. It is shown that there are two distinct approaches available to solve P1, dividing the set of all possible algorithms that solve P1 into two disjoint classes. The minimum worst-case path length possible in each class is determined and the universal lower bound on the worst case path length of any algorithm is found. The results are shown to be useful in developing algorithms and more general problem models.<<ETX>>