JACIII Vol.12 No.3 pp. 277-283
doi: 10.20965/jaciii.2008.p0277


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

April 17, 2007
September 22, 2007
May 20, 2008
unified planning, motion planning, autonomous digital actor, leaping and pushing motions

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.

Cite this article as:
Yueh-Tse Li and Tsai-Yen Li, “A Unified Approach to Planning Versatile Motions for an Autonomous Digital Actor,” J. Adv. Comput. Intell. Intell. Inform., Vol.12, No.3, pp. 277-283, 2008.
Data files:
  1. [1] 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.
  2. [2] 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.
  3. [3] 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.
  4. [4] 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.
  5. [5] 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.
  6. [6] 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.
  7. [7] J. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, 1991.
  8. [8] 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.
  9. [9] 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.
  10. [10] 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.
  11. [11] G. Wilfong, “Motion Planning in the Presence of Movable Obstacles,” Proc. of ACM Symp. Computational Geometry, pp. 279-288, 1988.
  12. [12] K. M. Lynch and M. T. Mason, “Stable pushing: Mechanics, controllability, and planning,” Int. Journal of Robotics Research, 15-6, pp. 533-556, 1996.
  13. [13] R. C. Gonzale and R. E. Woods, “Digital Image Processing,” Second Edition, Prentice Hall, pp. 224-244, 1985.
  14. [14] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, “Computational Geometry: Algorithms and Applications,” Second Edition, Chapter 7: Voronoi Diagrams, 2000.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Feb. 25, 2021