авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |   ...   | 9 |

«М.С. Корытов АВТОМАТИЗАЦИЯ СИНТЕЗА ОПТИМАЛЬНЫХ ТРАЕКТОРИЙ ПЕРЕМЕЩЕНИЯ ГРУЗОВ МОБИЛЬНЫМИ ГРУЗОПОДЪЕМНЫМИ КРАНАМИ В НЕОДНОРОДНОМ ОРГАНИЗОВАННОМ ...»

-- [ Страница 3 ] --

Таблица 3.1. Классификационные признаки критериев эффективности алгоритмов Классификационный 1 2 3 4 признак (обоб Локальный (частный) Детерминированный Экспериментальный Информационный Количественный Стохастический Аналитический Операционный Качественный Точностный Глобальный щенный) Название критерия 1. ПОЛНОТА + + + + + + + 2. ОПТИМАЛЬНОСТЬ + + + + + + + 2.1. Абсолютная погрешность результи + + + + + рующей величины алгоритма 2.1.1. МО абсолютной погрешности + + + + + 2.1.2. ДИ абсолютной погрешности + + + + + 2.2. Относительная погрешность (к услов + + + + + ному глобальному оптимуму) 2.2.1. МО относительной погрешности + + + + + 2.2.2. ДИ относительной погрешности + + + + + 3. ВРЕМЕННАЯ СЛОЖНОСТЬ + + + + + + + 3.1. Время расчетов + + + + + 3.1.1. МО времени расчетов + + + + + 3.1.2. ДИ времени расчетов + + + + + 3.2. Количество шагов алгоритма + + + + + + 3.2.1. МО количества шагов алгоритма + + + + + 3.2.2. ДИ количества шагов алгоритма + + + + + 3.3. Количество строк выполняемого кода + + + + + + 3.3.1. МО количества строк кода + + + + + 3.3.2. ДИ количества строк кода + + + + + 3.4. Асимптотическая временная сложность + + + + + + Окончание табл. 3. Классификационный 1 2 3 4 признак (обоб Локальный (частный) Детерминированный Экспериментальный Информационный Количественный Стохастический Аналитический Операционный Качественный Точностный Глобальный щенный) Название критерия 4. ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ + + + + + + + 4.1. Информационная длина алгоритма + + + + + + 4.2. Количество входных величин алгоритма + + + + + + 4.3. Количество выходных величин алго + + + + + + ритма 4.4. Количество используемых констант + + + + + + 4.5. Количество строк программы + + + + + + 4.6. Объем информации, занимаемой кодом + + + + + + программной реализации на носителе 4.7. Асимптотическая пространственная + + + + + + сложность 5. КОРРЕКТНОСТЬ + + + + + 6. УСТОЙЧИВОСТЬ + + + + + + 6.1. Критерий устойчивости по Ляпунову + + + + + + 6.1.1. МО критерия по Ляпунову + + + + + 6.1.2. ДИ критерия по Ляпунову + + + + + 6.2. Критерий устойчивости по Найквисту + + + + + + 6.2.1. МО критерия по Найквисту + + + + + 6.2.2. ДИ критерия по Найквисту + + + + + 6.3. Асимптотическая устойчивость + + + + + + 7. СХОДИМОСТЬ + + + + + + 7.1. Скорость сходимости + + + + + + 7.1.1. МО скорости сходимости + + + + + 7.1.2. ДИ скорости сходимости + + + + + 7.2. Интервал сходимости + + + + + + 7.2.1. МО интервала сходимости + + + + + 7.2.2. ДИ интервала сходимости + + + + + На рис. 3.5 изображено дерево иерархических связей глобальных и частных критериев по степени обобщения, по признаку математиче ской природы и по целевому признаку. Блоки глобальных критериев выделены затемнением. Используемые частные критерии выделены полужирным шрифтом.

Глобальные критерии оценки эффективности алгоритмов Информационные критерии Операционные критерии Точностные критерии Пространственная сложность Временная сложность Время расчетов Информационная длина алгоритма МО времени расчетов Количество входных величин алгоритма ДИ времени расчетов Количество выходных величин алгоритма Количество шагов алгоритма Количество используемых констант МО количества шагов алгоритма Количество строк программы ДИ количества шагов алгоритма Объем информации, занимаемой кодом Количество строк выполняемого кода программной реализации на носителе МО количества строк кода Асимптотическая пространственная ДИ количества строк кода сложность Асимптотическая временная сложность Нечисловые (качественные) критерии Числовые (количественные) критерии Полнота Сходимость Скорость сходимости МО скорости сходимости Корректность Устойчивость ДИ скорости сходимости Интервал сходимости Оптимальность МО интервала сходимости ДИ интервала сходимости Абсолютная погрешность результирующей величины алгоритма Критерий устойчивости по Ляпунову МО абсолютной погрешности МО критерия по Ляпунову ДИ абсолютной погрешности ДИ критерия по Ляпунову Относительная погрешность (к условному Критерий устойчивости по Найквисту глобальному оптимуму) МО критерия по Найквисту МО относительной погрешности ДИ критерия по Найквисту ДИ относительной погрешности Рис. 3.5. Дерево иерархических связей глобальных и частных критериев по пер вому, третьему и пятому классификационным признакам На рис. 3.6 изображено дерево иерархических связей частных критериев по характеру проведения исследований и получения ре зультатов и по признаку наличия/отсутствия элементов вероятностно го характера при задании исходных данных. Блоки используемых ча стных критериев выделены затемнением.

Всего в настоящей монографии использовано 3 самостоятельных частных численных критерия оценки эффективности алгоритмов и методик на их основе: T р – математическое ожидание значения вре мени расчетов, с;

M e – информационная длина исследуемого алго ритма (требуемый объем памяти, занимаемой всеми массивами и пе ременными алгоритма при его реализации), байт;

Lусл – математиче ское ожидание значения относительной погрешности к условному глобальному оптимуму, %.

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

Математическое ожидание значения времени расчетов T р опре деляется по зависимости T р = (T р )i, 1 ne (3.23) ne i = где Tр – время расчетов для отдельного эксперимента, с;

ne – число независимых экспериментов.

Требуемый объем памяти, занимаемой всеми массивами и пере менными алгоритма при его реализации M e, определяется как сумма объемов памяти, необходимой для размещения всех массивов и пере менных, объявленных в программной реализации алгоритма:

Me = (mm) j + (mp )k, pe me (3.24) j =1 k = где mm – объем памяти, занимаемый отдельным массивом данных, байт;

me – количество массивов данных алгоритма;

mp – объем памя ти, занимаемый отдельной переменной, байт;

pe – количество пере менных алгоритма.

Математическое ожидание значения относительной погрешности к условному глобальному оптимуму Lусл определяется по зависимо сти 1 ne Lусл = (Lусл )i, (3.25) ne i = где Lусл – относительная погрешность к условному глобальному оп тимуму, определенная для отдельного эксперимента, %.

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

Таблица 3.2. Принятые критерии оценки эффективности алгоритмов и методик Аналитическое Название критерия Параметры выражение Tр – время расчетов для от 1. Математическое ожи ( )i ne дельного эксперимента, с;

дание значения времени T р = 1 Tр ne – число независимых ne i = расчетов T р экспериментов mm – объем памяти, зани 2. Информационная длина маемый отдельным масси исследуемого алгоритма вом данных, байт;

me – ко Me (требуемый объем па- личество массивов данных ( )k pe me Me = (mm ) j + mp алгоритма;

mp – объем па мяти, занимаемой всеми массивами и переменны- мяти, занимаемый отдель j=1 k= ми алгоритма при его реа- ной переменной, байт;

pe – лизации) количество переменных ал горитма 3. Математическое ожи Lусл – относительная по ne дание значения относи (Lусл )i тельной погрешности к Lусл = ne грешность к условному гло бальному оптимуму для от i = условному глобальному дельного эксперимента, % оптимуму Lусл Задачу выбора оптимальной методики предлагается свести к за даче оптимизации с векторной целевой функцией из трех компонент [211, 213, 253]: r GTML =[ T р Me Lусл ]. (3.26) Относительная значимость компонент в общем случае заранее не определена. Компоненты вектора (3.26) являются конкурирующими, поэтому отсутствует единственное решение поставленной задачи. В этом случае может быть определено подмножество неулучшаемых методик, оптимальных по Парето [211, 213, 253].

Пусть имеется некоторое множество методик решения постав ленной задачи в критериальном пространстве компонент вектора (3.26) ={Метi}, i[1;

Nмет], (3.27) где Метi – отдельная методика;

Nмет – общее число рассматривае мых методик.

Для каждой из методик множества известны численные значе r ния компонент векторной целевой функции ( GTML )i вида (3.26).

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

1. Задание исходных данных: максимальных предельных значе ний частных критериев ( T р )max;

(Me)max;

( Lусл )max, значений шагов дискретизации частных критериев ( T р );

(Me);

( Lусл ) и множества r векторов {( GTML )i}, i[1;

Nмет].

2. Используются вложенные циклы по j, k, l, определяющие те кущие максимальные значения частных критериев (( Lусл )maxтек)j;

(( T р )maxтек)k;

((Me)maxтек)l соответственно:

(( Lусл )maxтек)j[( Lусл ):( Lусл ):( Lусл )max];

(( T р )maxтек)k[( T р ):( T р ):( T р )max];

((Me)maxтек)l[(Me):(Me):( Me)max]. (3.28) 3. Для каждого сочетания значений (( Lусл )maxтек)j;

(( T р )maxтек)k;

((Me)maxтек)l из множества методик ={Метi}, i[1;

Nмет] выбирается оптимальная методика Метiопт по минимальному значению min скалярной функции линейной свертки критериев i, определяемой в виде суммы отношений [166, 253]:

