On the near-optimality of sensor-based navigation in a 2D unknown environment with simple shape
On the near-optimality of sensor-based navigation in a 2D unknown environment with simple shape
复制标题
简单形状二维未知环境中基于传感器的导航的近最优
DOI：
10.1109/robot.1999.770004
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Kenji Urakawa
中科院分区：
文献类型：
--
作者：
H. Noborio;Kenji Urakawa
我们专注于如何移动的机器人选择其方向，以遵循遇到的障碍。为此，在一个不确定的二维环境中，简单的形状，我们提出了新的基于传感器的导航算法简单（Class 1）和简单（Bug 2）的基础上经典算法Class 1和Bug 2。此外，为了显示所提出的算法的接近最优性，我们确定了竞争比r/sub 1/=（Simple（Class 1）选择的路径长度）/（基于模型的路径规划选择的最短路径长度），并且还确定了最差比r/sub 2/=（Class 1选择的路径长度/（Simple（Class 1）选择的路径长度）。此外，我们确定竞争比r/sub 1/=（由Simple（Bug 2）选择的路径长度）/（由基于模型的路径规划选择的最短路径长度），并且还确定最差比r/sub 2/=（由Bug 2选择的路径长度）/（由Simple（Bug 2）选择的路径长度）。由于竞争比r/sub 1/是有界的，新算法被认为是近优算法。另一方面，由于最坏比r/sub 2/是由一个大的有限值或无穷大决定的，新算法相对于经典算法有了很大的改进。
We focus on how a mobile robot selects its direction to follow an encountered obstacle. For this purpose, in an uncertain 2D environment with simple shape, we propose new sensor-based navigation algorithms Simple(Class1) and Simple(Bug2) based on classic algorithms Class1 and Bug2. Moreover, in order to show a near-optimality of the proposed algorithms, we determine a competitive ratio r/sub 1/=(path length selected by Simple(Class1))/(the shortest path length selected by the model-based path-planning), and also determine a worst ratio r/sub 2/=(path length selected by Class1/(path length selected by Simple(Class1)). Also, we determine a competitive ratio r/sub 1/=(path length selected by Simple(Bug2))/(the shortest path length selected by the model-based path-planning), and also determine a worst ratio r/sub 2/=(path length selected by Bug2)/(path length selected by Simple(Bug2)). Since the competitive ratio r/sub 1/ is bounded by a small finite value, the new algorithms are regarded as near-optimal algorithms. On the other hand, since the worst ratio r/sub 2/ is determined by a large finite valve or infinite, the new algorithms are greatly improved against the classic algorithms.