Published
Collision-free path planning in multi-dimensional environments
Métodos para generar trayectorias libres de colisiones en entornos multidimensionales
DOI:
https://doi.org/10.15446/ing.investig.v31n2.23458Keywords:
robotics, path planning, obstacle avoidance. (en)robótica, generación de trayectorias, evasión de obstáculos, sistemas multidimensionales (es)
Downloads
Reliable path-planning and generation of collision-free trajectories has become an area of active research over the past decade where the field robotics has probably been the most active area. This paper' s main objective is to analyse the advantages and disadvantages of two of the most popular techniques used in collision-free trajectory generation in n-dimensional spaces. The importance of analysing such techniques within a generalised framework is evident as path-planning is used in a variety of fields such as designing medical drugs, computer animation and artificial intelligence and, of course, robotics. The review provided in this paper starts by drawing a historical map of path-planning and the techniques used in its early stages. The main concepts involved in artificial potential fields and probabilistic roadmaps will be addressed as these are the most influential methods and have been widely used in specialised literature.
Planear los movimientos de un robot de forma fiable sin que colisione con su entorno se ha convertido en un problema relevante en la última década. La idea central de este artículo es exponer dos de los principales métodos que permiten generar trayectorias libres de colisiones en cualquier espacio n-dimensional. La importancia de conocer estas estrategias radica en que estos mismos algoritmos se han aplicado en áreas distintas a la robótica, como diseño de medicamentos, animación computarizada e inteligencia artificial. También presentamos un referente histórico de varios métodos de generación de trayectorias y mostramos mediante simulaciones cómo las estrategias de los campos potenciales artificiales y de los mapas probabilísticos funcionan, siendo los más apropiados en virtud de los aspectos teóricos expresados en otros textos especializados.
References
Angeles, J., Fundamentals of robotic mechanical systems: theory, methods, and algorithms., New York, Berlin: Springer, 2007.
Brandt, D., Comparison of A* and RRT-Connect Motion Planning Techniques for Self-Reconfiguration Planning., Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on, Vol., Oct. 2006, pp.892-897.
Bresina, J.L., Jónsson, A.K., Morris, P.H., Rajan, K., Activity planning for the mars exploration rovers., 15th International Conference on Automated Planning and Scheduling, 2005, pp. 40-49.
Carsten, J., Rankin A., Ferguson D., Stentz A., Global planning on the Mars Exploration Rovers: Software integration and surface testing., J. Field Robot., Vol. 26, No. 4, 2009, pp. 337-357.
Choset, H., Lynch, K., Hutchinson, S., kantor, G., Bur-gard, W., Kavraki, L., Thrun, S., Principles of robot motion: theory, algorithms, and implementation., Cambridge, Mass.: MIT Press, 2005.
Cortes, J., Jaillet, L., Simeon, T., Disassembly Path Planning for Complex Articulated Objects., Robotics, IEEE Transactions on, Vol.24, No.2, April 2008a, pp.475- 481.
Cortes, J., Jaillet, L., Simeon, T., Transition-based RRT for path planning in continuous cost spaces., Intelligent Robots and Systems, 2008, IROS 2008. IEEE/RSJ International Conference on, 22-26 Sept. 2008b, pp.2145- 2150.
Craig, J., Introduction to Robotics: Mechanics and Control., Addison-Wesley, 1989.
Funge, J.D., Artificial intelligence for computer games: an introduction., Wellesley, Mass.: Peters, 2004.
Goldberg, K., Planar Robot Simulator with Obstacle Avoidance Configuration Space)., Disponible en: http://ford.ieor.berkeley.edu/cspace/.
Goldman, A., Path planning problems and solutions., in Book Path planning problems and solutions, Series Path planning problems and solutions, Vol.1, 1994, pp. 105-108.
Goo Bong, C., Soo Gang, L., Sungmin, K., Byung-Ju, Y., Whee-Kuk, K., Se Min, O., Young Soo, K., Jong, I.I.P., Seong Hoon, O., A robot-assisted surgery system for spinal fusion., in Book A robot-assisted surgery system for spinal fusion, Series A robot-assisted surgery system for spinal fusion, 2005, pp. 3015-3021.
Hsu, D., Randomized single-query motion planning in expansive spaces., PhD thesis, Department of Computer Science, Stanford University, 2000, Automation Science and Engineering, 2008. CASE 2008, IEEE International Conference on, Aug. 2008, pp.41-46, 23-26.
Jijie, X., Duindam, V., Alterovitz, R., Goldberg, K., Motion planning for steerable needles in 3D environments with obstacles using rapidly-exploring Random Trees and backchaining., Automation Science and Engineering, 2008, CASE 2008, IEEE International Conference on, Aug. 2008, pp.41-46, 23-26.
Kavraki, L., Svestka, P., Latombe, J.C., Overmars, M.H., Probabilistic roadmaps for path planning in high-dimensional configuration spaces., Robotics and Automation, IEEE Transactions on, Vol. 12, No. 4, 1996, pp. 566-580.
Khatib, O., Real-time obstacle avoidance for manipulators and mobile robots,. in Book Real-time obstacle avoidance for manipulators and mobile robots, Vol. 2, 1985, pp. 505, 500-505.
Kirillova, S., Cortes, J., Stefaniu, A., Simeon, T., An NMA-guided path planning approach for computing large-amplitude conformational changes in proteins., Proteins, Vol. 70, No. 1, 2008, p. 131.
Kuffner, J.J., Goal-Directed Navigation for Animated Characters Using Real-Time Path Planning and Control., Lecture notes in computer science., No. 1537, 1998, p. 171.
Kuffner, J. J., LaValle, S. M., RRT-connect: An efficient approach to single-query path planning., Robotics and Automation, 2000. Proceedings. ICRA’00. IEEE International Conference on, Vol.2, 2000, pp.995-1001.
Kuwata, Y., Fiore, G.A., Teo, J., Frazzoli, E., How, J.P., Motion planning for urban driving using RRT., Intelligent Robots and Systems, 2008. IROS 2008. IEEE/RSJ International Conference on, 22-26 Sept. 2008, pp.1681-1686.
Kwangjin, Y. and Sukkarieh, S., 3D smooth path planning for a UAV in cluttered natural environments., Intelligent Robots and Systems, 2008. IROS 2008. IEEE/RSJ International Conference on, Sept. 2008a, pp.794-800, 22-26.
Kwangjin, Y., Sukkarieh, S., Real-time continuous curvature path planning of UAVS in cluttered environments., Mechatronics and Its Applications, 2008. ISMA 2008, 5th International Symposium on, May 2008b, pp.1-6, 27-29.
Latombe, J.-C., Robot motion planning., Boston, MA: Kluwer Academic Publishers, 1991.
LaValle, S. M., Planning algorithms, Cambridge; New York: Cambridge University Press, 2006.
LaValle, S. M., Kuffner, J. J., Randomized kinodynamic planning., Robotics and Automation, 1999, Proceedings, IEEE International Conference on, Vol.1, 1999, pp.473-479.
LaValle, S. M., Kuffner, J. J., Rapidly-exploring random trees: Progress and prospects., In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions, A K Peters, Wellesley, MA, 2001, pp. 293 -308.
Lozano-Pérez, T., Automatic planning of manipulator transfer movements., IEEE Trans. Systems, Man, and Cybernetics SMC-11, No. 110, 1981, pp. 681-689- 681-689.
Maio, D., Rizzi, S., CICERO: An Assistant for Planning Visits to a Museum., Lecture notes in computer science, No. 978, 1995, pp. 564, 1995.
Sim, C., Wan Sing, N., Ming Yeong, T., Yong-Chong, L., Tseng Tsai, Y., Image-guided manipulator compliant surgical planning methodology for robotic skull-base surgery., in Book Image-guided manipulator compliant surgical planning methodology for robotic skull-base surgery, Series Image guided manipulator compliant surgical planning methodology for robotic skull-base surgery, pp. 26-29, 2001.
Spong, M., Hutchinson, S., Vidyasagar, M., Robot modeling and control., Hoboken, NJ: John Wiley & Sons, 2006.
Wenhu, Q., Xiaomei, L., Zhengxu Z., Study on Action Control of Virtual Actors., in Book Study on Action Control of Virtual Actors, Series Study on Action Control of Virtual Actors, 2007, pp. 907-912.
Yershova, A., Jaillet, L., Simeon, T., LaValle, S. M., Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain., Robotics and Automation ICRA 2005, Proceedings of the 2005 IEEE International Conference, 18-22 April 2005, pp. 3856-3861.
Dimensions
PlumX
Article abstract page views
Downloads
How to Cite
License
Copyright (c) 2011 Edwin Francis Cárdenas, Luis Miguel Mendez, Jorge Sofrony Esmeral
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:
1. The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;
2. The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;
3. The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;
4. The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.
