WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

Величина (К,Pr) названа критерием качества приближенной модели. Очевидно, что 0 (К,Pr) 1. При (К,Pr), близком к 1, имеет место хорошее качество приближения. В случае (К,Pr)=1 приближенная модель является точной для исходного контура. Если (К,Pr) близко к 0, то приближение неудовлетворительное. При (К,Pr)=0 двухмерный вписанный контур вырождается в кривую или точку.

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

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

1. Описанная полигональная модель произвольного контура в виде ломаной (алгоритм АПОПМ).

2. Описанный прямоугольник (АППРМ).

3. Описанная круговая модель произвольного контура (АПОКМ).

4. Одиночный вписанный выпуклый многоугольник (АПВВОК). В нем использованы вспомогательный алгоритм вычитания односвязных контуров (АВОК).

5. Полное покрытие контура вписанными полигонами (АПВВМК).

Результаты применения алгоритмов АПОПМ, АПОКМ и АПВВМК к исходным контурам объектов даны на рис. 2, 3, 4.

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

- 7-

Рис. 2. Результат АПОПМ Рис. 3. Результат АПОКМ

Рис. 4. Результат применения алгоритма АПВВМК

По разработанным алгоритмам создана библиотека программ Method на языке С++, позволяющая выполнять моделирование объектов внешней среды в режиме реального времени.

Третья глава посвящена построению структурной и программной реализации моделей МР и внешней среды. Введены понятия исходной и расширенной структурных моделей. С использованием принципов объектно-ориентированного программирования и особенностей языка С++ дана программная модель внешней среды. На основе библиотеки Method разработан общий алгоритм ее формирования.

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

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

Во внешней среде выделяется допустимая область (граница которой названа базовым контуром), в которой допускается перемещение тележки МР. Область может содержать внутри себя препятствия, среди которых выделены преодолимые и непреодолимые.

- 8 -

Первые создают затруднения при движении, но могут быть преодолены МР при движении на пониженной скорости. К ним относятся невысокие пороги и ступени, неглубокие впадины, пандусы с малыми уклонами и т.д.

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

В решаемой задаче расширенная модель включает:

1. Модифицированный исходный базовый контур и исходные контуры препятствий,

2. Приближенные модели на базовом контуре (выпуклые многогранники оптимального выпуклого вписанного образа и круговые модели вписанных выпуклых многогранников).

3. Приближенные модели препятствий (оптимальный описанный выпуклый многогранник и оптимальную описанную круговую модель).

4. Приближенную круговую модель мобильного робота.

Для хранения и преобразования всех данных модели разработан класс Cоntour. Данные расширенной модели являются его закрытыми членами.

Для формирования расширенной модели по заданной исходной разработана функция-конструктор Box.

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

struct BcNp - структура, содержащая все данные по базовому контуру и непреодолимым препятствиям:

  1. исходную модель базового контура,
  2. приближенную модель базового контура,
  3. исходные модели непреодолимых препятствий,
  4. приближенные описанные круговые модели непреодолимых препятствий,
  5. приближенные описанные выпуклые полигональные модели непреодолимых препятствий.

struct Pp – структура с данными по преодолимым препятствиям:

  1. исходные модели преодолимых препятствий,
  2. приближенные описанные круговые модели преодолимых препятствий,
  3. приближенные описанные выпуклые полигональные модели преодолимых препятствий.

struct Tra - структура, содержащая параметры допустимой опорной ломаной.

- 9 -

Формирование структур BcNp и Pp осуществляется в функции Box. Структуры типа Tra строятся в процессе решения задачи маршрутизации. Блок-схема функции Box приведена на рис. 5.

Рис. 5. Блок-схема работы функции Box

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

Для передачи и последующей обработки (в составе структур BcNp и Pp) закрытых данных класса Cоntour в него добавлены специальные функции GetLenghParameterOpen и GetArrayParameterOpen.

Четвертая глава посвящена разработке специальных методов расчета взаимодействия исходных и приближенных моделей объектов внешней среды с моделью МР и порождаемыми ею ломаными линиями.

Необходимость в данных методах вызвана тем, что реальное МР имеет габариты, соизмеримые с размерами объектов внешней среды. Поэтому его нельзя считать материальной точкой. Также нельзя пренебрегать шириной ометаемой полосы, необходимой МР для движения.

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

1. Определения пересечения круга со звеном контура (функция IntCirContBound).

2. Определение пересечения отрезка с кругом (IntStripCir).

3. Проверка попадания точки внутрь контура (IntPointContIn)

4. Определение ближайшего пересечения линии отрезка с контуром точки, а также расчета точки выхода (EntStripCont).

- 10 -

5. Определение пересечения полосы с базовым контуром и непреодолимыми препятствиями (IntLineBcNp).

