Определение позиции робота по сформированной двумерной карте помещения

Введение

Человек издавна размышлял над созданием различных механизмов: человекоподобных слуг, устройств, и статуй. Так, в древнегреческой мифологии имеется одно из первых упоминаний робота — медный человек-великан Талос, охранявший девушку на острове [1]. В XVIII веке автоматоны приобрели наибольшую популярность в интересах развлечений. Тогда были созданы такие известные механические игрушки, как фигуры людей, выполняющие человеческие действия (игра на музыкальных инструментах, письмо), утка с симуляцией пищеварения и махания крыльями, театр из двух сотен фигур [2].

В современном виде робототехника формировалась в середине прошлого века, прежде всего благодаря развитию цифровой вычислительной техники. В это раз потребность в роботах возникла из-за необходимости в помощи либо замене человека в опасных, либо недоступных ему условиях, а также по экономическим причинам. Первые механизмы (1940–1950 гг.) повторяли на расстоянии действия рук человека за счет его собственных усилий. Со временем появлялись новые способы управления, в частности манипуляторы стали автоматизированными и программируемыми [3].

Следующими важными направлениями в робототехнике – создание мобильных и автономных роботов, что привело к началу работы и появлению в 1965–1972 гг. первого мобильного робота Shakey [4], способного самостоятельно ориентироваться в неизвестной среде и перемещаться в ней к заданной точке.

В настоящее время ведется работа по добавлению новых датчиков роботам и совершенствованию искусственного интеллекта, позволяющие им выполнять все новые задачи [5]. Уже сейчас существуют роботы, обучаемые действиям на примере человека вместо их программирования [6].

В мобильных автономных роботах важное место занимает задача навигации. В этой задаче можно выделить следующие подзадачи: построение карты и локализация робота на ней. В работе будет рассматриваться последняя.

Объектом исследований выступает процесс локализации объекта в пространстве.

Предмет исследований: определение позиции объекта на карте по результатам его измерений.

Целью работы является исследование предлагаемых методов определения координат объекта на сформированной карте по результатам измерений, выполняемых объектом.

Представление карт

Карты разделяют на глобальные и локальные. Глобальные состоят из нескольких локальных карт и позволяют рассчитать местоположение робота в глобальной системе координат. С помощью локальных карт зачастую определяются относительные координаты устройства.

Также выделяют карты по способу хранения информации о внешней среде:

• топологическая — информация представляется в виде графа;

• дискретная метрическая — внешняя среда представлена в виде ячеек, содержащих информацию о внешней среде;
• непрерывная метрическая карта — карта содержит перечень геометрических объектов (таких как точки и линии), значения координат которых принадлежат к непрерывному числовому диапазону [7].

Еще карты можно классифицировать по числу измерений: двумерные и трехмерные. Использование трехмерных карт сильно повышает требования к вычислительным мощностям и объему памяти устройства, характеристикам сканирующего модуля.

Робот может использовать заранее подготовленные карты либо самостоятельно их строить и одновременно определять свое местоположение.

Системы навигации

Системы навигации классифицируют:

• пассивные — прием информации о собственных координатах и других характеристиках своего движения от внешних источников (метки, маяки, проложенные полосы, GPS и т.д.);
• активные — определение местоположения только своими силами (одометр, радары, сонары, лидары и т.д.) [8].

В навигации частое применение находят лазерные дальномеры за счет высокой точности и скорости измерений. Однако их недостатками являются наличие зависимостей от отражательной способности объекта и постороннего освещения в среде, вызывающих трудности с обнаружением тел прозрачных или с зеркальной поверхностью, а также в условиях высокой освещенности, плохой погоды. Перспективны и также используются технологии компьютерного зрения, которые в сравнении с лидаром имеют меньшую стоимость измерительного модуля и дают больше информации о самом объекте, однако сталкиваются с проблемами определения объектов, точности расчета расстояния, работы при наличии видимых помех (плохая погода, освещенность), требования высокой вычислительной мощности для обработки изображения [[8], [9], [10], [11]].

Принятые допущения

В работе используется двумерная дискретная метрическая карта и активная навигация. Приняты следующие допущения:

1. Карта точно соответствует описываемому помещению.
2. Карта ориентирована по географическому северному полюсу.
3. В момент измерения платформа неподвижна либо время измерений бесконечно мало.
4. Используемые датчики выполняют измерения без ошибок и с разрешением, равным разрешению карты.

Математическое описание

Рассматриваемый способ нахождения местоположения робота предполагает использование 2D лидара для определения дистанции d до предполагаемого препятствия и магнитометра для определения азимута α (принимается географическим).

Суть метода заключается в следующем:

1. По результатам измерения датчиков относительно препятствий строится обратный путь измерительного луча.
2. Точки получаемого множества, где путь заканчивается, считаются предполагаемыми местами робота.
3. Имея четыре множества, формируемые измерениями по азимуту с углами 0°, 90°, 180°, 270° и соответствующими измеренными дистанциями, находится их пересечение, сильно сокращающее число возможных позиций устройства.

В описываемой модели можно выделить два ключевых объекта: двумерная карта помещения и предполагаемые позиции робота.

Карта (G) представляется в виде матрицы:

(1)

где g_x,y = G(x, y) — ячейка двумерной карты G,

x — номер столбца карты,

y — номер строки,

n — количество столбцов,

m — количество строк.

Переменная g характеризует состояние соответствующей ячейки: -1 — состояние ячейки неизвестно (не сканирована), 0 — ячейка свободна, 1 — ячейка имеет препятствие. Определяемый ячейкой размер равен значению точности карты.

Нумерация по оси x происходит слева направо, y — сверху вниз. Столбцы и строки матрицы нумеруются начиная с верхнего левого угла. Если не указано противное, элементы g принадлежат множеству G.

Hα — гипотезы о возможных местах робота относительно препятствий по результатам измеренных углов и дистанций, где α — азимут. Построение гипотез для направлений 0°, 90°, 180°, 270° с учетом хода луча будет следующим:

(2)

где dα — измеренное расстояние по азимуту α.

Без трассировки измерительного луча за счет уменьшения числа проверок гипотез формулы упростятся следующим образом:

(3)

Однако, отсутствие проверок наличия препятствий по ходу лучей приведет к увеличению числа предполагаемых позиций во множествах гипотез, в свою очередь, оказывая влияние на время вычисления их пересечения. Важно отметить, что при упрощенном вычислении гипотез могут возникать ситуации, когда расчет позиции ведется сквозь препятствия, в результате чего возможно возникновение неверных итоговых позиций.

P — множество полученных позиций как результат пересечения сформированных ранее гипотез:

(4)

Экспериментальное исследование

Для тестирования рассматриваемого метода применена карта, представленная на рисунке 1. Размер одной ячейки считается равным 10 см. Используемые значения:

d0 = 40 см,

d90 = 50 см,

d180 = 40 см,

d270 = 40 см.

Результат по методу (формула 2): P = {(13, 4), (22, 4)} (на рис. 1 результирующие ячейки выделены оранжевым цветом и имеют значение 5, синим — препятствия (значение 1), красным — неисследованные участки (значение -1)). Результирующие позиции по второму методу (формула 3) показаны на рисунке 2.

При использовании упрощенного метода видно, что в результате присутствует третья позиция с координатами (31; 4) (рис. 2). Ее наличие объясняется отсутствием проверки пути луча, из-за чего не было учтено препятствие (33;4), что показано на рисунках 3 и 4 (значением -3 и зеленым цветов выделены содержимые в множестве H90 ячейки), где второй метод не учитывает препятствие с координатами (33;3), (33;4) и (33;5).

Рисунок 1 – Карта помещения с разрешением 10 см (метод 1)

Рисунок 2 – Карта помещения с разрешением 10 см (метод 2)

Рисунок 3 – Карта помещения с разрешением 10 см (метод 1)

Рисунок 4 – Карта помещения с разрешением 10 см (метод 2)

На рисунке 5 показан результат работы программы с картой с разрешением 10 см, где время 1 — среднее время расчета гипотез, время 2 — среднее время формирования пересечения гипотез, время 3 — среднее итоговое время выполнения метода как сумма времен 1 и 2. Из рисунка 5 следует, что метод 2 привел к уменьшению времени определения гипотез H, однако из-за расчета пересечения P с большим числом гипотез H общее время выполнения второго метода выше, чем первого.

Для определения скорости выполнения методов использовался таймер с точностью 100 нс. Рассматриваемые методы выполнялись по 10000 раз, после чего определялось среднее время выполнения двух этапов методов и общее время выполнения этапов как сумма их средних значений. Время работы методов при их первом вызове не учитывалось.

В таблице 1 и на рисунке 6 показаны результаты тестирований этой же карты с разрешениями, равными 10, 5, 1, и 0,5 см. Следует отметить, что за счет удаления краевых строк и столбцов с неисследованными ячейками (значение -1) и установкой неисследованными ячеек, недоступных для сканирования изнутри помещения (предположим, внутренних ячеек стен), карта, например, с разрешением 5 см не будет иметь размер, в четыре раза больший, чем карта с разрешением 10 см.