(Tр )i ( Lусл )i (M e )i i = + + (( Lусл )maxтек ) j ((T р )maxтек )k ((M e )maxтек )l. (3.29) iопт=Индекс(min({i}));

min=iопт. (3.30) Функцией Индекс обозначено выполнение известного алгоритма определения номера минимального элемента одномерного массива [74].

Методики, для которых не выполняется условие попадания внутрь допустимого интервала, не рассматриваются (i=). Условие выглядит следующим образом:

(( Lусл )i(( Lусл )maxтек)j (( T р )i(( T р )maxтек)k) ((Me)i((Me)maxтек)l, (3.31) где – знак логического умножения (конъюнкции).

Пуск min=;

iопт= Ввод исходных данных: i ( T р )max;

(Me)max;

( Lусл )max;

i=1;

iNмет;

i=i+ r ( T р );

(Me);

( Lусл );

{( GTML )i} jmax= ( Lусл )max/( Lусл ) ;

Нет (( Lусл )i(( Lусл )maxтек)j kmax= ( T р )max/( T р ) ;

(( T р )i(( T р )maxтек)k) lmax= (Me)max/(Me) ((Me)i((Me)maxтек)l j j=1;

jjmax;

j=j+1 Да ( Lусл )i (( Lусл )maxтек)j=j( Lусл ) i = + (( Lусл )maxтек ) j k (T р )i (M e )i k=1;

kkmax;

k=k+ + + ((T р )maxтек )k ((M e )maxтек )l (( T р )maxтек)k=k( T р ) l iопт=Индекс(min({i}));

min=iопт l=1;

llmax;

l=l+ 9 i ((Me)maxтек)l=l(Me) Nопт(j,k,l)=iопт l Вывод результатов:

k Nопт 19 j Останов Рис. 3.7. Блок-схема алгоритма интеллектуальной поддержки САПР выбора методики оптимизации траектории 4. Номер оптимальной для текущего сочетания значений (( Lусл )maxтек)j;

(( T р )maxтек)k;

((Me)maxтек)l методики заносится в трех мерный массив Nопт(j,k,l). В случае, если условие (3.31) не выполня ется ни для одной методики, принимается Nопт(j,k,l)=0.

5. Осуществляется вывод результатов (массив Nопт) в форме, удобной для восприятия исследователем. В массиве Nопт содержится множество номеров неулучшаемых методик.

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

Блок-схема алгоритма интеллектуальной поддержки САПР выбо ра методики расчета оптимальной траектории приведена на рис. 3.7.

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

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

Эквидистантные поверхности строятся на расстоянии эквиди стантного радиуса R от реальных поверхностей-препятствий, равном [102] R =lg+lзап, (3.32) где lg – расстояние от характерной точки начала координат системы груза до наиболее удаленной от начала координат периферийной точ ки груза в заданном направлении, определяемом угловой ориентацией груза относительно препятствия в момент его прохождения;

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

При этом необходимо указать на целесообразность задания фик сированного значения lg в виде максимального значения вдоль одной из координатных осей OgXgYgZg системы координат груза (lgx на рис.

3.8).

Предлагается модифицировать методику [102] построения поли дистантных (разноудаленных в различных направлениях) поверхно стей вокруг препятствий.

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

Так, например, если рассматривать перемещение Yg груза в форме цилиндра или параллелепипеда достаточно большой длины (как в при Zg Xg мере на рис. 3.8), для кото рого возможны в процессе перемещения только пово Груз роты вокруг вертикальной lg y оси Yg и недопустимы дру lgx l gz гие угловые перемещения, что является одним из са Рис. 3.8. Определение величин lg_г, lg_в мых часто встречающихся в практике расчетных случа ев, построение полидистантной поверхности вокруг препятствий по зволит учесть тот факт, что размер lgz для рассматриваемой на рис. 3. формы груза намного меньше lgx. Кроме того, возможное раскачива ние груза вызывает его смещения в основном в горизонтальной плос кости и лишь в незначительной степени – в вертикальном направле нии вверх. Следовательно, удаленность полидистантной поверхности вертикально вверх от поверхности препятствий должна быть меньше, чем в горизонтальном направлении.

Полидистантные поверхности в настоящей монографии предла гается строить на расстоянии горизонтальной полуоси (радиуса Rг от реальных поверхностей-препятствий в горизонтальном направлении) и на расстоянии вертикальной полуоси (радиуса Rв в вертикальном направлении) эллипса:

Rг =lg_г+lзап_г;

Rв =lg_в+lзап_в, (3.33) где lg_г – расстояние от характерной точки начала координат системы груза до наиболее удаленной от начала координат периферийной точ ки груза в горизонтальном направлении, lg_г= (l gx )2 + (l gz )2 ;

lg_в – рас стояние от характерной точки начала координат системы груза до наиболее удаленной от начала координат периферийной точки груза в вертикальном направлении, lg_в= lgz;

lзап_г – запас расстояния в гори зонтальном направлении;

lзап_в – запас расстояния в вертикальном на правлении.

Конечная точка Начальная точка Y0 Z0 Y X X0 Z а) б) Рис. 3.9. Реальная (а) и соответствующая ей полидистантная (б) поверхности с найденной кратчайшей траекторией движения точки (пример) При этом предлагается использовать вариант перехода от верти кального направления к горизонтальному по эллиптической кривой.

Рабочая область с препятствиями (рис. 3.9, а) задана в виде двух мерного массива чисел – высот точек реальной поверхности YПР(i,k).

rp k Y Rв i R y X0 rp X0,Z Rг Rг Z а) б) Рис. 3.10. Схема к построению полидистантных поверхностей: а – вид сверху;

б – вид сбоку Построение полидистантной поверхности YЭ на основе YПР на дискретной двухмерной сетке предлагается выполнять по следующе му алгоритму [94]:

- принять в первом приближении YЭ(i,k)=YПР(i,k), (3.34) где i[1;

imax];

k[1;

kmax];

- при помощи циклов, меняющих i и k, осуществить перебор каж дой точки сетки с высотой YПР(i,k) и для каждой из ее ближайших то чек-соседей, входящих в область радиуса Rг (за исключением тех, ко торые выходят за пределы рассматриваемой рабочей области), опре делить значения rp и y (рис. 3.10):

(i l )2 + (k l )2, rp = (3.35) где i=k=– Rг l …+ Rг l ;

l=(xк0–xн0)/imax – шаг квантования линейных координат;

rp (R )2 ;

y = 1 (3.36) (R ) 2 в г - для текущих значений i и k вычислить значение высоты y~:

y~= YЭ(i,k)+y;

(3.37) - сравнить высоты y~ и YЭ(i1,k1) и при выполнении неравенства y~YЭ(i1,k1) присвоить YЭ(i1,k1) значение y~:

YЭ(i1,k1)= y~, (3.38) где i1=i+i;

k1=k+k.

Зависимость (3.36) получена из эллиптического уравнения rp /Rг2+(y)2/Rв2=1 (см. рис. 3.10, б).

Блок-схема описанного алгоритма приведена на рис. 3.11.

Значения imax и kmax определяют шаг квантования сетки линейных координат (l), который зависит от максимальных значений коорди нат рассматриваемой области xmax=xк0;

zmax=xmax. Для рассматриваемо го примера (см. рис. 3.9) imax=kmax=100;

l=10/100=0,1 УЛЕ.

Пусть в качестве примера lgy=lgz=0,25 УЛЕ;

lgx=1,0 УЛЕ (см. рис.

(l gx )2 + (l gz )2 =1, 3.8). Примем lg_г= УЛЕ;

lg_в= lgz= 0,25 УЛЕ;

lзап_г=0,5 УЛЕ;

lзап_в=0,25 УЛЕ.

Пуск 1 Ввод исходных данных: v YПР;

lзап_г;

lзап_в;

(Rg )ig Определение lg_г, lg_в Rг =lg_г+lзап_г;

Rв =lg_в+lзап_в YЭ(i,k)=YПР(i,k), где i[1;

imax];

k[1;

kmax] i=1:imax k=1: kmax i=– R l :+ Rг l г k=– Rг l :+ Rг l i1=i+i k1=k+k (i1imax) Да Нет (i11) (k1kmax) (k11) (i l )2 + (k l ) rp = Нет 14 Да rpRг 1 rp ( R ) y = (R г ) в y~=YЭ(i,k)+y Да 17 Нет y~YЭ(i1,k1) ~ YЭ(i1,k1)=y 20 Вывод результатов:

Останов YЭ Рис. 3.11. Блок-схема алгоритма построения полидис тантной поверхности вокруг поверхности препятствий Горизонтальная полуось эллипса по (3.33) будет равна Rг =1, УЛЕ. Вертикальная полуось эллипса по (3.33) будет равна Rв =0, УЛЕ. Построенная в качестве примера для указанных значений поли дистантная поверхность и кратчайшая траектория движения точки для нее приведены на рис. 3.9, б.

Эквидистантная поверхность Полидистантная поверхность 1 Положения груза Y X Z X Рис. 3.12. Кратчайшие траектории, найденные для одной и той же конфигурации препятствий: 1 – в среде с эквидистантной поверхностью;

2 – в среде с полидис тантной поверхностью (вид сверху и вид сбоку) На рис. 3.12 приведены для сравнения эквидистантная поверх ность с эквидистантным радиусом 1,5 м и полидистантная поверх ность с приведенными выше значениями Rг и Rв, а также кратчайшие траектории, найденные для одной и той же конфигурации препятст вий в среде с эквидистантной поверхностью (кривая 1) и в среде с полидистантной поверхностью (кривая 2). Траектория 1 имеет боль шую длину, чем траектория 2 (14,15 и 13,2 УЛЕ соответственно), что позволяет сделать вывод о целесообразности использования предла гаемой модифицированной методики.

