К вопросу о планировании маршрута подвижного робота

Размещено на http://www.allbest.ru/

К вопросу о планировании маршрута подвижного робота

А.Г. Курочкин

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

Ключевые слова: робот, планирование маршрута, двоичный флаг, матрица ячеек

A.G. Kurochkin. About a planning of the route a mobile robot

This paper its show, a modification of the A-star route planning method for mobile robots is considered. It is shown that taking into account obstacles in the local vicinity of the mobile robot is necessary, but not sufficient for rational route planning. The essence of the modification is the use of additional information about the features of the original matrix of cells. This additional information is represented by binary flags. They denote matrix-free rows and columns.

Keywords: robot, route planning, binary flag, matrix of cells

Задача планирования маршрута понимается как задача поиска бесконфликтного пути из свободных состояний внешней среды [1]. Путь как последовательность разрешенных состояний должен удовлетворять некоторому целевому критерию . В качестве целевого критерия выбран критерий максимизации средней скорости движения робота по маршруту

планирование маршрут подвижной робот

(1)

где Vср - средняя скорость движения робота по маршруту, (t) -последовательность выбранных разрешенных состояний (маршрут).

Для планирования маршрута используется сеточный подход представления внешней среды. Внешняя среда разбивается сеткой с шагом x, y на ячейки. При условии x,=y формируется двумерная матрица ячеек M={mij}, (i=1-n, j=1-n). В дальнейшем планирование маршрута - это определение координат центров ячеек, через которые пройдет маршрут.

В работе в качестве базового метода планирования (поиска) маршрута выбран известный эвристический метод А* - (А-star) [2]. Для данного метода направление перемещения робота между ячейками оценивается на каждом шаге как минимизация целевой функции расстояния Limit

(2)

где G - суммарная длина пройденного пути, вычисляемая как Gk+1= Gk+ Lij; Gk - длина ранее пройденного участка; Lij -текущая длина; H - эвристическая оценка длины участка, оставшегося до цели H.

Основной недостаток метода A-star заключается в том, что он не исключает неопределенность выбора новой ячейки за счет сравнения ограниченного количества ближайших к роботу ячеек [3, 4]. Эта особенность приводит к непродуктивным затратам времени, останову робота и реализации возвратных перемещений по маршруту. Для повышения обоснованности принимаемых решений в классический метод поиска А* вносится дополнительная информация о состоянии групп ячеек в пределах строк и столбцов матрицы M. Эта информация представляется двоичными флагами, обозначающими свободные от препятствий строки и столбцы матрицы fl_x1 -fl_xn и fl_1x - fl_nx соответственно (рис.1) [3].

Для квадратной матрицы nn ячеек дополнительно вводятся строка флагов и столбец флагов fl_x1 -fl_xn и fl_1x - fl_nx соответственно. Каждый бит флага (status) информирует робота о том, что соответствующий столбец/строка свободные или занятые:

, (3)

, (4)

где - k - индекс ячейки в строке или столбце (k=1 - n).

Рисунок 1 - Исходная ситуация для построения маршрута, расширенная двоичными флагами

Таким образом, разработан модифицированный метод построения маршрута, включающий дополнительные шаги в метод А-star, а именно:

а) подготовка расширенной матрицы ячеек, содержащей не только информацию о препятствиях на местности, но и дополнительные строку и столбец флагов fl_x1 - fl_xn и fl_1x - fl_nx, каждый бит которых содержит информацию о наличии свободного столбца или строки в исходной матрице;

б) дополнительная проверка подмножества свободных ячеек по строке-флагу и столбцу-флагу и выборе ближайшей следующей ячейки, которая имеет минимальное расстояние до свободной строки или столбца в матрице ячеек;

в) контроль координат текущих ячеек робота R и целевой ячейки Goal, т.е. проверка логического условия ((xR=xGOAL) (yR=yGOAL))=TRUE.

В качестве показателей оценки маршрута взяты:

- отношения расстояний построенных маршрутов по двум методам;

- отношение времени прохождения маршрута по двум методам.

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

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

Список литературы

1. Казаков К.А. Семенов В.А. Обзор современных методов планирования движения // Труды института системного программирования РАН. 2016. Том 28, выпуск 4. С.241-296.

2. D. Delling, P. Sanders, D. Schultes, D. Wagner Engineering route planning algorithms // Algorithmics of large and complex networks. - Springer. 2009. 376 p

3. Авдеев В.О., Курочкин А.Г., Лоторев П.В., Титенко Е.А. Модифицированные метод и алгоритм с итерационным заглублением для построения маршрута по матрице ячеек // Информационно-измерительные и управляющие системы. 2016. Т. 14. № 10. С. 46-50.

4. Курочкин А.Г. Метод планирования маршрута подвижного робота на местности // Известия Юго-Западного государственного университета. Серия Управление, вычислительная техника, информатика. Медицинское приборостроение. 2016. № 3. С. 55-62.

Размещено на Allbest.ru