КЛАСИЧНІ МЕТОДИ ПЛАНУВАННЯ ШЛЯХУ ДЛЯ МОБІЛЬНИХ РОБОТІВ
DOI:
https://doi.org/10.26906/SUNZ.2019.3.143Ключові слова:
МАР, роботи, автономність, пошук шляху, планування рухуАнотація
Мобільні автономні роботи (МАР) використовуються для виконання великої кількості різноманітних завдань у різних галузях, таких як видобуток корисних копалин, пошук та порятунок, військових застосувань тощо. Окремо виділяється категорія МАР, які використовуються у закритих приміщеннях. Це пов’язано з додатковими технічними та програмними обмеженнями які накладаються на МАР та оператора. У цій статті розглядаються 35 класичних методів пошуку шляху для МАР та методів їх оптимізації. Класичні методи включають наступні категорії методів: методи клітинної декомпозиції; методи штучного потенційного поля; вибіркові методи; методи, що використовують мережу проміжних задач. У статті також розглядаються основні проблеми, що виникають під час виконання задачі пошуку шляхів. Методи аналізувалися за такими характеристиками: обмеження; режим планування; мнтрика, яка використовується для планування наступного кроку. Також у статті розглядаються основні проблеми з якими стикаються під час виконання задачі пошуку шляху.Завантаження
Посилання
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
