Содержание к диссертации
Введение
Глава I Методы, способы и алгоритмы планирования траектории движения мобильных транспортных роботов
1.1 Методы планирования маршрута движения мобильного транспортного робота, используемые в недетерминированной среде...
1.2 Методы планирования маршрута движения мобильного транспортногр робота, используемые в детерминированной среде
1.3 Постановка задач
Глава II Модернизация алгоритма Ли с целью его распространения на рабочем поле большого размера
2.1 Определение маршрута движения на базе волнового алгоритма Ли и графа зон Ь&
2.2 Модернизация волнового алгоритма Ли для применения на рабочих полях больших размеров
2.3 Методика построения ориентировочного маршрута УІ
Глава III Моделирование траектории движения мобильного транспортного робота
3.1 Методика построения кратчайшей траектории движения транспортного робота з
3.2. Аппроксимация траектории движения специальным радиусографическим обводом
3.3 Методика определения ширины коридора, обеспечивающего безопасность движения транспортного робота по маршруту 405
Заключение /У/
Список литературы
- Методы планирования маршрута движения мобильного транспортногр робота, используемые в детерминированной среде
- Постановка задач
- Модернизация волнового алгоритма Ли для применения на рабочих полях больших размеров
- Аппроксимация траектории движения специальным радиусографическим обводом
Введение к работе
Актуальность темы исследования. В настоящее время уровень автоматизации вспомогательного труда существенно ниже уровня автоматизации основного производства. Поэтому одним из важных направлений автоматизации сферы производства является направление по созданию автоматизированных систем для вспомогательного производства. Особое положение в этой области транспортных систем занимает разработка научных основ проектирования мобильных транспортных роботов и роботизированных транспортных комплексов различного назначения, отвечающих технологическим, конструктивным требованиям.
Одним из преимуществ автоматизации транспортных средств является сокращение времени ожидания грузов на * рабочих местах и сокращение затрат энергии за счет эффективного планирования маршрутов движения. Поэтому в системе управления мобильным транспортным роботом одно из основных мест занимает алгоритм прокладки трассы, цель которого заключается в формировании маршрута перемещения робота во внешней среде.
Анализ работ показал, что существуют различные методы решения этой проблемы. Но в основном они, как правило, даже не дают 100%-ной гарантии получения правильного ответа на вопрос: « Можно ли вообще добраться из точки старта о точку финиша?» Системы лее, позволяющие дать правильный ответ по прокладке маршрута, обладают тем недостатком, что они работают только на рабочих полях небольшого размера. Применение их на пространствах большого размера проблематично. Вопрос разработки метода, позволяющего прокладывать кратчайший, близкий к оптимальному маршрут движения для мобильных роботов, способных перемещаться на большие расстояния, до сих пор остается открытым.
Целью исследования является разработка и исследование методики планирования маршрута движения мобильного транспортного робота на рабочих полях больших размеров.
Основные задачи исследования:
- разработка и исследование способов, автоматизирующих процесс построения кратчайшего ориентировочного маршрута на полях большого размера, с целью составления списка огибаемых препятствий и определения направления стороны их обхода;
разработка алгоритма аппроксимации траектории движения геометрическими примитивами, реализуемыми контроллером робота.
Методы исследования. Поставленные в работе теоретические задачи решаются методами начертательной, проективной, вычислительной геометрии. В прикладной части работы при разработке программного обеспечения применялись численные методы и различные методы программирования.
Научная новизна работы заключается:
в разработке способа планирования траектории движения транспортного робота, базирующегося на теории графов и волновом алгоритме Ли;
в разработке способа модернизации волнового алгоритма Ли, позволившего использовать этот метод клеточной декомпозиции пространства при планировании маршрутов движения мобильного робота на полях больших размеров;
в разработке способа моделирования траектории движения мобильного транспортного робота.
Практическая ценность.
Результаты исследований, выполненных в диссертационной работе, были внедрены в НИИ. Реально действующие системы и пакеты программного обеспечения используются в научно-исследовательских работах,, а также в учебном процессе. Имеются акты внедрения.
Апробация работы. Результаты, полученные в ходе выполнения диссертационной работы, докладывались на различных конференциях: Всероссийской научной конференции "Роль геометрии в системах искусственного интеллекта и САПР" (Улан-Удэ, 1996); Российской научно-практической конференции "Образование в условиях реформ: опыт, проблемы, научные исследования" (Кемерово, 1997); межвузовской научно-методической конференции «Совершенствование подготовки учащихся и студентов в области графики, конфигурирования и стандартизации» (Саратов, 1998); международной конференции «Наука и образование на рубеже тысячелетий» (Чита, 1999).
Публикации. Результаты теоретических и прикладных исследований опубликованы в 6 научных статьях. На защиту выносится:
методика определения ориентировочной траектории;
методика построения кратчайшей траектории;
методика аппроксимации траектории движения мобильного транспортного робота геометрическими примитивами, реализуемыми контроллером робота;
методика расчетов участков пути, проходимых роботом в момент поворота передних колес;
методика определения ширины коридора безопасности для движения по найденному маршруту.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка использованной литературы и приложения. Работа содержит ПО стра-
ниц основного текста, 27 рисунков, 4 таблицы и 102 наименования использованных литературных источников, приложения.
Методы планирования маршрута движения мобильного транспортногр робота, используемые в детерминированной среде
Методы исследования. Поставленные в работе теоретические задачи решаются методами начертательной, проективной, вычислительной геометрии. В прикладной части работы при разработке программного обеспечения применялись численные методы и различные методы программирования. Научная новизна работы заключается: в разработке способа планирования траектории движения транспортного робота, базирующегося на теории графов и волновом алгоритме Ли; -в разработке способа модернизации волнового алгоритма Ли, позволившего использовать этот метод клеточной декомпозиции пространства при планировании маршрутов движения мобильного робота на полях больших размеров; -в разработке способа моделирования траектории движения мобильного транспортного робота.
Практическая значимость. Результаты исследования позволили разработать методику прокладки маршрута движения мобильного транспортного робота, которая может успешно использоваться в производственных условиях. Реализация работы. Результаты исследований, выполненных в диссертационной работе, были внедрены в НИИ и в учебный процесс. Реально действующие системы и пакеты программного обеспечения используются в научно-исследовательских работах, а также в учебном процессе. Имеются акты внедрения.
На защиту выносятся: - методика определения ориентировочной траектории; - методика построения кратчайшей траектории; - методика аппроксимации траектории движения мобильного транспортного робота геометрическими примитивами, реализуемыми контроллером робота; - методика расчетов участков пути, проходимых роботом в момент поворота передних колес; - методика определения ширины коридора безопасности для движения по найденному маршруту.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка использованной литературы и приложения. Работа содержит ПО страниц основного текста, 27 рисунков, 4 таблицы и 102 наименования использованных литературных источников, приложения.
В первой главе диссертации проведен анализ отечественных и зарубежных работ, посвященных существующим методам планирования траектории движения мобильного транспортного робота. Проведенный анализ показал, что необходимо разработать методику планирования траектории движения на больших расстояниях, которая позволяет находить кратчайший маршрут. Во второй главе рассматриваются алгоритм планирования траектории движения, основанный на теории графов и стандартном волновом алгоритме Ли, и способы модернизации волнового алгоритма. Целью модернизации является устранение основного недостатка метода клеточной декомпозиции, а именно низкого быстродействия из-за необходимости обработки большого объема информации, не позволяющего применить этот метод на рабочих полях больших размеров. В третьей главе приведена методика построения кратчайшей траектории движения, описана методика аппроксимации траектории движения радиусографическим обводом, рассматривается методика определения ширины коридора, обеспечивающего безопасность движения по маршруту.
Разработка методики автоматического планирования маршрута движения мобильного транспортного робота в среде с препятствиями решалась на базе научных исследований, проведенных учеными Ли Ц.И., Охоцимского Д.Е., Платонова А.К., Кирильченко А.А., Найханова В.В., Мартынюка В.В., Гонсалеса Р., Телешева Н.С, Фролова С.А., Якунина В.И., Рыжова Н.Н., Иванова Г.С. и других.
Постановка задач
В случае, когда мелких клеток может быть настолько много, что возможна нехватка памяти, производится запуск алгоритма дополнительного разбиения клеток. Суть алгоритма заключается в том, что клетки, имеющие самую наименьшую глубину деления, подвергаются объединению, то есть понижению уровня на единицу. При этом для исходной последовательности зон получается несколько новых последовательностей, и для каждой из них выполняются действия III и VI вышеописанного алгоритма. По завершении пункта VI будет найден наиболее оптимальный путь в исходной последовательности зон. Он запоминается как кратчайший маршрут. Далее следует выход из алгоритма дополнительного разбиения клеток и возврат к алгоритму, который его вызвал.
В реальных ситуациях размер "маленьких" клеток редко кратен линейным размерам рабочего пространства. Поэтому перед началом поиска кратчайшего пути производят подгон размеров рабочего пространства. Подгонка производится таким образом, чтобы количество клеток вдоль каждой стороны было кратно двум потому, что применяется половинное деление прямоугольников, а размеры полученных таким образом прямоугольников тоже должны быть кратны размерам "маленьких" клеток. При планировании маршрута дополнительного пространства предполагается, что оно занято под препятствие.
Подгон размера рабочего пространства производится для исключения ошибок моделирования маршрута путем искусственного добавления дополнительного пространства.
Использование этого способа для определения траектории движения робота позволяет находить наиболее оптимальный путь. При применении этого метода устраняется основной недостаток теории графов, а именно: используются только те графы, которые достигают цели, другие же графы в список не включаются. Это позволяет существенно уменьшить количество рассматриваемых вариантов. Но этот метод обладает одним недостатком, который заключается в том, что при его использовании на большие расстояния, такие, как город, количество рассматриваемых клеток намного увеличивается, что приводит к расходу большого объема памяти.
Для того, чтобы приспособить волновой алгоритм для работы на рабочих полях больших размеров, предлагается решить данную задачу последовательно в несколько этапов. На первоначальном этапе задачу прокладки маршрута можно решать на поле с клетками больших размеров. Затем полученное решение можно уточнить, разбив клетку или клетки на более мелкие. Размеры клеток можно уменьшать до тех пор, пока они не станут равными клеткам стандартного алгоритма Ли.
При этом на каждом следующем этапе анализа рабочего пространства на клетках меньшего размера рассматривается не все рабочее пространство, а только те клетки, через которые прошла траектория, смоделированная на предыдущем этапе. Причем эти клетки анализируются не все сразу вместе, а по частям. На наш взгляд, такое поэтапное решение задачи по планированию траектории движения является оправданным по следующим соображениям:
1. На первоначальном этапе принципиально важно определить, можно ли из пункта "старт" переместиться в пункт "финиш". Если это возможно, то важно определить, в каком направлении нужно начать двигаться, чтобы достичь цели. А эту задачу как раз можно разрешить, работая с клетками больших размеров. Использование клеток больших размеров позволяет ЭВМ использовать при решении задачи меньший объем памяти, вследствие чего увеличивается быстродействие.
2. При работе программного обеспечения на следующих этапах прокладки маршрута появляются более мелкие клетки. Для уточнения маршрута на клетки меньшего размера делится не все пространство, а только те клетки, по которым проходит ориентировочный маршрут. Кроме того, при уточнении маршрута можно делить не все клетки сразу, по которым прошел ориентировочный маршрут, а уточнять маршрут частями. Использование такого приема позволяет значительно уменьшить анализируемые массивы информации при уточнении маршрута движения. Причем вложенность циклов по уменьшению клеток, как отмечалось выше, может быть какой угодно. Это, в свою очередь, позволяет в нужных участках маршрута последовательно анализировать ситуацию до мельчайших подробностей.
Модернизация волнового алгоритма Ли для применения на рабочих полях больших размеров
В предыдущем параграфе была рассмотрена модернизация волнового алгоритма Ли для применения на полях большой размерности. Теперь рассмотрим процесс распространения волны по этим клеткам.
При декомпозиции поля на клетки им присваивается признак наличия в них препятствий. Часть клеток, которые попали на препятствия, считаются занятыми, а остальные свободными. Затем из клетки, в которой присутствует точка финиша - F, запускается волна согласно правилу Ли. Эта процедура распространения волны осуществляется до тех пор, пока она не достигнет клетки с точкой старта - S. Далее осуществляется обратный ход по волновому полю. Обратный ход осуществляется в сторону максимального понижения значения волны рис. 28. Одним из усовершенствований алгоритма Ли, внесенного нами, является то, что программа при выборе продолжения маршрута движения должна анализировать разницу между значениями волны в клетках. Эта разница не должна превышать число, равное двум. Контроль на превышение разницы двум осуществляется для того, чтобы избежать ошибки при моделировании маршрута. Одновременно этот контроль позволяет строить маршрут, который имеет восемь направлений движений (стандартный же алгоритм Ли позволяет рассчитывать ориентировочные маршруты, в которых возможны только четыре направления движения). На рис. 28 приведен пример, когда контроль за не превышением разницы больше двух между весами волн в соседних клетках позволяет исключить возможность неправильного моделирования маршрута. Движение из клетки (i=4, j=5, вес волны=8) в клетку (i=3, j=4, вес волны=2) невозможно из-за превышения разницы значений волн 8-2 = 6 2.
Выше было отмечено, что на первом этапе решения задачи по автоматической прокладке траектории движения подвижного робота необходимо сформулировать список огибаемых препятствий с учетом очередности их обхода и с указанием стороны огибания. Пока же, из приведенного выше материала, трудно представить, как можно решить данную задачу. Поэтому продолжим рассуждения, нацеленные на ее решение. Для этого рассмотрим рабочее пространство, на котором точки старта, финиша и конфигурация препятствий имеют положение и вид, приведенный на рис. 29. Распространим волну на этом рабочем пространстве, за центр волн примем точку F. Обратный ход позволит построить маршрут робота из точки старта в точку финиша. Далее, если запустить волну на этом же поле, только теперь уже с центром в точке S и отследить обратный ход из клетки F в клетку S (рис. 30), то можно увидеть, что полученная в этом случае траектория движения несколько отличается от траектории, приведенной на рис. 29. Второй маршрут частично совпадает с первым, а частично не совпадает. Совместив эти два маршрута движения, можно легко получить маршрут, близкий к кратчайшему. Этот маршрут проходит через точки, обозначенные на рис. 31 буквами S, С, D, Е, G, L, М, N, К, R, F.
Рисунок 31 хорошо показывает, что волновой алгоритм с двумя обратными ходами позволяет построить маршрут, близкий к кратчайшему, при обходе различных препятствий. А по рис. 32 видно, что эта же задача легко реализуется и при прокладке маршрута в сложном пространстве. Построение маршрута, близкого к кратчайшему, с помощью двух волн, распространяемых поочередно, из точки F и из точки S является нашим вторым усовершенствованием волнового алгоритма Ли. Из рисунка 31 видно, что несовпадающие части маршрутов образуют либо
Аппроксимация траектории движения специальным радиусографическим обводом
Для транспортных роботов, работающих в пространствах с препятствиями, важной задачей является задача по определению ширины коридора, которая позволила бы огибать препятствия и легко вписываться в свободное пространство между ними. Для определения ширины коридора возникает необходимость расчета наружного радиуса (Дбез.нар) и внутреннего (Кбез.внутр.) [1,52,89]. Но прежде, чем перейти к расчету ширины коридора введем условные обозначения основных геометрических параметров транспортного средства (рис.43).
На этом рисунке 43 показано схематичное изображение мобильного колесного робота в тот момент, когда его передние колеса отклонены на некоторый угол от направления его продольной оси. Глядя на этот рисунок можно утверждать, что характерными точками, которые определяют ширину коридора, по которому будет перемещаться мобильный робот, являются точки D и Т. Ширина же необходимого коридора, или другими словами ширина огибающей поверхности на виде сверху, равна разности радиусов RBHem и RBHyTp Из рисунка также видно, что по радиусу RBHein перемещается точка Т, а по RBHyip точка D. Здесь также следует отметить, что при этом расчетная точка робота - Н перемещается по дуге расчетного
Определение параметров, регулирующих ширину коридора безопасности № радиуса RpaC4. Величину радиуса RBHem равного длине отрезка ОТ можно рассчитать по формуле я_= +%)2+я2; (із) где h - габаритная ширина робота; g - расстояние от оси задних колес до переда робота. Внутренний же радиус рассчитывается следующим образом Естественно, для повышения безопасности движения необходимо предусмотреть расстояния, которые обеспечивали бы зазор между роботом и предметами, мимо которых он перемещается. Обозначим их через AhBHem - внешний зазор и AhBHyTp - зазор с внутренней стороны. Обозначения «внутренний» и «внешний» приняты по отношению к центру кривизны. Сторона робота, расположенная ближе к центру будет внутренней, а дальняя от центра, соответственно, внешней. Тогда ширину безопасного коридора можно рассчитать как сумму кор.безоп. Цнеш. "внутр. (15) № в свою очередь, hemtu, и hmym„ Можно рассчитать по формулам: "внеш. К-внеш. К-расч +Z1 гівнеш. (16) U = U/2 + Л U где A hemuL и Л Нвнутр должны определяться экспериментальным путем.
На наш взгляд, эти величины могут зависеть от скорости движения, от того, насколько близки у мобильного робота расчетная и реальная траектории движения. Естественно, что эти величины не являются постоянными, они должны увеличиваться в зависимости от величины отхождения реальной траектории от расчетной по мере движения по маршруту.
С учетом последних рассуждений ясно видно, что в момент уточнения траектории движения к контурам препятствий необходимо уже строить квазиэквидистанты величина их отстояния каждой ее точки от контура будет равна либо Ьвнеш (для точек внутреннего контура препятствия), либо вдоль траектории движения, а также зная с какой скоростью будет двигаться робот по рабочему полю, и зная точки, в которых робот будет уточнять свое положение в пространстве, можно к препятствиям построить квазиэквидистанты, которые реально и будут выступать в качестве «контуров» препятствий.
На самом же деле гораздо более важна другая задача, решение которой позволило бы не только пройти роботу по маршруту, но и пройти с максимально возможной скоростью. А это можно, сделать если известна кратчайшая траектория и известны зависимости, определяющие Ьвнеш и Іівнутр, которые, в свою очередь, и определяет ширину коридора безопасности.
Тогда, имея кратчайшую траекторию, можно, следуя по маршруту с небольшим шагом, в каждой его точке определить кратчайшие расстояния до ближайших препятствий по обе стороны от маршрута. Сумма этих обоих расстояний и покажет величину коридора безопасности в каждой конкретной точке. Это позволит определить зависимость, приведенную на рисунке 44. Эта зависимость позволит определить в конечном итоге пвнеш и Ьвнутр по которым и можно будет определить наилучшую скорость прохождения на каждом участке маршрута.