請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/27790完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 黃漢邦(Han-Pang Huang) | |
| dc.contributor.author | Hsiao-Chieh Yen | en |
| dc.contributor.author | 顏孝杰 | zh_TW |
| dc.date.accessioned | 2021-06-12T18:20:43Z | - |
| dc.date.available | 2008-04-30 | |
| dc.date.copyright | 2007-08-28 | |
| dc.date.issued | 2007 | |
| dc.date.submitted | 2007-08-23 | |
| dc.identifier.citation | [1] N. M. Amato, O. B. Bayazit, L. K. Dale, C. V. Jones, and D. Vallejo, “OBPRM: An Obstacle-Based PRM for 3D Workspaces,” Proc. Int. Workshop on Algorithmic Foundations of Robotics (WAFR), 1998.
[2] J. Andrews and N. Hogan, “Impedance Control as a Framework for Implementing Obstacle Avoidance in a Manipulator,” Control of Manufacturing Processes and Robotic Systems, Boston, USA, pp. 243–251, 1983. [3] G. Antonini and M. Bierlaire, “Capturing Interactions in Pedestrian Walking Behavior in a Discrete Choice Framework,” Technical Report, Sep. 2005. [4] J. Barraquand and J.-C. Latombe, “Robot Motion Planning: A Distributed Representation Approach,” The International Journal of Robotics Research, Vol. 10, No. 6, pp. 628–649, Dec. 1991. [5] M. Bennewitz, W. Burgard, and S. Thrun, “Adapting Navigation Strategies Using Motion Patterns of People,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2003. [6] J. van den Berg, D. Ferguson, and J. J. Kuffner, “Anytime Path Planning and Replanning in Dynamic Environments,” Proc. IEEE International Conference on Robotics and Automation (ICRA), Florida, USA. 2006. [7] J. van den Berg and M. Overmars, “Planning the Shortest Safe Path amidst Unpredictably Moving Obstacles,” Proc. Workshop on Algorithmic Foundations of Robotics, July 2006. [8] R. Bohlin and L. E. Kavraki, “Path Planning Using Lazy PRM,” Proc. Int’l. Conf. on Robotics and Automation, Vol. 1, pp. 521–528, 2000. [9] J. Borenstein and Y. Koren, “Real-Time Obstacle Avoidance for Fast Mobile Robots in Cluttered Environments,” Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati, Ohio, USA, pp. 572–577, May, 1990. [10] J. Borenstein and Y. Koren, 'The Vector Field Histogram – Fast Obstacle-Avoidance for Mobile Robots,' IEEE Journal of Robotics and Automation, Vol. 7, No. 3, pp. 278–288, June 1991. [11] O. Brock and O. Khatib, “High-Speed Navigation Using the Global Dynamic Window Approach,” IEEE Int. Conf. on Robotics and Automation, Detroit, MI, USA, pp. 341–346, 1999. [12] A. Bruce and G. Gordon, “Better Motion Prediction for People-Tracking,” Proceedings of the IEEE International Conference on Robotics & Automation (ICRA), 2004. [13] J. Bruce and M. Veloso, “Real-Time Randomized Path Planning for Robot Navigation,” Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), 2002. [14] P. Cheng and S. M. LaValle, “Reducing Metric Sensitivity in Randomized Trajectory Design,” Proc. IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems, pp. 43–48, 2001. [15] P. Cheng and S. M. LaValle, “Resolution Complete Rapidly-Exploring Random Trees,” Proc. IEEE Int'l Conf. on Robotics and Automation, pp. 267–272, 2002. [16] M. Cherepov, M. Hirst, C. Jones, and M. Zimmerman, “Hard Real-Time with Ardence RTX on Microsoft Windows XP and Windows XP Embedded,” MSDN Library, June, 2002. Available Online: http://msdn2.microsoft.com/en-us/library/ms838340.aspx [17] S. Y. Chung and H. P. Huang, 'Relative-Absolute Map Filter for Simultaneous Localization and Mapping,' Proc. IEEE International Conference on Intelligent Robotics and Systems, Beijing, China, pp. 436–441, Oct. 2006. [18] H. Dee and D. Hogg, “Detecting Inexplicable Behaviour,” British Machine Vision Conference, Kingston, UK, 2004. [19] E. W. Dijkstra, 'A Note on Two Problems in Connection with Graphs,' Numerical Mathematics, Vol. 1, pp. 269–271, 1959. [20] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, 2nd Edition, New York, USA: Wiley, pp. 526-528, 2000. [21] D. Ferguson, “Real-time Planning for Single Agents and Multi-agent Teams in Unknown and Dynamic Environments,” Dissertation Proposal, Robotics Institute, Carnegie Mellon University, 2006. [22] D. Ferguson, N. Kalra, and A. Stentz, “Replanning with RRTs,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 1243–1248, May 2006. [23] D. Ferguson, M. Likhachev, G.. Gordon, A. Stentz, and S. Thrun, “Anytime Dynamic A*: An Anytime, Replanning Algorithm,” Proceedings of the International Conference on Automated Planning and Scheduling, 2005. [24] D. Ferguson, A. Stentz, and S. Thrun, “PAO* for Planning with Hidden State,' Proc. IEEE International Conference on Robotics and Automation (ICRA), New Orleans, LA., USA, 2004. [25] D. Fox, W. Burgard, and S. Thrun, “The Dynamic Window Approach to Collision Avoidance,” IEEE Robotics & Automation Magazine, Vol. 4, No. 1, March 1997. [26] K. S. Fu, R. C. Gonzalez, and C. S. G. Lee, Robotics: Control, Sensing, Vision, and Intelligence, NY, USA: McGraw-Hill Book Co., 1987. [27] D. Hsu, T. Jiang, J. Reif, and Z. Sun, “The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners,” Proc. IEEE International Conference on Robotics and Automation, 2003. [28] D. Hsu, R. Kindel, J.-C. Latombe, and S. Rock, “Randomized Kinodynamic Motion Planning with Moving Obstacles,” The Fourth Workshop on the Algorithmic Foundations of Robotics, Boston, MA, USA, 2000. [29] D. Helbing and P. Molnar, “Social Force Model for Pedestrian Dynamics,” Physical Review E, Vol. 51, No. 5, pp. 4282–4286, May 1995. [30] Y. K. Hwang and N. Ahuja, “A Potential Field Approach to Path Planning,” IEEE Transactions on Robotics and Automation, Vol. 8, No. 23, 1992. [31] L. Jaillet, T. Siméon, “A PRM-Based Motion Planner for Dynamically Changing Environments,” Proc. IEEE Int. Conf. on Int. Robots and Systems (IROS), Vol. 2, pp. 1606–1611, September 2004. [32] S. R. Jang, C. T. Sun, and E. Mizutani, Neuro-Fuzzy and Soft Computing, 1st Edition, NJ, USA: Prentice Hall, pp. 175–180, 1997. [33] R. A. Jarvis, “Collision-Free Trajectory Planning Using Distance Transforms,” Transactions of the Institution of Engineers, Australia, Mechanical Engineering, Vol. 10, No. 3, pp. 187–191, September 1985. [34] L. Kaebling, M. Littman, and A. Cassandra, “Planning and Acting in Partially Observable Stochastic Domains,” Artificial Intelligence, 1998. [35] M. Kalisiak and M. van de Panne, “Faster Motion Planning Using Learned Local Viability Models,” Proc. IEEE Int'l Conf. on Robotics and Automation, Apr. 2007. [36] M. Kalisiak and M. van de Panne, “RRT-Blossom: RRT with a Local Flood-Fill Behavior,” Proc. IEEE Int'l Conf. on Robotics and Automation, 2006. [37] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Space,” IEEE Trans. on Robotics and Automation, Vol. 12, No. 4, pp. 566–580, 1996. [38] O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” Proceedings of the IEEE International Conference on Robotics and Automation, pp. 500–505, 1985. [39] D. E. Koditschek, “Exact Robot Navigation by Means of Potential Functions: Some Topological Considerations,” Proc. IEEE Int. Conf. Robot. & Autom., pp. 1–6, 1987. [40] Y. Koren and J. Borenstein, 'Potential field methods and their inherent limitations for mobile robot navigation,' Proceedings of the IEEE Int. Conf. on Robotics and Automation, pp. 1398–1404, 1991. [41] J. J. Kuffner and S. M. LaValle, “RRT-Connect: An Efficient Approach to Single-Query Path Planning,” Proc. IEEE Int'l Conf. on Robotics and Automation, pp. 995–1001, 2000. [42] F. Lamiraux, D. Bonnafous, and O. Lefebvre, “Reactive Path Deformation for Nonholonomic Mobile Robots,” IEEE Trans. on Robotics and Automation, Vol. 20, No 6, pp. 967–977, December 2004. [43] J. C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991. [44] S. M. LaValle, “A Game-Theoretic Framework for Robot Motion Planning,” PhD Dissertation, University of Illinois, Urbana, IL, USA, July 1995. [45] S. M. LaValle, Planning Algorithms, Cambridge Univ. Press, 2006. [46] S. M. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Technical Report, Computer Science Dept., Iowa State University, Oct. 1998. [47] S. M. LaValle and J. J. Kuffner, “Randomized Kinodynamic Planning,” Proc. IEEE Int. Conf. on Robotics and Automation, pp. 473– 79, 1999. [48] S. M. LaValle and R. Sharma, “Motion Planning in Stochastic Environments: Theory and Modeling Issues,” Proc. IEEE Int'l Conf. on Robotics and Automation, pp. 3057 – 3062, 1995. [49] T.-Y. Li and Y.-C. Shie, “An Incremental Learning Approach to Motion Planning with Roadmap Management,” Proc. IEEE Int'l Conf. on Robotics and Automation, Vol. 4, pp. 3411 – 3416, 2002. [50] M. Likhachev, G. Gordon, and S. Thrun, “ARA*: Anytime A* Search with Provable Bounds on Sub-Optimality,” Proceedings of Conference on Neural Information Processing Systems (NIPS), MIT Press, Cambridge, MA, USA, 2003. [51] T. Lozano-Perez, M. T. Mason and R. H. Taylor, “Automatic Synthesis of Fine-Motion Strategies for Robots,” Int’l. J. of Robotics Research, Vol. 3, No. 1, 1984, pp.3–24. [52] V. Lumelsky. Sensing, Intelligence, Motion: How Robots and Humans Move in an Unstructured World. Wiley & Sons, New York, 2006. [53] D. Makris, T. Ellis, “Spatial and Probabilistic Modelling of Pedestrian Behaviour,” British Machine Vision Conference, Vol. 2, pp. 557–566, Cardiff, UK, 2002. [54] N. A. Melchior and R. Simmons. “Particle RRT for Path Planning with Uncertainty,” Proc. IEEE Int'l Conf. on Robotics and Automation, Apr. 2007. [55] H.P. Moravec and A.E. Elfes, “High Resolution Maps from Wide Angle Sonar,” Proc. IEEE Int. Conf. Robotics and Automation, pp. 116–121, 1985. [56] S. Parise and P. Smyth. “Learning Stochastic Path Planning Models from Video Images,” Technical Report UCI-ICS 04-12, University of California, Irvine, June 2004. [57] R. Pepy and A. Lambert, “Safe Path Planning in an Uncertain-Configuration Space using RRT,” Proc. IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems, Beijing, China, pp. 5376–5381, Oct. 2006. [58] S. Rodriguez, X. Tang, J.-M. Lien, and N. M. Amato, “An Obstacle-Based Rapidly-Exploring Random Tree,” Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Orlando, FL, USA, pp. 895–900, May 2006. [59] S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 2nd Edition, Pearson Education, Inc, 2003. [60] M. Schwager and D. Rus, “Data-Driven Identification of Group Dynamics for Motion Prediction and Control,” Proc. Int’l. Conf. on Field and Service Robotics, Chamonix, France, July 2007. [61] R Siegwart and I Nourbaksh, Introduction to Autonomous Mobile Robots, Bradford, 2004. [62] D. Simon, Optimal State Estimation: Kalman, H-infinity, and Nonlinear Approaches, John Wiley & Sons, 2006. [63] A. Stentz, “Optimal and Efficient Path Planning for Partially-Known Environments,” Proceedings of the IEEE International Conference on Robotics and Automation, May 1994. [64] Y. Suzuki, S. Kagami, and J. J. Kuffner, 'Path Planning with Steering Sets for Car-Like Robots and Finding an Effective Set,' Proceedings of IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 1221–1226, December 2006. [65] R. B. Tilove, “Local Obstacle Avoidance for Mobile Robots Based on the Method of Artificial Potentials,” Proc. IEEE Int. Conf. Robot. & Autom., pp. 566–571, May 1990. [66] C. Urmson and R. Simmons, “Approaches for Heuristically Biasing RRT. Growth,” Proc. IEEE Int’l. Conf. on Intelligent Robots and Systems, pp. 1178–1183, 2003. [67] S. A. Wilmarth, N. M. Amato, and P. F. Stiller, “MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space,” Proc. IEEE International Conference on Robotics and Automation, pp. 1024–1031, 1999. [68] A. Zelinsky and S. Yuta, “Reactive Planning for Mobile Robots Using Numeric Potential Fields,” Proc. Int. Conf. on Intelligent Autonomous Systems, PA, USA, 1993. [69] Q. Zhu, “Hidden Markov Model for Dynamic Obstacle Avoidance of Mobile Robot Navigation,” IEEE Trans. Robotics and Automation, Vol. 7, No. 3, pp. 390–397, 1991. [70] M. Zucker, J. Kuffner, and M. Branicky, 'Multipartite RRTs for Rapid Replanning in Dynamic Environments,' Proc. IEEE Int. Conf. Robotics and Automation, April 2007. [71] OGRE 3D Website: http://www.ogre3d.org/ [72] Simple DirectMedia Layer Website: http://www.libsdl.org/ [73] Boost C++ Libraries Website: http://www.boost.org/ [74] Box and Whisker Plots from Peltier Technical Services, Inc. Website: http://peltiertech.com/Excel/Charts/BoxWhiskerH.html | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/27790 | - |
| dc.description.abstract | 本文之主要目的在設計與建立一機器人的自動導航系統，使其能在充滿行人的室內工作。為了降低機器人對人類活動的干擾，並提高行人與機器人本身的安全性，本文開發一套預測式的路徑規畫系統。
本文提出一目標導向的行人運動模型，透過估計行人的行進目標預測其未來之軌跡。首先將環境中已知行人軌跡的起迄點進行群聚，即可得到數個可能之目標。再對於每個可能的目標，使用NF1演算法推估行人理想的行進方向，並使用位能場模型表示行人與行人以及機器人間的相互影響。比較推估與觀測的行人行為，即可估計行人的行進目標，進而預測行人未來的軌跡。經實驗證實，本文所提出之運動模型可有效估計行人目標並預測行人路徑。 本文進而提出Predictive Anytime RRT 路徑規畫演算法，利用上述的預測模型，在狀態 – 時間空間中搜尋機器人可行的路徑。當行進路線將遭受阻礙時，此演算法可找出令機器人在某段時間下原地等待的路徑。此外，利用改良的距離量度標準提升效率，在複雜的地圖下速度則可達RRT-Blossom的30倍。 實驗分為模擬與實作。模擬部分建立一多功能的軟體平台，使用行為庫模擬行人的動態，並物理引擎模擬機器人的運動，再以立體影像呈現路徑規畫與執行結果。在實作上，整合了使用雷射感測器之同步定位地圖建置與追蹤系統。整體系統可在室內環境中進行即時導航。 | zh_TW |
| dc.description.abstract | The main objective of this thesis is to develop an autonomous navigation system for a mobile robot, which operates in indoor environments among moving people. To reduce distraction to human activities, and to ensure safety, a path planner which predicts human motion is developed.
A goal-directed model of pedestrian motion is proposed. Pedestrians are assumed to be moving toward a set of possible destinations, which are extracted from human trajectories collected in the environment. Human motion is then modeled to follow a navigation function to each goal, and interaction between people is modeled with an interaction force model. The probability a new person is going toward each destination is estimated using the motion model. And given that, the future positions of the person can be predicted. The model is shown to capture typical pedestrian motion faithfully. The thesis further develops the Predictive Anytime Rapidly-Exploring Random Tree (PARRT) path planner to find the path of a mobile robot in state-time space. In dynamic environments the algorithm is able to plan in real time. Moreover, with the help of an improved distance metric the planner is faster than RRT-Blossom for 30 times in complex maps. A software platform is developed for both simulation and for real-world navigation, where environment and planning results are visualized in 3D. In real-world implementation a simultaneous localization and mapping (SLAM) with moving object tracking (MOT) module, a global planner using Probabilistic Roadmap (PRM), and a motor control module are integrated. In our experiments, the system is able to navigate in indoor environments in real time. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-12T18:20:43Z (GMT). No. of bitstreams: 1 ntu-96-R94522810-1.pdf: 2027339 bytes, checksum: 644ff81d93a465e57d11ad9b0a2456ba (MD5) Previous issue date: 2007 | en |
| dc.description.tableofcontents | Chapter 1 Introduction 1
1.1 Motivation 1 1.2 Objectives and Contributions 4 1.3 Thesis Organization 6 Chapter 2 Background Knowledge and Relevant Research 8 2.1 Planning as a Search Problem 9 2.1.1 Basic Search Strategies 10 2.1.2 Heuristic Search 11 2.1.3 Bidirectional and Multi-Directional Search 13 2.2 Adapting Path Planning Problems to Search Problems 14 2.2.1 The Configuration Space 15 2.2.2 Distance Metric 16 2.3 Potential Field Methods 18 2.3.1 Vector Force Field Method 18 2.3.2 Navigation Function 19 2.4 Randomized Path Planning 21 2.4.1 Probabilistic Roadmap 21 2.4.2 Rapidly-Exploring Random Tree 22 2.5 Planning under Uncertainty 23 2.5.1 Sources of Uncertainty 24 2.5.2 Efficient Replanning 26 2.5.3 Planning with Prediction 28 Chapter 3 Motion Prediction of Pedestrians 32 3.1 Introduction 32 3.1.1 Uncertainty Models 32 3.1.2 Motion Prediction 33 3.2 Modeling Pedestrian Motion 34 3.2.1 Motion Models for Motion Prediction 34 3.2.2 Goal-Directed Motion Models 36 3.2.3 The Proposed Goal-Directed Model 38 3.3 Modeling Interaction 43 3.3.1 Interaction Force Model 44 3.3.2 Applying Interaction Model in Prediction 45 3.4 Extracting and Learning Goals of Pedestrians 48 3.4.1 Extracting Goal Points 49 3.4.2 On-Line Clustering with Leader-Follower and k-Means 50 3.5 Obtaining Model Parameters 55 3.5.1 Sub-Optimality in Pedestrian Decision 55 3.5.2 Error in Pedestrian Speed 57 3.5.3 Interaction Force between People 58 3.6 Motion Mode Estimation 58 3.7 Motion Prediction Given Motion Mode 61 3.8 Integrating Prediction and Planning 62 3.8.1 Motion Prediction for Use in Planning 63 3.8.2 Integration Frameworks 64 Chapter 4 Predictive Anytime RRT for Local Planning 69 4.1 Planning in the State Space 70 4.2 Planning with RRT 72 4.2.1 Basic RRT Planner 72 4.2.2 Nonholonomic planning with RRT 73 4.3 Planning in Dynamic Environments 79 4.3.1 Modifications to RRT 79 4.3.2 RRT-Blossom 82 4.3.3 Regression Test in Dynamic Environments 88 4.4 Performance Enhancements 89 4.4.1 Better Distance Metric 89 4.4.2 Adaptive Biasing for Efficient Planning 91 4.5 Robust Anytime Planning 94 Chapter 5 Implementation and Experimental Results 98 5.1 Software Platform 98 5.2 Localization and Tracking with Laser Scanner 100 5.3 Probabilistic Roadmap for Global Planning 101 5.4 Experimental Results 102 5.4.1 “Dead-End” Scenario 102 5.4.2 “Crossroad” Scenario 104 5.4.3 Multiple Planning Sequences 108 5.4.4 Integration on a Real-World Robot 112 Chapter 6 Conclusions and Future Works 114 6.1 Conclusions 114 6.2 Future Works 116 References 118 | |
| dc.language.iso | en | |
| dc.title | 行動機器人在動態環境之路徑規畫 | zh_TW |
| dc.title | Path Planning for Mobile Robots in Dynamic Environments | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 95-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 李蔡彥(Tsai-Yen Li),王傑智(Chieh-Chih Wang) | |
| dc.subject.keyword | 行人預測,路徑規畫,運動規畫,機器人, | zh_TW |
| dc.subject.keyword | motion prediction,pedestrian model,motion planning,path planning,rapidly-exploring random tree,RRT,robotics, | en |
| dc.relation.page | 125 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2007-08-23 | |
| dc.contributor.author-college | 工學院 | zh_TW |
| dc.contributor.author-dept | 機械工程學研究所 | zh_TW |
| 顯示於系所單位： | 機械工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-96-1.pdf 目前未授權公開取用 | 1.98 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。