( 您好!臺灣時間:2021/04/15 12:25
字體大小: 字級放大   字級縮小   預設字形  


研究生(外文):CHENG, YI-PING
論文名稱(外文):On the prison breaker's problem
指導教授(外文):Gene Eu Jan
外文關鍵詞:High Geometry Maze RouterPiano Mover’s ProblemPrison Breaker’s Problemnear-optimal pathobstaclesearchlightsignal cell robotweighted region
  • 被引用被引用:0
  • 點閱點閱:244
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:42
  • 收藏至我的研究室書目清單書目收藏:0
機器人路經規劃一直是個重要的研究方向。過去傳統的路徑規劃通常將機器人外型與複雜的現實環境作簡化的假設,以便求出由起始點至終點的最短路徑。在考慮了機器人的外在型態與環境的互動而有學者定義了鋼琴移動問題(Piano Mover’s Problem),機器人除了規劃最短路徑的同時還必須在經過狹窄道路時具備旋轉的能力。為了模擬真實的環境與減少簡化性的假設,我們以可移動與固定障礙物與權重區域還有探照燈建構出越獄場景,機器人必須在此場景中規劃出且能夠閃避探照燈、障礙物以及盡量避開高權重區域或是重力、風速、水流等字人因素而由起始點至終點的越獄路徑,我們將此問題定義為Prison Breaker’s Problem。本文的路徑演算法是由High Geometry Maze Router架構發展而來,在二維網格圖上的單一網格機器人能夠避開移動的探照燈光區並且考慮環境中的靜態與移動的權重區域與障礙物,必要時尋找掩蔽物與等待適當時機再繼續規劃通往終點的路徑。其時間複雜度為O(dN+qN),其中N為地圖的網格數目,d為探照燈來回轉動週期,q是為了達到動態規劃的目的由起始點至終點(假如可到達終點)含等待所需的時間,其值大於等於路徑總長度。若是存在一條越獄路徑,在我們的方法中,機器人能夠規劃出一條閃避探照燈光區、障礙物、或是高權重區域。在某些情況下,機器人還必須找出遮蔽區並且等待適當的時機繼續規劃通往終點的路徑。
Collision-free path planning has been intensively studied in the literature of robotics. The traditional path planning usually simplified the assumptions of robot formation and the complex environment in order to reduce the complicated computation to obtain the optimal path between source and destination. Unfortunately, the real world is very complicated and time-varying and thus the simple assumptions must be modified to meet the real requirement of environment. The problems which occur when planning paths through complex narrow corridors that require the robot to rotate are known as the piano-mover’s problem. In order to simulate the real environment, we construct the collision-free path by adding some areas such as illuminated regions, obstacles (static or movable) and weighted regions (static or movable), and/or even gravity, wind and water flow. The robot will plan the path that can evade searchlight, obstacles and sometimes heavy weighted regions if necessary from the source to the destination that we define this issue as Prison Breaker's Problem.
In this article, we develop an efficient algorithm to solve the Prison Breaker's Problem based on High Geometry Maze Router, and its time complexity is O(dN+qN), where N is the number of cells in the electronic map, d is the period of searchlight and q is the same order of the path length. In our model, the signal cell robot in 2-Di- mensional cell map can avoid the illuminated regions, obstacles and sometimes heavy weighted regions if necessary to research the destination with near-optimal time if this path exited. Under certain circumstances, the robot must find some shadow and waiting for the right moment to move ahead to the destination.
1. 緒論
2. 動態環境路徑規劃
2.1 變數表
2.2 靜態及可移動權重區域
3. 越獄路線規劃演算法
3.2 效能分析
3.3 範例模擬
4. 結論與未來研究
[1]N. Aggarwal and K. Fujimura, ”Motion Planning Amidst Planar Moving Obstacles,” Proceedings of the 1994 IEEE International Conference on Robotics and Automation, vol. 3, pp. 2153–2158, May, 1994.
[2]J. Chuang and N. Ahuja, “An analytically tractable potential field model of free space and its application in obstacle avoidance,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 28, no. 5, pp. 729–736, Oct. 1998.
[3]K.Y. Chang, G.E. Jan, W.Q. Luo and C.P. Yin, ”The optimal path-planning for mobile vehicles with GPS on 3-D electronic maps,” Journal of Aeronautics and Aviation, Series B, Vol. 38, No. 1, pp. 63-70, 2006.
[4]K. Fujimura, ”Motion Planning Using Transient Pixel Representations,” Proceedings of the 1993 IEEE International Conference on Robotics and Automation, vol. 2, pp. 34–39, May, 1993.
[5]J. Fawcett and P. Robinson, “Adaptive Routing for Road Traffic,” IEEE Computer Graph, vol. 20, no. 3, pp. 46-53, June 2000.
[6]Y.K. Hwang and N. Ahuja, “Gross Motion Planning - A Survey,” ACM Computing Surveys, pp. 219-291, 1992.
[7]P.E. Hart, N.J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. Syst. Sci. Cybern., vol. SSC-4, no. 2, pp. 100–107, Jul. 1968.
[8]Z. Huiliang and H.S. Ying, “Dynamic map for obstacle avoidance,” Proceedings of the 2003 IEEE Intelligent Transportation Systems, vol. 2, pp. 12-15, Oct., 2003.
[9]G.E. Jan, K.Y. Chang and I. Parberry, “A New Maze Routing Approach for Path Planning of A Mobile Robot,” Proceedings of The IEEE/ASME International Conference on Advanced Intelligent Mechatronics, Kobe, Japan, vol. 1, pp. 552-557, July 2003.
[10]G.E. Jan, M.B. Lin and Y.Y. Chen, “Computerized Shortest Path Searching for Vessels,” Journal of Marine Science and Technology, vol. 5, no. 1, pp. 95-99, June 1997.
[11]P. John, “Introduction to robotics,” McKerrow, pp. 123-124, 1991.
[12]C.Y. LEE, “An algorithm for path connections and its applications,” IRE Trans. Electron. Comput. EC-10, pp. 346–365. 1961.
[13]L. Kavraki, P. Svestka, J. Latombe, and M. Overmars, "Probabilistic Roadmaps for Fast Path Planning in High-Dimensional Configuration Spaces," IEEE Transaction on Robotics and Automation, 12:566-580, 1996.
[14]O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” Int. J. Rob. Res., vol. 5, no. 1, pp. 90–98, 1986.
[15]D. Leven and M. Sharir, “An efficient and simple motion planning algorithms for a ladder moving in two-dimensional space amidst polygonal barriers,” in Proc. 1st ACM Symp. Computational Geometry, Nice, France, pp. 1208–1213, 1997.
[16]M.V. Lent, “Game Smarts,” IEEE Computer Society, vol. 40, Issue 4, pp. 99-101, Apr. 2007.
[17]Y.L. Lin, Y.C. Hsu and F.S. Tsai, “Hybrid Routing,” IEEE Trans. on CAD, pp. 151-157, Feb. 1990.
[18]K. Mikami and K. Tabuchi, “A Computer Program for Optimal Routing of Printed Circuit Connections,” IFIPS Proc., vol. H-47, pp. 1475-1478, 1968.
[19]J.L. Shih, G.E. Jan, C.M. Su and F.Y Lin, “Path Planning on Raster in Environments PART I: Static and Movable Weighted Regions,” Intelligent Living Technology, pp.727-734, Taiping, Taichung County, Taiwan, June 2006。
[20]J.L. Shih, G.E. Jan, C.M. Su and F.Y Lin, “Path Planning on Raster in Environments PART II: Movable Obstacle,” Intelligent Living Technology, pp.1174-1181 , Taiping, Taichung County, Taiwan, June 2006。
[21]J.T. Schwartz and M. Sharir, “On The Piano Movers Problem: I. The Case of A Two-Dimensional Rigid Polygonal Body Moving Amidst Polygonal Barriers,” Comm. on Pure and Applied Math., Vol. 36, pp. 345-398, 1983.
[22]J.T. Schwartz and M. Sharir, “On the Piano Movers Problem: II. General Techniques for Computing Topological Properties of Real Algebraic Manifolds,” Advances in Applied Math., Vol. 4, pp. 298-351, 1983.
[23]J.T. Schwartz and M. Sharir, “On The Piano Movers Problem: V. The Case of A Rod Moving in Three Dimensional Space Amidst Polyhedral Obstacles,” Technical Report 083 R13, New York University, Courant Institute, Dept. of Computer Sciences, 1983.
[24]O. Takahashi and R.J. Schilling, “Motion planning in a plane using generalized Voronoi diagrams,” IEEE Trans. Robot. Autom., vol. 5, no. 2, pp. 143–150, Apr. 1989.
[25]K.P. Valavanis, T. Hebert, R. Kolluru, and N. Tsourveloudis, “Mobile robot navigation in 2-d dynamic environments using an electrostatic potential field,” IEEE Trans. Syst., Man, Cybern. A, Syst., Humans, vol. 30, no. 2, pp. 187–196, Mar. 2000.
[26]C.W. Warren,“Fast path planning using modified a* method,” in Proc. IEEE Int. Conf. Robotics and Automation, Atlanta, pp. 662–667, 1993.
[27]B. Xu, D.Z. Chen and R.J. Szczerba, “A new algorithm and simulation for computing optimal paths in a dynamic and weighted 2-D environment,” IEEE International Conference on Systems, Man, and Cybernetics, pp. 313 – 318, Oct. 2000.
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