Разработанная методика позволяет сформировать полидистант ную поверхность в виде матрицы высот [YЭ] вокруг любой реальной поверхности препятствий [YПР], заданной на двухмерной равномерной дискретной сетке с произвольным шагом. Методика предназначена для использования в составе методик поиска оптимального пути пе ремещения груза в системах автоматического управления мобильных ГПК.

3.4. Методика построения гиперповерхности минимальных значений вертикальных координат условного центра груза с учетом его угловых координат Гиперповерхность минимальных вертикальных координат услов ного центра груза с учетом его угловых координат представляет со бой функцию минимально возможных (при выполнении условия не пересечения с препятствиями) значений вертикальной координаты y точки начала локальной системы координат груза OgХgYgZg, принятой за условный центр груза, в неподвижной системе координат O0Х0Y0Z0.

Аргументами данной функции выступают оставшиеся 4 из пяти рас сматриваемых координат груза в пространстве с препятствиями:

Ymin=f(x, z,, ). Эта функция в общем случае разрывная, легко может быть описана дискретно в виде 4-мерного массива Ymin(i,k,l,m), где ин дексы i, k, l, m соответствуют координатам x, z,,, заданным на рав номерной решетке.

а) в) X0 X x1 x Z0 Z z1 z Y0 Y 1= (Ymin)1 (Ymin) б) г) X0 X x x Рис. 3.13. Определение значений элементов массива гиперповерхности [Ymin] Массив гиперповерхности [Ymin] использован в описанных ниже методиках дискретной оптимизации траектории перемещения груза в среде с препятствиями и позволяет значительно упростить предлагае мые алгоритмы [77].

Рис. 3.13 иллюстрирует, каким образом определяются значения элементов данного массива. Показаны два положения груза (а, б и в, г), которые отличаются друг от друга только значением угловой ко ординаты. Высота гиперповерхности Ymin с учетом формы препятст вий и формы груза при этом будет различной:

