РУАЭСТ (RUAEST)
Приближённые алгоритмы локализации мобильного робота
Рассматриваются два приближённых алгоритма локализации мобильного робота, снабженного картой в виде простого многоугольника без дыр. Гипотезам локализации соответствуют экземпляры карты с отметкой предполагаемого положения робота. Робот должен определить свое истинное начальное местоположение, перемещаясь и обозревая видимую окрестность, чтобы устранить все неправильные гипотезы. При этом суммарная длина перемещений робота должна быть минимальной. Оптимизационная задача локализации робота является NP-полной, поэтому рассматриваются приближенные алгоритмы. Один из алгоритмов основан на использовании триангуляции простого многоугольника, представляющего карту. Предобработка в виде триангуляции простого многоугольника позволяет эффективно реализовать основные действия алгоритма, такие как, например, вычисление многоугольника видимости, поиск кратчайшего пути в многоугольнике между двумя точками, отсечение лишних гипотез. Второй алгоритм использует оверлей (пересечение) экземпляров карты. В пересечении выделяются так называемые окна, «заглядывая» в которые робот отсекает ложные гипотезы. На основе программной реализации нескольких алгоритмов проведено их экспериментальные исследование, использующее сгенерированные модельные карты. Приведены численные результаты машинных экспериментов и дана их интерпретация. Предлагаемые алгоритмы по критерию минимизации длины пройденного роботом пути незначительно уступают известным ранее алгоритмам, но на модельных примерах работают быстрее. Анализируются возможные способы уменьшения времени работы алгоритмов за счет использования параллелизма.