A Unified Approach to Planning Versatile Motions for an Autonomous Digital Actor
Yueh-Tse Li and Tsai-Yen Li
Computer Science Department, National Chengchi University, 64, Sec. 2, Zhi-Nan Rd. Taipei, Taiwan 116
Enabling a digital actor to move autonomously in a virtual environment is a challenging problem that has attracted much attention in recent years. The systems proposed in several researches have been able to plan the walking motions of a humanoid on an uneven terrain. In this paper, we aim to design a planning system that can generate various types of motions for a humanoid with a unified planning approach. Based on our previous work, we add two additional motion abilities: leaping and moving obstacles into the system. In previous work, the order of moving obstacles is determined first, and then the corresponding paths for the pushing/pulling motions are generated. In this work, we take a unified approach that accounts for all types of motions at the same time. We have implemented a planning system with this unified approach for a humanoid moving in a layered virtual environment. Several simulation examples are demonstrated in this paper to illustrate the effectiveness of the system.
-  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.
-  Z. Shiller, K. Yamane, and Y. Nakamura, “Planning Motion Patterns of Human Figures Using a Multi-Layered Grid and the Dynamics Filter,” Proc. of 2001 IEEE Int. Conf. on Robotics and Automation, pp. 1-8, 2001.
-  T. Y. Li and P. Z. Huang, “Planning Humanoid Motions with Striding Ability in a Virtual Environment,” Proc. of the 2004 IEEE Int. Conf. on Robotics & Automation, pp. 3195-3200, 2004.
-  E. D. Demaine, M. L. Demaine, and J. O’Rourke, “PushPush and Push-1 are NP-hard in 2D,” Proc. of the 12th Annual Canadian Conf. on Computational Geometry, pp. 211-219, 2000.
-  M. Stilman and J. Kuffner, “Navigation Among Movable Obstacles: Real-time Reasoning in Complex Environments,” Proc. IEEE Int. Conf. on Humanoid Robotics (Humanoids’04), 2004.
-  J. Schwartz and M. Sharir, “On the ‘piano movers’ problem II, General techniques for computing topological properties of real algebraic manifolds,” Advances in Applied Mathematics, 4, pp. 298-351, 1983.
-  J. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, 1991.
-  J. Barraquand, L. Kavraki, J. C. Latombe T. Y. Li, and P. Raghavan, “A Random Sampling Scheme for Path Planning,” Int. J. of Robotics Research, 16-6, pp. 759-774, 1997.
-  T. Y. Li, P. F. Chen, and P. Z. Huang, “Motion Planning for Humanoid Walking in a Layered Environment,” Proc. of the 2003 Int. Conf. on Robotics and Automation, 2003.
-  P. C. Chen and Y. K. Hwang, “Practical path planning among movable obstacles,” Proc. of IEEE Int. Conf. on Robotic Automation, pp. 444-449, 1991.
-  G. Wilfong, “Motion Planning in the Presence of Movable Obstacles,” Proc. of ACM Symp. Computational Geometry, pp. 279-288, 1988.
-  K. M. Lynch and M. T. Mason, “Stable pushing: Mechanics, controllability, and planning,” Int. Journal of Robotics Research, 15-6, pp. 533-556, 1996.
-  R. C. Gonzale and R. E. Woods, “Digital Image Processing,” Second Edition, Prentice Hall, pp. 224-244, 1985.
-  M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, “Computational Geometry: Algorithms and Applications,” Second Edition, Chapter 7: Voronoi Diagrams, 2000.