跳到主要內容

臺灣博碩士論文加值系統

(35.175.191.36) 您好!臺灣時間:2021/07/30 12:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:劉欽鴻
研究生(外文):Chin-HungLiu
論文名稱:利用改良的雙向A演算法實現最佳路徑規劃
論文名稱(外文):Using Improved Bidirectional A Algorithm to Achieve Optimal Path Planning
指導教授:莊哲男
指導教授(外文):Jer-Nan Juang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:工程科學系碩博士班
學門:工程學門
學類:綜合工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:43
中文關鍵詞:路徑規劃導航系統機器人行走規劃
外文關鍵詞:a* algorithmpath planningshortest path
相關次數:
  • 被引用被引用:5
  • 點閱點閱:479
  • 評分評分:
  • 下載下載:31
  • 收藏至我的研究室書目清單書目收藏:0
現今科技發展迅速,無論是網路、電腦、手持式裝置或者各種資訊,這些與十年前的發展相比堪稱一日千里。而現代人到任何一個陌生的地方旅行也是件相當平常的事情,因為只要有了導航系統似乎就不怕到不了哪裡,所以在地圖搜索方面似乎是現代人必定會接觸的事情。但是我們常聽到有導航裝置會將使用者引導至死路或者是原地打轉,在我們進一步了解後,推論出這是其使用的演算法有所缺陷導致這種結果。
路徑規劃可以使用的演算法有太多種作法,而我們是採用A* Algorithm 為基礎架構,並且在已知環境作最佳路徑的探討。A* Algorithm 是一種比較純粹依賴邏輯判斷的圖形搜索演算法,因為這類的演算法是以邏輯構築而成,這種方式與我們人類在思考時會比較相像,所以採用這類的演算法。A* Algorithm 主要經由其演算法中所提到的評估方程式來判斷各個位置的資訊以便選擇最佳的路徑。
本篇論文在實作方面,整體程式使用Java 語言在Android 模擬器的環境下進行模擬實現。而在論文內容方面,首先介紹傳統的A* Algorithm,接著介紹許多篇論文所提及的改良方式,接著將所有介紹的演算法實作出來,並提出新的想法與實現。最後,針對執行結果在時間、路徑以及不同未知節點展開數量的多寡進行分析。甚至在資料結構上的因素我們也考慮進去,將以往大家會使用的資料型態替換成另一種資料型態,這使得搜索速度更進一步提升,經由不斷地改進A* Algorithm,最後提出我們所想出的方法,使得可以更快速地搜索到最短路徑。
Over the last several decades, computer technology has drastically changed the landscape of the online world and the way we lead our life. Thanks to the advances in navigation
technologies, it is now easy for people to travel to new places via path planning. However, at the same time, navigation devices may guide users to undesired places due to imperfect path planning algorithms.
There are many path-planning methods we could use. We select A* algorithm to be our baseline approach and investigate how it arrives the optimal path in a known environment. A * algorithm is a kind of graphic search algorithms that merely depend on the logic operations. So its idea is to compute the cost of all nodes using a predesignated evaluation function, and the computed results are used to do optimal path planning. Its improved methods had also been studied in many papers.
Since A* has a computational inefficiency problem, its improved algorithms had also been studied in some researches. In this thesis, we propose a new idea and implement all (improved) algorithms in order to compare their efficiency. We analyze the executing time, path, and the amounts of unknown expanded nodes. Taking the data structure into consideration,we replace the type people used with another data type to improve the search speed. After improving A* algorithm constantly, we propose our innovative method to get the shortest path more quickly. Finally, we implemented the simulation program with Java Program language and Android SDK, and then simulated it on the Android simulator.
[1] Z. Hui-zhong, D. Shu-xin, and W. Tie-jun, ``Research on path planning and related
algorithms for robots,' in Bulletin of Science and Technology, March 2004.
[2] M. Tarokh, ``Hybrid intelligent path planning for articulated rovers in rough terrain,' in
Fuzzy Sets and Systems, p. 2927–2937, February 2008.
[3] P. Hart, N. Nilsson, and B. Raphael, ``A formal basis for the heuristic determination of
minimum cost paths,' IEEE Transactions on Systems Science and Cybernetics, vol. 4,
pp. 100 --107, July 1968.
[4] P. Lester, ``A* pathfinding for beginners.' http://www.policyalmanac.org/
games/aStarTutorial.htm, July 2005.
[5] Y. Junfeng, Z. Binbin, and Z. Qingda, ``The optimization of a* algorithm in the practical
path finding application,' in WRI World Congress on Software Engineering (WCSE'09),
vol. 2, pp. 514 --518, May 2009.
[6] J. Xu, F. Hu, and X. Han, ``Realization of bidirectional a* algorithm based on the hierarchical
thinking during the process of path planning,' in International Conference on
Computer Science and Software Engineering, vol. 1, pp. 415 --418, December 2008.
[7] J. Yao, C. Lin, X. Xie, A. Wang, and C.-C. Hung, ``Path planning for virtual human
motion using improved a* star algorithm,' in Seventh International Conference on Information
Technology: New Generations (ITNG), pp. 1154 --1158, April 2010.
[8] C. Warren, ``Fast path planning using modified a* method,' in IEEE International Conference
on Robotics and Automation, pp. 662 --667 vol.2, May 1993.
[9] H. Zou, L. Zong, H. Liu, C. Wang, Z. Qu, and Y. Qu, ``Optimized application and practice
of a* algorithm in game map path-finding,' in IEEE 10th International Conference
on Computer and Information Technology (CIT), pp. 2138 --2142, July 2010.
[10] D. Fan and P. Shi, ``Improvement of dijkstra's algorithm and its application in route
planning,' in Seventh International Conference on Fuzzy Systems and Knowledge Discovery
(FSKD), vol. 4, pp. 1901 --1904, August 2010.
[11] S. Bandi and D. Thalmann, ``Path finding for human motion in virtual environments,'
in Computational Geometry, p. 103–127, February 2000.
[12] P. Švestka and M. H. Overmars, ``Coordinated path planning for multiple robots,' in
Robotics and Autonomous Systems, p. 125–152, March 2001.
[13] Caterpillar, ``Introduction to data structure of list.' http://caterpillar.onlyfun.
net/Gossip/JavaGossip-V2/JavaGossip2.htm, July 2009.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