CLASSICAL METHODS OF PATH PLANNING FOR MOBILE ROBOTS
DOI:
https://doi.org/10.26906/SUNZ.2019.3.143Keywords:
MAR, robot, autonomy, path search, motion planningAbstract
Mobile autonomous robots (MAR) are used to perform a large number of diverse tasks in various industries, such as mining, search and rescue, military, etc. Separately allocated category of MAR, which is used in enclosed spaces. This is due to the additional technical and software limitations that are imposed on the MAR and the operator. The problem of moving robots from point A to point B is a basic problem that applies to all robots, but when used in underground structures, the solution to this problem is complicated by the presence of additional factors such as lack of communication with the operator and the inability to use GPS systems. This article discusses 35 classic methods of pathfinding for MAR and methods for optimizing them. Classical methods find solutions to the problem of finding a way, or prove that it does not exist, without finding a compromise between the quality of the path and the amount of time / resources required to find it. Classical methods include the following categories of methods: methods of cell decomposition; methods of the artificial potential field; selective methods; methods that use a subgoal network. The article also discusses the main problems encountered during the execution of the pathfinding task. Methods were analyzed for the following characteristics: restrictions; planning mode; the metric used to plan the next step. The limitations on a system for which the method may be used are either holonomic or non-holonomic. Holonomic restrictions can be applied to systems where motion is described only through coordinates and time, without taking into account speeds and accelerations, which makes them ideal for theoretical calculations.The planning mode shows whether this method can be used for planning on-the-go (online) or before it starts (offline). Even methods that are in the same category may vary significantly depending on which mode they were designed for. Under the metrics of path search algorithms, we mean methods for obtaining a better solution for the current step of the algorithm, or for the algorithm in general.Downloads
References
Causes of Coal Mine Accidents in the World and Turkey/ Küçük, F., and Ilgaz, A. // Turkish thoracic journal – Vol. 16. – P. 9–14. – 2015. https://doi.org/10.5152/ttd.2015.003
An affordable, robust mining inspection robot / CD. A. Carnegie, J. McVay, L. Molyneaux and C. Chitty // 2015 IEEE 7th International Conference on Cybernetics and Intelligent Systems (CIS) and IEEE Conference on Robotics, Automation and Mechatronics (RAM) – P. 143-148 – 2015. https://doi.org/10.1109/ICCIS.2015.7274611
Mobile robots in mine rescue and recovery/ R. R. Murphy, J. Kravitz, S. L. Stover and R. Shoureshi // IEEE Robotics & Automation Magazine – Vol. 16. – No. 2. – P. 91-103. – 2009. https://doi:10.1109/MRA.2009.932521
Gross motion planning—a survey/ Yong K. Hwang and Narendra Ahuja // ACM Computing Surveys (CSUR) – Vol. 24. – No. 3. – P. 219-291 – 1992. https://doi.org/10.1145/136035.136037
Robot Motion Planning: A Distributed Representation AProach /Barraquand Jerome and Latombe Jean-Claude // International Journal of Robotic Research - IJRR – Vol. 10. – P. 628-649. – 1991. https://doi.org/10.1177/027836499101000604
Coverage of Known Spaces: The Boustrophedon Cellular Decomposition / Choset, H // Autonomous Robots – Vol. 9. – P. 247-253 – 2000. doi.org/10.1023/A:1008958800904
Sensor-Based Coverage: Incremental Construction of Cellular Decompositions/ Yong K. Hwang and Narendra Ahuja // Algorithmic Foundations of Robotics V. Springer Tracts in Advanced Robotics – Vol. 7. – P. 399-415 – 2004. https://doi.org/10.1007/978-3-540-45058-0_24
Optimizing cell decomposition path planning for mobile robots using different metrics/ M. Kloetzer, C. Mahulea and R., Gonzalez // 2015 19th International Conference on System Theory, Control and Computing (ICSTCC) – P. 565-570 – 2015. https://doi.org/10.1109/ICSTCC.2015.7321353
Path tracking control coverage of a mining robot based on exhaustive path planning with exact cell decomposition/ D. H. Kim et al. // 2014 14th International Conference on Control, Automation and Systems (ICCAS 2014) – P. 730-735 – 2014. https://doi.org/10.1109/ICCAS.2014.6987875.
A subdivision algorithm in configuration space for findpath with rotation/ R. A. Brooks and T. Lozano-Pérez // IEEE Transactions on Systems, Man, and Cybernetics – Vol. SMC-15. – No. 2. – P. 224-233 – 1985. https://doi.org/10.1109/TSMC.1985.6313352
Information-Driven Sensor Path Planning by AProximate Cell Decomposition/ C. Cai and S. Ferrari // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) – Vol. 39. – No. 3. – P. 672-689 – 2009. https://doi.org/10.1109/TSMCB.2008.2008561
A quadtreebased pathplanning algorithm for a mobile robot / Noborio Hiroshi , Naniwa Tomohide and Arimoto Suguru // Journal of Robotic Systems – Vol. 7. – P. 219-291. – 1990. https://doi.org/10.1002/rob.4620070404
Framed-quadtree path planning for mobile robots operating in sparse environments / A. Yahja, A. Stentz, S. Singh and B. L. Brumitt // Proceedings. 1998 IEEE International Conference on Robotics and Automation – Vol. 1. – P. 650-655. – 1998. https://doi.org/10.1109/ROBOT.1998.677046
The K-Framed Quadtrees AProach for Path Planning Through a Known Environment / Rodrigues A., Costa P. and Lima J. // ROBOT 2017. Advances in Intelligent Systems and Computing – Vol. 693. – P. 49-59 – 2018. https://doi.org/10.1007/978- 3-319-70833-1_5
Adaptive online cell decomposition with a laser range finder in unknown non-rectilinear environments, B., Lee, S.-G., Quang, T. B., Gwak, K.-W., and Lee, B. // International Journal of Precision Engineering and Manufacturing – Vol. 18(4). – P. 487–495 – 2017. https://doi.org/10.1007/s12541-017-0059-7
Path planning using probabilistic cell decomposition / Lingelbach, F. // 2004 IEEE International Conference on Robotics and Automation – P. 467–472. – 2004. https://doi.org/10.1109/ROBOT.2004.1307193
Path planning using Harmonic Functions and Probabilistic Cell Decomposition / Rosell, J., and Iniguez, P. // Proceedings of the 2005 IEEE International Conference on Robotics and Automation – P. 1803–1808. – 2005. https://doi.org/10.1109/ROBOT.2005.1570375
Real-time obstacle avoidance for manipulators and mobile robots / O. Khatib // Proceedings. 1985 IEEE International Conference on Robotics and Automation – P. 500-505. – 1985. https://doi.org/10.1109/ROBOT.1985.1087247
Dynamic motion planning for mobile robots using potential field method / Ge, S., and Cui, Y. // Autonomous Robots – Vol. 13. – P. 207-222. – 2002. https://doi.org/10.1023/A:1020564024509
An efficient improved artificial potential field based regression search method for robot path planning / Li, G., Yamashita, A., Asama, H., and Tamura, Y. // 2012 IEEE International Conference on Mechatronics and Automation – P. 1227–1232. – 2012. https://doi.org/10.1109/ICMA.2012.62835
Evolutionary artificial potential fields and their aPlication in real time robot path planning / P. Vadakkepat, Kay Chen Tan and Wang Ming-Liang // ACM Computing Surveys (CSUR) – Vol. 1. – P. 256-263. – 2000. https://doi.org/10.1109/CEC.2000.870304
Autonomous mobile robot dynamic motion planning using hybrid fuzzy potential field / Jaradat, M. A. K., Garibeh, M. H., & Feilat, E. A. // Soft Computing – Vol. 16(1). – P. 153–164. – 2012. https://doi.org/10.1007/s00500-011-0742-z
Multiple robot path coordination using artificial potential fields / C. W. Warren // Proceedings., IEEE International Conference on Robotics and Automation – Vol. 1. – P. 500-505. – 1990. https://doi.org/10.1109/ROBOT.1990.126028
A study of cluster robots line formatted navigation using potential field method / Y. H. Kang, M. C. Lee, C. Y. Kim, S. M. Yoon and C. B. Noh // 2011 IEEE International Conference on Mechatronics and Automation – P. 1723-1728. – 2011. https://doi.org/10.1109/ICMA.2011.5986370
Sampling-Based Robot Motion Planning: A Review / M. Elbanhawi and M. Simic // IEEE Access – Vol. 2. – P. 56-77. – 2014. https://10.1109/ACCESS.2014.2302442
Robot Motion Planning: A Distributed Representation AProach / Barraquand, J. and Latombe, J.C. // The International Journal of Robotics Research – Vol. 10(6). – P. 628–649. – 1991. https://doi.org/10.1177/027836499101000604
The "Ariadne's clew" algorithm: global planning with local methods / P. Bessiere, J., Ahuactzin, E., Talbi and E. Mazer // Proceedings of 1993 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '93) – Vol. 3. – P. 1373- 1380. – 1993. https://doi.org/10.1109/IROS.1993.583784
Path planning in expansive configuration spaces / D. Hsu, J.Latombe and R. Motwani // Proceedings of International Conference on Robotics and Automation – Vol. 3. – P. 2719-2726. – 1997. https://doi.org/10.1109/ROBOT.1997.619371
Visibility-polygon search and euclidean shortest paths / T. Asano, T. Asano, L. Guibas, J. Hershberger and H. Imai // 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) – P. 155-164. – 1985. https://doi.org/10.1109/SFCS.1985.65
A Voronoi method for the piano-movers problem, Proceedings / J. Canny // 1985 IEEE International Conference on Robotics and Automation – P. 530-535. – 1985. https://doi.org/10.1109/ROBOT.1985.1087297
Probabilistic roadmaps for path planning in high-dimensional configuration spaces / L. E. Kavraki, P. Svestka, J. Latombe and M. H. Overmars //IEEE Transactions on Robotics and Automation – Vol. 12. – No.4. – P. 566-580 – 1996. https://doi.org/10.1109/70.508439
A randomized roadmap method for path and manipulation planning / N. M. Amato and Y. Wu // Proceedings of IEEE International Conference on Robotics and Automation – Vol. 1. – P. 113-120. – 1996. https://doi.org/10.1109/ROBOT.1996.503582
Probabilistic roadmaps for robot path planning / Kavraki, L. E., Latombe, J. C., and Latombe, E. // Practical Motion Planning in Robotics: Current AProaches and Future. – 1998. https://doi.org/10.1.1.19.5276
Probabilistic Road Map sampling strategies for multi-robot motion planning / Clark, C. M. // Robotics and Autonomous Systems – Vol. 53(3-4). – P. 244-264 – 2005. https://doi.org/10.1016/j.robot.2005.09.002
Coordinated path planning for multiple robots / Švestka, P., & Overmars, M. H. // Robotics and Autonomous Systems – Vol. 23(3). – P. 125–152. – 1998. https://doi.org/10.1016/S0921-8890(97)00033-X
Multiple query probabilistic roadmap planning using single query planning primitives / Bekris, K. E., Chen, B. Y., Ladd, A. M., Plaku, E., and Kavraki, L. E. // Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) – P. 656–661. – 2003. https://doi.org/10.1109/IROS.2003.1250704
Path planning using lazy PRM / R. Bohlin and L. E. Kavraki // Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings – Vol. 1. – P. 521-528. – 2000. https://doi.org/10.1109/ROBOT.2000.844107
The Gaussian sampling strategy for probabilistic roadmap planners / V. Boor, M. H. Overmars and A. F. van der StaPen // Proceedings 1999 IEEE International Conference on Robotics and Automation – P. 1018–1023. – 1999. https://doi.org/10.1109/ROBOT.1999.772447
Mobile robot navigation system based on Probabilistic Road Map (PRM) with Halton sampling of configuration space /Velagic, J., Delimustafic, D., & Osmankovic, D. // 2014 IEEE 23rd International Symposium on Industrial Electronics (ISIE) – P. 1227–1232. – 2014. https://doi.org/10.1109/ISIE.2014.68647
The bridge test for sampling narrow passages with probabilistic roadmap planners / Hsu, D., Jiang, T., Reif, J., and Sun, Z. // IEEE International Conference on Robotics and Automation, 2003. Proceedings. ICRA ’03 – Vol. 3. – No. 3. – P. 4420–4426. – 2003. https://doi.org/10.1109/ROBOT.2003.1242285
Rapidly-Exploring Random Trees: A New Tool for Path Planning / LaValle, S. M. // 1998. https://doi.org/10.1.1.35.1853
RRT-connect: An efficient aProach to single-query path planning / Kuffner, J. J., and LaValle, S. M. (2000) // Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation – Vol. 2. – P. 995–1001. – 2000. https://doi.org/10.1109/ROBOT.2000.844730
AProaches for heuristically biasing RRT growth / Urmson, C., and Simmons, R. // Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) – Vol. 2. – P. 1178–1183. – 2003. https://doi.org/10.1109/IROS.2003.1248805
Augmenting RRT-planners with local trees / Strandberg, M. // IEEE International Conference on Robotics and Automation – Vol. 4. – P. 3258–3262. – 2004. https://doi.org/10.1109/ROBOT.2004.1308756
An obstacle-based rapidly-exploring random tree / Rodríguez, S., Tang, X., Lien, J. M., and Amato, N. M. // IEEE Inter- ?ational Conference on Robotics and Automation – P. 895–900. – 2006. https://doi.org/10.1109/ROBOT.2006.1641823
Optimal Bidirectional Rapidly-Exploring Random Trees / Jordan, M., and Perez, A. // Computer Science and Artificial Intelligence Laboratory - 2013.
Sampling-based algorithms for optimal motion planning / Karaman, S., and Frazzoli, E. // The International Journal of Robotics Research – Vol. 30(7). – P. 846–894. – 2011. https://doi.org/10.1177/0278364911406761
Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic / J. D. Gammell, S. S. Srinivasa and T. D. Barfoot // 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems – P. 2997-3004. – 2014. https://doi.org/10.1109/IROS.2014.6942976
Rapidly-exploring random tree based memory efficient motion planning / O. Adiyatov and H. A. Varol // 2013 IEEE International Conference on Mechatronics and Automation – P. 354-359. – 2013. https://doi.org/10.1109/ICMA.2013.6617944
A local based aProach for path planning of manipulators with a high number of degrees of freedom /Faverjon, B., and Tournassoud, P. // Proceedings. 1987 IEEE International Conference on Robotics and Automation – Vol. 4. – P. 1152–1159. – 1987. https://doi.org/10.1109/ROBOT.1987.1087982
Solving findpath by combination of goal-directed and randomized search / Glavina, B. // 1990 IEEE International Conference on Robotics and Automation – Vol. 3. – P. 1718–1723. – 1990. https://doi.org/10.1109/ROBOT.1990.126257
SANDROS: a motion planner with performance proportional to task difficulty / Chen, P. C., & Hwang, Y. K. // Proceedings 1992 IEEE International Conference on Robotics and Automation – P. 2346–2353. – 1992. https://doi.org/10.1109/ROBOT.1992.220112
Path planning with neural subgoal search/ B. Baginski and M. Eldracher // Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN'94) – Vol. 5. – P. 2732-2736. – 1994. https://doi.org/10.1109/ICNN.1994.374662
Robot Real-Time Motion Planning and Collision Avoidance in Dynamically Changing Environments / Jin-xue Z. // Emerging Research in Artificial Intelligence and Computational Intelligence, Communications in Computer and Information Science – Vol. 237. – P. 325-334. – 2011. https://doi.org/10.1007/978-3-642-24282-3_44
A dynamic subgoal path planner for unpredictable environments / H. Liu, W. Wan and H. Zha // 2010 IEEE International Conference on Robotics and Automation – P. 994-1001. – P. 219-291 – 2010. https://doi.org/10.1109/ROBOT.2010.5509324
An improved hierarchical motion planner for humanoid robots / Candido, S., Kim, Y. T., and Hutchinson, S. // 2008 8th IEEE-RAS International Conference on Humanoid Robots, Humanoids 2008 – P. 654–661. – 2008. https://doi.org/10.1109/ICHR.2008.4756021
A two-layered subgoal based mobile robot navigation algorithm with vision system and IR sensors / Nirmal Singh, N., Chatterjee, A., Chatterjee, A., and Rakshit, A. // Measurement: Journal of the International Measurement Confederation – Vol. 44(4). – P. 620–641. – 2011. https://doi.org/10.1016/j.measurement.2010.12.002
