Аннотация
Рассматриваются два приближённых алгоритма локализации мобильного робота, снабженного картой в виде простого многоугольника без дыр. Гипотезам локализации соответствуют экземпляры карты с отметкой предполагаемого положения робота. Робот должен определить свое истинное начальное местоположение, перемещаясь и обозревая видимую окрестность, чтобы устранить все неправильные гипотезы. При этом суммарная длина перемещений робота должна быть минимальной. Оптимизационная задача локализации робота является NP-полной, поэтому рассматриваются приближенные алгоритмы. Один из алгоритмов основан на использовании триангуляции простого многоугольника, представляющего карту. Предобработка в виде триангуляции простого многоугольника позволяет эффективно реализовать основные действия алгоритма, такие как, например, вычисление многоугольника видимости, поиск кратчайшего пути в многоугольнике между двумя точками, отсечение лишних гипотез. Второй алгоритм использует оверлей (пересечение) экземпляров карты. В пересечении выделяются так называемые окна, «заглядывая» в которые робот отсекает ложные гипотезы. На основе программной реализации нескольких алгоритмов проведено их экспериментальные исследование, использующее сгенерированные модельные карты. Приведены численные результаты машинных экспериментов и дана их интерпретация. Предлагаемые алгоритмы по критерию минимизации длины пройденного роботом пути незначительно уступают известным ранее алгоритмам, но на модельных примерах работают быстрее. Анализируются возможные способы уменьшения времени работы алгоритмов за счет использования параллелизма.
Ключевые слова: вычислительная геометрия, робототехника, мобильный робот, локализация робота, простой многоугольник, многоугольник видимости, генерация гипотез, проверка гипотез, пересечение полигонов, триангуляция полигона, сложность алгоритма, приближённый алгоритм, генерация карты, экспериментальное исследование алгоритма
Список литературы
[1] Dudek G., Jenkin M. Computational principles of mobile robotics. – 2nd rev. ed. – Cambrigde Univ. Press, 2010. – 406 p.
[2] De Berg M., Cheong O., Van Kreveld M., Overmars M. Computational geometry: algorithms and applications. – 3nd rev. ed. – Berlin; Heidelberg: Springer-Verlag, 2008. – 386 p.
[3] Guibas L.J., Motwani R., Raghavan P. The robot localization problem // The SIAM J. on Computing. – 1997. – № 26. – P. 1120–1138.
[4] Dudek G., Romanik K., Whitesides S. Localizing a robot with minimum travel // The SIAM J. on Computing. – 1998. – № 27. – P. 583–604.
[5] Rao M., Dudek G., Whitesides S. Randomized algorithms for minimum distance localization // Intern. J. Robotics Research. – 2007. – № 26. – P. 917–934.
[6] Koenig S., Mitchell J. S. B., Mudgal A., Tovey C. A near-tight approximation algorithm for the robot localization problem // The SIAM J. on Computing. – 2009. – № 39. – P. 461–490.
[7] Скворцов А.В. Триангуляция Делоне и её применение. – Томск: Изд-во Том. гос. ун-та, 2002. – 128 с.
[8] Hershberger J. and Snoeyink J. Computing minimum length paths of a given homotopy class // Computational Geometry. Theory and Applications. – 1994. – № 4. – P. 63–98.
[9] Seidel R. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons // Computational Geometry. Theory and Applications. – 1991. – № 1 (1). – P. 51–54.
[10] Дао Зуй Нам, Ивановский С.А. Приближенный алгоритм локализации мобильного робота с использованием окон в многоугольнике карты // Известия СПБГЭТУ «ЛЭТИ». – 2014. – № 3. – С. 38–43.
[11] Дао Зуй Нам, Ивановский С.А. Экспериментальный анализ алгоритмов локализации мобильного робота // Известия СПБГЭТУ «ЛЭТИ». – 2014. – № 1. – С. 19–24.
[12] Dаo Duy Nam, Ivanovskiy S.A. Two new approaches to minimum distance localization // J. of Science and Technology Univ. of Danang. – 2013. – № 12 (73). – P. 52–57.
[13] Qi M., Cao T.-T., Tan T.S. Computing 2D constrained delaunay triangulation using graphics Hardware [Electronic resource] // Technical Report / National University of Singapore, School of Computing. – 2011. – # TRB3/11. – 9 p. – URL: http://www.comp.nus.edu.sg/~tants/cdt.html
[14] Сандерс Дж., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров. – М.: ДМК Пресс, 2011. – 232 с.
[15] Фирсов М.А., Ивановский С.А. Параллельная реализация алгоритма построения пересечения простых полигонов с использованием технологии CUDA // Известия СПБГЭТУ «ЛЭТИ». – 2013. – № 9. – С. 29–34.
[16] Скворцов А.В. Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции // Вычисл. методы и программирование. – 2002. – Т. 3. – С. 116–123.
[17] Фирсов М.А. Сравнение параллельных реализаций алгоритма пересечения полигонов на многоядерном и на графическом процессорах // 67-я научно-техническая конференция профессорско-преподавательского состава университета, Санкт-Петербург, 27 января–3 февраля 2014 г.: сб. докл. студентов, аспирантов и молодых ученых. – СПб.: Изд-во СПБГЭТУ «ЛЭТИ», 2014. – С. 103–107.
