Разработка алгоритма обучения мобильного робота в целях обнаружения препятствий в замкнутом пространстве

XXI век – век высоких технологий. В настоящее время наша жизнь окружена информационными технологиями: у каждого есть мобильный телефон, компьютер и прочая техника (иногда называемая гаджетами). Сами не замечая, мы все больше и больше используем их в своей жизни. Уже дошло до того, что мы начинаем использовать роботов в своих целях. Не пройдет и десяти лет, как у каждого будет свой личный мобильный робот.

Правильно запрограммированный робот может выполнять большое количество задач. Одной из распространенных проблем, возникающих при проектировании роботов, является проблема разработки эффективного алгоритма обхода препятствий. Робот во время своего движения не должен застревать и останавливаться, пока не выполнит задачу. Для успешного выполнения данной задачи в памяти робота должна храниться карта рабочего пространства, на которой отмечены места, где находятся препятствия для робота [1–6].

Постановка задачи

Необходимо разработать алгоритм, позволяющий роботу построить карту местности за конечное(минимальное) время. Карта представляет собой поверхность замкнутого пространства, разделенную на квадраты. Площадь каждого квадрата равна площади основания робота или квадрату длины шага робота.

Метод решения

Для изучения пространства используется алгоритм, основанный на алгоритмах движения робота «Спираль» и «Движение вдоль стены» [7].

Алгоритм «Спираль» представляет собой движение по окружности с увеличение радиуса. На рисунк е 1 представлена блок-схема алгоритма.

Рисунок 1. Алгоритм «Спираль»

Figure1. “Spiral” algorithm

Алгоритм «Движение вдоль стены» представляет собой алгоритм, при котором робот движется по периметру пространства. В отличие от алгоритма «Спираль» в данном алгоритме робот может обходить препятствия. Блок-схема алгоритма представлена на рисунке 2.

Рисунок 2. Алгоритм «Движение вдоль стены»

Figure 2. Algorithm “Movement along the wall”

Предлагаемый алгоритм обучения мобильного робота в целях обнаружения препятствий является модифицированным объединением двух вышеописанных алгоритмов. Алгоритм обучения состоит из трех частей. Первую часть можно назвать основной – это алгоритм прохода одного круга. Робот начинает свое исследование пространства с возможного периметра, и с каждым кругом он сужает его до радиуса меньше на единицу. Блок-схема алгоритма представлена на рисунке 3.

Рисунок 3. Алгоритм прохода одного круга

Figure 3. Algorithm pass one circle

Для того чтобы робот с каждым пройденным кругом сужал радиус, необходима вторая часть алгоритма – алгоритм начала исследования нового круга. На рисунке 4 представлена блок-схема алгоритма.

Рисунок 4. Алгоритм начала исследования нового круга Figure 4. Algorithm for beginning of the study the new circle

После окончания движения по данному алгоритму роботу необходимо проверить пространство на неисследованные участки (рисуно к 5) . В случае, когда препятствий будет мало и их форма будет простой, робот исследует пространство за один проход. В противном случае останутся темные, неизвестные роботу участки. Чтобы робот не затратил много времени на путь до такого участка, необходимо использовать алгоритм поиска кратчайшего пути. Так как на пути робота могут быть препятствия, то алгоритм должен искать кратчайший путь, обходя все возможные препятствия на своем пути.

Рисунок 5. Алгоритм завершения обучения

Figure5. Algorithm for completion of training

Заключение

Существует множество алгоритмов обхода препятствий. Наиболее эффективным является алгоритм Дейкстры. Этот алгоритм применим только к графам с неотрицательными весами. Алгоритм Дейкстры находит кратчайшие пути к вершинам графа в порядке их удаления от данной исходной вершины. Главным в алгоритме Дейкстры является то, что достаточно сравнить длины таких путей [8].