Рассматриваются два приближённых алгоритмы локализации мобильного робота, снабженного картой в виде простого многоугольника. Гипотезам локализации соответствуют экземпляры карты с отметкой предполагаемого положения робота. Первый алгоритм основан на использовании триангуляции простого многоугольника в качестве предобработки для реализации основных операций, таких как пересечение многоугольников, вычисление многоугольников видимости, нахождение кратчайших путей. Во втором алгоритме в дополнение к триангуляции используется понятие окна в пересечении экземпляров карты. «Заглядывая» в окно, робот отсекает ложные гипотезы. Проведены экспериментальные исследования этих алгоритмов и сравнение с другими алгоритмами. C. 25-41.

Two approximate algorithms of the robot localization problem with the map in the form of a simple polygon is considered. Hypotheses localization correspond to copies maps from assumed mark of robot’s position. The first algorithm is based on a triangulation of a simple polygon as a preprocessing for the implementation of the basic operations, such as the intersection of polygons, computing visibility polygons, finding shortest paths. The second algorithm is used other than the triangulation additional concept of the window at the intersection of copies of the map. Looking» in the window, the robot cuts false hypotheses. Experimental studies of these algorithms and compared with other algorithms.