(x1= x2;

z1= z2;

1 2) (Ymin)1 (Ymin)2. (3.39) Методика построения гиперповерхности [Ymin] заключается в следующей последовательности шагов [77]. v 1. Задание численных значений исходных данных: { Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

u;

lзап_г;

lзап_в.

2. Определение шага дискретности линейных координат l по (3.5).

3. Определение максимальных и минимальных предельных зна чений угловых координат max, min, max, min:

max=н0+(0,5lmaxu);

min=н0–(0,5lmaxu);

max=н0+(0,5mmaxu);

min=н0–(0,5mmaxu). (3.40) 4. Построение полидистантной поверхности вокруг реальной по верхности препятствий по методике, изложенной в разделе 3.3 [94, 102]. В результате построения формируется дискретная матрица вы сот [YЭ] того же размера, что и исходная матрица препятствий [YПР].

Исходными параметрами при построении [YЭ] кроме исходной по верхности [YПР] будет пара значений параметров: lзап_г;

lзап_в. Матрица [YЭ] задает собственно физические препятствия и определенную сво бодную область запрещенного для движения объекта пространства, примыкающую к физическим препятствиям.

5. Используя метод однородных координат [127], формируется 4 мерный массив [Ms] линейных смещений габаритных точек поверх ности объемного тела груза в зависимости от всевозможных сочета ний угловых координат на дискретной равномерной сетке относи тельно нулевых значений угловых координат.

Данный массив размером (4cгlmaxmmax) может быть представлен v как 3-мерный массив векторов (Rs ) j смещения точек вида (Rs ) j = [x j ] v zj 1T, j[1;

(cгlmaxmmax) ], yj (3.41) определяемых как v v (Rs ) j = ( A )k (Rg )ig, (3.42) где (A)k – матрица вращения;

ig[1;

cг];

k[1;

(lmaxmmax)].

Матрица (A)k определяется в результате определенной последо вательности перемножения матриц поворота системы координат гру за вокруг соответствующих осей собственной системы координат:

(A)k = (A)k(A)k, (3.43) где (A)k, (A)k – матрицы поворота вокруг осей Хg и Yg соответствен но, имеющие следующий вид:

cos k 0 sin k 1 0 0 0 cos 0 sin k 0 1 (A )k ;

(A )k = =. (3.44) k 0 sin k 0 sin k cos k cos k 0 1 0 0 0 0 Отсюда cos k sin k sin sin cos k cos k sin k ( A )k =.

k k (3.45) sin k cos k sin k cos k cos k 0 0 Массив [Ms] будет иметь индексы (ik, ig, l, m), определяющие со ответственно: ik =1, 2, 3 – смещения габаритной точки вдоль осей Х0, Y0, Z0 неподвижной системы координат;

ig[1;

cг] – номер габаритной точки;

l[1;

lmax] – координату ;

m[1;

mmax] – координату.

6. Исходя из условия непересечения груза с препятствиями и за прещенной зоной строится гиперповерхность минимальных возмож ных значений вертикальных координат [Ymin] точки начала локальной системы координат груза OgХgYgZg в неподвижной системе координат O0Х0Y0Z0 с учетом значений линейных координат x и z, а также его уг ловых координат и в 5-мерном пространстве.

Для этого, используя вложенные циклы по i, k, l, m, определяю щие x, z,, соответственно, рассматриваются всевозможные сочета ния координат груза x, z, и на дискретной равномерной сетке, а для каждого сочетания указанных координат – последовательно все v габаритные точки (Rg )ig, ig[1;

cг].

Пуск Ввод исходных данных: (xн0, yн0, zv, сн0, н0);

(xк0, yк0, zк0, к0, к0);

imax;

jmax;

н kmax;

lmax;

mmax;

{ Rig };

[YПР];

u;

lзап_г;

lзап_в l= (xк0 – xн0)/imax;

max=н0+(0,5lmaxu);

min=н0–(0,5lmaxu);

max=н0+(0,5mmaxu);

min=н0–(0,5mmaxu).

Построение полидистантной поверхности [YЭ] вокруг реальной поверхности препятствий [YПР] по методике раздела 3.3 [94, 102] 6 j=0;

k=1 5 i=1:imax l=1:lmax 7 k =(l–0,5lmax)u k=1:kmax l=1:lmax m=1:mmax 9 k =(m–0,5mmax)u m=1:mmax 10 Задание матрицы (A)k ig=1:cг со значениями углов k, k ix= (il+Ms(1, ig, l, m))/l ;

iz= (kl+Ms(3, ig, l, m))/l 11 ig=1:cг Коррекция ix, iz по (3.47) j=j+ Yc(ig)=YЭ(ix,iz)–Ms(2,ig,l,m) v v (Rs ) j = ( A )k (Rg )ig, Ymin(i,k,l,m)=min(Yc(ig)) j [1;

(cгlmaxmmax)] Ms(ik, ig, l, m)= (Rs )ik ;

Вывод результатов ik [1;

3] [Ymin] Останов k=k+ Рис. 3.14. Блок-схема алгоритма построения гиперповерхности минимальных значений вертикальных координат условного центра груза для пяти учитывае мых обобщенных координат Используя массив Ms(ik, ig, l, m) линейных смещений габаритных точек в зависимости от значений угловых координат, определяют значения индексов ix и iz линейных координат x и z текущей габарит ной точки на равномерной сетке с учетом смещений:

ix= (il+Ms(1, ig, l, m))/l ;

iz= (kl+Ms(3, ig, l, m))/l. (3.46) Значения индексов ix и iz, вычисленные по (3.46), проверяются на выполнение условия невыхода за границы диапазонов заданной сетки ix[1;

imax];

iz[1;

kmax] соответственно и при необходимости коррек тируются. Условия коррекции выглядят следующим образом:

ix при 1 ix imax ;

iz при 1 iz k max ;

ix = 1 при ix 1;

iz = 1 при iz 1;

(3.47) i k max при ix imax. max при iz k max.

По индексам ix и iz, полученным по (3.46), (3.47), для различных габаритных точек груза при одних и тех же значениях координат формируется одномерный вектор Yc высот точки начала координат груза, элементы которого определяются по зависимости Yc(ig)=YЭ(ix,iz) – Ms(2, ig, l, m). (3.48) Отдельный элемент массива гиперповерхности [Ymin] определяет ся как минимальный элемент вектора Yc:

Ymin(i,k,l,m)=min(Yc(ig)), ig[1;

cг]. (3.49) Блок-схема алгоритма построения гиперповерхности минималь ных значений вертикальных координат условного центра груза при ведена на рис. 3.14.

3.5. Методика дискретной локальной оптимизации заданной траектории в неоднородном организованном трехмерном пространстве Локальная оптимизация отдельной заданной траектории S может быть выполнена при соблюдении условия непересечения груза с эк видистантной (полидистантной) поверхностью вокруг препятствий [80, 94, 102]. В случае, если имеется некоторая траектория, в общем случае не являющаяся оптимальной, локальная оптимизация позволя ет сравнительно быстро достичь положения ближайшего локального оптимума по целевой функции L путем последовательного изменения положения точек траектории sp, p[1;

imax]. Поскольку траектории и полидистантная поверхность [YЭ] заданы дискретно на равномерной сетке, предлагается следующий алгоритм дискретной локальной оп тимизации отдельной траектории [80].

Последовательно для каждой из точек sp траектории с координа тами sp=(xp, yp, zp, p, p), (3.50) где p[1;

imax];

xp=pl, осуществляется дискретная оптимизация точек из интервала p[2;

(imax–1)], т.е. точка sp перемещается в новое положение, минимизи рующее целевую функцию L. Поскольку значение целевой функции L (3.19) определяется дискретно в виде суммы, при изменении положе ния одной точки будут меняться значения только двух слагаемых этой суммы, поэтому вместо значения L при оптимизации может быть использовано значение Lp, вычисление которого занимает в (imax/2) меньше времени по сравнению с L:

(x x )2 + ( y y )2 + (z z )2 + p 1 p 1 p p p p Lp = + + c ( p p 1 ) + ( p p 1 ) 2 (x x )2 + ( y y )2 + (z z )2 + p +1 p +1 p + p p p +. (3.51) + c ( p p +1 ) + ( p p +1 ) 2 При использовании в качестве целевой функции СВД линейных и угловых перемещений появляется возможность дополнительного со кращения времени расчетов. Вместо значения Lp при оптимизации может быть использовано значение Lp1 – СВД от точки искомого оп тимума sp с учетом препятствий до предварительно определенной точки sp1, находящейся в пространстве обобщенных координат груза на прямой линии между точками sp–1 и sp+1 без учета препятствий.

При отсутствии препятствий между sp–1 и sp+1 точка sp1 с коорди натами (xp1, yp1, zp1, p1, p1), находящаяся посредине между точками sp–1 и sp+1, будет являться оптимумом при любом значении весового коэффициента c в выражении (3.51). Следовательно, точка sp, опре деленная с учетом препятствий как ближайшая к sp1, будет являться оптимумом при наличии препятствий. При оптимизации положения отдельной точки sp в качестве оптимизируемой функции может быть использовано значение Lp1, вычисление которого занимает еще в раза меньше времени по сравнению с Lp:

(x x )2 + ( y y )2 + (z z )2 + p p1 p p1 p p =.

L p1 (3.52) + c ( p p1 ) + ( p p1 ) 2 Это позволяет использовать для оптимизации положения отдель ной точки траектории метод полного перебора на ограниченной об ласти-гиперкубе с центром в исходном положении точки sp.

Описание методики локальной оптимизации для отдельной точки траектории приведено в пп. 1–9 [80].

1. Для текущего значения p определяются оптимальные значения координат (xp1, yp1, zp1, p1, p1) точки sp без учета препятствий, т.е. на прямой между точками sp–1 и sp+1:

xp1=(xp–1+xp+1)/2;

yp1=(yp–1+yp+1)/2;

zp1=(zp–1+zp+1)/2;

p1=(p–1+p+1)/2;

p1=(p–1+p+1)/2. (3.53) Соответствующие индексы координат на равномерной дискрет ной сетке определяются следующим образом:

p= xp1/l ;

jp= yp1/l ;

kp= zp1/l ;

lp= (p1–min)/u ;

mp= (p1– min)/u. (3.54) 2. В случае, если для индексов, полученных по (3.54), выполняет ся условие нахождения точки sp над гиперповерхностью [Ymin] ypYmin(p,kp,lp,mp), (3.55) оптимизация по текущей точке sp завершается, и начинается оптими зация по следующей точке sp+1. В противном случае выполняется сле дующий п. 3.

3. Используя вложенные циклы по k, l, m, определяющие z,, соответственно, для оптимизируемой точки sp с фиксированным p рассматриваются всевозможные сочетания координат груза z, и на дискретной равномерной сетке для ограниченной области-гиперкуба с центром в исходном положении точки sp. Для этого варьируются ин дексы k, l, m в следующих диапазонах (области-гиперкубе):

k[(kp–dkp);

(kp+dkp)];

l[(lp–dlp);

(lp+dlp)];

m[(mp–dmp);

(mp+dmp)], (3.56) где kp, lp, mp – индексы, соответствующие координатам zp, p, p точки sp до оптимизации;

dkp, dlp, dmp – положительные целочисленные зна чения приращений индексов k, l, m соответственно, определяющие область гиперкуба и удовлетворяющие условиям dkpkmax;

dlplmax;

dmpmmax. (3.57) 4. Значения индексов k, l, m, варьируемые по (3.56), проверяются на выполнение условия невыхода за границы диапазонов исходной сетки k[1;

kmax];

l[1;

lmax];

m[1;

mmax] соответственно и при необ ходимости корректируются. Условия коррекции выглядят следующим образом:

k при 1 k k max ;

l при 1 l lmax ;

k = 1 при k 1;

l = 1 при l 1;

k l max при k k max. max при l lmax.

m при 1 m mmax ;

m = 1 при m 1;

(3.58) m max при m mmax.

5. Для каждого сочетания значений индексов k, l, m в области ги перкуба определяются текущие значения координат yu, zu, u, u опти мизируемой точки sp с учетом препятствий:

y p при y p Ymin ( p,k,l,m );

yu = (3.59) Ymin ( p,k,l,m ) при y p Ymin ( p,k,l,m );

zu=kl;

u=lu;

u=mu, где u[1;

(dkp2+dlp2+dmp2)] – индекс, соответствующий уникально му сочетанию значений индексов k, l, m и координат yu, zu, u, u. Для каждого значения u из приведенного диапазона в массиве [tgu] запо минаются соответствующие значения координат yu, zu, u, u.

6. Для каждого сочетания значений координат yu, zu, u, u в об ласти гиперкуба определяется расстояние (Lp1)u:

(x x )2 + ( y y )2 + (z z )2 + (L p1 )u p p1 u p1 u p =. (3.60) + c ( u p1 ) + (u p1 ) 2 7. По выходе из циклов по k, l, m определяется значение индекса um, соответствующее минимальному значению (Lp1)u:

um=Индекс(min({(Lp1)u})). (3.61) Функцией Индекс обозначено выполнение известного алгоритма определения номера минимального элемента одномерного массива [74].

Пуск Ввод исходных данных: {Sq};

C;

imax;

kmax;

lmax;

mmax;

[Ymin];

c;

l;

u;

opt 3 Вывод результатов: {Sq} Останов q=1:С 6 opt=0;

Lopt= Да ((Lopt–1)–Lopt)/(Lopt–1)opt Нет 8 k=(kp–dkp) : (kp+dkp) p=2:(imax–1) 9 l=(lp–dlp) : (lp+dlp) xp1=(xp–1+xp+1)/2;

yp1=(yp–1+yp+1)/2;

zp1=(zp–1+zp+1)/2;

p1=(p–1+p+1)/2;

m=(mp–dmp):(mp+dmp) p1=(p–1+p+1)/2;

p= xp1/l ;

Коррекция k,l,m по (3.58) jp= yp1/l ;

kp= zp1/l ;

lp= (p1–min)/u ;

mp= (p1–min)/u u=u+1 при y p Ymin ( p,k,l,m);

Да yp ypYmin(p,kp,lp,mp) yu = Ymin ( p,k,l,m) при y p Ymin ( p,k,l,m);

Нет zu=kl;

u=lu;

u=mu;

Формирование массива [tgu] u= (x x )2 + ( y y )2 + (z z )2 + um=Индекс(min({(Lp1)u})) (L p1 )u p p1 u p1 u p = 13 + c ( u p1 )2 + (u p1 )2 Восстановление из массива [tgu]: xp=xp1;

yp=yum;

zp=zum;

p=um;

p=um 22 Определение Lopt по (3.19) opt=opt+ Рис. 3.15. Блок-схема алгоритма дискретной локальной оптимизации траектории в среде с препятствиями для пяти учитываемых обобщенных координат груза 8. Оптимальные значения координат yp, zp, p, p точки sp восста навливаются по значению um из массива [tgu]:

yp=yum;

zp=zum;

p=um;

p=um. (3.62) Координата xp принимается равной xp=xp1. (3.63) 9. Оптимизация по текущей точке sp завершается, и начинается оптимизация по следующей точке sp+1:

p=p+1. (3.64) После выполнения п. 9. начинается выполнение с п. 1 с новым значением индекса p, который для каждой траектории изменяется в диапазоне p[2;

(imax–1)]. После того, как p достигает значения (imax–1), по (3.19) определяется значение целевой функции Lopt для траектории Sopt на итерации opt.

Затем начинается следующий цикл оптимизации: p=2, 3,…, (imax–1) и.т.д. Оптимизация отдельной траектории прекращается при выполнении условия окончания расчета, которое заключается в сни жении относительного убывания значения целевой функции на теку щей итерации ниже заданного порогового значения opt:

((Lopt–1)–Lopt)/(Lopt–1)opt. (3.65) После этого начинается оптимизация следующей траектории из множества траекторий общим числом C, подлежащих локальной оп тимизации: {Sq} C=1.

q Блок-схема алгоритма дискретной локальной оптимизации от дельной траектории приведена на рис. 3.15.

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

3.6. Методика планирования траектории на основе генетического подхода Генетические алгоритмы (ГА) хорошо зарекомендовали себя при решении широкого круга оптимизационных задач, особенно обла дающих большой размерностью. Это обусловило целесообразность разработки модификации ГА, позволяющей решить поставленную в разделе 3.1 задачу планирования траектории движения груза в среде с препятствиями с учетом угловой ориентации.

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

Это обуславливает ряд отличий в терминологии предлагаемой методики от терминологии традиционных реализаций ГА, работаю щих с битовыми строками [61, 81, 91, 155]. В качестве генов рассмат риваются вещественные значения линейных и угловых обобщенных координат груза в узловых точках траектории движения груза из на чального положения в конечное. Индивидуумы (наборы хромосом) – траектории груза, описываемые как последовательные наборы коор динат узловых точек груза в пространстве его линейных и угловых обобщенных координат. При этом хромосома – вектор-строка из ве щественных чисел-генов, задающая все обобщенные координаты гру за в отдельной узловой точке на траектории. Популяция индивидуу мов представляет собой набор траекторий, удовлетворяющих ограни чениям на непересечение с препятствиями и на предельные значения линейных и угловых координат груза. Препятствия – это не только физические тела, но и определенная свободная область пространства, запрещенного для движения груза, примыкающая к физическим пре пятствиям. Отбор элитных особей подразумевает отбор наилучших траекторий по величине целевой функции.

Предлагается модифицированный алгоритм для поиска кратчай шего пути перемещения ГПК груза с учетом координат угловой ори ентации в трехмерном пространстве с препятствиями. В качестве примера рассматривается 5 координат, определяющих положение груза в пространстве: 3 линейных координаты и 2 угла поворота гру за. Данное сочетание координат описывает довольно распространен ный частный случай положения груза в форме цилиндра. Предлагае мый алгоритм на основе генетического подхода для постановки зада чи, изложенной в разделе 3.1, заключается в следующей последова тельности шагов.

Описание алгоритма перемещения груза, положение которого определяют 3 линейные и 2 угловые обобщенные координаты [61, 81, 91]. Обобщенная блок-схема ГА представлена на рис. 3.16.

Пуск Ввод исходных данных: (xн0, yн0, zн0, н0, н0);

(xк0, yк0, zк0, к0, к0);

G;

C;

E;

M;

v imax;

jmax;

kmax;

lmax;

mmax;

{ (Rg )ig };

[YПР];

c;

u;

opt;

lзап_г;

lзап_в Создание исходной популяции (инициализация) Вычисление функции приспособленности L для всех особей популяции Выбор индивидуумов для кроссинговера Нет Условие окончания расчета выполнено? Кроссинговер части индивидуумов Да 6 Выбор индивидуумов для мутации Вывод результатов (лучший Мутация части индивидуумов индивидуум S*, L*) Формирование новой популяции Останов Рис. 3.16. Обобщенная блок-схема ГА Предложенный алгоритм на основе генетического подхода за ключается в следующей последовательности шагов:

1. Задание численных значений исходных данных: sнач=(xн0, yн0, v zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

{ Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

G;

C;

E;

M;

c;

u;

opt;

lзап_г;

lзап_в.

Параметры соответствуют описанным при постановке задачи в разделе 3.1, за исключением следующих собственных параметров ал горитма на основе генетического подхода, задаваемых эмпирически:

G – количество итераций алгоритма;

C – количество траекторий мно жества;

E – количество наилучших отбираемых траекторий для ре комбинации;

M – количество отбираемых траекторий для случайных изменений [155].

2. По методике, изложенной в разделе 3.4, формируется массив [Ymin] гиперповерхности минимальных значений вертикальных коор динат условного центра груза с учетом его угловых координат:

Ymin(i,k,l,m), i[1;

imax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax].

3. Генерируется случайным образом начальное множество траек торий. Для создания отдельной траектории при помощи генератора случайных чисел создается (imax–2) точек траектории с координатами:

sp=(xp, yp, zp, p, p), p[2;

(imax–1)], (3.66) где xp=pl;

yp=jpl;

zp=kpl;

p=(lp–0.5lmax)u;

p=(mp–0.5mmax)u;

(3.67) jp= Randjmax ;

kp= Randkmax ;

lp= Randlmax ;

mp= Randmmax, (3.68) где Rand – случайное число в интервале [0;

1] с равномерным законом распределения.

Значения xp, yp, zp, p, p, полученные для каждого значения p, должны удовлетворять условию непересечения груза с эквидистант ной (полидистантной) поверхностью [YЭ], что через массив гиперпо верхности Ymin описывается следующим условием:

ypYmin(p,kp,lp,mp). (3.69) При выполнении этого условия значение p увеличивается на 1, в противном случае генерация отдельной точки траектории по (3.67), (3.68) повторяется.

Первая (p=1) и последняя (p=imax) точки траектории будут совпа дать с начальной и конечной заданными точками:

s1=sнач=(xн0, yн0, zн0, н0, н0);

simax=sкон=(xк0, yк0, zк0, к0, к0). (3.70) Отдельная траектория S компонуется как последовательность то чек S={sp} ip=1.

max (3.71) Получается множество из C возможных траекторий:

{Sq} C=1. (3.72) q 4. Оптимизируется начальное множество траекторий путем ло кальной оптимизации отдельных траекторий множества {Sq} при вы полнении условия непересечения груза с эквидистантной (полидис тантной) поверхностью вокруг препятствий по методике, изложенной в разделе 3.4.

5. Определяется множество значений целевой функции {Lq} для каждой траектории множества {Sq} по (3.19).

6. Инициализируется значение переменной g счетчика итераций алгоритма:

g=1. (3.73) Дальнейшие пункты алгоритма (пп. 7–12) выполняются много кратно в итерационном цикле g [1;

G].

7. Отбираются траектории из множества {Sq} по возрастанию значений целевой функции Lq. После сортировки L*=L1;

S*=S1.

L1L2…LC–1LC;

(3.74) 8. Осуществляется подбор траекторий для рекомбинации. Ис пользуется наиболее распространенный, простой для алгоритмиче ской реализации и универсальный оператор отбора – панмиксия с предварительной селекцией и отбором усечения (Truncation selection) на определенном отрезке траекторий множества с наименьшим зна чением функции приспособленности [155], например [1;

C/2]. В дан ном примере количество отбираемых для рекомбинации траекторий из исходного полного множества траекторий E= C/2. Значение E мо жет быть задано произвольно в пределах E[2;

C/2].

Селекция состоит в том, что для рекомбинации выбираются тра ектории, значение приспособленности которых не меньше пороговой величины, например значения приспособленности «срединной» особи SC/2. Число траекторий для рекомбинации выбирается в соответствии с порогом [1;

E]. Порог определяет, какое число траекторий, начиная с самой первой (самой оптимальной), будет принимать участие в ре комбинации. Такой подход обеспечивает более быструю сходимость алгоритма [61, 81, 91, 155, 226].

Каждому члену промежуточного множества траекторий, ото бранных для рекомбинации {Sr}, r[1;

E], соответствует случайное целое число dr на отрезке [1;

E], которое будет номером второй траек тории из этого же промежуточного множества, принимающей участие в рекомбинации:

dr= RandE. (3.75) 9. Дискретная рекомбинация (Discrete recombination) траекторий промежуточного множества {Sr} осуществляется путем случайного обмена точками траектории по оригинальной модели, заимствующей некоторые специфические свойства модели генитор (Genitor) [155, 249, 252]. Исследования, проведенные рядом зарубежных авторов, показали, что поиск гиперплоскостей при использовании генитора происходит лучше, а сходимость быстрее, чем у классического ГА [249, 252].

В предлагаемой модели, так же как в модели генитор, из пары случайных исходных траекторий синтезируется только одна новая траектория. Эта новая траектория заменяет не одну из исходных, а одну из худших по значению целевой функции траекторий. Отличие предлагаемой модели от модели генитор заключается в том, что при гениторе на каждом шаге ГА в множестве обновляется только одна траектория, а в предлагаемой модели для ускорения сходимости на каждом шаге обновляется (C–E) неоптимальных траекторий исходно го множества [249, 252].

Введены обозначения: ap – точка первой исходной траектории, отобранной для рекомбинации, с номером r из промежуточного мно жества, a p = s p, где (s p S r );

bp – точка второй исходной траектории с ( ) номером dr из промежуточного множества, b p = s p, где s p S d r ;

cp – точка вновь полученной траектории с номером Er из полного множе ства траекторий, c p = s p, где (s p S Er );

Er=E+r.

Рекомбинации подвергаются все точки отобранных в {Sr} исход ных траекторий, кроме первой и последней: p[2;

(imax–1)]. Выбор ис ходной траектории, точка с номером p которой переходит в новую траекторию, определялся случайным образом с равной вероятностью:

при Rand 0,5;

b p cp = (3.76) при Rand 0,5.

a p Траектория, полученная в результате рекомбинации траектории с номером r с траекторией с номером dr, занимает в исходном множест ве место траектории с номером Er, не участвующей в рекомбинации.

10. Осуществляется отбор части траекторий полного множества для случайных изменений. Отбор членов промежуточного множества {Sev}, v[2;

M] для случайных изменений производится способом случайной выборки среди всех членов полного множества, за исклю чением самой первой оптимальной траектории (S*=S1), по закону рав номерного распределения. Номер ev каждой траектории из полного множества, входящей в промежуточное множество {Sev}, подвергае мое случайным изменениям, определяется по зависимости ev=1+ RandM, v[2;

M]. (3.77) 11. Осуществляется случайное изменение траекторий промежу точного множества {Sev} путем вставки сформированных случайным образом по (3.67), (3.68) с проверкой условия (3.69) точек траектории на место исходных точек:

sp=smp, p[2;

(imax–1)], (3.78) где smp=(xmp, ymp, zmp, mp, mp) – сформированная случайным обра зом по (3.67), (3.68) с проверкой выполнения условия (3.69) точка траектории.

Случайное изменение траекторий в ГА предотвращает прежде временное схождение алгоритма к локальному оптимуму (субопти мальному решению).

12. Осуществляется переход к следующей итерации алгоритма:

g=g+1, g [1;

G]. (3.79) Если выполняется условие завершения работы алгоритма gG, (3.80) осуществляется переход к п. 13, в противном случае – к п. 7.

13. Выполняется локальная оптимизация лучшей траектории S* по методике, изложенной в разделе 3.5. При этом траектория обнов ляется.

Пуск Ввод исходных данных: (xн0, yн0, zн0v сн0, н0);

(xк0, yк0, zк0, к0, к0);

G;

C;

E;

M;

, imax;

jmax;

kmax;

lmax;

mmax;

{ Rig };

[YПР];

c;

u;

opt;

lзап_г;

lзап_в Построение массива гиперповерхности [Ymin] по методике раздела 3. q=1:С s1=sнач=(xн0, yн0, zн0, н0, н0) p= jp= Randjmax ;

kp= Randkmax ;

lp= Randlmax ;

mp= Randmmax ;

xp=pl;

yp= jpl;

zp=kpl;

p=(lp–0,5lmax)u;

p=(mp–0,5mmax)u Нет ypYmin(p,kp,lp,mp) Да p=p+ 11 Да Нет simax=sкон=(xк0, yк0, zк0, к0, к0) p(imax–1) Рис. 3.17. Блок-схема модифицированного алгоритма на основе генетического подхода для пяти учитываемых обобщенных координат груза (начало) 11 Локальная оптимизация траекторий Определение множества значений {Sq}, q[1;

С] по методике раздела функции приспособленности {Lq} множества траекторий по (3.19) 3. g=1:G v=2:M Сортировка траекторий {Sq} по возрас танию Lq. Выделение S*, L* ev=1+ RandM r=1:E p= dr= RandE ;

Er=E+r jp= Randjmax ;

kp= Randkmax ;

lp= Randlmax ;

mp= Randmmax ;

p=2:(imax–1) 18 xmp=pl;

ymp=jpl;

zmp=kmpl;

b p при Rand 0,5;

mp=(lp–0.5lmax)u;

mp=(mp– cp = a p при Rand 0,5;

–0,5mmax)u a p S r ;

b p S d r ;

c p S Er Нет ympYmin(p,kp,lp,mp) Да p=p+ Да p(imax–1) Нет sp=smp=(xmp, ymp, zmp, mp, mp) 28 Вывод результатов (лучшая Останов траектория S*, L*) Рис. 3.17. Блок-схема модифицированного алгоритма на основе генетического подхода для пяти учитываемых обобщенных координат груза (окончание) 14. Определяется уточненное значение целевой функции L* оп тимизированной лучшей траектории S* по (3.19).

15. Вывод результатов: L*, S*. Окончание работы алгоритма.


Блок-схема модифицированного алгоритма на основе генетиче ского подхода приведена на рис. 3.17. Вычислительные реализации модифицированного алгоритма и описанной методики на его основе в средах Microsoft Visual C++ и MATLAB показали работоспособность и эффективность алгоритма для решения поставленной задачи [61, 81, 91].

3.7. Методика планирования траектории на основе модифицированного алгоритма роевого интеллекта Алгоритмы роевого интеллекта относятся к современному на правлению искусственного интеллекта – природным вычислениям (Natural Computing) и отличаются высокой эффективностью [62, 85, 110, 199, 217].

Эти алгоритмы доказали свою применимость при решении раз личных комбинаторных задач на графах. В основу любого алгоритма положена вероятностная эвристическая функция. Каждый агент пе ремещается по графу независимо от других агентов, руководствуясь при выборе пути достаточно простыми правилами. В то же время происходит косвенный обмен информацией между агентами за счет феромона, оставляемого каждым агентом на ребрах графа или в его вершинах при прохождении. В результате вершины или ребра, вхо дящие в более краткие маршруты, будут накапливать большее коли чество феромона [62, 85, 110, 199, 217].

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

Для поставленной в разделе 3.1 задачи предлагается две модифи кации алгоритма роевого интеллекта на взвешенном графе, адаптиро ванном для поиска кратчайшего пути перемещения ГПК груза с уче том его координат угловой ориентации в трехмерном пространстве с препятствиями: последовательная и с распараллеливанием.

Для описания пространства состояний груза на равномерной дис кретной решетке координат формируется граф Gr=(Sr, Er), где Sr={s1, s2,…, sng} – множество вершин графа;

Er = {(si1, s j1 )} ing, j1=1 – множество ребер. Общее количество вершин графа определяется количеством рассматриваемых точек равномерной сетки координат:

ng=imaxjmaxkmaxlmaxmmax.

Необходимо найти оптимальную траекторию с минимальным значением целевой функции L* из начальной вершины sнач в конечную вершину sкон, представляющую собой последовательность из смежных вершин на равномерной решетке S={sp} ip=1. Каждой вершине графа max соответствует определенное пространственное линейно-угловое по ложение груза.

Модифицированный алгоритм роевого интеллекта в последова тельном исполнении [62, 85, 110].

1. Задание численных значений исходных данных: sнач=(xн0, yн0, v zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

{ Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

rкол;

;

;

er;

G;

c;

u;

[T];

opt;

lзап_г;

lзап_в. Параметры соответст вуют описанным при постановке задачи в разделе 3.1, за исключени ем следующих собственных параметров алгоритма роевого интеллек та, задаваемых эмпирически: rкол – количество независимых агентов;

и – весовые относительные коэффициенты значимости феромона и видимости;

G – количество итераций алгоритма роевого интеллекта;

[T] – матрица феромонов (с начальными постоянными значениями уровня);

er – количество элитных агентов.

2. По методике, изложенной в разделе 3.4, формируется массив [Ymin] гиперповерхности минимальных значений вертикальных коор динат условного центра груза с учетом его угловых координат:

Ymin(i,k,l,m), i[1;

imax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax].

3. Используя вложенные циклы по i, j, k, l, m, определяющие ко ординаты x, y, z,, соответственно, c использованием массива [Ymin] гиперповерхности минимальных значений вертикальных координат условного центра груза с учетом его угловых координат формируется квадратная матрица смежности вершин графа A=[ai1,j1] ing j1=1 размером 1, ngng, элементы которой равны:

ai1,j1=1, если существует дуга (si1, sj1);

ai1,j1=0, если нет дуги (si1, sj1). (3.81) Причем по (3.81) проверяются только смежные с текущей вер шины, поскольку перемещение осуществляется только в определен ные вершины-преемники, смежные с текущей:

i1=mlmaxkmaxjmaximax+lkmaxjmaximax+kjmaximax+jimax+i;

j1=mplmaxkmaxjmaximax+lpkmaxjmaximax+kpjmaximax+jpimax+ip;

(3.82) ip[i–1;

i+1];

jp[j–1;

j+1];

kp[k–1;

k+1];

lp[l–1;

l+1];

mp[m–1;

m+1].

Отсутствие дуги подтверждается в случае, если условие (3.55) не выполняется хотя бы для одной из двух точек: i1 с индексами коор динат i, j, k, l, m или j1 с индексами ip, jp, kp, lp, mp.

Остальные элементы матрицы [A] принимаются равными 0. Мат рица смежности [A] полностью определяет структуру графа с учетом геометрии препятствий в рабочей области, про которые принято до v пущение об их неподвижности, и геометрии объекта (точек (Rg )ig, ig[1;

cг]).

4. Алгоритм роевого интеллекта состоит в последовательности итераций g1, g2, …, G, на каждой из которых rкол агентов независимо друг от друга совершают полный цикл движения из sнач в sкон, двига ясь только через смежные вершины. Выбор вершины sj1 для перехода в нее отдельного агента из текущей вершины si1 осуществляется при помощи вероятностного правила на основе двух компонент – видимо сти i1,j1 и уровня феромонов i1,j1, которые ассоциированы с верши нами, смежными с текущей.

Каждая дуга (si1, sj1)Nr имеет весовой коэффициент i1,j1. В тер минах традиционного алгоритма роевого интеллекта, разработанного для решения задачи коммивояжера, i1,j1 – это видимость между вер шинами si1 и sj1. Это величина, обратная значению целевой функции [62, 85, 110, 199, 217]:

i1,j1 =1/Li1,j1, (3.83) где Li1,j1 – значение целевой функции между вершинами si1 и sj1, опре деляемое по (3.18) (СВД);

i1[1;

ng];

j1[1;

ng].

Предложен и исследован на применимость другой способ опре деления видимости i1,j1 для вершины sj1, смежной с текущей рас сматриваемой вершиной si1. Видимость предлагается определять как предполагаемое (прогнозируемое) значение целевой функции между смежной вершиной sj1 и конечной вершиной sкон без учета препятст вий. Данный подход используется в эвристических алгоритмах поиска кратчайшей траектории на графах, в частности в алгоритме А* и его модификациях, и доказал свою эффективность [74, 175]. «Жадная»

эвристическая функция расстояния до ближайшего соседа (3.18) из классического алгоритма роевого интеллекта заменяется эвристиче ской функцией оценки предполагаемого расстояния до цели:

Li1, j1 = (x j1 xк0 )2 + ( y j1 yк0 )2 + (z j1 zк0 )2 + c ( j1 к0 )2 + (j1 к0 )2. (3.84) Для работы алгоритма используются две квадратные матрицы:

видимости N=[i1,j1] ing j1=1 и феромонов T(g)=[i1,j1] ing j1=1, где i1,j1(g) – 1, 1, количество феромонов на дуге (si1, sj1) на итерации g. В начальный момент времени все элементы матрицы феромонов T принимаются равными некоторому постоянному малому положительному значе нию.

l=–1, 0, +1;

m=–1, 0, + j+ а) j Y Yg j– Xg i+ X i Zg k–1 Z k k+ Y j+ X j+1, k+ Y j i i+ б) Z0 в) j– j–1, k–1 j–1, k+ l+1, m– i+1 l+ l+1, m+ k–1 k k+ m+ X i m– Z г) д) l–1, m+ l– l–1, m– Рис. 3.18. Возможные состояния-«преемники» для текущего состояния груза в пространстве: а – пространственный вид;

