Top > JRM > Rapid Short-Time Path Planning for Phase Space

single-rb.php

JRM Vol.23 No.2 pp. 271-280
doi: 10.20965/jrm.2011.p0271
(2011)

Paper:

Views over last 60 days: 631

Rapid Short-Time Path Planning for Phase Space

Chyon Hae Kim*, Hiroshi Tsujino*, and Shigeki Sugano**

*Honda Research Institute Japan Co., Ltd., 8-1 Honcho, Wako-shi, Saitama 351-0188, Japan

**Department of Mechanical Engineering, Waseda University, 3-4-1 Okubo, Shinjuku-ku, Tokyo 169-8555, Japan

Received:
September 30, 2010
Accepted:
February 7, 2011
Published:
April 20, 2011
Creative Commons License
Keywords:
motion planning, optimization, short time motion, phase space, search tree
Abstract
This paper addresses optimal motion for general machines. Approximation for optimal motion requires a global path planning algorithm that precisely calculates the whole dynamics of a machine in a brief calculation. We propose a path planning algorithm that consists of path searching and pruning algorithms. The pruning algorithmis based on our analysis of state resemblance in general phase space. To confirm precision, calculation cost, optimality and applicability of the proposed algorithm, we conducted several shortest time path planning experiments for the dynamic models of double inverted pendulums. Precision to reach the goal states of the pendulums was better than other algorithms. Calculation cost was 58 times faster at least. We could tune optimality of proposed algorithm via resolution parameters. A positive correlation between optimality and resolutions was confirmed. Applicability was confirmed in a torque based position and velocity feedback control simulation. As a result of this simulation, the double inverted pendulums tracked planned motion under noise while keeping within torque limitations.
Cite this article as:
C. Kim, H. Tsujino, and S. Sugano, “Rapid Short-Time Path Planning for Phase Space,” J. Robot. Mechatron., Vol.23 No.2, pp. 271-280, 2011.
Data files:
References
  1. [1] J. E. Bobrow, S. Dubowsky, and J. S. Gibson, “Time-optimal control of robotic manipulators along specified paths,” The Int. J. of Robotics Research, Vol.4, No.3, pp. 3-17, 1985.
  2. [2] J. E. Bobrow, “Optimal robot path planning using the minimumtime criterion,” IEEE Trans. on Robotics and Automation, Vol.4, No.4, pp. 443-450, 1988.
  3. [3] K. G. Shin and N. D. McKa, “Minimum-time control of robotic manipulators with geometric path constraints,” IEEE Trans. on Automatic Control, Vol.30, No.5, pp. 531-541, 1985.
  4. [4] K. G. Shin and N. D. McKay, “A dynamic programming approach to trajectory planning of robotic manipulators,” IEEE Trans. on Automatic Control, Vol.31, No.6, pp. 491-500, 1986.
  5. [5] D. Verscheure, B. Demeulenaere, J. Swevers, J. D. Schutter, and M. Diehl, “Time-Energy Optimal Path Tracking for Robots: a Numerically Efficient Optimization Approach,” IEEE Int. Workshop on Advanced Motion Control (AMC), 2008.
  6. [6] Y. Suzuki, S. Thompson, and S. Kagami, “High-Speed Planning and Reducing Memory Usage of a Precomputed Search Tree Using Pruning,” IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2009.
  7. [7] A. Eele and A. Richards, “Rapid Updating for Path-Planning using Nonlinear Branch-and-Bound,” IEEE Int. Conf. on Robotics and Automation (ICRA), 2010.
  8. [8] S. M. LaValle and J. J. Kuffner, Jr., “Rapidly-Exploring Random Trees: Progress and Prospects,” Algorithmic and Computational Robotics: New Directions, pp. 293-308, 2001.
  9. [9] L. E. Kavraki, P. Svestka, J. Latombe, and M. H. Overmars, “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces,” IEEE Trans. on Robotics and Automation, Vol.12, No.4, 1996.
  10. [10] E. Yoshida, C. Esteves, I. Belousov, J. Laumond, T. Sakaguchi, and K. Yokoi, “Planning 3-D Collision-Free Dynamic Robotic Motion Through Iterative Reshaping,” IEEE Trans. on Robotics, Vol.24, No.5, 2008.
  11. [11] Z. Shiller, “On Computing the Global Time-Optimal Motions of Robotics Manipulators in the Presence of Obstacles,” IEEE Trans. on Robotics and Automation, Vol.7, No.6, 1991.
  12. [12] G. Sahar and J. M. Hollerbach, “Planning of Minimum-Time Trajectories for Robot Arms,” In Proc. of IEEE Int. Conf. on Robotics and Automation (ICRA), 1985.
  13. [13] J. Phillips, N. Bedrossian, and L. E. Kavraki, “Guided Expansive Spaces Trees: A Search Strategy for Motion- and Cost-Constrained State Spaces,” Proc. of IEEE Int. Conf. on Robotics and Automation, 2004.
  14. [14] B. Donald, P. Xavier, J. Canny, and J. Reif, “Kinodynamic Motion Planning,” J. of the ACM (JACM), Vol.40, pp. 1048-1066, 1993.
  15. [15] P. S. Huang, “Planning For Dynamic Motions Using a Search Tree,” Graduate Thesis at Toronto University, 1996.
  16. [16] S. M. LaValle and J. J. Kuffner, Jr., “Randomized Kinodynamic Planning,” J. of Robotics Research, Vol.20, No.5, pp. 378-400, 2001.
  17. [17] H. Ritter and K. Schulten, “Planning a Dynamic Trajectory via Path Finding in Discretized Phase Space,” Lecture Notes in Computer Science, 1987.
  18. [18] Y. Tazaki and J. Imura, “Graph-based Model Predictive Control of a Planar Bipedal Robot,” Int. Symposium on Mathematical Theory of Networks and Systems, pp. 128-133, 2006.
  19. [19] Y. Tazaki and J. Imura, “Approximately Bisimilar Discrete Abstractions of Nonlinear Systems Using Variable-resolution Quantizers,” Proc. of American Control Conf., 2010.
  20. [20] D. J. Block, “Mechanical Design and Control of the Pendubot,” thesis of University of Illinois, 1991.
  21. [21] I. Fantoni, R. Lozano, and M. W. Spong, “Energy Based Control of the Pendubot,” IEEE Trans. of Automatic Control, Vol.45, No.4, 2000.
  22. [22] R. M. Murray and J. Hauser, “Nonlinear controllers for nonintegrable systems: The Acrobot example,” In Proc. of the American Control Conf., Vol.1, pp. 669-671, 1990.
  23. [23] M. W. Spong, “The Swing Up Control problem For The Acrobot,” IEEE Control System Magazine, Vol.15, No.1, pp. 45-55, 1995.
  24. [24] G. Boone, “Minimum Time Control of the Acrobot,” Proc. of the IEEE Int. Conf. on Robotics and Automation, pp. 3281-3287, 1997.
  25. [25] M. Nishimura, J. Yoshimoto, and S. Ishii, “Acrobot Control by Learning the Switching ofMultiple Controllers,” J. of Artificial Life and Robotics, Vol.9, No.2, pp. 67-71, 2005.
  26. [26] R. Haschke, E. Weitnauer, and H. Riter, “On-Line Planning of Time-Optimal, Jerk-Limited Trajectories,” Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2008.
  27. [27] J. Barraquand and J. Latombe, “Nonholonomic Multibody Mobile Robots: Controllability and Motion Planning in the Presence of Obstacles,” Proc. of IEEE Int. Conf. on Robotics and Automation (ICRA), 1991.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

Copyright© 2011 by Fuji Technology Press Ltd. and Japan Society of Mechanical Engineers. All right reserved.

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

Last updated on Dec. 06, 2024