1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 自動產生具多樣化運動的虛擬人物動畫
Generating Humanoid Animation with Versatile Motions in a Virtual Environment
作者 黃培智
Huang,Pei-Zhi
貢獻者 李蔡彥
Li,Tsai-Yen
黃培智
Huang,Pei-Zhi
關鍵詞 Motion Planning
Humanoid
Animation
日期 2003
上傳時間 17-Sep-2009 13:53:56 (UTC+8)
摘要 Research on global path planning and navigation strategies for mobile robots has been well studied in the robotics literature. Since the problem can usually be modeled as searching for a collision-free path in a 2D workspace, very efficient and complete algorithms can be employed. However, enabling a humanoid robot to move autonomously in a real-life environment remains a challenging problem. Unlike traditional wheeled robots, legged robots such as humanoid robots have advanced abilities of stepping over an object or striding over a deep gap with versatile locomotions. In this thesis, we propose a motion planning system capable of generating both global and local motions for a humanoid robot in layered environment cluttered with obstacles and deep narrow gaps. The planner can generate a gross motion that takes multiple locomotions, humanoid’s geometric properties and striding ability into consideration. A gross motion plan that satisfies the constraints is generated and further realized by a local planner, which determines the most efficient footsteps and locomotion over uneven terrain. If the local planner fails, the failure is fed back to the global planner to consider other alternative paths. The experiments show that our system can efficiently generate humanoid motions to reach the goal in a real-life environment. The system can also apply to a real humanoid robot to provide a high-level control mechanism.
參考文獻 [1] A. Bruderlin and T. W. Calvert, “Goal-Directed, Dynamic Animation of Human Walking,” Proc. of ACM SIGGRAPH, 1989.
[2] A. Witkin and Z. Popovic, “Motion Warping,” Computer Graphics Proceedings, SIGGRAPH95, pp.105-108, 1995.
[3] D. Sent and M. H. Overmars, “Motion Planning in Environments with Dangerzones,” Proc. of 2001 IEEE Intl. Conf. on Robotics and Automation, pp.1488-1493, May 2001.
[4] H. Ko and N.I. Badler, “Animating Human Locomotion with Inverse Dynamics,” IEEE Transaction on Computer Graphics, 16(2), pp.50-59, 1996.
[5] H. C. Sun and N. M. Dimitris, “Automating gait generation,” Proc. of ACM SIGGRAPH, 2001.
[6] H. Miura and I. Shimoyama, “Dynanic Walk of a Biped,” Intl. J. of Robotics Research, pp.60-74, 1984.
[7] J. Barraquand and J. Latombe, “Robot Motion Planning: A Distributed Representation Approach,” Intl J. of Robotics Research, 10:628-649, 1991.
[8] J. Barraquand, L. Kavraki, J.C. Latombe, T.Y. Li, and P. Raghavan, “A Random Sampling Scheme for Path Planning,” Intl. J. of Robotics Research, 16(6), pp.759-774, Dec. 1997.
[9] J. Chestnutt, J. Kuffner, K. Nishiwaki, and S. Kagami, “Planning Biped Navigation Strategies in Complex Environments,” Proc. of IEEE Intl. Conf. on Humanoid Robotics, 2003.
[10] J.H. Reif, “Complexity of the Mover`s Problem and Generalizations,” Proc. of the 20th IEEE Symp. on Foundations of Computer Science, pp. 421-427, 1979.
[11] J. Kuffner, K. Nishiwaki, S. Kagami, M. Inaba, and H. Inoue, “Motion Planning for Humanoid Robots under Obstacle and Dynamic Balance Constraints,” Proc. of IEEE Intl. Conf. on Robotics and Automation, May 2001.
[12] J. Kuffner, “Goal-Directed Navigation for Animated Characters Using Real-time Path Planning and Control” Proc. of CAPTECH’98 Workshop on Modeling and Motion capture Techniques for Virtual Environments, Springer-Verlag, 1998.
[13] J. Kuffner, K. Nishiwaki, S. Kagami, M. Inaba, and H. Inoue, “Footstep Planning Among Obstacles for Biped Robots,” Proc. of 2001 IEEE Intl. Conf. on Intelligent Robots and Systems (IROS 2001), 2001.
[14] J. Latombe, Robot Motion Planning, Kluwer, Boston, MA, 1991.
[15] J. Pettre, J.-P. Laumond, and T. Simeon, “A 2-Stages Locomotion Planner for Digital Actors,” Proc. of Eurographics/SIGGRAPH Symposium on Computer Animation, 2003.
[16] K. Yamane and Y. Nakamura, “Dynamics Filter – Concept and Implementation of On-Line Motion Generator for Human Figures,” Proc. of IEEE Intl. Conf. on Robotics and Automation, pp.688-695, April 2000.
[17] L. Kavraki, P.Svestka, J. Latombe, and M. Overmars, “Probabilistic Roadmaps for Fast Path Planning in High-Dimensional Configuration Spaces,” IEEE Trans. on Robotics and Automation, 12:566-580, 1996.
[18] M. Kalisiak and M. Panne, “A grasp-based motion planning algorithm for character animation,” J. of Visualization and computer animation, pp.117-129, 2001.
[19] M.G. Choi, J. Lee, S.Y. Shin, “Planning Biped Locomotion using Motion Capture Data and Probabilistic Roadmaps,” ACM Transactions on Graphics, Vol. V, pp.1–25, October 2002.
[20] N.M. Amato, O.B. Bayazit, L.K. Dale, C. Jones, and D. Vallejo, “OBPRM: An Obstacle-Based PRM for 3D Workspaces,” Robotics: The Algorithmic Perspective, pp.630-637, 1998.
[21] N. Pollard, J. Hodgins, M. Riley, and C. Atkeson, “Adapting Human Motion for the Control of a Humanoid Robot,” Proc. of 2002 IEEE Intl. Conf. on Robotics and Automation, pp.2265-2270, May 2002.
[22] P.F. Chen, and T.Y. Li, “Planning Efficient Walking Gaits in Real-Time for Human Characters,” Proc. of 2003 Computer Graphics Workshop, Taiwan, 2003.
[23] Q. Huang, K. Kaneko, K. Yokoi, S. Kajita, K. Kotoku, N. Koyachi, H. Arai, N. Imamuna, K. Komoriya, K. Tanie, “Balance Control of a Biped Robot Combining Off-line Pattern with Real-time Modification,” Proc. of IEEE Intl. Conf. on Robotics and Automation, pp.3346-3352, April 2000.
[24] R. A. Brooks and T. Lozano-Perez, “A subdivision Algoritm in Computer Space for Find-Path with Rotation,” IEEE Trans. on System. Man, and Cybernetics, vol. 15, pp.224-244, 1985.
[25] R.C. Gonzale and R.E. Woods, Digital Image Processing Second Edition, Prentice Hall, 2002.
[26] S. M. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Technical Report No. 98-11, Iowa State University, 1998.
[27] S.Y. Shin and T. Kunii, “Pseudo Dynamic Keyframe Animation with Motion Blending on the Configuration Space of a Moving Mechanism,” Proc. of Pacific Graphics, August 1995.
[28] T.-Y. Li, J.M. Lien, S.Y. Chiu, and T.H. Yu, “Automatically Generating Virtual Guided Tours,” in Proc. of the Computer Animation `99 Conf., pp.99-106, May 1999.
[29] T.-Y. Li, and H.-K Ting., “An Intelligent User Interface with Motion Planning for 3D Navigation,” Proc. of the IEEE Virtual Reality 2000 Conf., March 2000.
[30] T.Y. Li, M.Y. Liao, and J.F. Liao, “An Extensible Scripting Language for Interactive Animation in a Speech-Enabled Virtual Environment,” Proc. of the IEEE Intl. Conf. on Multimedia and Expo (ICME2004), Taipei, Taiwan, 2004.
[31] T.Y. Li, P.F. Chen, and P.Z. Huang, “Motion Planning for Humanoid Walking in a Layered Environment,” in Proc. of the 2003 Int. Conf. on Robotics and Automation, 2003.
[32] T.Y. Li and P.Z. Huang, “Motion Planning for a Humanoid Walking in a 3D Space,” Proc. of the 2001 National Computer Symposium, Taipei, Taiwan, 2001.
[33] Y.K. Hwang and N. Ahuja, “Gross Motion Planning – a Survey,” ACM Comp. Surveys, 24(3):219-291, 1992.
[34] Z. Shiller, K. Yamane, and Y. Nakamura, “Planning Motion Patterns of Human Figures Using a Multi-Layered Grid and the Dynamics Filter” Proc. of IEEE Intl. Conf. on Robotics and Automation, pp.1-8, May 2001.
描述 碩士
國立政治大學
資訊科學學系
91753002
92
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0091753002
資料類型 thesis
dc.contributor.advisor 李蔡彥zh_TW
dc.contributor.advisor Li,Tsai-Yenen_US
dc.contributor.author (Authors) 黃培智zh_TW
dc.contributor.author (Authors) Huang,Pei-Zhien_US
dc.creator (作者) 黃培智zh_TW
dc.creator (作者) Huang,Pei-Zhien_US
dc.date (日期) 2003en_US
dc.date.accessioned 17-Sep-2009 13:53:56 (UTC+8)-
dc.date.available 17-Sep-2009 13:53:56 (UTC+8)-
dc.date.issued (上傳時間) 17-Sep-2009 13:53:56 (UTC+8)-
dc.identifier (Other Identifiers) G0091753002en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/32633-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 91753002zh_TW
dc.description (描述) 92zh_TW
dc.description.abstract (摘要) Research on global path planning and navigation strategies for mobile robots has been well studied in the robotics literature. Since the problem can usually be modeled as searching for a collision-free path in a 2D workspace, very efficient and complete algorithms can be employed. However, enabling a humanoid robot to move autonomously in a real-life environment remains a challenging problem. Unlike traditional wheeled robots, legged robots such as humanoid robots have advanced abilities of stepping over an object or striding over a deep gap with versatile locomotions. In this thesis, we propose a motion planning system capable of generating both global and local motions for a humanoid robot in layered environment cluttered with obstacles and deep narrow gaps. The planner can generate a gross motion that takes multiple locomotions, humanoid’s geometric properties and striding ability into consideration. A gross motion plan that satisfies the constraints is generated and further realized by a local planner, which determines the most efficient footsteps and locomotion over uneven terrain. If the local planner fails, the failure is fed back to the global planner to consider other alternative paths. The experiments show that our system can efficiently generate humanoid motions to reach the goal in a real-life environment. The system can also apply to a real humanoid robot to provide a high-level control mechanism.zh_TW
dc.description.tableofcontents 1 Introduction ....................................................................................................1
1.1 Motivations ..............................................................................................2
1.2 Autonomous Digital Actor .......................................................................3
1.3 Realism vs. Interactivity ..........................................................................4
1.4 Contributions ...........................................................................................5
1.5 Mathematical Formulation ......................................................................6
1.6 Organization ............................................................................................7
2 Related Work ..................................................................................................8
2.1 Gross Motion Planning ............................................................................9
2.2 Character Animation ..............................................................................10
2.3 Two-Level Motion Planning ..................................................................11
2.3.1 Low DOF Workspace Approach .................................................12
2.3.2 Randomized Approach ...............................................................13
3 Problem Description .....................................................................................14
3.1 Overall Problem Description .................................................................14
3.2 Virtual Human Modeling ................................................................16
3.3 Global Motion Planning Problem ..........................................................18
3.4 Local Motion Planning Problem ............................................................20
3.5 Replanning Problem ..............................................................................22
4 Environment Modeling .................................................................................24
4.1 Binary Bitmap Representation ...............................................................25
4.2 Height Map Representation ...................................................................26
4.3 Layered Height Map Representation .....................................................27
4.4 Merging Sparse Layers Representation .................................................29
5 Reachability and Collision Modeling ...........................................................33
5.1 Virtual human’s Kinematic and Geometric Properties ..........................34
5.2 Locomotion Ability ................................................................................37
5.2.1 Extend the Reachable Region In Search ....................................39
5.2.2 Extend the Reachable Region In Preprocessing .........................39
5.3 Instability ...............................................................................................42
5.4 Static Collision Detection ......................................................................44
5.5 Reachability Map with Multiple Locomotion .......................................46
6 Global Path Searching ..................................................................................51
6.1 Potential Field ........................................................................................52
6.2 Path Planning Algorithm .......................................................................54
6.3 Dynamic Collision Detection ................................................................56
6.4 Search Criteria .......................................................................................57
6.5 Post Processing ......................................................................................58
7 Replanning ....................................................................................................60
7.1 Fully Reconstruct Approach ..................................................................60
7.2 Partial Update Approach ........................................................................63
8 Experimental Results ..............................................................................66
8.1 Experiments with Different Step Height ...............................................66
8.2 Experiments with Different Preferences ................................................68
8.3 Effect of Virtual Human’s Height ..........................................................70
8.4 Stair-like Terrain Examples ...................................................................72
8.5 Layered Environment Examples ...........................................................74
8.6 Replanning Examples ............................................................................74
8.7 Global Planning with Striding Ability ...................................................77
8.8 Versatile Locomotion Examples ............................................................79
9 Conclusions and Future Work ......................................................................83
9.1 Summary ................................................................................................83
9.2 Discussion ..............................................................................................84
References ..........................................................................................................86		zh_TW
dc.format.extent 43647 bytes-
dc.format.extent 19621 bytes-
dc.format.extent 12475 bytes-
dc.format.extent 12401 bytes-
dc.format.extent 41519 bytes-
dc.format.extent 45285 bytes-
dc.format.extent 352111 bytes-
dc.format.extent 530883 bytes-
dc.format.extent 545470 bytes-
dc.format.extent 192429 bytes-
dc.format.extent 145498 bytes-
dc.format.extent 1571170 bytes-
dc.format.extent 93215 bytes-
dc.format.extent 138297 bytes-
dc.format.extent 41096 bytes-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0091753002en_US
dc.subject (關鍵詞) Motion Planningen_US
dc.subject (關鍵詞) Humanoiden_US
dc.subject (關鍵詞) Animationen_US
dc.title (題名) 自動產生具多樣化運動的虛擬人物動畫zh_TW
dc.title (題名) Generating Humanoid Animation with Versatile Motions in a Virtual Environmenten_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] A. Bruderlin and T. W. Calvert, “Goal-Directed, Dynamic Animation of Human Walking,” Proc. of ACM SIGGRAPH, 1989.zh_TW
dc.relation.reference (參考文獻) [2] A. Witkin and Z. Popovic, “Motion Warping,” Computer Graphics Proceedings, SIGGRAPH95, pp.105-108, 1995.zh_TW
dc.relation.reference (參考文獻) [3] D. Sent and M. H. Overmars, “Motion Planning in Environments with Dangerzones,” Proc. of 2001 IEEE Intl. Conf. on Robotics and Automation, pp.1488-1493, May 2001.zh_TW
dc.relation.reference (參考文獻) [4] H. Ko and N.I. Badler, “Animating Human Locomotion with Inverse Dynamics,” IEEE Transaction on Computer Graphics, 16(2), pp.50-59, 1996.zh_TW
dc.relation.reference (參考文獻) [5] H. C. Sun and N. M. Dimitris, “Automating gait generation,” Proc. of ACM SIGGRAPH, 2001.zh_TW
dc.relation.reference (參考文獻) [6] H. Miura and I. Shimoyama, “Dynanic Walk of a Biped,” Intl. J. of Robotics Research, pp.60-74, 1984.zh_TW
dc.relation.reference (參考文獻) [7] J. Barraquand and J. Latombe, “Robot Motion Planning: A Distributed Representation Approach,” Intl J. of Robotics Research, 10:628-649, 1991.zh_TW
dc.relation.reference (參考文獻) [8] J. Barraquand, L. Kavraki, J.C. Latombe, T.Y. Li, and P. Raghavan, “A Random Sampling Scheme for Path Planning,” Intl. J. of Robotics Research, 16(6), pp.759-774, Dec. 1997.zh_TW
dc.relation.reference (參考文獻) [9] J. Chestnutt, J. Kuffner, K. Nishiwaki, and S. Kagami, “Planning Biped Navigation Strategies in Complex Environments,” Proc. of IEEE Intl. Conf. on Humanoid Robotics, 2003.zh_TW
dc.relation.reference (參考文獻) [10] J.H. Reif, “Complexity of the Mover`s Problem and Generalizations,” Proc. of the 20th IEEE Symp. on Foundations of Computer Science, pp. 421-427, 1979.zh_TW
dc.relation.reference (參考文獻) [11] J. Kuffner, K. Nishiwaki, S. Kagami, M. Inaba, and H. Inoue, “Motion Planning for Humanoid Robots under Obstacle and Dynamic Balance Constraints,” Proc. of IEEE Intl. Conf. on Robotics and Automation, May 2001.zh_TW
dc.relation.reference (參考文獻) [12] J. Kuffner, “Goal-Directed Navigation for Animated Characters Using Real-time Path Planning and Control” Proc. of CAPTECH’98 Workshop on Modeling and Motion capture Techniques for Virtual Environments, Springer-Verlag, 1998.zh_TW
dc.relation.reference (參考文獻) [13] J. Kuffner, K. Nishiwaki, S. Kagami, M. Inaba, and H. Inoue, “Footstep Planning Among Obstacles for Biped Robots,” Proc. of 2001 IEEE Intl. Conf. on Intelligent Robots and Systems (IROS 2001), 2001.zh_TW
dc.relation.reference (參考文獻) [14] J. Latombe, Robot Motion Planning, Kluwer, Boston, MA, 1991.zh_TW
dc.relation.reference (參考文獻) [15] J. Pettre, J.-P. Laumond, and T. Simeon, “A 2-Stages Locomotion Planner for Digital Actors,” Proc. of Eurographics/SIGGRAPH Symposium on Computer Animation, 2003.zh_TW
dc.relation.reference (參考文獻) [16] K. Yamane and Y. Nakamura, “Dynamics Filter – Concept and Implementation of On-Line Motion Generator for Human Figures,” Proc. of IEEE Intl. Conf. on Robotics and Automation, pp.688-695, April 2000.zh_TW
dc.relation.reference (參考文獻) [17] L. Kavraki, P.Svestka, J. Latombe, and M. Overmars, “Probabilistic Roadmaps for Fast Path Planning in High-Dimensional Configuration Spaces,” IEEE Trans. on Robotics and Automation, 12:566-580, 1996.zh_TW
dc.relation.reference (參考文獻) [18] M. Kalisiak and M. Panne, “A grasp-based motion planning algorithm for character animation,” J. of Visualization and computer animation, pp.117-129, 2001.zh_TW
dc.relation.reference (參考文獻) [19] M.G. Choi, J. Lee, S.Y. Shin, “Planning Biped Locomotion using Motion Capture Data and Probabilistic Roadmaps,” ACM Transactions on Graphics, Vol. V, pp.1–25, October 2002.zh_TW
dc.relation.reference (參考文獻) [20] N.M. Amato, O.B. Bayazit, L.K. Dale, C. Jones, and D. Vallejo, “OBPRM: An Obstacle-Based PRM for 3D Workspaces,” Robotics: The Algorithmic Perspective, pp.630-637, 1998.zh_TW
dc.relation.reference (參考文獻) [21] N. Pollard, J. Hodgins, M. Riley, and C. Atkeson, “Adapting Human Motion for the Control of a Humanoid Robot,” Proc. of 2002 IEEE Intl. Conf. on Robotics and Automation, pp.2265-2270, May 2002.zh_TW
dc.relation.reference (參考文獻) [22] P.F. Chen, and T.Y. Li, “Planning Efficient Walking Gaits in Real-Time for Human Characters,” Proc. of 2003 Computer Graphics Workshop, Taiwan, 2003.zh_TW
dc.relation.reference (參考文獻) [23] Q. Huang, K. Kaneko, K. Yokoi, S. Kajita, K. Kotoku, N. Koyachi, H. Arai, N. Imamuna, K. Komoriya, K. Tanie, “Balance Control of a Biped Robot Combining Off-line Pattern with Real-time Modification,” Proc. of IEEE Intl. Conf. on Robotics and Automation, pp.3346-3352, April 2000.zh_TW
dc.relation.reference (參考文獻) [24] R. A. Brooks and T. Lozano-Perez, “A subdivision Algoritm in Computer Space for Find-Path with Rotation,” IEEE Trans. on System. Man, and Cybernetics, vol. 15, pp.224-244, 1985.zh_TW
dc.relation.reference (參考文獻) [25] R.C. Gonzale and R.E. Woods, Digital Image Processing Second Edition, Prentice Hall, 2002.zh_TW
dc.relation.reference (參考文獻) [26] S. M. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Technical Report No. 98-11, Iowa State University, 1998.zh_TW
dc.relation.reference (參考文獻) [27] S.Y. Shin and T. Kunii, “Pseudo Dynamic Keyframe Animation with Motion Blending on the Configuration Space of a Moving Mechanism,” Proc. of Pacific Graphics, August 1995.zh_TW
dc.relation.reference (參考文獻) [28] T.-Y. Li, J.M. Lien, S.Y. Chiu, and T.H. Yu, “Automatically Generating Virtual Guided Tours,” in Proc. of the Computer Animation `99 Conf., pp.99-106, May 1999.zh_TW
dc.relation.reference (參考文獻) [29] T.-Y. Li, and H.-K Ting., “An Intelligent User Interface with Motion Planning for 3D Navigation,” Proc. of the IEEE Virtual Reality 2000 Conf., March 2000.zh_TW
dc.relation.reference (參考文獻) [30] T.Y. Li, M.Y. Liao, and J.F. Liao, “An Extensible Scripting Language for Interactive Animation in a Speech-Enabled Virtual Environment,” Proc. of the IEEE Intl. Conf. on Multimedia and Expo (ICME2004), Taipei, Taiwan, 2004.zh_TW
dc.relation.reference (參考文獻) [31] T.Y. Li, P.F. Chen, and P.Z. Huang, “Motion Planning for Humanoid Walking in a Layered Environment,” in Proc. of the 2003 Int. Conf. on Robotics and Automation, 2003.zh_TW
dc.relation.reference (參考文獻) [32] T.Y. Li and P.Z. Huang, “Motion Planning for a Humanoid Walking in a 3D Space,” Proc. of the 2001 National Computer Symposium, Taipei, Taiwan, 2001.zh_TW
dc.relation.reference (參考文獻) [33] Y.K. Hwang and N. Ahuja, “Gross Motion Planning – a Survey,” ACM Comp. Surveys, 24(3):219-291, 1992.zh_TW
dc.relation.reference (參考文獻) [34] Z. Shiller, K. Yamane, and Y. Nakamura, “Planning Motion Patterns of Human Figures Using a Multi-Layered Grid and the Dynamics Filter” Proc. of IEEE Intl. Conf. on Robotics and Automation, pp.1-8, May 2001.zh_TW