К вопросу о планировании маршрута подвижного робота
Комплексно рассмотрена модификация метода планирования маршрута А-звездочка для подвижных роботов. Показано, что учет препятствий в локальной окрестности подвижного робота является необходимым, но не достаточным для рационального планирования маршрута.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 01.02.2019 |
| Размер файла | 798,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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
...Подобные документы
Программные продукты для решения задачи построения оптимального маршрута. Выбор аппаратных и программных средств для построения маршрута обхода пациентов. Математическая модель муравьиного алгоритма: состав, структура, тестирование, отладка, реализация.
дипломная работа [1,9 M], добавлен 03.12.2017Способ реализации автоматизированной системы расчета маршрута для курьерской компании. Особенности архитектуры ОС Android. Обзор и решение ключевых задач. Прогнозирование времени прохождения маршрута, диспетчеризация. Графический интерфейс системы.
дипломная работа [4,8 M], добавлен 22.06.2012Назначение и типы роботов-андроидов. Функции обнаружения объектов в робототехнике; машинное, электромагнитное зрение, датчики препятствий на ИК лучах. Разработка концептуально-функциональной модели робота типа "шагающий" с функцией обнаружения объекта.
курсовая работа [3,0 M], добавлен 20.12.2012Порядок и назначение разработки подсистемы планирования действий интеллектуального робота. Задачи, решаемые данной подсистемой и функциональные требования к ней. Информационное моделирование функционирования интеллектуального робота и управление им.
дипломная работа [864,0 K], добавлен 10.06.2010Обзор схемы конструкции автоматизированного мобильного робота. Выбор компонентов конструкции. Общая классификация роботов; виды двигателей. Выбор типа микроконтроллера. Осуществление программирования на основе расчётов по математической модели робота.
курсовая работа [1,2 M], добавлен 20.05.2015Особенности создания виртуальных лабораторий с точки зрения дискретной математики. Специфика разработки виртуальной лаборатории, реализующей волновой алгоритм для поиска минимального маршрута и определения метрических характеристик заданного графа.
курсовая работа [3,2 M], добавлен 15.08.2012Математическая модель алгоритма с модификацией муравьиной колонии. Выбор аппаратных и программных средств для разработки программы. Особенность построения оптимального маршрута обхода пациентов. Характеристика тестирования и отладки данного проекта.
дипломная работа [1,9 M], добавлен 17.11.2017Разработка программы, относящейся к классу задач маршрутизации и системы принятия решения, предназначенной для выбора оптимального маршрута перемещения в лабиринте из начальной клетки в конечную, с учетом необходимости посещения определенных клеток.
контрольная работа [14,7 K], добавлен 11.11.2010Анализ техники ходьбы по количеству точек опоры шагающих роботов. Обзор существующих конструкций. Функциональная схема устройства. Выбор электронных компонентов. Трёхмерная модель робота и его модулей. Исследование цифровой системы на устойчивость.
дипломная работа [3,2 M], добавлен 04.08.2014Знайомство з інтерфейсом ОС Linux, робота з довідковою системою Linux. Робота з утилітами командного рядка. Символічні посилання та архівація даних. Пошук файлів за критеріями. Робота з програмою Midnight Commander. Використання офісних додатків.
методичка [396,5 K], добавлен 17.05.2011Середовище програмування Visual Studio 2010. Функції стандартного введення-виведення. Робота з побітовими операціями. Робота з функцією заміни у рядку символів. Робота з масивами. Тестування алгоритму роботи програми. Представлення двовимірного масиву.
курсовая работа [652,2 K], добавлен 15.01.2014Назначение, технические характеристики промышленного робота МП20. Режимы работы робота и кинематическая схема. Приводные электродвигатели. Элементы электроавтоматики. Алгоритм управления следящим цифроаналоговым приводом. Интерфейс станочной магистрали.
курсовая работа [1,7 M], добавлен 15.04.2013Прямая и обратная задача кинематики и позиционирования захвата манипуляционного робота. Разработка алгоритмов и решений, позволяющих организовать процесс нанесения рисунков на поверхность изделия при помощи робота-манипулятора FS03N фирмы Kawasaki.
дипломная работа [4,1 M], добавлен 17.09.2013Сущность теории графов и сетевого моделирования. Выбор оптимального пути и стоимости переезда коммивояжера с помощью метода ветвей и границ. Разработка программы выбора самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу.
курсовая работа [3,5 M], добавлен 08.08.2013Обзор задач, решаемых методом динамического программирования. Составление маршрута оптимальной длины. Перемножение цепочки матриц. Задача "Лестницы". Анализ необходимости использования специальных методов вероятностного динамического программирования.
курсовая работа [503,3 K], добавлен 28.06.2015Составление программы для построения траектории движения захвата манипулятора робота: запись системы линейных алгебраических уравнений, получение коэффициентов. Анимация движения манипулятора. Схема направления движения точки соединения звеньев робота.
лабораторная работа [274,4 K], добавлен 01.12.2013Робота зі сторінками, абзацами та текстом у Microsoft Word, використання таблиць замість символів табуляції, робота з формулами та малюнками. Робота з Microsoft Excel, використання статистичних функцій, вирішення рівнянь, створення адресної книги.
контрольная работа [1,6 M], добавлен 21.04.2011История возникновения сигвея. Аналитическая модель обратного маятника. Практическая реализация управления шаговыми двигателями. Внешний вид драйвера. Гироскоп и его подключение к микроконтроллеру. Метод сетевого планирования. Охрана труда, микроклимат.
дипломная работа [3,8 M], добавлен 24.06.2013Классификация и назначение промышленных роботов. Применение робототехнических комплексов в промышленности. Описание основных узлов пневматического робота, его структурная схема и процессорный модуль. Промышленное программное обеспечение фирмы Siemens.
дипломная работа [3,6 M], добавлен 17.09.2012Разработка и условия использования автоматического строительного робота, который кладет кирпич, использует раствор и 3D-сканнер для определения расположения стен дома. Принцип работы Hadrian, устройство и функции. Создание роботов-термитов, их действие.
презентация [2,9 M], добавлен 24.04.2016