6. Определение пересечения полосы с преодолимыми препятствиями (IntLinePp).

7. Определение попадания круга в преодолимые препятствия (IntCirPp).

8. Определение выхода заданной ломаной из группы преодолимых препятствий (EntBrGrPp).

9. Определение пересечения выпуклого полигона с полосой (IntersStripPol).

10. Определение пересечения произвольного контура с полосой (IntersStripCont).

11. Определение пересечения произвольного полностью закрытого контура с полосой (IntersStripContClosed).

12. Определение пересечения произвольного контура с кругом (IntersCirCont).

13. Определение пересечения полигона с кругом (IntersCirPol).

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

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

Опорная ломаная задает примерную траекторию движения идеального геометрического центра МР. Реальная тележка МР имеет вполне определенные геометрические размеры. Они учитываются радиусом rt приближенной круговой модели. Полосу, которую ометает на плоскости круг радиуса rt при движении его центра по опорной ломаной Lm, назовем следом опорной ломаной Lm и обозначим через Tr(Lm ).

В качестве оценки оптимальности рассмотрены: 1) минимум затрат времени на прохождение по опорной ломанной или 2) минимум затрат энергии.

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

Обозначим часть плоскости ограничиваемую замкнутым контуром K, через П(K,), а ее объединение с K – через ГП(K,).

- 11 -

Основная задача поиска оптимальной опорной ломаной сформулирована следующим образом.

I. Управляемые параметры :

1. Число точек опорной ломаной nv

2. Множество координат ее вершин {V} = {Vi, i= 1,…, nv } (3.а)

II. Неуправляемые параметры:

1. Радиус круговой модели МР rt,

2. Замкнутая ломаная Bc, описывающая базовый контур, а также вектор свойств ее звеньевL,

3. Множество замкнутых ломаных {Nр} = {Nрk, 1 k Nnp}, описывающих непреодолимые препятствия, и векторы свойств их звеньев,

4. Множество замкнутых ломаных {Pр} = {Ррj, 1 j Npp}, описывающих преодолимые препятствия а также вектор коэффициентов затруднения движения по ним Q={ qj 1 j Npp }.

III. Ограничения задачи.

1. След Lm лежит внутри базового контура: Tr(Lm ) П(Bc); (3 б)

2. След Lm не должен пересекать закрытые звенья (границу) базового контура : Tr(Lm ) Bc =; (3 в)

3. След Lm не должен пересекаться ни с непреодолимыми препятствиями ни с закрытыми звеньями базового контура:

Tr(Lm ) ГП({Nр}) =, Tr(Lm)Вс=. (3 г)

IV. Целевая функция и критерий ее оптимальности.

, (3 д)

где w i = q j, если Tr(li ) ГП(Ррj), (1 j Npp),

w i= 1, если Tr(li ) П(Bc) \ { ГП(Pр)}, (1 j Npp).

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

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

В рассматриваемой задаче форма границ Bc, {Nр} и {Pр}, а также вектор коэффициентовQ могут быть произвольными. Возможна ситуация, когда допустимых решений ее вообще не существует (МР не может преодолеть препятствия на пути из начальной в конечную точку).

Поэтому полное точное решение задачи (3) заключается:

- 12 -

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

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

При этом требование глобальной оптимальности получаемого решения заменяется его локальной минимальностью.

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

Целевая функция вспомогательной задачи и критерий ее оптимальности.

(4)

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

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

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

Для практической реализации предложенных методов создана библиотека программ TRACE на языке С++, включающая:

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

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

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

- 13 -

Рис. 6. Блок-схема алгоритма приближенного решения основной задачи построения оптимальных опорных ломаных

Пример. В качестве примера рассмотрена складская территория. Ее внутренняя область ограничена базовым контуром, внутри находятся 3 непреодолимых и 5 преодолимых препятствий, обозначенных соответственно np и pp. Необходимо с помощью предложенного метода маршрутизации построить оптимальную опорную ломаную для перевода из начальной точки Рнач =(100;230) в конечную точку Ркон=(320; 10) тележки прямоугольной формы, размеры которой следующие: длина 2 м, ширина – 1,3 м.

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

а) б)

Рис. 7. Оптимизированный вариант участков ломаной

- 14 -

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

Значения критерия по всем построенным допустимым ломаным следующие: 0) 514,950; 1) 420,870; 2) 638,067; 3) 420,099.

Наименьшее значение целевой функции у третьей допустимой ломаной (рис. 8). Она и принимается в качестве искомого приближенного решения основной задачи.

Рис. 8. Построение третьей допустимой ломаной

В заключении представлены основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В диссертации разработаны математические методы и программные средства решения задач маршрутизации в автоматизированных транспортных системах химических производств.

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.