Top > JRM > Memory Efficient Real-Time Motion Planning by Dual-Resolution ...

single-rb.php

JRM Vol.19 No.1 pp. 114-123
doi: 10.20965/jrm.2007.p0114
(2007)

Paper:

Views over last 60 days: 464

Memory Efficient Real-Time Motion Planning by Dual-Resolution Heuristic Search

Ralf Gomm and Sabri Cetinkunt

Department of Mechanical and Industrial Engineering, University of Illinois at Chicago, Chicago, IL 60607, USA

Received:
August 22, 2006
Accepted:
November 7, 2006
Published:
February 20, 2007
Creative Commons License
Keywords:
sampling based planner, heuristic guided A* search, mobile equipment, construction machinery
Abstract
Memory efficient path planning is achieved in real-time for a linkage mechanism with five degrees of freedom (DOF) as found in mobile construction machinery. Collision-free end-effector positions are obtained in an off-line preprocessing phase utilizing deterministic dual-resolution sampling. Moving obstacles are decoupled for complexity and memory reduction. Solutions to particular path planning problems are computed during an on-line phase by heuristic driven A* search. To enable path planning on current and future anticipated embedded computer resources of construction machinery, the search strategy is optimized by designing the behavior of heuristic functions specifically for our problem space. The performance of the heuristic guided method is evaluated and compared to other non-heuristic and heuristic searches.
Cite this article as:
R. Gomm and S. Cetinkunt, “Memory Efficient Real-Time Motion Planning by Dual-Resolution Heuristic Search,” J. Robot. Mechatron., Vol.19 No.1, pp. 114-123, 2007.
Data files:
References
  1. [1] R. Gomm, S. Cetinkunt, I. Gharsalli, V. Bhaskar, and Y. Zhu, “Method for Automatically Planning a Collision Free Motion Path of the Blade Mechanism of a Motor Grader,” 2006, U.S. Patent Application under review.
  2. [2] J. C. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, 1991.
  3. [3] T. Lozano-Perez, “A Simple Motion-Planning Algorithm for General Robot Manipulators,” IEEE Journal of Robotics and Automation, Vol.RA-3, No.3, 1987.
  4. [4] T. Lozano-Perez and M. A. Wesley, “An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles,” Communications of the ACM, Vol.22, No.10, pp. 560-570, 1979.
  5. [5] J. T. Schwartz and M. Sharir, “On the Piano Movers’ Problem II. General Techniques for Computing Topological Properties of Real Algebraic Manifolds,” Advances in applied Mathematics, Academic Press, Vol.4, pp. 298-351, 1983.
  6. [6] E. Rimon and D. E. Kodischeck, “Exact Robot Navigation using Artificial Potential Functions,” IEEE Transaction on Robotics and Automation, Vol.8, pp. 501-518, 1992.
  7. [7] D. E. Kodischek, “Exact Robot Navigation by Means of Potential Functions: Some Topological Considerations,” Proceedings of the IEEE International Conference on Robotics and Automation, Raleigh, NC, 1987.
  8. [8] N. J. Nilsson, “A Mobile Automaton: An Application of Artificial Intelligence Techniques,” Proceedings of the 1st International Joint Conference on Artificial Intelligence, pp. 509-520, 1969.
  9. [9] C. O’Dúnlaing, M. Sharir, and C. K. Yap, “Retraction: A New Approach to Motion-Planning,” ACM Symposium on Theory of Computing, pp. 207-220, 1983.
  10. [10] R. A. Brooks, “Solving the Find-Path Problem by Good Representation of Free Space,” IEEE Transaction on Systems, Man and Cybernetics, pp. 190-197, 1983.
  11. [11] J. F. Canny, “The Complexity of Robot Motion Planning,” MIT Press, Cambridge, MA, 1988.
  12. [12] J. Barraquand and J.-C. Latombe, “Robot Motion Planning: A Distributed Representation Approach,” STAN-CS-89-1257, Department of Computer Science, Stanford University Stanford, CA, 1989.
  13. [13] R. Chatila, “Path Planning and Environmental Learning in a Mobile Robot System,” Proceedings of the European Conference on Artificial Intelligence, Osray, France, 1982.
  14. [14] L. Gouzenes, “Strategies for Solving Collision-Free Trajectories Problems for Mobile and Manipulator Robots,” International Journal of Robotics Research, pp. 51-65, 1984.
  15. [15] F. Aurenhammer, “Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, pp. 345-405, 1991.
  16. [16] L. E. Kavraki, P. Švestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces,” IEEE Transactions on Robotics and Automation, Vol.12, No.4, 1996.
  17. [17] L. E. Kavraki, M. N. Kolountzakis, and J.-C. Latombe, “Analysis of Probabilistic Roadmaps for Path Planning,” IEEE Transaction on Robotics and Automation, Vol.14, pp. 166-171, 1998.
  18. [18] J. Barraquand, L. E. Kavraki, J.-C. Latombe, R. Motwani, T. Y. Li, and P. Raghavan, “A Random Scheme for Path Planning,” Proc. Int. Symp. on Robotics Research, pp. 249-264, 1996.
  19. [19] S. M. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Computer Science Department, Iowa State University, 1998.
    http://msl.cs.uiuc.edu/rrt/papers/Lav98c.ps.gz
  20. [20] J. J. Kuffner and S. M. LaValle, “RRT-Connect: An efficient Approach to Single-Query Path Planning,” Proceedings of the 2000 IEEE Transaction on Robotics and Automation, San Francisco, CA, 2000.
  21. [21] P. C. Chen and Y. K. Hwang, “SANDROS: A Motion Planner with Performance Proportional to Task Difficulty,” IEEE International Conference on Robotics and Automation, pp. 2346-2353, 1992.
  22. [22] P. C. Chen and Y. K. Hwang, “SANDROS: A Dynamic Graph Search Algorithm for Motion Planning,” IEEE Transactions on Robotics and Automation, Vol.14, No.3, 1998.
  23. [23] K. Kondo, “Motion Planning with Six Degrees of Freedom by Multistrategic Bidirectional Heuristic Free-Space Enumeration,” IEEE Transaction on Robotics and Automation, pp. 267-277, 1991.
  24. [24] F. Lingelbach, “Path Planning using Probabilistic Cell Decomposition,” Proceedings of the 2004 IEEE International Conference on Robotics and Automation, New Orleans, LA, 2004.
  25. [25] S. Kambhampati and L. S. Davis, “Multiresolution Path Planning for Mobile Robots,” IEEE Journal of Robotics and Automation, Vol.RA-2, No.3, 1986.
  26. [26] B. Glavina, “Solving findpath by combination of goal-directed and randomized search,” IEEE International Conference on Robotics and Automation, pp. 1718-1723, 1990.
  27. [27] O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robot,” International Journal of Robotic Research, Vol.5, No.1, p. 60, 1986.
  28. [28] P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems, Science and Cybernetics SSC4(2), pp. 100-107, 1968.
  29. [29] R. Dechter and J. Pearl, “Generalized best-first search strategies and the optimality of A*,” Journal of the ACM, Vol.32, No.3, pp. 505-536, 1985.

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

Copyright© 2007 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 Apr. 22, 2024