б – вид сзади;

в – вид сбоку;

г – вид сверху;

д – углы поворота Матрица видимости [N] получается путем умножения соответст вующих значений целевой функции (3.18) между текущей и всеми смежными вершинами по прямой либо между всеми смежными и ко нечной вершинами по прямой (3.84) без учета препятствий на соот ветствующие элементы матрицы смежности [A] (3.81):

i1,j1=ai1,j1Li1,j1, i1[1;

ng];

j1[1;

ng]. (3.85) Для практической реализации алгоритма предлагается использо вать подходы из области искусственного интеллекта. Формализуем функцию определения «преемника» для произвольного состояния объекта [175]. Отдельный агент перемещает груз по узлам графа на равномерной сетке. В соответствии с принятым при постановке зада чи расположением осей неподвижной системы координат прираще ние индекса i (координаты x) на единицу целесообразно на каждом шаге агента, т.к. уменьшает расстояние до цели и общее число шагов.

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

Для каждой вершины графа в общем случае получим Fпр=(qv)wv вершин-«преемников», где qv=3 – число вариантов выбора по от дельной координате;

wv=4 – количество координат, допускающих многовариантность при выборе преемника. В нашем случае Fпр= = (qv)wv =34=81. Однако, учитывая, что некоторые вершины графа не проходимы вследствие пересечения груза с препятствиями, общее число «преемников» Fпр для каждой конкретной вершины может быть меньше 81. В некоторых пространственных состояниях число вер шин-«преемников» может быть равно 0, в этом случае путь тупико вый, он убирается из рассмотрения.

