Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/32619
|
| Title: | 以階層式動態編隊的方法計劃群體運動 |
| Authors: | 周旭騏 |
| Contributors: | 李蔡彥
周旭騏 |
| Keywords: | 群體運動計劃
分離式
集中式
階層式動態編隊
球形樹 |
| Date: | 2002 |
| Issue Date: | 2009-09-17 13:52:18 (UTC+8) |
| Abstract: | 群體機器人運動的自動產生，可以應用在可移式機器人群的路徑規劃或電腦動畫中虛擬人群的模擬上。文獻上研究對此運動計劃問題，多以分離式或集中式的方法來解決。分離法是把群體的計劃，切割為多個個別機器人的連續計劃。本論文採優先順序的分離法依序解決個別機器人的計劃；而個別計畫的方法係採用位能場與A*搜尋法，我們並針對群體運動的特性提出改進方案。分離法的搜尋由於受到前面計劃結果的限制，因此缺乏計劃的完整性；相對而言，集中法同時考慮所有機器人的組態，因此可以完整地搜尋整個群體機器人的組態空間。我們首先採用的集中法是以位能場為基礎的隨機路徑計劃法。此法雖然具備完整性，但在機器人數量多時，機器人間的碰撞機會太高，所以計劃所需時間通常較長。因此，我們設計了一個採用階層式動態編隊方式的集中式計畫法。階層式動態編隊就是以球形樹組織機器人隊伍，依照搜尋時的狀況，動態地進行隊伍的分離或合併。同隊伍中的機器人會維持一致的運動方向，因此減少了機器人間發生碰撞的機會，因而改善了計劃的效率。我們實驗比較分離法、集中法、與動態編隊法，並分析各種情況下適合的計劃方法，以提出使用建議。我們並且設計了一個平滑化路徑的方法，將計劃出來的群體運動路徑調整平順，以應用在電腦動畫的製作過程中，自動產生擬真的虛擬人群運動。
The automatic generation of crowd motions can be used in planning the path of many mobile robots and in simulating the motions of virtual humans in computer animation. In the literature, there exist two categories of approaches to this problem: decoupled and centralized approaches. The decoupled approach divides the planning problem into several sub-problems, each of which is for a robot. In this thesis we have used a prioritized planning approach with an artificial potential field and the A* search algorithm to solve each sub-problem in a given order. This decoupled approach usually is not complete because later planning must be under the constraint of previous planned results. On the other hand, the centralized approach considers the configurations of all robots and can be made complete by searching the composite configuration space. In this thesis, we use the randomized path planner (RPP) with a potential field as an example of the centralized approach. However, this planner is not very efficient for a large number of robots because of frequent inter-collisions between robots. Therefore we propose a hierarchical dynamic grouping method to improve the centralized RPP method. The robots are organized as groups enclosed by a sphere tree structure that can split or merge dynamically according to the environment. The robots in the same group always move with the same direction. Consequently the collisions between robots decrease significantly during the search and the planning efficiency is greatly improved. We have designed extensive experiments to compare the performance of the decoupled approach, the centralized approach and the dynamic grouping method. We also analyze these approaches in various scenarios in order to illustrate their tradeoffs. In addition, we have designed a path-smoothing method and apply the planning result to a production process of computer animation. |
| Reference: | 參考文獻
[1] B. Aronov, M. T. de Berg, A. F. van der Stappen, P. Svestka, J. M. Vleugels, “Motion Planning for Multiple Robots,” Technical Report UU-CS-1998-30, Department of Computer Science, Utrecht University, 1998.
[2] M. Bennewitz, W. Burgard, and S. Thrun, “Optimizing Schedules for Prioritized Path Planning of Multi-Robot Systems,” Proceedings of the International Conference on Robotics and Automation (ICRA), 2001.
[3] R. Bohlin and L. E. Kavraki, “A Randomized Algorithm for Robot Path Planning Based on Lazy Evaluation,” Handbook on Randomized Computing, pp. 221–249, Kluwer Academic Publishers, 2001.
[4] J. Barraquand, L. Kavraki, J.C. Latombe, T.Y. Li, and P. Raghavan, “A Random Sampling Scheme for Path Planning,” International Journal of Robotics Research, 16(6), pp.759-774, Dec. 1997.
[5] J. Barraquand and J.C. Latombe, “Robot Motion Planning: A Distributed Representation Approach,” International Journal of Robotics Research, 10(6):628-649, 1991.
[6] O. B. Bayazit, J. M. Lien, and N. M. Amato, “Simulating Flocking Behaviors in Complex Environments,” Technical Report TR02-003, PARASOL LAB, Department of Computer Science, Texas A&M University, April 2002.
[7] J. Barraquand, B. Langlois, and J.C. Latombe, “Numerical Potential Field Techniques for Robot Path Planning,” IEEE Transactions on Systems, Man, and Cybernetics, 22(2):224-241, 1992.
[8] Thomas Chadzelek, Jens Eckstein, and Elmar Schömer, “Heuristic Motion Planning with Movable Obstacles,” the 8th Canadian Conference on Computational Geometry, 1996.
[9] Y.U. Cao, A.S. Fukunaga, A.B. Kahng, and F. Meng, “Cooperative Mobile Robotics: Antecedents and Directions,” Proceedings of IEEE/TSJ International Conference on Intelligent Robots and Systems, pp.226-234, 1995.
[10] C.M. Clark, S.M. Rock, and J.C. Latombe, “Motion Planning for Multiple Mobile Robot Systems Using Dynamic Networks,“ Proceedings of IEEE International Conference on Robotics and Automation, Taipei, Taiwan, 2003.
[11] M. Erdmann and T. Lozano-Perez, “On Multiple Moving Objects,” AI Memo No. 883, Artificial Intelligence Laboratory, MIT, 1986.
[12] R. Fierro, P. Song, A. Das, and V. Kumar, “Cooperative Control of Robot Formations,” in Cooperative Control and Optimization, Kluwer Academic Press, 2001.
[13] V. Gervasi and G. Prencipe, “Flocking by a Set of Autonomous Mobile Robots,” Technical Report TR-01-24, Dipartimento di Informatica, Universita di Pisa, Italy, Oct. 2001.
[14] K. Gupta, “Motion Planning for “Flexible” Shapes (Systems with Many Degrees of Freedom): A Survey,” The Visual Computer, Volume 14, Issue 5/6, pp.288-302, 1998.
[15] S. Hert, V. Lumelsky, “Planar Curve Routing for Tethered-Robot Motion Planning,” International Journal of Computational Geometry & Applications, Vol. 17, No. 3, 225-252, 1997.
[16] Y. Koga, K. Kondo, J. Kuffner, and J.C. Latombe, “Planning Motions with Intentions,” Computer Graphics (SIGGRAPH’ 94), pp.395-408, 1994.
[17] L. E. Kavraki, P. Svestka, J.C. Latombe, and M. Overmars, “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces,” IEEE Transactions on Robotics and Automation, 12(4):566-580, 1996.
[18] J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, Boston, 1991.
[19] S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” TR 98-11, Computer Science Dept., Iowa State University, Oct. 1998.
[20] T.Y. Li and J.S. Chen, “Incremental 3D Collision Detection with Hierarchical Data Structures,” in Proceedings of ACM Symposium on Virtual Reality Software and Technology (VRST’98), pp.139-144, Taipei, Taiwan, 1998.
[21] T. Y. Li, Y. J. Jeng, and S. I. Chang, “Simulating Virtual Human Crowds with a Leader-Follower Model,” Proceedings of the 2001 Computer Animation Conference, Korea, 2001.
[22] S. M. LaValle and S. A. Hutchinson, “Optimal Motion Planning for Multiple Robots Having Independent Goals,” IEEE Transactions on Robotics and Automation, 14(6):912--925, 1998.
[23] T. Y. Li and Y. C. Shie, “An Incremental Learning Approach to Motion Planning with Roadmap Management,” in Proceedings of International Conference on Robotics and Automation, Washington, 2002.
[24] L. E. Parker, “Current Research in Multi-Robot Systems,” Journal of Artificial Life and Robotics, vol. 7, 2003.
[25] G. Prencipe, “A New Distributed Model to Control and Coordinate a Set of Autonomous Mobile Robots: The CORDA Model,” Technical Report TR-00-10, Dipartimento di Informatica, Universita di Pisa, Italy, 2000.
[26] S. Quinlan, "Efficient Distance Computation between Non-Convex Objects," Proceedings of International Conference on Robotics and Automation, San Diego, CA, 1994.
[27] C. Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model,” Proceedings of ACM SIGGRAPH ’87, pp.25-34, 1987.
[28] C. W. Reynolds, “Steering Behaviors For Autonomous Characters,” Proceedings of Game Developers Conference, pp.763-782, 1999.
[29] S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, New Jersey, 1995.
[30] J. H. Reif and H. Wang, “Social Potential Fields: A Distributed Behavioral Control for Autonomous Robots,” Robotics and Autonomous Systems, Vol. 27, no.3, pp.171-194, 1999.
[31] G. Sanchez and J.C. Latombe, “A Single-Query Bi-Directional Probabilistic Roadmap Planner with Lazy Collision Checking,” International Symposium on Robotics Research (ISRR`01), Lorne, Victoria, Australia, November 2001.
[32] G. Sanchez and J.C. Latombe, “Using a PRM Planner to Compare Centralized and Decoupled Planning for Multi-Robot Systems,” Proceedings IEEE International Conference on Robotics and Automation, 2002.
[33] T. Simeon, S. Leroy, J.-P. Laumond, “Path Coordination for Multiple Mobile Robots: a Resolution Complete Algorithm,” IEEE Transaction on Robotics and Automation, Vol 18 n 1, Feb 2002.
[34] P. Svestka and M. H. Overmars, “Coordinated Path Planning for Multiple Robots,” Technical Report UU-CS-1996-43, Department of Computer Science, Utrecht University, 1996. |
| Description: | 碩士
國立政治大學
資訊科學學系
90753002
91 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0090753002 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
