[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Heuristic Algorithm for Robot Path Planning Based on Real Space Renormalization

  • Conference paper
Advances in Artificial Intelligence (IBERAMIA 2000, SBIA 2000)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1952))

Abstract

The development of a path planning algorithm based on an approximate cell decomposition of the workspace is presented. The free space of the robot is recursively decomposed into a set of non-overlapping cells through a real space renormalization procedure. The algorithm includes a previously calculated data base of heuristics defining the optimal paths that cross a cell between any two predefined edge points. The first step of the algorithm consists on the computation of a straight path from the initial configuration to the goal position. This initial proposed path is further recursively corrected in the following steps until a definitive path is obtained. The recursive process is stopped when the complete path lies on a free collision space or the size of the cell reaches some predefined value of resolution. The algorithm of path planning was experimentally tested on a workspace cluttered with thirty randomly distributed obstacles. In each case, with very little computational effort a good free collision path is calculated. The results indicate that the proposed path planning algorithm is very suitable for real time applications.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Amato, N. and Wu, Y. (1996). “A Randomized Roadmap for Path Manipulation Planning”. IEEE, International Conference on Robotics and Automation: 113–12

    Google Scholar 

  2. Barraquand, J. and Latombe, J.C. (1990). “A Monte Carlo Algorithm for Path Planning with Many Degrees of Freedom”. IEEE, International Conference on Robotics and Automation: 1712–1717

    Google Scholar 

  3. Barraquand, J., Langlois, B. and Latombe, J. C. (1992). “Numerical Potential Field Techniques for Robot Path Planning”. IEEE, Transactions on System, Man and Cybernetics. 22(2): 224–241

    Article  MathSciNet  Google Scholar 

  4. Behring, C. (1999). “Robot Motion Planning with Cellular Automata”. Thesis. University of Dortmund, Dortmund, Germany

    Google Scholar 

  5. Brooks, R.A. and Lozano Pérez, T. (1985). “A Subdivision Algorithm in Configuration Space for Findpath with Rotation”. IEEE, Transactions on System, Man and Cybernetics, 15(2): 224–233

    Article  Google Scholar 

  6. Hwang, Y. and Ahuja, N. (1992). “A Potential Field Approach to Path Planning”. tiIEEE, Transactions on Robotics and Automation, 8(1)

    Google Scholar 

  7. Kavraki, L. E. and Latombe, J. C. (1994). “Randomized Preprocessing of Configurations Space for Path Planning”. IEEE International Conference on Robotics and Automation: 2138–2139

    Google Scholar 

  8. Lozano Pérez, T. (1979). “An Algorithm for Planning Collision Free Path among Polyhedral Obstacles”. Communication of the ACM, 22(10): 560–70

    Article  Google Scholar 

  9. Lozano Pérez, T. (1983). “Spatial Planning: A Configuration Space Approach”. IEEE Transactions on Computers, C-32(2): 108–120

    Article  MathSciNet  Google Scholar 

  10. Lozano Pérez, T., Mason, M. T., and Taylor, R. H. (1984). “Automatic Synthesis of Fine Motion Strategies for Robots”. International Journal of Robotics Research, 3(1): 3–24

    Article  Google Scholar 

  11. Latombe, J. C. (1991). “Robot Motion Planning”. Kluwer Academic Publishers, Boston, MA

    Book  Google Scholar 

  12. LaValle, S. M. (1995). “Robot Motion Planning: A Game Theoretic Foundation”. PhD thesis, University of Illinois. http://www.janowiec.cs.iastate.edu/lavalle/ Iowa State University

  13. LaValle, S. M., González Baños, H. H., Becker, C., and Latombe, J.C..(1997). “Motion Strategies for Maintaining Visibility of a Moving Target”. IEEE International Conference on Robotics and Automation, 731–736

    Google Scholar 

  14. Yoshiyuki, U. and Yoshiki, K. (1995) “New Method of Solving the Travelling Salesman Problem Based on Real Space Renormalization Theory”, Physical Review Letters 75: 1683–1686

    Article  Google Scholar 

  15. Zhu, D. and Latombe, J. C. (1991). “New Heuristic Algorithms for Effcient Hierarchical Path Planning”. Transactions on Robotics and Automation. A(7): 9–20

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Unidad de Investigación en Inteligencia Artificial, Decanato de Ciencias. Universidad Centroccidental Lisandro Alvarado, Barquisimeto, Venezuela

    Maritza Bracho de Rodríguez

  2. Laboratorio de Computación Emergente, Facultades de Ciencias e Ingeniería, Universidad Central de Venezuela, Caracas, Venezuela

    José Ali Moreno

Authors
  1. Maritza Bracho de Rodríguez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José Ali Moreno
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Statistics Computational Intelligence Laboratory, University of São Paulo, Avenida Trabalhador Sãocarlense 400, 13566-590, São Carlos, Brazil

    Maria Carolina Monard

  2. Computer Engineering Department Intelligent Techniques Laboratory, University of São Paulo, Av. Prof. Luciano Gualberto, 158, tv. 3, 05508-900, São Paulo, Brazil

    Jaime Simão Sichman

Rights and permissions

Reprints and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

de Rodríguez, M.B., Moreno, J.A. (2000). Heuristic Algorithm for Robot Path Planning Based on Real Space Renormalization. In: Monard, M.C., Sichman, J.S. (eds) Advances in Artificial Intelligence. IBERAMIA SBIA 2000 2000. Lecture Notes in Computer Science(), vol 1952. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44399-1_39

Download citation

  • DOI: https://doi.org/10.1007/3-540-44399-1_39

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-41276-2

  • Online ISBN: 978-3-540-44399-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation