автореферат диссертации по инженерной геометрии и компьютерной графике, 05.01.01, диссертация на тему:Автоматизация моделирования маршрута движения мобильного транспорта робота на рабочих полях больших размеров

На правах рукописи

УДК 514.18:519.876:621.856.8

РГ5 од - 5 СЕН Ж

Будажапова Бальжима Базаровна

АВТОМАТИЗАЦИЯ МОДЕЛИРОВАНИЯ МАРШРУТА ДВИЖЕНИЯ МОБИЛЬНОГО ТРАНСПОРТНОГО РОБОТА НА РАБОЧИХ ПОЛЯХ БОЛЬШИХ РАЗМЕРОВ

Специальность 05.01.01 - Прикладная геометрия

и инженерная графика

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 2000 г.

Работа выполнена на кафедре "Инженерная и компьютерная графика" Восточно-Сибирского государственного технологического университета.

Научный руководитель - доктор технических наук,

профессор Найханов В.В.

Официальные оппоненты: доктор технических наук,

профессор Бусыгин В.А. кандидат технических наук, Битюков Ю.И.

Ведущая организация: указана в решении специализированного совета

Защита состоится "23" мая 2000г. в /6 часов на заседании диссертационного Совета Д 063.51.07 по специальности 05.01.01 - "Прикладная геометрия и инженерная графика" при Московском Государственном университете пищевых производств в ауд. 504 корп. Д .

Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью, просим присылать по адресу: 125080, Москва, Волоколамское шоссе, 11, МГУПП, отдел Ученого секретаря.

С диссертацией можно ознакомиться в библиотеке МГУПП.

Автореферат разослан "20" апреля 2000г.

Ученый секретарь

диссертационного Совета,

д.п.н., профессорс^^^^^х/ Акимова И.Н.

094-05,0

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Анализ работ показал, что существуют различные методы решения этой проблемы. Но в основном они, как правило, даже не дают 100%-ной гарантии получения правильного ответа на вопрос: « Можно ли вообще добраться из точки старта о точку финиша?» Системы же, позволяющие дать правильный ответ по прокладке маршрута, обладают тем недостатком, что они работают только на рабочих полях небольшого размера. Применение их на пространствах большого размера проблематично. Вопрос разработки метода, позволяющего прокладывать кратчайший, близкий к оптимальному маршрут движения для мобильных роботов, способных перемещаться на большие расстояния, до сих пор остается открытым.

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

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

разработка алгоритма аппроксимации траектории движения геометрическими примитивами, реализуемыми контроллером робота.

Методы исследования. Поставленные в работе теоретические задачи решаются методами начертательной, проективной, вычислительной геометрии. В прикладной части работы при разработке программного обеспечения применялись численные методы и различные методы программирования.

Научная новизна работы заключается:

в разработке способа планирования траектории движения транспортного робота, базирующегося на теории графов и волновом алгоритме Ли;

в разработке способа модернизации волнового алгоритма Ли, позволившего использовать этот метод клеточной декомпозиции пространства при планировании маршрутов движения мобильного робота на полях больших размеров;

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

Практическая ценность.

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

Апробация работы. Результаты, полученные в ходе выполнения диссертационной работы, докладывались на различных конференциях: Всероссийской научной конференции "Роль геометрии в системах искусственного интеллекта и САПР" (Улан-Удэ, 1996); Российской научно-практической конференции "Образование в условиях реформ: опыт, проблемы, научные исследования" (Кемерово, 1997); межвузовской научно-методической конференции «Совершенствование подготовки учащихся и студентов в области графики, конфигурирования и стандартизации» (Саратов, 1998); международной конференции «Наука и образование на рубеже тысячелетий» (Чита, 1999).

Публикации. Результаты теоретических и прикладных исследований опубликованы в 6 научных статьях.

На защиту выносится:

методика определения ориентировочной траектории;

методика построения кратчайшей траектории; методика аппроксимации траектории движения мобильного транспортного робота геометрическими примитивами, реализуемыми контроллером робота;

методика расчетов участков пути, проходимых роботом в момент поворота передних колес;

методика определения ширины коридора безопасности для движения по найденному маршруту.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка использованной литературы и приложения. Работа содержит 110 стра-

ниц основного текста, 27 рисунков, 4 таблицы и 102 наименования использованных литературных источников, приложения.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность исследования, сформулированы цель и основные задачи исследования, их научная новизна и практическая значимость. Приведены сведения о структуре и объеме работы.

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

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

Решение же всей задачи от прокладки маршрута до его реализации предлагается проводить в три этапа:

1. Построение в конфигурационном пространстве свободной от столкновения линии, соединяющей начальную и конечную точки (ориентировочная траектория). Основная цель этого этапа - формирование списка огибаемых роботом препятствий, в котором также должны указываться направления обхода препятствий.

2. Построение кратчайшей траектории.

3. Перевод траектории движения в геометрические примитивы, реализуемые контроллером робота.

Во второй главе рассмотрен разработанный нами способ планирования маршрута движения, основанный на теории графов и стандартном волновом алгоритме Ли. Алгоритм, основанный на теории графов и стандартном волновом алгоритме Ли, создает списки свободных зон, формируя при этом комбинации всех возможных путей достижения цели.

I. Исходное пространство вначале делится на четыре прямоугольника, размеры которых равны половине длин соответствующих сторон исходного пространства. После этого начинается последовательное рассмотрение этих клеток. На рисунках 1 и 2 показаны общий и частный порядки создания и нумерации клеток.

1 2 /

/ 3 -*■ 4

1 -2

/

3 4

— — 7

5

Рис. 1. Порядок рассмотрения областей одного уровня деления

Рис. 2. Общий порядок рассмотрения областей

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

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

к = м-/1, (1)

где - ширина конечной клетки;

/ - размер минимальной клетки. Если конечная клетка содержит часть препятствия или целиком лежит внутри него, то она исключается из списка рассматриваемых клеток. На рисунке 3 показаны только те клетки, которые вошли в список зон.

II. По графам зон, используемых для движения, определяются все возможные пути достижения точки финиша Б из точки старта 8, которые будут представлены несколькими линейными списками зон. На рисунке 3 видно, что линейный список можно записать следующим образом: 38, 40, 45, 99, 97, 98, 14, 5, 4, 1. _

1

Ч и!®,1 15

и 1 п 1--Iй ______1 ГГ 17; Гзт «¡П* ** ___ со я; '' я

" Ъм • [ :е»* Г 1 : к г. ' >1 1 1 1 1Ю

Рис. 3. Области представляющие свободное для движения пространство 8

III. Для каждого полученного списка выполняются следующие действия:

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

б) по этим клеткам запускается волновой алгоритм Ли.

IV. Из всех полученных путей по одному из критериев выбирается кратчайший для движения робота путь. Длина пути или время прохождения между точками S и F минимальна.

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

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

мелкие. Размеры клеток уменьшаются до тех пор, пока они не станут равными клеткам минимального размера.

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

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

1. По определению количества зон в произвольной

клетке.

2. По распространению волны по клеткам, имеющим несколько зон.

3. По определению обратного хода.

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

Г

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

что позволяет значительно повысить быстродействие работы системы.

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

Задачу по определению количества зон предлагается решать следующим образом. Допустим, что эквидистанта контура препятствия имеет форму, показанную на рис. 4. Все точки пересечения эквидистанты с границами клетки нумеруются. Нумерация выполняется таким образом, чтобы общий ход при обходе по контуру препятствия был против часовой стрелки. В качестве первой точки назначается такая точка, которая находится на участке, свободном от препятствия. Тогда количество свободных зон в клетке будет равно количеству участков границы клетки, не занятых препятствием, у которых смежные номера пересечений свободной зоны расположены по возрастающей ( рис. 4). Для приведенного примера количество зон равно трем. Суммарное количество зон (рис. 5) от нескольких препятствий рассчитывается по формуле

Кол. зон общ. = £ Кол. зон. 1 пр. - (Кол. пр. -1), (2)

где Кол. зон общ - количество зон от нескольких препятствий;

ЕКол. зон шр - суммарное количество зон от всех препятствий;

Кол. пр . - количество препятствий, образующих зоны в клетке.

1-4 7-6 5-8 9-10 3-2 1 0 1 1 0=3 Рис. 4. Определение количества

Рис.5. Определение количества

зон, образуемых одним препятст- зон, образуемых группой препяг-вием ствий

В-третьих, после того, как показана возможность определения количества зон в клетке, определяются значения волны в каждой зоне. Для решения этой задачи вначале определяются все точки пересечения границ клетки с эквиди-стантами контуров препятствий. Полученные точки вводятся в точечные базисы по препятствиям. Точки старта и финиша приписываются границам зон, в которых они находятся, для этого они соединяются отрезками с левыми нижними точками клеток, в которых находятся. Если отрезки пересекли какой-либо контур препятствия, то точка старта или финиша, находящаяся в этой клетке, приписывается контуру пересеченного препятствия. В случае, если таких точек окажется несколько, то за приписываемую точку принимается точка, ближайшая к исходной. На рисунке 6а приписанные точки обозначены Б * и Б * . Точки, приписанные контуру препятствия, должны также вводиться в состав его точечного базиса. Все это выполняется для того, чтобы можно было, обходя границу зоны, "увидеть", определено ли значение волны в ней, а если значение волны в анализируемой зоне не определено, то определить его значение. Далее для решения этой задачи предлагается в оперативной

памяти бортовой ЭВМ создать один временный массив точек, в котором будут записаны значения волны. Структура этого массива показана в таблице !. Приведенная таблица заполнена по данным рисунка 6.

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

(2)

Г3>

1 1 1 1

2 2 3 1

1 г 1 1

1 1 2 2

1 г 3 4

Рис.б. Построение ориентировочного маршрута по крупным клеткам: а-изображение рабочей ситуации; б- количество зон по клеткам.

Таблица 1

Номер точки Координаты точки Значение волны Анализируемая клетка Номер точки приписки предыдущей волны

X У столбец строка

Б* 93 41 0 4 3 0

р* 14.27 27.03 0 1 2 0

1 11.36 20.5 1 1 1 р*

2 23.25 11.71 2 2 1 1

3 46.5 12.34 -> .5 3 1 2

4 46.5 3.754 3 3 1 2

Далее в работе рассматривается, как распространяется волна по клеткам. Распространение волны на рабочем поле показано на рисунке 7, за центр волн принимается точка Т\ Обратный ход позволяет строить маршрут робота из точки старта до точки финиша. Далее, если запустить волну на этом же поле, только теперь уже с центром в точке Б, и отследить обратный ход из клетки Б в клетку Б, то полученная в этом случае траектория движения несколько отличается от траектории, запущенной из точки Р. Второй маршрут частично не совпадает с первым. Совместив их, можно легко получить близкий к кратчайшему маршрут, который проходит через точки, обозначенные на рисунке 7 буквами БСБЕОЫУШ К К Р.

На рисунке 7 видно, что волновой алгоритм с двумя обратными ходами позволяет построить кратчайший маршрут. Построение такого маршрута с помощью двух волн, распространяемых поочередно, из точки Р VI из точки Б, является одним из усовершенствований волнового алгоритма Ли. Рисунок 7 показывает, что несовпадающие части маршрутов образуют либо параллелограммы 5 В С А , в 3 Ь Н, либо более сложные фигуры К О Я Т Р Р Также из рисунка видно, что ориентировочная траектория в таких местах "начинается" и "кончается" в точках "схода" этих двух маршрутов. В некоторых случаях кратчайший путь на этом участке сразу же определяется как прямая, соединяющая точки схождения двух маршрутов Б С или ОЬ, а в некоторых случаях она является ломаной КБЛ7 (на рис. 7).

Рис. 7 Формирование ориентировочного маршрута движения робота на базе двух маршрутов, рассчитанных по волновому алгоритму Ли с центрами в клетках Р и Б

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

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

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

го меньше, чем в алгоритме, основанном на теории графов и стандартном волновом алгоритме Ли. Поэтому при планировании маршрута движения мобильного робота на большие расстояния предлагается использовать в работе модернизированный алгоритм Ли.

В третьей главе приведена методика построения кратчайшей траектории. После того, как построена ориентировочная траектория, робот может приступить к построению кратчайшего пути движения. Для построения кратчайшей траектории необходимо определить отрезки прямых, касающихся двух препятствий, которые следуют друг за другом в сформированном списке обхода препятствий, и отрезки прямых, появляющихся при обходе отдельных препятствий от одной точки касания до другой. Методика построения общих касательных приведена в работе [47,48]. Также в кратчайшую траекторию будут входить дуги эквидистантных обводов, расположенных между точками касания.

Далее в работе рассматривается методика аппроксимации кратчайшей траектории движения радиусографическим обводом. Задача по моделированию траектории движения транспортного робота сводится к построению сглаженного обвода, моделирующего траекторию движения средней точки оси задних колес. Аппроксимировать эту траекторию предлагается специальным радиусографическим обводом первого порядка гладкости, когда радиусы аппроксимирующих дуг окружностей принимаются равными только радиусам из специального ряда (рис. 8). Причем смежные дуги должны иметь радиусы, расположенные рядом в специальном ряде радиусов, который формируется с учетом дискретного поворота передних колес и расстояния между осями колес.

