(3.235.25.169) 您好!臺灣時間:2021/04/18 03:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊凱傑
研究生(外文):Kai-Chieh Yang
論文名稱:二次曲面最短路徑搜尋及其應用
論文名稱(外文):The Near-Shortest Path Search on a Quadric Surface and Its Application
指導教授:呂紹偉詹景裕詹景裕引用關係
指導教授(外文):Shao-Wei LeuGene-Eu Jan
學位類別:碩士
校院名稱:國立臺灣海洋大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:28
中文關鍵詞:三角剖分巡弋飛彈路徑規劃Dijkstra演算法稜點最短路徑
外文關鍵詞:Cruise missile mission planningDelaunay triangulationDijkstra algorithmRidge pointnear-shortest path
相關次數:
  • 被引用被引用: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.
摘要 I
Abstract II
Contents III
List of Figures IV
List of Tables V
Chapter 1 Introduction 1
Chapter 2 Background 6
Chapter 3 Algorithms and Illustrations 8
Chapter 4 Performance Analysis 15
Chapter 5 Experimental Results 17
Chapter 6 Conclusion 25
Reference 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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