Вероятность перехода отдельным агентом из текущей вершины si1 в смежную вершину sj1 определяется по известному правилу [199, 217] i, j1 ( g ) i, j Pi1, j1 ( g ) = u 1, (3.86) i1,l ( g ) i1,l l = где и – весовые относительные коэффициенты значимости феро мона и видимости соответственно, +=1,0.

4.1. Для реализации выбора отдельной вершины из списка смеж ных с текущей вершин одномерный вектор вероятностей Pi1,j1, j1[1;

u] преобразуется в одномерный вектор сумм вероятностей j1, элемен ты которого определяются следующим образом:

j1 = (Pi1,v ).

j (3.87) v = Компоненты вектора сумм вероятностей j1 представляют собой последовательность монотонно возрастающих чисел со значениями в интервале [0,1]. Последний компонент вектора сумм вероятностей имеет значение u=1. Затем при помощи генератора случайных чисел получается число Rand в интервале [0,1] с равномерным законом рас пределения. Вершина-«преемник» определяется как компонент век тора сумм j1, ближайший меньший к Rand:


(j1 Rand) (Rand –)min, (3.88) где – знак логического умножения (конъюнкции).

4.2. При достижении индексом i (индекс координаты x), который детерминированно увеличивается на 1 при каждом шаге агента, зна чения (imax–1), построение пути агентом завершается. После того, как на итерации g построен путь Sr(g) для отдельного агента колонии с номером r (r[1;

rкол]), определяется длина этого пути как сумма функций стоимости всех дуг вида (3.18), входящих в данный путь:

Lr ( g ) = (Li,i 1 ).

iкон (3.89) i= 4.3. После нахождения путей перемещения для всех rкол агентов колонии из совокупности путей {S1(g), S2(g),…, Srкол (g)} выбирается путь с минимальным значением функции стоимости пути на данной итерации алгоритма g:

L*(g)= min{L1(g), L2(g),…, Lrкол (g)}. (3.90) Последовательность вершин Sr(g) в описываемой реализации представляет собой матрицу размером [imax4], в каждой строке кото рой хранятся индексы j(i), k(i), l(i), m(i) вершины пути, имеющей ин декс i.

4.4. Затем длина оптимального пути на данной итерации L*(g) сравнивается с текущим значением длины глобального оптимального пути L* и при необходимости последнее значение обновляется:

L*= min{L*(g), L*}. (3.91) Последовательность вершин S* глобального оптимального пути длиной L* сохраняется и при уменьшении значения L* по (3.91) также обновляется.

4.5. После завершения каждой итерации происходит обновление феромона на всех дугах графа по известной зависимости [199, 217] i1, j1 ( g + 1) = (1 p f ) i1, j1 ( g ) + i1, j1 ( g ), (3.92) где pf – коэффициент испарения феромона, p f [0, 1];

i1[1;

ng];

j1[1;

ng].

rкол i1, j1 ( g ) = i1, j1, r ( g ) ;

(3.93) r = Q Lr ( g ) если (i1, j1) S r ( g );

i1, j1, r ( g ) = (3.94) 0 если (i1, j1) S r ( g ), где Sr(g) – последовательность вершин графа, пройденных агентом r на итерации g;

Lr(g) – величина целевой функции (длина пути, прой денного агентом r) на итерации g;

Q – постоянная.

4.6. Уровень феромона на ребрах глобального оптимального пути длиной L* после каждой итерации дополнительно увеличивается на величину [62, 85, 110, 199, 217] e ( g ) = er Q L*, (3.95) где er – количество элитных агентов.

5. Цикл завершается после выполнения заданного числа итера ций: gG. После этого выполняется локальная оптимизация лучшей найденной траектории S* глобального оптимального пути L* с учетом препятствий рабочей области по методике, изложенной в разделе 3.5, на этом завершается работа алгоритма.

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

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

Пуск v Ввод исходных данных: sнач=(xн0,yн0,zн0,н0,н0);

sкон=(xк0,yк0,zк0,к0,к0);

{ Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

rкол;

;

;

er;

G;

c;

Gr;

u;

[T];

opt;

lзап_г;

lзап_в Построение массива гиперповерхности [Ymin] по методике раздела 3. Формирование матрицы смежности [A] с использованием массива гиперповерхности [Ymin] по (3.81) Вычисление ассоциированных расстояний Li,j по (3.18) или (3.84). Вычисление мат рицы видимости [N] по [A] и Li1,j1 по (3.85). Задание L*=. Вычисление iнач, jнач, kнач, lнач, mнач по (3.54). Положить i(1)=iнач;

j(1)=jнач;

k(1)=kнач;

l(1)=lнач;

m(1)=mнач g=1:G Выбор пути, оп r=1:rкол тимального на Вычисление дли- данной итерации ны пути Lr(g) i=2:(imax–1) L*(g) по условию агента r по (3.89) (3.90) nm=0 10 Генерация слу- Сравнение L*(g) и чайного числа dj=–1:+1 * * 11 Rand в интервале L, обновление L по (3.91);

обнов j(i)=j(i–1)+dj;

[0;

1] ление последова Ограничения: j(i)jmax;

j(i)1 Определение тельности вершин 12 глобального оп индексов j(i), dk=–1:+ тимального пути 13 k(i), l(i), m(i) S*;

обновление новой верши k(i)=k(i–1)+dk;

феромона по Ограничения: k(i)kmax;

k(i)1 ны пути Sr(g) (3.92) и (3.95) агента r по dl=–1:+1 (3.88) Локальная опти мизация лучшей l(i)=l(i–1)+dl;

найденной траек Ограничения: l(i)lmax;

l(i) тории S* гло 16 бального опти dm=–1:+ мального пути L* по методике раз m(i)=m(i–1)+dm;

nm=nm+1;

дела 3. Ограничения: m(i)mmax;

m(i) 18 Вычисление P(nm) по (3.86) и Вывод резуль (nm) по (3.87) для смежной с те татов: S*, L* кущей вершины с индексами i, j, Останов k, l, m Рис. 3.19. Блок-схема последовательного алгоритма роевого интеллекта для пяти учитываемых обобщенных координат груза Пуск v Ввод исходных данных: sнач=(xн0,yн0,zн0,н0,н0);

sкон=(xк0,yк0,zк0,к0,к0);

{ Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

rкол;

;

;

er;

G;

c;

Gr;

u;

[T];

opt;

lзап_г;

lзап_в Построение массива гиперповерхности [Ymin] по методике раздела 3. Формирование матрицы смежности [A] с использованием массива гиперповерхности [Ymin] по (3.81) Вычисление ассоциированных расстояний Lij по (3.18) или (3.84). Вычисление мат рицы видимости [N] по [A] и Li1,j1 по (3.85). Задание L*=. Вычисление iнач, jнач, kнач, lнач, mнач по (3.54). Положить i(1)=iнач;

j(1)=jнач;

k(1)=kнач;

l(1)=lнач;

m(1)=mнач g=1:G Выбор пути, оп тимального на 7 8 Независи- Независи- Независи- данной итерации мый поиск мый поиск мый поиск... L*(g) по условию пути аген- пути аген- пути аген (3.90) том r=1 том r=2 том r= rкол * * * Сравнение L (g) и L, обновление L по (3.91);

обновление последова тельности вершин глобального оптимального пути S*;

обновление феро мона по (3.92) и (3.95) 14 Локальная оптимизация лучшей траектории S* Вывод резуль Останов глобального оптимального пути L* татов: S*, L* по методике раздела 3. Рис. 3.20. Блок-схема распараллеленного алгоритма роевого интеллекта (затемнены блоки, выполняемые параллельно) для пяти учитываемых обобщен ных координат груза Анализ последовательного алгоритма роевого интеллекта позво ляет выделить в нем следующие этапы решения задачи: 1) начальный этап, включающий в себя загрузку и инициализацию исходных дан ных;

2) последовательное построение маршрутов колонией агентов, т.е. основной вычислительный этап;

3) обработка и вывод получен ных результатов.

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

обновление следа феромона от всех агентов на те кущей итерации.

… Вычисление дли ны пути Lr(g) i=2:(imax–1) агента r по (3.89) nm=0 Генерация слу чайного числа dj=–1:+ 4 в интервале [0;

1] j(i)=j(i–1)+dj;

Определение Ограничения: j(i)jmax;