к

и

г—-т—-I— .

^01 102 р I

а

б

Рис. 8 Сглаженный обвод, моделирующий траекторию движения транспортного робота: а - траектория движения; б- график радиусов кривизны.

При построении обвода на исходной сглаженной траектории отмечаются места, в которых радиусы кривизны равны табличным значениям. Затем в этих точках через одну строятся соприкасающиеся окружности. Две смежные окружности сопрягаются дугой, радиус которой равен промежуточному табличному значению.

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

ростыо (О пт п к — const . Через некоторое время Ai, передние колеса изменят свое положение относительно продольной оси робота на угол А (р , который равен сопт пк * Д t,

а сам робот проедет расстояние Д S=R¡k*cojk* kt. Базируясь

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

R K*t R "со

Л"'= COS(--:-:-* In/cos(í!>0 + i, * t)/+ +---* ln/cosp0 /) * /-¡ч

В* со В*й)„с

* *<»,,;

R * со .* t R * со

y'= sin(--1-* ln/cos(?>0 + a>,r * i) I+*¥„ н----— * ln/cos^0 /) *

& * m., В* ft),, r

* *<",/.

где (o , r - угловая скорость поворота задних колес;

о) к - угловая скорость поворота передних колес; R3 K - радиус заднего колеса; ¥ - угол касательной к кривой; Ф - угол поворота передних колес; В - база робота.

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

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

стороны от маршрута. Сумма этих расстояний покажет величину коридора безопасности в каждой конкретной точке (рис. 9.). По графикам, характеризующим близость объекта с обеих сторон можно определить в конечном итоге ширину коридора, а по нему можно определить и скорость прохождения на каждом участке маршрута. Это возможно если иметь зависимостьУ(б), где 5 - расстояние от точки маршрута до ближайшей точки препятствия для левой и правой сторон.

Рис. 9. Корректировка маршрута с учетом расстояния до препятствия: а - моделирование реального маршрута движения;

б - график расчетной ширины коридора вдоль маршрута.

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

1. Анализ методов, способов и алгоритмов планирования маршрута движения показал, что наиболее надежным методом, который обеспечивает нахождение маршрута, близкого к кратчайшему, является метод простой

а

б

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

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

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

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

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

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

Основные положения диссертации опубликованы в следующих работах:

1. Будажапова Б.Б. Определение ориентировочной траектории с помощью модернизированного волнового алгоритма Ли и графа зон.// Тез. докл. междунар. конф. «Наука и образование на рубеже тысячелетий». - Чита, 1999, -С.20 - 22.

2. Будажапова Б.Б, Верхотуров А.Н, Бурлаков А.Н. Внедрение элементов инновационного обучения на примере разработки транспортного робота//Тез. Рос. науч.-практ. конф. «Образование условиях реформ: опыт, проблемы, научные исследования». - Кемерово, 1997 - С.68.

3. Найханов В.В., Будажапова Б.Б. Определение кратчайшей траектории движения робота на основе ориентировочной траектории.//Сб. докл. Всеросс. науч. конф. "Роль геометрии в искусственном интеллекте и САПР"/ ВСГТУ - Улан-Удэ, 1996- С. 31-33.

4. Найханова Л.В., Будажапова Б.Б. Состав и структура информации модернизированного волнового алгоритма Ли//Тез. докл. междунар. конф. «Наука и образование на рубеже тысячелетий». - Чита, 1999 - С. 22 -24.

5. Найханова Л.В., Будажапова Б.Б., Найханов В.В. Моделирование прямого и обратного ходов модернизированного волнового алгоритма Ли при работе на полях большого размера// Совершенствование подготовки учащихся и студентов в области графики, конфигурирования и стандартизации: Сб. докл./Саратов, гос. техн. ун. (СГТУ). - Саратов, 1998-С. 68-73.

6. Budazhapova B.B Strategy of determination the path of moving a mobile transport robot by means of the graph of adjacent areas and Lee's wave algorithm// Interactive systems: the problems of human-computer interaction. Proceedings of the International Conference. - Ulianovsk, 1999.

Отпечатано в типографии ВСГТУ. Усл.п.л. 1,39. уч.-изд..1.0,9. Тираж 70 экз.-2000. С. 69.