Из результатов следует, что первый метод в случаях рассматриваемых карт с разрешениями 10, 5 и 2 см (814, 3024, 18462 ячеек соответственно) выполнил работу быстрее, чем второй. Однако второй метод при разрешениях карт 1 и 0,5 см (72992 и 289842 ячеек) завершил выполнение быстрее первого.

Рисунок 5 – Результат работы программы с картой с разрешением 10 см

Рисунок 6 – График зависимости скорости выполнения методов от количества ячеек рассматриваемой карты

Выводы

Полученные методы позволяют определить возможные координаты устройства по известной карте. В данном варианте результат определения местоположения при наличии одинаковых помещений или участков с точки зрения их состояния может быть неоднозначен.

Результаты тестирования показали, что второй метод оказался медленнее первого при малом разрешении карты и быстрее при большом. Модификация упрощенного метода дополнительной проверкой для каждой гипотезы, возможно, в данном случае будет способна приблизить его время выполнения к методу с полным отслеживанием хода измерительного луча при малом разрешении карты и сделать быстрее упрощенного метода при большом разрешении. мощностями устройством.

В дальнейших исследованиях для уточнения позиции устройства может применяется его перемещение с ведением истории маршрута и последующим повторным определением возможных позиций. Также в будущем необходимо учитывать параметры датчиков, в частности неточность их результатов измерений.

Литература

1. Мифы народов мира: Энциклопедия / Гл. ред. С. А. Токарев. – М., 2008. – Электронное издание. – Текст: электронный // Internet Archive : [сайт]. – URL: https://archive.org/details/Myths_of_the_Peoples_of_the_World_Encyclopedia_Electronic_publication_Tokarev_and_others_2008/page/n689/mode/2up
2. Сычев, И. Автоматоны: 200-летние роботы / И. Сычев. – Текст: электронный // Хабр : [сайт]. – 2016. – URL: https://habr.com/ru/articles/399133/
3. Юревич, Е. Основы робототехники : учебное пособие / Е. И. Юревич – Текст: электронный // ЭБ СПбПУ. – 2-е изд. – URL: http://elib.spbstu.ru/dl/325.pdf
4. Kuipers, B. Shakey: From Conception to History / B. Kuipers, E. A. Feigenbaum, P. E. Hart, N. J. Nilsson. – Текст : электронный // AI Magazine. – 2017. – № 38. – С. 88–103. – URL: https://onlinelibrary.wiley.com/doi/10.1609/aimag.v38i1.2716
5. Титенок, А. В. Основы робототехники : учебное пособие / А. В. Титенок. — Москва, Вологда : Инфра-Инженерия, 2022. – 236 c. — ISBN 978-5-9729-0872-1. — Текст : электронный // Цифровой образовательный ресурс IPR SMART : [сайт]. — URL: https://www.iprbookshop.ru/124173.html.— Режим доступа: для авторизир. пользователей
6. TRI Teaching Robots to Help People in their Homes // Toyota Research Institute : [site] – URL:https://www.tri.global/news/tri-teaching-robots-help-people-their-homes
7. ГОСТ Р 60.6.8.1-2023. Роботы и робототехнические устройства. Представление картографических данных для навигации роботов : национальный стандарт Российской Федерации : издание официальное : утвержден и введен в действие Приказом Федерального агентства по техническому регулированию и метрологии от 31 августа 2023 г. № 781-ст : введен впервые : дата введения 2024-01-01 / подготовлен Федеральным государственным автономным научным учреждением Центральный научно-исследовательский и опытно-конструкторский институт робототехники и технической кибернетики (ЦНИИ РТК) – Текст: электронный // База ГОСТов : [сайт]. – URL: https://allgosts.ru/25/040/gost_r_60.6.8.1-2023
8. Бобровский, С. Навигация мобильных роботов / С. Бобровский – Текст: электронный // Виртуальный компьютерный музей : [сайт]. – 2016. – URL: https://computer-museum.ru/frgnhist/robonav.htm
9. Радиоэлектронные системы: Основы построения и теория : справочное издание / Я. Д. Ширман, С. Т. Багдасарян, А. С. Маляренко [и др.] – 2-е изд., перераб. и доп. – Москва: «Радиотехника», 2007. – 512 с. – Текст : непосредственный.
10. Игнатов, А. «Глаза» беспилотных автомобилей: LiDAR и компьютерное зрение / А. Игнатов ; FirstVDS – Текст: электронный // Хабр : [сайт]. – 2023. – URL: https://habr.com/ru/companies/first/articles/728224/
11. Мир глазами автомобиля. Каким его видят беспилотники? / Toshiba – Текст: электронный // Хабр : [сайт]. – 2018. – URL: https://habr.com/ru/companies/toshibarus/articles/431388/