j(i) индексов j(i), dk=–1:+1 k(i), l(i), m(i) 6 новой верши k(i)=k(i–1)+dk;

ны пути Sr(g) Ограничения: k(i)kmax;

k(i)1 агента r по (3.88) dl=–1:+ l(i)=l(i–1)+dl;

Ограничения: l(i)lmax;

l(i) dm=–1:+ m(i)=m(i–1)+dm;

nm=nm+1;

Ограничения: m(i)mmax;

m(i) Вычисление P(nm) по (3.86) и (nm) по (3.87) для смежной с те кущей вершины с индексами i, j, k, l, m … Рис. 3.21. Блок-схема выполняемого параллельно kernel ядра алгоритма роевого интеллекта для пяти координат, описывающих положение груза Анализ программной реализации описанного выше последова тельного алгоритма, учитывающего 5 координат, определяющих по ложение груза в пространстве, показал, что суммарное время выпол нения подэтапа 2-го этапа, заключающегося в последовательном не зависимом поиске пути агентами колонии, составляет в среднем око ло 86 % от общего времени выполнения всей программы. В то же время данный блок задачи, в отличие от всех остальных, является ин формационно независимым.

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

Блок-схема распараллеленного в соответствии с приведенным подходом алгоритма роевого интеллекта, учитывающего 5 координат, приведена на рис. 3.20, 3.21.

В соответствии с законом Амдала (Amdahl) ускорение Sпр процес са вычислений при использовании pпр параллельных процессов огра ничивается величиной [8] S пр, (3.96) + (1 f по ) pпр f по где fпо – доля последовательных операций в рассматриваемом алго ритме.

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

Согласно приведенной формуле (3.96), возможно 7-кратное уско рение по сравнению с последовательным алгоритмом роевого интел лекта (верхняя оценка ускорения Sпр7), что подтверждено результа тами вычислительных экспериментов.

Вычислительные реализации разработанных последовательной и параллельной модификаций алгоритма роевого интеллекта и описан ной методики на его основе в средах Microsoft Visual C++ и MATLAB показали работоспособность и эффективность алгоритмов роевого интеллекта для решения поставленной задачи. Для распараллеленного алгоритма были разработаны программные реализации с использова нием гибридной технологии: массивно-параллельных вычислений на графических процессорах Compute Unified Device Architecture (NVIDIA CUDA) совместно с библиотекой параллельного програм мирования систем с распределенной памятью Message Passing Interface (MPI) и открытого стандарта параллельного программирова ния многопоточных систем с общей памятью Open Multi-Processing (OpenMP).

3.8. Методика планирования траектории на основе модифицированного алгоритма вероятностной дорожной карты Алгоритм вероятностной дорожной карты PRM (Probabilistic Road Map) относится к современным подходам в области планирова ния траекторий. Этот подход считается одним из ведущих методов планирования движения, в первую очередь для механических систем со многими степенями свободы в среде с препятствиями. Вероятност ный метод PRM считается высокоэффективным, простым в реализа ции и применимым для различных видов задач, связанных с планиро ванием движения [212, 221, 228, 229, 230, 234].

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

Обобщенный алгоритм ВДК состоит в формировании простран ства конфигураций, состоящего из случайным образом полученных возможных положений движущегося объекта (т.н. дорожной карты), в которых он не пересекается с препятствиями. При генерации возмож ных положений объекта те из них, которые пересекаются с препятст вием, удаляются. Оставшиеся добавляются в качестве узлов в граф дорожной карты, дискретно описывающий непрерывное пространство конфигураций. Требуемое число узлов графа заранее определено.

Сумма степеней свободы объекта определяет размерность простран ства конфигураций [141, 212, 221, 234].

Формируется граф Gr=(Sr, Er), где Sr={s1, s2,…, sng} – множество вершин графа;

Er = {(si1, s j1 )} ing, j1=1 – множество дуг (ребер). Общее ко личество вершин графа ng определяется заданным количеством рас сматриваемых точек в пространстве конфигураций, свободном от препятствий.

Необходимо найти оптимальную траекторию S* с минимальным значением целевой функции L* из начальной вершины sнач в конечную вершину sкон, представляющую собой последовательность из несколь ких вершин графа дорожной карты Gr: S*={sp} sn=1. Каждой вершине p графа соответствует определенное пространственное линейно угловое положение груза в свободном пространстве дорожной карты.

Структура графа дорожной карты определяется квадратной мат рицей весов дуг N=[Li1,j1] ing j1=1. Значения весов Li1,j1 определяются по 1, зависимости целевой функции СВД (3.18). Если две вершины не со единены между собой, например по причине наличия препятствий между ними, вес соответствующей дуги (ребра) графа принимается равным бесконечно большому значению:

Li1,j1=. (3.97) Существует несколько реализаций алгоритма ВДК с различными подходами к формированию дуг между вершинами и матрицы весов графа соответственно.

Традиционный подход, успешно применяемый для соединения точек дугами в 2- и 3-мерном евклидовом пространстве, заключается в использовании быстрого и простого алгоритма соединении дугами каждой точки с ближайшими соседями, например при помощи метода триангуляции [221, 230, 234].

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

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

В настоящей монографии предложен и реализован другой под ход, обладающий полнотой [63, 100]. Полученные случайным обра зом вершины графа соединяются между собой дугами с учетом види мости, т.е. выполнением условия непересечения с препятствиями при движении из вершины в вершину по прямой в пространстве конфигу раций. Выполняется проверка видимости между текущей вершиной si1{Sr} и каждой из подмножества вершин sj1{Sx} с большими или равными значениями линейной координаты груза x. Подмножество {Sx} формируется из множества {Sr}по условию (s j1 {Sx});

x j1 ( xi1 {Sr}), (3.98) где {Sx} {Sr}.

После того, как сформирована матрица весов графа [N], осущест вляется поиск кратчайшего пути между двумя вершинами графа (sнач и sкон) при помощи традиционных алгоритмов поиска на графе [216].

Последним этапом алгоритма ВДК является интерполяция и ло кальная оптимизация найденной траектории. После локальной опти мизации найденная траектория будет представлять собой последова тельность из смежных вершин, заданных уже на равномерной решет ке S={sp} ip=1.

max Блок-схема обобщенного алгоритма ВДК представлена на рис.

3.22.

v (Rg ) ig Рис.3.22. Обобщенная блок-схема алгоритма ВДК Описание алгоритма ВДК перемещения груза, положение кото рого определяют 3 линейные и 2 угловые обобщенные координаты [63, 100]. Предложенный модифицированный алгоритм ВДК заклю чается в следующей последовательности шагов:

1. Задание численных значений исходных данных: sнач=(xн0, yн0, v zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

{ Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

ng;

c;

u;

opt;

lзап_г;

lзап_в.

Параметры соответствуют описанным при постановке задачи в разделе 3.1, за исключением следующего собственного параметра ал горитма ВДК, задаваемого эмпирически: ng – количество вершин графа дорожной карты.

2. По методике, изложенной в разделе 3.4, формируется массив [Ymin] гиперповерхности минимальных значений вертикальных коор динат условного центра груза с учетом его угловых координат:

Ymin(i,k,l,m), i[1;

imax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax].

3. Генерируется случайным образом множество вершин Sr={s2,…, sng–1} графа дорожной карты, представляющих собой точки в пространстве конфигураций, т.е. возможные положения груза в пре делах заданной сетки координат, в которых он не пересекается с пре пятствиями.

Для создания дорожной карты при помощи генератора случай ных чисел создается ng точек в пространстве конфигураций с коорди натами sp=(xp, yp, zp, p, p), p[2;

ng–1], (3.99) где xp=ip l;

yp=jpl;

zp=kpl;

p=(lp–0,5lmax)u;

p=(mp–0,5mmax)u;

(3.100) ip= Randimax ;

jp= Randjmax ;

kp= Randkmax ;

lp= Randlmax ;

mp= Randmmax. (3.101) Значения xp, yp, zp, p, p, полученные для каждого значения p, должны удовлетворять условию непересечения груза с эквидистант ной (полидистантной) поверхностью [YЭ], что через массив гиперпо верхности Ymin описывается следующим условием:

ypYmin(ip,kp,lp,mp). (3.102) При выполнении этого условия значение p увеличивается на 1, в противном случае генерация отдельной точки по (3.100), (3.101) по вторяется.

Первая (p=1) и последняя (p=ng) точки траектории будут совпа дать с начальной и конечной заданными точками:

s1=sнач=(xн0, yн0, zн0, н0, н0);

sng =sкон=(xк0, yк0, zк0, к0, к0). (3.103) 4. Формируется матрица весов дуг N=[Li1,j1] ing j1=1. Выполняется 1, проверка видимости между текущей точкой si1{Sr} и каждой из подмножества точек sj1{Sx} с большими или равными значениями линейной координаты груза x. Подмножество {Sx} формируется из множества {Sr} с выполнением условия (3.98). Для этого используют ся два вложенных цикла: внешний i1[1;

ng] и внутренний j1[1;

ng].

Для каждого сочетания значений i1 и j1 осуществляется проверка вы полнения условия (3.98). При невыполнении данного условия вес ду ги (si1,sj1) принимается равным бесконечно большому значению по (3.97).

Если условие выполняется, то проводится дополнительная про верка выполнения условия непересечения с препятствиями всех то чек, лежащих на прямой в пространстве конфигураций между точка ми si1 и sj1. Находят применение два способа осуществления подобной проверки [221, 234, 244]: 1) при помощи инкрементного алгоритма (алгоритма последовательных малых приращений);

2) при помощи рекурсивного алгоритма деления отрезка пополам (используя метод дихотомии).

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

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

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



Pages:     | 1 | 2 || 4 | 5 |   ...   | 9 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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