Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.
Влияние пространственного разрешения на оптимальность пути мобильного робота в двумерных решеточных моделях
В данной работе исследуется влияние пространственного разрешения дискретизированного (решеточного) представления окружающей среды на эффективность и корректность поиска оптимального пути в сложных условиях. Рассматриваются сценарии, характеризующиеся возможным наличием узких проходов, неоднородным распределением препятствий и зонами повышенных требований к безопасности в непосредственной окрестности препятствий. Несмотря на широкое применение решеточных представлений окружающей среды в робототехнике благодаря их совместимости с сенсорными данными и поддержке классических алгоритмов планирования траекторий, разрешение этих решеток оказывает существенное влияние как на достижимость цели, так и на показатели оптимального пути. Предлагается алгоритм, сочетающий анализ связности среды, оптимизацию траектории и геометрическое уточнение безопасности. На первом этапе с помощью алгоритма Лиса (Leath) оценивается достижимость целевой точки путем выявления связной компоненты, содержащей стартовую позицию. При подтверждении достижимости целевой точки на втором этапе алгоритм A* применяется к узлам данной компоненты для построения пути, минимизирующего одновременно как длину пути, так и риск столкновения. На третьем этапе для узлов, расположенных в зонах безопасности, осуществляется уточненная оценка расстояния до препятствий с помощью комбинации алгоритмов Гилберта-Джонсона-Кирти (GJK) и расширяющегося многогранника (EPA). Экспериментальный анализ позволил выявить нелинейную зависимость вероятности существования и эффективности оптимального пути от параметров решетки: так, снижение пространственного разрешения решетки повышает вероятность потери связности и недостижимости цели, тогда как увеличение ее пространственного разрешения влечет рост вычислительной сложности без пропорционального улучшения характеристик оптимального пути.
1. Ferguson D., Stentz A. Using interpolation to improve path planning: The Field D* algorithm // Journal of Field Robotics. — 2006. — Vol. 23, No. 2. — P. 79–101. — DOI: https://doi.org/10.1002/rob.20109.
2. Goldstein R., Breslav S., Walmsley K., Khan A. SpaceAnalysis: a tool for pathfinding, visibility, and acoustics analyses in generative design workflows // Proceedings of the 11th Annual Symposium on Simulation for Architecture and Urban Design. — San Diego, CA, USA : Society for Computer Simulation International. — 2020. — URL: https://simaud.org/2020/proceedings/2.pdf.
3. Gu J., Cao Q. Path planning for mobile robot in a 2.5‐dimensional grid‐based map // Industrial Robot: An International Journal. — 2011. — Vol. 38, No. 3. — P. 315–321. — DOI: https://doi.org/10.1108/01439911111122815.
4. Lingelbach F. Path planning using probabilistic cell decomposition // IEEE International Conference on Robotics and Automation. — Proceedings. ICRA’04. — 2004. — Vol.1. — P. 467–472. — DOI: https://doi.org/10.1109/robot.2004.1307193.
5. Otte M. W., Richardson S. G., Mulligan J., Grudic G. Path planning in image space for autonomous robot navigation in unstructured environments // Journal of Field Robotics. — 2009 — Vol. 26, No. 2. — P. 212–240. — DOI: https://doi.org/10.1002/rob.20274.
6. Gaisbauer F., Agethen P., Lunde R., Rukzio E. Iterative path adaption (IPA): Predictive trajectory-estimation using static pathfinding algorithms // Procedia CIRP. — 2018. — Vol. 67. — P. 24–29. — DOI: https://doi.org/10.1016/j.procir.2017.12.170.
7. Otte M. W., Richardson S. G., Mulligan J., Grudic G. Local path planning in image space for autonomous robot navigation in unstructured environments // International Conference on Intelligent Robots and Systems. — 2007. — P. 2819–2826. — DOI: https://doi.org/10.1109/iros.2007.4399343.
8. Zhang W., Li J., Yu W., Ding P., Wang J., Zhang X. Algorithm for UAV path planning in high obstacle density environments: RFA-Star // Frontiers in Plant Science. — 2024. — Vol. 15. — DOI: https://doi.org/10.3389/fpls.2024.1391628.
9. Radhakrishnan S., Gueaieb W. A state-of-the-art review on topology and differential geometry-based robotic path planning—part I: planning under static constraints // International Journal of Intelligent Robotics and Applications. — 2024. — Vol. 8, No. 2. — P. 435–454. — DOI: https://doi.org/10.1007/s41315-024-00330-5.
10. Bandi S., Thalmann D. Path finding for human motion in virtual environments // Computational Geometry. — 2000. — Vol. 15, No. 1–3. — P. 103–127. — DOI: https://doi.org/10.1016/s0925-7721(99)00046-2.
11. Leath P. L. Cluster size and boundary distribution near percolation threshold // Physical Review B. — Vol. 14, No. 11. — P. 5046–5055 (1976). — DOI: https://doi.org/10.1103/PhysRevB.14.5046.
12. Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE Transactions on Systems Science and Cybernetics. — 1968. — Vol. 4, No. 2. — P. 100-107. — DOI: https://doi.org/10.1109/TSSC.1968.300136.
13. Gilbert E. G., Johnson D. W., Keerthi S. S. A fast procedure for computing the distance between complex objects in three-dimensional space // IEEE Journal on Robotics and Automation. — 1988. — Vol. 4, No. 2. — P. 193–203. — DOI: https://doi.org/10.1109/56.795.
14. Ericson C. Real-time collision detection. — Morgan Kaufmann Publishers, 2005. — 633 p. — URL: https://realtimecollisiondetection.net.
15. Chau J. gslnls: GSL multi-start nonlinear least-squares fitting. — Version 1.4.2. — CRAN: Contributed Packages, 2021. — DOI: https://doi.org/10.32614/cran.package.gslnls.
