A Robot Navigation Strategy in Unknown Environment and Its Efficiency (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
We consider a class of unknown scenes S_k(n) with rectangular obstacles aligned with the axes such that Euclidean distance between the start point and the target is n, and any side length of each obstacle is at most k. We propose a strategy called the adaptive-bias heuristic for navigating a robot in such a scene, and analyze its efficiency. We show that a ratio of the total distance walked by a robot using the strategy to the shortest path distance between the start point and the target is at most 1+3/5k, if k=o(√<n>) and if the start point and the target are at the same horizontal level. This ratio is better than a ratio obtained by a any strategy previously known in the class of scenes, S_k(n), such that k=o(√<n>).
社団法人電子情報通信学会の論文
1994-04-25