(3.235.25.169) 您好！臺灣時間：2021/04/18 03:53

### 詳目顯示:::

:

• 被引用:0
• 點閱:576
• 評分:
• 下載:23
• 書目收藏:0
 本文提出一個以三角剖分和稜點為基礎的尋找最短路徑演算法。利用本文尋找稜點演算法與Dijkstra演算法，並輔以Pathshortening，以及避免陡升、陡降對油耗的影響，特別加入三角剖面角度的限制(
 Recently, a new algorithm to obtain the sub-shortest path in the Euclidean plane based on the concepts of Delaunay triangulation, an improved Dijkstra algorithm and Fermat points was presented. The length of path obtained by this algorithm is the shortest among two other fastest O(n log n) algorithms in the literature. Based on the previous works, a novel O(n log n) sub–shortest path algorithm in the Quadric plane based on the Delaunay triangulation, an improved Dijkstra algorithm and Ridge points is presented in this paper. Compare to the another O(n log n) sub–shortest path approach (Kanai and Suzuki, KS’s algorithm [21]), the average path of the proposed algorithm is 2.81% longer than the KS’ algorithm, but the computation is about 4215 times faster when KS’s SP point is 29. This, however, has only a few path length difference which still give a good result but best computing time. It is worth to notice that the proposed fast algorithm is ideal to be extended to solve the near-shortest path problem on the quadric surface or even the cruise missile mission planning.
 摘要 IAbstract IIContents IIIList of Figures IVList of Tables VChapter 1 Introduction 1Chapter 2 Background 6Chapter 3 Algorithms and Illustrations 8Chapter 4 Performance Analysis 15Chapter 5 Experimental Results 17Chapter 6 Conclusion 25Reference 26
 [1] R. Ahuja, K. Mehlhorn, J. Orlin, and R. Tarjan, “Faster Algorithms for the Shortest Path Problem,” Journal of the ACM, vol. 37, pp. 213–223, Apr. 1990.[2] O. Byer, F. Lazebnik, and D. L. Smeltzer, Methods for Euclidean Geometry. Mathematical Association of America, 2010.[3] J. Canny and J. Reif, “New lower bound techniques for robot motion planning problems”, Proc. 1987, IEEE FOCS, 49-60.[4] H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations. The MIT Press, 2005.[5] J. Chen and Y. Han. Shortest paths on a polyhedron. In Proc. 6th ACM Symp. on Computational Geometry, pages360–369, 1990.[6] E. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959.[7] A. Einstein, “Die Feldgleichungen der Gravitation,” Sitzungsberichte der Preussischen Akademie der Wissenschaften zu Berlin, pp. 844–847, 1915.[8] P. Fermat and M. Miller, Pierre de Fermats abhandlungen ´uber maxima und minima. Leipzig: Akademische Verlagsgesellschaft m. b. h., 1934.[9] S. Fortune, “A sweepline algorithm for voronoi diagrams,” in Proceedings of the second annual ACM Symposium on Computational Geometry, 1986, pp. 313–322.[10] Ana Irene RamƯrez Galarza &; Jose A. Seade. (2007) Introduction to classical geometries. Springer.[11] B. Gao, D. Xu, F. Zhang, and Y. Yao, “Constructing visibility graph and planning optimal path for inspection of 2D workspace,” in IEEE International Conference on Intelligent Computing and Intelligent Systems, vol. 1, Nov. 2009, pp. 693 –698.[12] F. Hadlock, “Finding a maximum cut of a planar graph in polynomial time,” SIAM Journal of Computing, vol. 4, pp. 221– 225, Sep. 1975.[13] K. Harada, S. Hattori, H. Hirukawa, M. Morisawa, S. Kajita, and E. Yoshida, “Two-stage time-parameterized gait planning for humanoid robots,” IEEE/ASME Transactions on Mechatronics, vol. 15, no. 5, pp. 694–703, Oct. 2010.[14] M. Hanan, “On steiner’s problem with rectilinear distance,” SIAM Journal on Applied Mathematics, vol. 14, pp. 255–265, 1966.[15] R. V. Helgason, J. L. Kenning, and K. R. Lewis, “Cruise Missile Mission Planning: A Heuristic Algorithm for Automatic Path Generation ,” Journal of Heuristics, vol. 7 pp.473-479, Sep. 2001.[16] D. Hightower, “A solution to line-routing problems on the continuous plane,” in Design Automation Conference, 1969, pp. 1–24.[17] Gene Eu Jan, C.-C. Sun, W.-C. Tsai, and T.-H. Lin, “An O(n log n) shortest path planning based on Delaunay triangulation,” accepted and to appear in IEEE/ASME Transactions on Mechatronics, 2013. (Regular paper)[18] G. E. Jan, K. Y. Chang, S. Gao, and I. Parberry, “A 4-Geometry Maze Router and Its Application on Multiterminal Nets,” ACM Transactions on Design Automation of Electronic Systems, vol. 10, pp. 116–135, Jan. 2005.[19] G. E. Jan, K. Y. Chang, and I. Parberry, “Optimal path planning for mobile robot navigation,” IEEE/ASME Transactions on Mechatronics, vol. 13, no. 4, pp. 451–460, Aug. 2008.[20] Jingyi Jin, Three Novel Algorithms for Triangle Mesh Processing: Progressive Delaunay Refinement Mesh Generation, MLS-based Scattered Data Interpolation and Constrained Centroid Voronoi-based Quadrangulation. University of Illinois at Urbana-Champaign, 2008.[21] T. Kanai and H. Suzuki, “Approximate shortest path on a polyhedral surface and its applications,” Computer-Aided Design 33, Elsevier, 2001.[22] R. Kimmel and J. A. Sethian, “Computing geodesic paths on manifolds,” Proceedings of the National Academy of Sciences on Applied Mathematics, Vol. 95, pp. 8431–8435, July 1998.[23] J. Latombe, Robot Motion Planning. Kluwer Academic Publishers, 1991.[24] C. Y. Lee, “An Algorithm for Path Connections and Its Applications,” IRE Transactions on Electronic Computers, vol. EC-10, no. 3, pp. 346 –365, Sep. 1961.[25] K. Mikami and K. Tabuchi, “A computer program for optimal routing of printed circuit connectors,” in Proceedings of IFIP, vol. 47, 1968, pp. 1475–1478.[26] J. S. B. Mitchell. Geometric shortest paths and network optimization. In J. R. Sack and J. Urrutia, editors, The Handbook of Computational Geometry. Elsevier Science, 1998.[27] J. S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou. The discrete geodesic problem. SIAM J. Computing, 16(4):647–668, 1987.[28] F. P. Preparata and M. I. Shamos, Computational Geometry: An Intro. Springer-Verlag, 1985.[29] H. Rohnert, “Shortest paths in the plane with convex polygonal obstacles,” Information Processing Letters, vol. 23, no. 2, pp. 71–76, 1986. [Online]. Available: http://www.sciencedirect.com/science/ article/pii/0020019086900451[30] J.R. Sack and J. Urrutia, Handbook of Computational Geometry, Elsevier, 1999.[31] M. Sharir and A. Schorr, “On shortest paths in polyhedral spaces”. SIAM J. Computing, 15:193–215, 1986.[32] J. Soukup, “Fast Maze Router,” in Design Automation Conference, 1978, pp. 100–102.[33] P. Spain, “The fermat point of a triangle,” Mathematics Mag., vol. 69, no. 2, pp. 131–3, Apr. 1996.[34] Y. Wu, D. Sun, W. Huang, and N. Xi, “Dynamics analysis and motion planning for automated cell transportation with optical tweezers,” IEEE/ASME Transactions on Mechatronics, vol. PP, no. 99, pp. 1–8, Jan. 2012.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 多面體表面最短路徑實作 2 Polygonal surfaces上最短路徑規劃

 無相關期刊

 1 智慧型手機上多點實際道路路徑規劃 2 CCC平行電腦架構下之完美負載平衡與容錯最佳傳繞設計 3 應用類神經網路於球鞋造形曲線認知與設計之研究 4 以改良式Dijkstra’s演算法改善車型機器人移動效率 5 使用Kinect之抽菸事件分析 6 基於條碼辨識的圖書館藏書盤點系統 7 碎形方法於影像編碼和紋理分析:搜尋效能的改進和應用 8 利用區域切割之最短路徑規劃研究 9 以線迷宮鼠實現最短路徑演算法之研究 10 二維平面上繞行多圓最短路徑之研究 11 圖的最短路徑譜及強最短路徑譜 12 圖的最短路徑譜及強最短路徑譜 13 企業雲端服務計價探索分析 14 於雲端環境下設計調適性資源分配法以改善處理績效 之研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室