109–121 СОВРЕМЕННЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ УДК 004.896:004.42 Приближённые алгоритмы локализации мобильного робота ДАО ЗУЙ НАМ1, С. <...> В.И. Ульянова (Ленина), к. т. н., доцент, e-mail: saivanovsky@mail.ru Рассматриваются два приближённых алгоритма локализации мобильного робота, снабженного картой в виде простого многоугольника без дыр. <...> Гипотезам локализации соответствуют экземпляры карты с отметкой предполагаемого положения робота. <...> Робот должен определить свое истинное начальное местоположение, перемещаясь и обозревая видимую окрестность, чтобы устранить все неправильные гипотезы. <...> При этом суммарная длина перемещений робота должна быть минимальной. <...> Оптимизационная задача локализации робота является NP-полной, поэтому рассматриваются приближенные алгоритмы. <...> Один из алгоритмов основан на использовании триангуляции простого многоугольника, представляющего карту. <...> Предобработка в виде триангуляции простого многоугольника позволяет эффективно реализовать основные действия алгоритма, такие как, например, вычисление многоугольника видимости, поиск кратчайшего пути в многоугольнике между двумя точками, отсечение лишних гипотез. <...> Предлагаемые алгоритмы по критерию минимизации длины пройденного роботом пути незначительно уступают известным ранее алгоритмам, но на модельных примерах работают быстрее. <...> Ключевые слова: вычислительная геометрия, робототехника, мобильный робот, локализация робота, простой многоугольник, многоугольник видимости, генерация гипотез, проверка гипотез, пересечение полигонов, триангуляция полигона, сложность алгоритма, приближённый алгоритм, генерация карты, экспериментальное исследование алгоритма ВВЕДЕНИЕ Развитие аппаратной базы разнообразных мобильных робототехнических устройств (в том числе их сенсорного оснащения) стимулировало растущий интерес к широкому кругу прикладных задач (от применения в промышленности и медицинских клиниках до микро- и нанороботов), к методам <...>