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

題名 以統一的觀點規劃自主式數位演員之多種運動能力
A unified approach to the motion planning of an autonomous digital actor with multiple motion abilities
作者 李岳澤
Li,Yueh-Tse
貢獻者 李蔡彥
Li,Tsai-Yen
李岳澤
Li,Yueh-Tse
關鍵詞 運動計畫
數位演員
電腦動畫
搬移障礙物
日期 2006
上傳時間 17-Sep-2009 14:00:08 (UTC+8)
摘要 讓數位演員能夠在虛擬場景中自主的規劃路徑並且移動，一直是一個富有挑戰性的問題。近年來已有相當多與此相關的研究，數位演員已能夠在高低起伏的分層地形中做路徑的規劃。我們的目標是除了能處理更一般化的場景外，對於場景中障礙物的定義，也會隨著數位演員的能力而有所不同。本研究為數位演員所擴充的新的能力包含了翻越過障礙物的能力以及搬移障礙物的能力。在以往藉由搬移障礙物而抵達目的地的研究中，都是以先決定欲搬移障礙物的順序，再為數位演員以本身擁有的運動能力規劃出一條合理且無碰撞的路徑。而本研究的特色則是將搬移障礙物這項能力與數位演員其他的運動能力一併考量，將各種運動能力以一致的觀點來規劃數位演員的行走路徑。我們將以數個模擬的例子說明此運動計畫器的有效性。
Enabling a digital actor to move autonomously in a virtual environment is a challenging problem that has attracted much research attention in recent years. Many researches have been also to generate the motion of a digital actor in an uneven layered environment. In this thesis, we have extended our previous work to enable the digital actor to have the ability of jumping over a barrier and the ability of manipulating obstacles in order to make room for passing. Most previous work in generating manipulation plans for obstacles must first decide the order of manipulation and then manipulate obstacles in accordance with the sequence. In this thesis, we design a motion planner that can take all motion abilities of the digital actor into account in generating a collision-free path in a layered environment cluttered with various types of obstacles. This planer takes a unified view to consider all types of motions including manipulating objects that could change the system configuration. The experimental results will be demonstrated with several simulation examples to show the effectiveness of the system
參考文獻 [1] R. Alami, J.-P. Laumond, and T. Siméon. “Two manipulation planning algorithms,” in J.-P. Laumond and M. Overmars, editors, Algorithms for Robotic Motion and Manipulation. A.K. Peters, Wellesley, MA, 1997.
[2] 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.
[3] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Second Edition, Chapter 7: Voronoi Diagrams, 2000.
[4] A. Bruderlin and T. W. Calvert, “Goal-Directed, Dynamic Animation of Human Walking,” in Proceedings of ACM SIGGRAPH, 1989.
[5] P. C. Chen and Y. K. Hwang, “Practical path planning among movable obstacles,” in Proceedings of IEEE International Conference on Robotic Automation, pp.444-449, 1991.
[6] P. F. Chen and T. Y. Li, “Generating Humanoid Lower-Body Motions with Real-Time Planning,” in Proceeding of 2002 Computer Graphics Workshop, Taiwan, 2002.
[7] E. D. Demaine, M. L. Demaine, and J. O`Rourke, “PushPush and Push-1 are NP-hard in 2D,” in Proceedings of the 12th Annual Canadian Conference on Computational Geometry, pp. 211-219, August 2000.
[8] R. C. Gonzale and R. E. Woods, Digital Image Processing, Second Edition, Prentice Hall, pp.224-244, 1985.
[9] M. Lau and J. Kuffner, “Behavior Planning for Character Animation,” in Proceeding of ACM SIGGRAPH / Eurographics Symposium on Computer Animation, Los Angeles, CA, 2005.
[10] J. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991.
[11] T.Y. Li and P.Z. Huang, “Motion Planning for a Humanoid Walking in a 3D Space,” in Proceeding of the 2001 National Computer Symposium, Taipei, Taiwan, 2001.
[12] T.Y. Li, and P.Z. Huang, “Planning Humanoid Gross Motions on a Layered Scene,” in Proceeding of 2002 Computer Graphics Workshop, Taiwan, 2002.
[13] T.Y. Li and P.Z. Huang, “Planning Humanoid Motions with Striding Ability in a Virtual Environment,” in Proceeding of the 2004 IEEE Intl. Conference on Robotics & Automation, pp. 3195–3200, 2004.
[14] T.Y. Li, M.Y. Liao, and P.C. Tao, 2005.05, “IMNET: An Experimental Testbed for Extensible Multi-user Virtual Environment Systems," in ICCSA 2005, pp. 957–966, Singapore.
[15] K. M. Lynch and M. T. Mason, “Stable pushing: Mechanics, controllability, and planning,” Int. Journal of Robotics Research, 15(6):533–556, 1996.
[16] J. Kuffner, “Goal-Directed Navigation for Animated Characters Using Real-time Path Planning and Control,” in Proceeding of CAPTECH’98 Workshop on Modeling and Motion Capture Techniques for Virtual Environments, Springer-Verlag, 1998.
[17] M.T. Mason. Mechanics of Robotic Manipulation. MIT Press, 2001.
[18] J. Schwartz, M. Sharir, “On the ‘piano movers’ problem II, General techniques for computing topological properties of real algebraic manifolds,” Advances in Applied Mathematics, 4:298--351, 1983.
[19] Z. Shiller, K. Yamane, and Y. Nakamura, “Planning Motion Patterns of Human Figures Using a Multi-Layered Grid and the Dynamics Filter” in Proceeding of 2001 IEEE Intl. Conf. on Robotics and Automation, pp.1-8, May 2001.
[20] S. Y. Shin and T. Kunii, ”Pseudo Dynamic Keyframe Animation with Motion Blending on the Configuration Space of a Moving Mechanism,” in Proceeding of Pacific Graphics, August 1995.
[21] M. Stilman and J. Kuffner, “Navigation Among Movable Obstacles: Real-time Reasoning in Complex Environments,” in Proceeding IEEE International Conference on Humanoid Robotics (Humanoids`04), 2004.
[22] H. C. Sun and N. M. Dimitris, “Automating Gait Generation,” in Proceedings of ACM SIGGRAPH, 2001.
[23] A. Witkin, and Z. Popovic, “Motion Warping,” in Proceedings of ACM SIGGRAPH, 1995.
[24] G. Wilfong, “Motion Planning in the Presence of Movable Obstacles,” in Proceeding ACM Symposium on Computational Geometry, pp. 279–288, 1988.
[25] S. K. Chung and J. K. Hahn, “Animation of Human Walking in Virtual Environments,” in Proceedings of Computer Animation Conference, 1999
描述 碩士
國立政治大學
資訊科學學系
93753037
95
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0093753037
資料類型 thesis
dc.contributor.advisor 李蔡彥zh_TW
dc.contributor.advisor Li,Tsai-Yenen_US
dc.contributor.author (Authors) 李岳澤zh_TW
dc.contributor.author (Authors) Li,Yueh-Tseen_US
dc.creator (作者) 李岳澤zh_TW
dc.creator (作者) Li,Yueh-Tseen_US
dc.date (日期) 2006en_US
dc.date.accessioned 17-Sep-2009 14:00:08 (UTC+8)-
dc.date.available 17-Sep-2009 14:00:08 (UTC+8)-
dc.date.issued (上傳時間) 17-Sep-2009 14:00:08 (UTC+8)-
dc.identifier (Other Identifiers) G0093753037en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/32665-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 93753037zh_TW
dc.description (描述) 95zh_TW
dc.description.abstract (摘要) 讓數位演員能夠在虛擬場景中自主的規劃路徑並且移動，一直是一個富有挑戰性的問題。近年來已有相當多與此相關的研究，數位演員已能夠在高低起伏的分層地形中做路徑的規劃。我們的目標是除了能處理更一般化的場景外，對於場景中障礙物的定義，也會隨著數位演員的能力而有所不同。本研究為數位演員所擴充的新的能力包含了翻越過障礙物的能力以及搬移障礙物的能力。在以往藉由搬移障礙物而抵達目的地的研究中，都是以先決定欲搬移障礙物的順序，再為數位演員以本身擁有的運動能力規劃出一條合理且無碰撞的路徑。而本研究的特色則是將搬移障礙物這項能力與數位演員其他的運動能力一併考量，將各種運動能力以一致的觀點來規劃數位演員的行走路徑。我們將以數個模擬的例子說明此運動計畫器的有效性。zh_TW
dc.description.abstract (摘要) Enabling a digital actor to move autonomously in a virtual environment is a challenging problem that has attracted much research attention in recent years. Many researches have been also to generate the motion of a digital actor in an uneven layered environment. In this thesis, we have extended our previous work to enable the digital actor to have the ability of jumping over a barrier and the ability of manipulating obstacles in order to make room for passing. Most previous work in generating manipulation plans for obstacles must first decide the order of manipulation and then manipulate obstacles in accordance with the sequence. In this thesis, we design a motion planner that can take all motion abilities of the digital actor into account in generating a collision-free path in a layered environment cluttered with various types of obstacles. This planer takes a unified view to consider all types of motions including manipulating objects that could change the system configuration. The experimental results will be demonstrated with several simulation examples to show the effectiveness of the systemen_US
dc.description.tableofcontents 第一章 導論 1
1.1. 簡介與研究動機 1
1.2. 研究目標 2
1.3. 論文貢獻 3
1.4. 本論文之章節架構 4
第二章 相關研究 5
2.1. 全域運動計畫(Gross motion planning) 5
2.2. 可移動物體(Movable object) 7
2.3. 角色動畫(Character animation) 9
第三章 問題描述 11
3.1. 整體問題描述 11
3.2. 場景定義 11
3.3. 數位演員定義 16
3.4. 可抵達區域 17
3.4.1 以數位演員的描述限制來定義可抵達區域 17
3.4.2 以數位演員的能力來定義可抵達區域 18
3.5. 不穩定區域 22
3.6. 搬動之運動能力 24
3.6.1 數位演員開始搬動障礙物的觸發點 25
3.6.2 搬動障礙物時的工作空間 26
第四章 一致化全域路徑規劃 28
4.1. 虛擬位能場 28
4.2. 一致化的計畫原則 29
4.3. 搬移障礙物 31
4.3.1 預估數位演員通過障礙物的路徑 32
4.3.2 依據路徑建立欲搬移障礙物的組態空間 33
4.3.3 運算實體 34
4.3.4 後製路徑的規劃 36
4.4. 數位演員的路徑規劃 36
第五章 實驗結果與討論 41
5.1. 實驗環境 41
5.2. 翻越障礙物的運動能力 42
5.3. 搬移障礙物問題的處理 44
5.3.1 連續搬移問題 44
5.3.2 在分層式場景中搬移 46
5.4. 一致化的路徑規劃 49
5.5. 討論 53
第六章 結論與未來發展 56
6.1. 結論 56
6.2. 未來發展 56
參考文獻 58		zh_TW
dc.format.extent 63768 bytes-
dc.format.extent 71973 bytes-
dc.format.extent 90415 bytes-
dc.format.extent 110270 bytes-
dc.format.extent 133776 bytes-
dc.format.extent 329212 bytes-
dc.format.extent 554213 bytes-
dc.format.extent 580077 bytes-
dc.format.extent 577383 bytes-
dc.format.extent 70921 bytes-
dc.format.extent 39955 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.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0093753037en_US
dc.subject (關鍵詞) 運動計畫zh_TW
dc.subject (關鍵詞) 數位演員zh_TW
dc.subject (關鍵詞) 電腦動畫zh_TW
dc.subject (關鍵詞) 搬移障礙物zh_TW
dc.title (題名) 以統一的觀點規劃自主式數位演員之多種運動能力zh_TW
dc.title (題名) A unified approach to the motion planning of an autonomous digital actor with multiple motion abilitiesen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] R. Alami, J.-P. Laumond, and T. Siméon. “Two manipulation planning algorithms,” in J.-P. Laumond and M. Overmars, editors, Algorithms for Robotic Motion and Manipulation. A.K. Peters, Wellesley, MA, 1997.zh_TW
dc.relation.reference (參考文獻) [2] 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.zh_TW
dc.relation.reference (參考文獻) [3] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Second Edition, Chapter 7: Voronoi Diagrams, 2000.zh_TW
dc.relation.reference (參考文獻) [4] A. Bruderlin and T. W. Calvert, “Goal-Directed, Dynamic Animation of Human Walking,” in Proceedings of ACM SIGGRAPH, 1989.zh_TW
dc.relation.reference (參考文獻) [5] P. C. Chen and Y. K. Hwang, “Practical path planning among movable obstacles,” in Proceedings of IEEE International Conference on Robotic Automation, pp.444-449, 1991.zh_TW
dc.relation.reference (參考文獻) [6] P. F. Chen and T. Y. Li, “Generating Humanoid Lower-Body Motions with Real-Time Planning,” in Proceeding of 2002 Computer Graphics Workshop, Taiwan, 2002.zh_TW
dc.relation.reference (參考文獻) [7] E. D. Demaine, M. L. Demaine, and J. O`Rourke, “PushPush and Push-1 are NP-hard in 2D,” in Proceedings of the 12th Annual Canadian Conference on Computational Geometry, pp. 211-219, August 2000.zh_TW
dc.relation.reference (參考文獻) [8] R. C. Gonzale and R. E. Woods, Digital Image Processing, Second Edition, Prentice Hall, pp.224-244, 1985.zh_TW
dc.relation.reference (參考文獻) [9] M. Lau and J. Kuffner, “Behavior Planning for Character Animation,” in Proceeding of ACM SIGGRAPH / Eurographics Symposium on Computer Animation, Los Angeles, CA, 2005.zh_TW
dc.relation.reference (參考文獻) [10] J. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991.zh_TW
dc.relation.reference (參考文獻) [11] T.Y. Li and P.Z. Huang, “Motion Planning for a Humanoid Walking in a 3D Space,” in Proceeding of the 2001 National Computer Symposium, Taipei, Taiwan, 2001.zh_TW
dc.relation.reference (參考文獻) [12] T.Y. Li, and P.Z. Huang, “Planning Humanoid Gross Motions on a Layered Scene,” in Proceeding of 2002 Computer Graphics Workshop, Taiwan, 2002.zh_TW
dc.relation.reference (參考文獻) [13] T.Y. Li and P.Z. Huang, “Planning Humanoid Motions with Striding Ability in a Virtual Environment,” in Proceeding of the 2004 IEEE Intl. Conference on Robotics & Automation, pp. 3195–3200, 2004.zh_TW
dc.relation.reference (參考文獻) [14] T.Y. Li, M.Y. Liao, and P.C. Tao, 2005.05, “IMNET: An Experimental Testbed for Extensible Multi-user Virtual Environment Systems," in ICCSA 2005, pp. 957–966, Singapore.zh_TW
dc.relation.reference (參考文獻) [15] K. M. Lynch and M. T. Mason, “Stable pushing: Mechanics, controllability, and planning,” Int. Journal of Robotics Research, 15(6):533–556, 1996.zh_TW
dc.relation.reference (參考文獻) [16] J. Kuffner, “Goal-Directed Navigation for Animated Characters Using Real-time Path Planning and Control,” in Proceeding of CAPTECH’98 Workshop on Modeling and Motion Capture Techniques for Virtual Environments, Springer-Verlag, 1998.zh_TW
dc.relation.reference (參考文獻) [17] M.T. Mason. Mechanics of Robotic Manipulation. MIT Press, 2001.zh_TW
dc.relation.reference (參考文獻) [18] J. Schwartz, M. Sharir, “On the ‘piano movers’ problem II, General techniques for computing topological properties of real algebraic manifolds,” Advances in Applied Mathematics, 4:298--351, 1983.zh_TW
dc.relation.reference (參考文獻) [19] Z. Shiller, K. Yamane, and Y. Nakamura, “Planning Motion Patterns of Human Figures Using a Multi-Layered Grid and the Dynamics Filter” in Proceeding of 2001 IEEE Intl. Conf. on Robotics and Automation, pp.1-8, May 2001.zh_TW
dc.relation.reference (參考文獻) [20] S. Y. Shin and T. Kunii, ”Pseudo Dynamic Keyframe Animation with Motion Blending on the Configuration Space of a Moving Mechanism,” in Proceeding of Pacific Graphics, August 1995.zh_TW
dc.relation.reference (參考文獻) [21] M. Stilman and J. Kuffner, “Navigation Among Movable Obstacles: Real-time Reasoning in Complex Environments,” in Proceeding IEEE International Conference on Humanoid Robotics (Humanoids`04), 2004.zh_TW
dc.relation.reference (參考文獻) [22] H. C. Sun and N. M. Dimitris, “Automating Gait Generation,” in Proceedings of ACM SIGGRAPH, 2001.zh_TW
dc.relation.reference (參考文獻) [23] A. Witkin, and Z. Popovic, “Motion Warping,” in Proceedings of ACM SIGGRAPH, 1995.zh_TW
dc.relation.reference (參考文獻) [24] G. Wilfong, “Motion Planning in the Presence of Movable Obstacles,” in Proceeding ACM Symposium on Computational Geometry, pp. 279–288, 1988.zh_TW
dc.relation.reference (參考文獻) [25] S. K. Chung and J. K. Hahn, “Animation of Human Walking in Virtual Environments,” in Proceedings of Computer Animation Conference, 1999zh_TW