四分木・八分木とＦＦＴによる経路探索

DOI Web Site 被引用文献1件 参考文献6件

書誌事項

タイトル別名
  • Path Search by Means of Quadtree, Octree and Fast Fourier Transform.
  • 4ブンギ 8ブンギ ト FFT ニヨル ケイロ タンサク

この論文をさがす

抄録

In this study, a new algorithm to search the shortest path of mobile robot between start and goal points in given environment is proposed. In the path search, computation of collision domain of robot and environment is crucial. A domain on which the reference point of robot must not trespass is called collision domain. Collision domain is quickly computed by Inverted Template Method using double-stage fast Fourier transform. Collision and collision-free domains are represented by a tree structure to save memory and to reduce the calculation time. When robot does not rotate, path is searched in a two-dimensional plane and the domains are represented by a quadtree. The path is taken in collision-free domain by Minimum Total Distance Method. Firstly, the L1 distance of each cell in collision free domain is determined successively from the start point, and then from the goal point. Secondly, thetwo values on each cell are summed up to obtain total distance map. Finally, the shortest path is found by tracing the cells which have the minimum total distance in the map. When robot can rotate in xy-plane, the rotation angle is associated with z-axis. The shortest path is searched in three-dimensional collision free domain represented by an octree.

収録刊行物

  • 精密工学会誌

    精密工学会誌 62 (11), 1557-1561, 1996

    公益社団法人 精密工学会

被引用文献 (1)*注記

もっと見る

参考文献 (6)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