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

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

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


Pages:     | 1 || 3 | 4 |   ...   | 9 |

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

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

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

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

Методики и алгоритмы поиска кратчайшего пути на графах мож но разделить на две группы: методики и алгоритмы неинформирован ного (слепого) поиска и методики и алгоритмы информированного (эвристического) поиска.

К первой группе относятся: поиск в ширину (BFS, Breadth-first search, волновой алгоритм);

поиск в глубину (DFS, Depth-first search);

поиск с ограничением глубины;

поиск в глубину с итеративным уг лублением;

двунаправленный поиск [74, 175, 234].

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

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

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

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

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

При поиске в глубину (DFS – Depth First Search, бэктрекинг, по иск с возвращением) всегда развертывается самый глубокий узел в текущей периферии дерева поиска. Суть этого метода – продвижение вперед в неисследованную область, пока это возможно. Если вокруг все уже исследовано, необходимо отступить на шаг назад и искать новые пути для продвижения вперед. Главное отличие от поиска в ширину состоит в том, что при поиске в глубину в качестве активной выбирается та из открытых вершин (вершина, у которой не все инци дентные ребра уже исследованы), которая была посещена последней.

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

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

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

2 б) а) Рис. 1.11. Схематическое представление двунаправленного (а) и однонаправлен ного (б) поиска в ширину: 1 – начальный узел;

2 – конечный узел Поиск с ограничением глубины – это поиск в глубину с заранее определенным пределом глубины l. Т.е. узлы на глубине l рассматри ваются как не имеющие преемников. Применение предела глубины позволяет не рассматривать бесконечные или слишком длинные пути.

Поиск в глубину с итеративным углублением заключается в по степенном увеличении глубины поиска (который сначала принимает ся равным 0 шагов, затем 1, 2 и т.д. шагов) до тех пор, пока не будет найдена цель. При этом сочетаются преимущества поиска в глубину и поиска в ширину. Как и поиск в глубину, он характеризуется малой пространственной сложностью. Как и поиск в ширину, он является полным, если коэффициент ветвления (максимальное количество пре емников любого узла) конечен, и оптимальным, если стоимость пути представляет собой неубывающую функцию глубины узла [137, 175].

В табл. 1.1 приведено сравнение стратегий неинформированного поиска по четырем показателям эффективности, приведенным выше (полнота, оптимальность, временная сложность, пространственная сложность) согласно [175]. Используются следующие обозначения: b – коэффициент ветвления;

d – глубина самого глубокого решения;

m – максимальная глубина дерева поиска;

l – предел глубины;

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

б – метод полный, если стоимость каждого этапа при некотором по ложительном значении ;

в – метод оптимальный, если стоимости всех этапов являются одинаковыми;

г – метод применим, если в обоих на правлениях осуществляется поиск в ширину.

Таблица 1.1. Сравнение методов неинформированного поиска на графах Поиск с Поиск с Двунаправ Поиск Поиск по кри- Поиск Характе- ограни- итератив- ленный по в ши- терию стои- в глу ристика чением ным уг- иск (если он рину мости бину глубины лублением применим) Даа Даа, б Даа Даа, г Полнота Нет Нет Временная O(bd+l) O(b с * / ) l+ O(bm) O(bl) O(bd) O(bd/2) сложность Простран O(bl+ с * / ) O(bd+l) O(bd/2) ственная O(bm) O(bl) O(bd) сложность Оптималь Дав Да Дав Дав, г Нет Нет ность Алгоритмы неинформированного поиска целесообразно исполь зовать, когда заранее неизвестно расположение цели (переменное по ложение) либо целей несколько. В настоящей монографии в предпо ложении организованности пространства более целесообразным представляется использование методов информированного поиска.

К группе методов информированного поиска относятся: «жад ный» поиск «по первому наилучшему совпадению», или best-first search (алгоритмы Дейкстры, Беллмана-Форда);

алгоритм Аcтар (аль тернативные названия: A*, «А-звездочка», направленный волновой алгоритм);

алгоритм A* с итеративным углублением (IDA*);

рекур сивный поиск по первому наилучшему совпадению (Recursive Best First Search – RBFS);

упрощенный поиск A* с ограничением памяти (SMA* – Simplified Memory-bounded А*);

алгоритмы роевого интел лекта (муравьиных колоний, роя частиц и др.).

Методики и алгоритмы информированного поиска перечислены в порядке возрастания их эффективности [137, 175, 241].

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

A* является более эффективным алгоритмом, чем поиск в шири ну (волновой алгоритм) [224, 234]. Алгоритмы RBFS и SMA* пред ставляют собой надежные, оптимальные алгоритмы поиска, в кото рых используются ограниченные объемы памяти. При наличии доста точного количества времени эти алгоритмы могут решать такие зада чи, которые не позволяет решать алгоритм А*, поскольку исчерпыва ет доступную память [74, 175, 224, 232, 241].

Методики эвристического поиска используют известные знания, специфические для конкретной задачи. Информированные методики поиска находят решения более эффективно, чем слепые, при этом расходуется меньший объем памяти. Эвристическая информация о глобальном характере графа и общем расположении цели поиска мо жет быть использована для направления поиска в сторону цели, рас крывая в первую очередь наиболее «перспективные» узлы графа. Об щее обозначение методов информированного поиска, связанных с выбором наилучшего варианта, – BFS (best-first search). Ключевой компонентой информированных методов является эвристическая функ ция h(n), которая оценивает наименьшую стоимость пути от узла n до целевого узла. Эвристику можно рассматривать в качестве некоторого правила влияния, которое, хотя и не гарантирует успеха, в большинстве случаев оказывается весьма полезным [74, 175, 224, 232, 234, 241].

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

Способы дискретизации непрерывного пространства с препят ствиями при поиске на графах. Исходя из специфики рассматривае мой задачи, существенное, а в некоторых случаях определяющее, влияние на эффективность поиска оптимальной траектории на графе может оказывать способ описания (дискретизации) непрерывного пространства с препятствиями. Можно выделить три способа опреде ления вершин графа для описания пространства с препятствиями [175, 212, 221, 234]:

1) нанесение сетки на пространство, не занятое препятствиями, либо рандомизация свободного пространства (рис. 1.12, а, б, в, рис.

1.13);

2) скелетирование свободного пространства (рис. 1.14);

3) рас смотрение точек только на поверхности препятствий (рис. 1.15).

Начальный узел Начальный узел Препятствия Препятствия Конечный узел Конечный узел а) б) в) Рис. 1.12. Способы дискретизации пространства, двухмерный пример: а – способ C-Cells;

б – способ квадрантных деревьев;

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

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

Способ квадрантных де- Конечный узел ревьев заключается в разде- Рис. 1.13. Способ рандомизации пространст лении пространства на квад- ва с последующей триангуляцией (двухмер раты (кубы или гиперкубы ный пример) для многомерного простран- Начальный узел ства). Каждый квадрат, не являющийся однородным, т.е. входящий в препятствие, разделяется на 4 меньших квадрата (для двухмерного случая). Для многомерного пространства число разбие ний составит 2n, где n – раз мерность пространства по- Линия Вороного ложений объекта. Центры Препятствия квадратов соединяются меж ду собой и используются для Конечный узел поиска траектории (см. рис.

1.12, б). Способ квадрантных Рис. 1.14. Способ скелетирования свободно деревьев позволяет умень- го пространства построением шить количество рассматри- линий Вороного ваемых узлов по сравнению с C-Cells, однако неявное описание графа в этом случае проблематично.

Псевдоравномерная рандомизация с последующим соединением узлов (способом триангуляции): метод известен под названием веро ятностной дорожной карты (PRM – Probabilistic Road Map). Реализу ется повторяющийся алгоритм построения случайных точек в свобод ном пространстве, которые затем соединяются при помощи простого и быстрого алгоритма, например триангуляции (см. рис. 1.13).

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

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

Рис. 1.15. Способ выделения точек на Кроме того, сравнительно малое число случайных точек в про поверхности препятствий странстве состояний не гаранти рует оптимальности метода. Во многих, однако не во всех, рас четных случаях возможно дости жение оптимальности (кратчай шей траектории) последующей после поиска обработкой (Post Рис. 1.16. Оптимизация найденной ме- оптимизация), например устране тодом вероятностной дорожной карты нием промежуточных точек в траектории устранением промежуточ- пределах видимости (рис. 1.16).

ных точек в пределах видимости:

--- ис- Метод вероятностной дорожной ходная траектория;

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

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

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

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

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

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

Независимо от того, каким из трех способов описывается про странство с препятствиями, на нем возможен поиск при помощи лю бого из методов информированного поиска.

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

Распространенным подходом к решению задачи выбора пути яв ляется использование метода потенциалов (другие названия: «искус ственных потенциальных полей» artificial potential fields, «полей вир туальных сил» virtual force field-VFF, «гистограммы векторных сил»

vector field histogram-VFH) [210, 251].

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

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

Элементарные методики поиска могут использовать различные подходы. Они также могут использовать как непрерывное, так и дис кретное описание пространства с препятствиями. К элементарным ал горитмам можно отнести алгоритм обхода препятствий по правилу правой (левой) руки, алгоритм «разделяй и властвуй» и др. [74, 175].

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

Алгоритм «разделяй и властвуй» неоптимален, т.е. не гарантиру ет, что найденный путь будет кратчайшим, и может не работать в случае сложной формы препятствий (например, U-образных и с внут ренними полостями для двухмерной карты), т.е. не является полным.

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

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

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

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

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

Классификация известных методов и алгоритмов планирования оптимальной траектории по перечисленным выше классификацион ным признакам приведена на рис. 1.17. Классификация способов дис кретизации непрерывного пространства с препятствиями при поиске на графах приведена на рис. 1.18.

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

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

Методы и алгоритмы планирования оптимальной траектории перемещения груза Аналитические методы Численные методы оптимиза- Методы поиска на графах Прочие методы ции (с явными переменными) Метод нахо- Метод геоде- Метод Методы Методы Методы Методы ждения про- зических (ва- потенциалов неинформиро- информирован условной безусловной изводных риационное ванного поиска ного поиска Элементар оптимизации оптимизации функции и исчисление) ные методы Поиск по критерию решения поиска стоимости Методы прямого поиска Метод полного перебора системы не Алгоритм обхода пре линейных Поиск в ширину (BFS) Метод Гаусса-Зейделя Метод штрафных функций пятствий по правилу конечных уравнений Метод Хука-Дживса правой (левой) руки Метод барьерных функций Поиск в глубину (DFS) Алгоритм «разделяй и Метод Нелдера-Мида Метод прямого поиска с возвратом Поиск с ограничением властвуй»

глубины Метод возможных направлений Градиентные методы Поиск в глубину с ите- «Жадные» алгоритмы (BFS) Метод множителей Метод наискорейшего ративным углублением градиентного спуска Алгоритм Дейкстры Методы случайного спуска Двунаправленный поиск Метод Флетчера-Ривса Алгоритм Беллмана Методы Монте-Карло Методы эволюционно- Форда Метод имитации отжига Метод Дэвидона- го поиска Флетчера-Пауэлла Алгоритм A* (А*) Алгоритм «Лас-Вегас»

Метод кубической A* с итеративным уг Алгоритмы роевого интерполяции лублением (IDA*) интеллекта Метод Ньютона A* с ограничением па мяти (SMA*) Метод Ньютона-Рафсона Рекурсивный поиск по первому Метод Марквардта Генетические алгоритмы наилучшему совпадению (RBFS) Рис. 1.17. Классификация методов и алгоритмов планирования оптимальной траектории перемещения груза Способы дискретизации непрерывного пространства с препятствиями Нанесение сетки на Рассмотрение точек на поверхно- Скелетирование свободное пространство сти препятствий свободного пространства Нанесение рав- Нанесение ран Нанесение Рандомиза номерной сетки домизирован равномер- ция свобод- Линия на поверхность ной сетки на ной сетки ного про- Вороного поверхность препятствий на свобод- странства препятствий ное про- Метод ве странство роятност Способ Квадрантные/кубические деревья ной дорож деревь- ной карты Треугольные/тетраэдрические де ев ревья Другие Треугольная/тетраэдрическая равномерная сетка способы Определение проблемы Квадрантная/кубическая равномерная сетка Рис. 1.18. Классификация способов дискретизации непрерывного пространства с препятствиями при поиске на графах Большую сложность вызывает не только поиск траектории, для которого существуют эффективные методы и подходы, но и предва рительная подготовка и описание пространства и объекта. Для мно гомерного пространства наибольшие затраты времени при вычисле ниях может вызывать описание его топологии, формы и размеров препятствий и связанного с ними графа состояний, от эффективности и удачности которого зависит быстрота и точность последующего по иска. На первый план при этом выступают неформальные (эвристиче ские) методы, основанные на использовании некоторых специфиче ских особенностей задачи или ее физических аналогов. Особенностью комбинаторных задач, к которым относится и задача планирования оптимальной траектории объекта в общем многомерном случае, явля ется невозможность применения хорошо разработанного классиче ского аппарата бесконечно малых. Это в основном и обусловливает сложность их решения. Необходим поиск специальных приемов и ме тодов для их преодоления применительно к задаче поиска оптималь ной траектории объекта в трехмерной среде с препятствиями с учетом координат угловой ориентации объекта.

2. ОБЩАЯ МЕТОДИКА ИССЛЕДОВАНИЙ ПЛАНИРОВАНИЯ РАБОЧИХ ПРОЦЕССОВ МОБИЛЬНЫХ ГРУЗОПОДЪЕМНЫХ КРАНОВ В НЕОДНОРОДНОМ ОРГАНИЗОВАННОМ ТРЕХМЕРНОМ ПРОСТРАНСТВЕ 2.1. Методика теоретических исследований планирования рабочих процессов мобильных грузоподъемных кранов в неоднородном организованном трехмерном пространстве Исследование любой сложной системы требует постановки про блемы, т.е. выявления проблемной ситуации. Рациональное решение проблем предполагает использование методов и моделей теории сис тем и системного анализа [7, 25, 136, 173]. В главе 1 монографии применительно к грузам, перемещаемым ГПК, была сформулирована проблема оптимизации траектории перемещения объемного объекта произвольной заданной формы с учетом его угловых координат в не однородном организованном трехмерном пространстве с произволь ным расположением и формой препятствий по принятым критериям оптимальности.

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

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

Объект исследований: процессы синтеза оптимальных траекто рий перемещения груза в неоднородном организованном пространст ве и координат установки ГПК.

Предмет исследований: закономерности синтеза оптимальных траекторий перемещения груза в неоднородном организованном про странстве и координат установки ГПК.

Методика проведения системного анализа не является универ сальной, т.к. каждая проблема имеет свои особенности и требует от исследователя инициативы, воображения и интуиции, чтобы пра вильно определить цели проекта и успешно их реализовать [7, 25, 136, 173]. Укрупненно основные этапы поиска рационального решения проблемы приведены на рис. 2.1. Данная общая схема действий мо жет быть модифицирована в деталях.

Методологической основой принятия какого-либо решения, как правило, выступает функциональная зависимость, связывающая цель решения и средства ее достижения. Подобные зависимости выявляются на основе законов научных знаний. Опираясь на данные законы, можно выявить определенные системные закономерности, характерные для ис следуемой проблемы. Выявление закономерностей поведения системы при определенных условиях позволяет создать концепцию, т.е. выдви нуть основную идею для построения новой теории при решении сфор мулированной проблемы. Если теории не существует, то выдвигается научная гипотеза, на основе которой разрабатываются концептуально имитационные модели, с использованием которых могут быть достигну ты поставленные цели, т.е. решены задачи исследования. Одним из ос новных критериев достижения цели является эффективность методов решения сформулированных задач [7, 25, 136, 173].

Генерирова Формулировка Опреде ние альтер задачи, огра- Оценка Выбор опти ление нативных ничений и кри- мального вариантов проблемы вариантов териев для варианта оценки решения решений Реализация Обратная связь Рис. 2.1. Этапы рационального решения проблемы При решении поставленной проблемы необходимо сформулиро вать задачи ее решения и далее найти методы их решения. Проблема отличается от задач тем, что метод ее решения зачастую не имеет четкого решения. Задачи же решаются определенными научными ме тодами. Рациональное решение поставленной проблемы в рамках сис темного подхода предусматривает использование комплексного ме тода решения, включающего как теоретические, так и эксперимен тальные методы исследований. При этом основным научным средст вом реализации цели настоящего исследования с использованием теории систем для практического решения задач выступил метод формализации, который понимается как построение теории знаний в виде, позволяющем использовать количественные (математические) средства исследования. Под формализацией понимается способ оце нивания системы качественными и/или количественными характери стиками с использованием математических методов. В то же время применение математических средств возможно лишь тогда, когда оп ределены средства оценки, измерения всех существенных параметров системы [7, 25, 136, 173].

На основании изложенного решение задач настоящей моногра фии с применением методологии системного анализа было представ лено следующими этапами [7, 25, 136, 173]:

1. Формулирование научной проблемы и цели работы как реше ния поставленной проблемы.

2. Определение объекта и предмета исследования.

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

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

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

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

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

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

- разработка методик и алгоритмов решения задачи на основе пе речисленных подходов;

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

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

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

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

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

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

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

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

- обоснование и выбор энергетических и временных критериев оценки оптимальности траекторий перемещения объекта-груза в про странстве конфигураций ГПК.

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

- разработка полной методики определения управляемых коорди нат ГПК по известным координатам груза с учетом углов наклона ба зового шасси ГПК относительно горизонтальной плоскости и упро щенной методики без учета последних (решение обратной задачи ки нематики);

- разработка методики и алгоритма планирования оптимальной траектории объемного объекта-груза в пространстве конфигураций ГПК на основе метода вероятностной дорожной карты;

- разработка автоматизированных средств реализации методик и алгоритмов планирования оптимальной траектории объемного объек та-груза в пространстве конфигураций ГПК с ограничениями по ус тойчивости.

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

- выбор критериев оценки эффективности совмещенного рабоче го процесса двух ГПК, перемещающих общий груз;

- разработка методики оптимизации технологических параметров рабочего процесса единичного ГПК;

- разработка комплексной методики оптимизации технологиче ских параметров совмещенного рабочего процесса двух ГПК, пере мещающих общий груз.

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

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

При описании и моделировании динамической системы ГПК ис пользовались методы: однородных координат, а также составления и интегрирования систем дифференциальных уравнений, описывающих механическую систему [71, 127].

Теоретические исследования проводились с использованием ПЭВМ и языков программирования C++, MATLAB, а также прило жения визуального моделирования динамических систем Simulink системы MATLAB.

Подобный способ обладает рядом преимуществ перед натурными испытаниями:

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

возможность внешнего вмешательства на любом этапе прове дения исследований;

возможность моделирования таких условий эксперимента, вос произведение которых в реальных условиях затруднено или невоз можно.

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

2.2. Методика проведения экспериментальных исследований Комплексный метод исследований включает проведение как тео ретических, так и экспериментальных исследований. Основными за дачами последних являются: подтверждение адекватности математи ческой модели объекта исследования;

определение численных значе ний параметров, входящих в математические модели объекта;

под тверждение работоспособности и эффективности технических реше ний, внедренных в производство [133, 192].

В настоящее время представленные в настоящей монографии под системы ГПК, такие как механическая подсистема и гидропривод, доста точно подробно математически изучены и описаны. Отечественными и зарубежными учеными проведено большое количество эксперименталь ных исследований. В результате накоплена значительная масса эмпири ческих данных, что позволяет принять и использовать в настоящей моно графии уже имеющийся математический аппарат [71, 127].

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

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

определения значений рациональных технологических параметров ГПК (оценка и уточнение констант теоретических моделей);

построе ния регрессионной модели рациональных технологических парамет ров ГПК;

подтверждения адекватности математической модели дина мической системы ГПК.

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

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

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

При проведении активного вычислительного эксперимента на ком плексной математической модели ГПК с механической, гидравлической и ДВС-подсистемами выделение безопасных подобластей сочетания уровней факторов согласно диаграмме грузоподъемности ГПК выполня лось по отдельному алгоритму. Целью вычислительного эксперимента на комплексной математической модели ГПК являлось получение регрес сионных зависимостей, позволяющих определить удельные затраты топ лива при перемещении ГПК грузов по заданным траекториям. Это от крывает возможность использования разработанной регрессионной мо дели при поиске оптимальной траектории перемещения груза ГПК в не однородном организованном трехмерном пространстве.

Выбор экспериментальной области факторного пространства свя зан с тщательным анализом априорной информации. В частности, вы бор интервалов варьирования факторов связан с неформализованным этапом планирования эксперимента. Выбор интервалов варьирования факторов в настоящей монографии производился путем выделения из областей, заданных конструктивными ограничениями управляемых координат и предельной грузоподъемностью крана, безопасных по добластей сочетания уровней факторов согласно диаграмме грузо подъемности ГПК. На комплексной математической модели ГПК проводился полный факторный эксперимент типа 2k на безопасных подобластях работы ГПК с числом интервалов каждого значимого фактора 5 [133, 192].

Для оценки качества регрессионных моделей, полученных в ре зультате экспериментальных исследований, использовались следую щие показатели качества [32, 194, 245]: коэффициент детерминации R2;

скорректированный коэффициент детерминации R 2 ;

критерий Фишера F;

сумма квадратов остатков RSS;

стандартная ошибка урав нения регрессии SEE;

максимальная относительная погрешность ап проксимации max, %. Кроме того, статистическая значимость коэф фициентов уравнений регрессии оценивалась с помощью t-критерия Стьюдента.

Максимальная относительная погрешность аппроксимации max определяется по формуле ) yi yi max = max100, i[1;

k], (2.1) yi где yi – наблюдаемое значение зависимой переменной в наблюдении i;

) y i – аппроксимированное по уравнению регрессии значение зависи мой переменной в наблюдении i;

k – количество наблюдений.

Сумма квадратов остатков RSS (остаточная сумма квадратов) измеряет необъясненную часть вариации (ошибки уравнения регрес сии) зависимой переменной:

) RSS = ( yi yi ) 2 = ei 2. (2.2) Стандартная ошибка уравнения регрессии SEE – это величина квадрата ошибки, приходящаяся на одну степень свободы регресси онной модели:

RSS SEE =, (2.3) k n где n – число объясняющих переменных в уравнении регрессии (фак торов).

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

Коэффициент детерминации R2 показывает, насколько уравне ние регрессии объясняет вариацию значений зависимой переменной относительно ее среднего значения, т.е. долю общей дисперсии зави симой переменной y, объясненной вариацией всех факторных пере менных x1…xm, включенных в уравнение регрессии.

Коэффициент детерминации может быть рассчитан по зависимо стям:

ESS RSS = R2 =, (2.4) TSS TSS где ESS – сумма квадратов отклонений, объясненная регрессионной моделью (объясненная сумма квадратов), ) ESS = ( yi y) 2, (2.5) здесь y – среднее арифметическое наблюдаемых значений зависимой переменной на множестве наблюдений i[1;

k];

TSS – полная сумма квадратов:

TSS = ( yi y ) 2. (2.6) Значения R2 не выходят за пределы [0;

1]. Чем ближе R2 к 1, тем точнее уравнение регрессии. Низкое значение R2 не обязательно сви детельствует о низком качестве регрессионной модели. Это может объясняться наличием существенных факторов, которые не включили в модель. Если R20,8, модель принято считать точной [32, 194, 245].

Для сравнения моделей с разным числом факторов, для того, что бы число факторов не влияло на статистику, R2 обычно заменяется на скорректированный коэффициент детерминации, который добавляет штрафы за дополнительные включенные факторы [32, 194, 245].

Скорректированный коэффициент детерминации R показывает долю объясненной дисперсии c учетом числа переменных уравнения регрессии [32, 194, 245]:

n R = R2 (1 R 2 ). (2.7) k n Скорректированный коэффициент детерминации не превосходит по величине множественный коэффициент детерминации R2. При большом объеме выборочной совокупности (kn) значения R2 и R практически не отличаются друг от друга.

Критерий Фишера F представляет собой отношение объясненной суммы квадратов ESS в расчете на одну независимую переменную к остаточной сумме квадратов RSS в расчете на одну степень свободы.

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

качества уравнения регрессии [32, 194, 245].

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

Проверка гипотезы о значимости модели множественной регрес сии заключается в проверке гипотезы о значимости коэффициента де терминации R2. Основная гипотеза Н0 состоит в предположении о не значимости коэффициента детерминации: R2=0. Обратная гипотеза Н состоит в предположении о значимости коэффициента детерминации:

R20. Данные гипотезы проверяются с помощью критерия Фишера F.

При проверке основной гипотезы Н0 наблюдаемое значение F-критерия сравнивается с табличным критическим значением F-критерия. Наблюдаемое значение F-критерия рассчитывается по выражениям [32, 194, 245]:

R 2 /n ESS/n ( ESS/TSS )/n F= = =. (2.8) RSS/(k n 1) ( RSS/TSS )/(k n 1) (1 R 2 )/(k n 1) Критическое значение F-критерия определяется как табличная функция Fкрит(a;

k1;

k2), где а – уровень значимости (вероятность, обычно a=0,95);

k1=n–1 и k2=k–n – число степеней свободы.

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

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

Проверка значимости коэффициентов уравнения регрессии. При составлении модели множественной регрессии выполняется проверка значимости коэффициентов уравнения регрессии bi, i[1;

p]. Основ ной гипотезой при этом является значимость их отличия от нулевого значения.

Основная гипотеза Н0 состоит в предположении о незначимости каждого из коэффициентов уравнения множественной регрессии:

H 0 : b0 = b1 =... = b p = 0. (2.9) Обратная гипотеза Н1 состоит в предположении о значимости каждого из коэффициентов уравнения множественной регрессии:

H 1 : b0 b1... b p 0. (2.10) Указанные гипотезы проверяются с помощью t-критерия Стью дента, который связан с частным F-критерием Фишера. Наблюдаемое значение t-критерия сравнивается с табличным критическим значени ем t-критерия.

При проверке основной гипотезы Н0 о значимости коэффициен тов уравнения множественной регрессии bi используется следующая взаимосвязь между t-критерием Стьюдента и F-критерием Фишера:

F. (2.11) t= Критическое табличное значение t-критерия Стьюдента определяет ся как функция tкрит(а;

k–l–1), где а – уровень значимости (вероятность);

k – объем выборочной совокупности;

l – число параметров, оцениваемых по выборке;

(k–l–1) – число степеней свободы, которое определяется по таблице распределений t-критерия Стьюдента [32, 194, 245].

При проверке основной гипотезы наблюдаемое значение частно го F-критерия Фишера рассчитывается по формуле R 2 ( y, x1 K xk ) R 2 ( y, x1 K xk 1 ) F ( xk ) = (k l ). (2.12) 1 R 2 ( y, x1 K xk ) Далее по (2.11) определяется наблюдаемое значение t-критерия.

При проверке основной гипотезы возможны следующие варианты.

При ttкрит основная гипотеза Н0 о незначимости коэффициента bk модели множественной регрессии отвергается, т.е. он признается зна чимым. При ttкрит гипотеза Н0 о незначимости коэффициента bk мо дели множественной регрессии принимается.

3. РАЗРАБОТКА МЕТОДИК ПЛАНИРОВАНИЯ ТРАЕКТОРИИ ПЕРЕМЕЩЕНИЯ ОБЪЕМНОГО ОБЪЕКТА-ГРУЗА В ДИСКРЕТНОМ ПРОСТРАНСТВЕ ЕГО КООРДИНАТ С УЧЕТОМ УГЛОВОЙ ОРИЕНТАЦИИ И ПРЕПЯТСТВИЙ.

СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДИК 3.1. Постановка задачи планирования траектории перемещения грузоподъемным краном груза в пространстве его координат с учетом угловой ориентации и препятствий В соответствии с поставленной целью работы необходимо ре шить задачу определения наиболее эффективных методик планирова ния траекторий перемещения груза ГПК в среде с препятствиями.

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

Анализ состояния вопроса в данной области позволил выделить несколько наиболее перспективных подходов к решению задачи пла нирования траектории на основе: генетического подхода;

алгоритмов роевого интеллекта;


алгоритма вероятностной дорожной карты;

на правленного волнового алгоритма.

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

2) направление вертикальной оси Y0 неподвижной системы координат O0Х0Y0Z0, в которой задано по ложение рабочей области с препятствиями, а также начальной и конеч ной точек перемещения груза совпадает с гравитационной вертикалью;

3) горизонтальная ось X0 неподвижной системы координат O0Х0Y0Z0 на правлена параллельно линии, соединяющей начальную sнач и конечную sкон точки условного центра груза на его траектории;

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

5) среда, в которой происходит перемещение, является полностью наблюдаемой и детерминированной в рассматриваемый отре зок времени – организованная неоднородная среда;

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

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

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

Также существует требование о том, что расположение грузового ка ната в процессе перемещения груза должно оставаться вертикальным (что регламентируется Правилами техники безопасности при экс плуатации стреловых самоходных кранов ВСН 274-88 [169]). Четвер тое допущение позволило использовать в предлагаемых методиках и алгоритмах гиперповерхность минимальных вертикальных координат условного центра груза с учетом его угловых координат (раздел 3.4).

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

Заданы линейные и угловые координаты груза в начальной sнач и конечной sкон точках траектории груза в пространстве (рис. 3.1):

sнач = [xн0;

yн0;

zн0;

н0;

н0];

sкон = [xк0;

yк0;

zк0;

к0;

к0], (3.1) где xн0, yн0, zн0 – линейные координаты точки начала локальной системы координат груза OgХgYgZg в неподвижной системе координат O0Х0Y0Z0, связанной с рабочей областью перемещений, соответствующие началь ному положению груза;

xк0, yк0, zк0 – линейные Препятствия Начальная координаты, соответст- Конечная точка sнач точка sкон вующие конечному по- (xн0, yн0, zн0, (xк0, yк0, zк0, ложению груза;

н0, н0 н0, н0) к0, к0) Yg – координаты углов L* Yg Zg Xg поворота груза вокруг осей Хg, Yg в начальной Og Zg Og Xg точке;

к0, к0 – угловые координаты, соответст вующие конечному по- Y ложению груза в про- Z странстве. Линейные X0 O координаты заданы в Рис. 3.1. Начальное и конечное положения условных линейных перемещаемого груза (пример) единицах (УЛЕ), угло вые – в радианах. Исходные направления осей Хg, Yg и Zg для отсчета углов поворота и во всех точках траектории груза совпадают с на правлениями осей Х0, Y0 и Z0 соответственно.

Ось X0 неподвижной системы координат согласно принятому до пущению № 3 направлена параллельно линии, соединяющей две точ ки в пространстве: начальную sнач и конечную sкон точки траектории (линейные координаты условного центра груза), что формализуется условием zн0=zк0. (3.2) Как показали исследования, это позволяет упростить расчет и значительно уменьшить объем вычислений для большинства предла гаемых методик.

Предварительная обработка исходных данных в случае их непол ного соответствия условиям задачи. Рассмотрим возможный расчет ный случай, когда начальная и конечная точки положения условного центра груза, а также исходная поверхность препятствий Y'ПР(x',z') за даны в некоторой прямоугольной системе координат O0'Х0'Y0'Z0', для которой выполняется допущение № 2 и не выполняется допущение № 3 (3.2). В этом случае исходные данные не полностью удовлетворяют условиям представления данной задачи. Необходимо осуществить пе ренос имеющихся исходных данных (координат дискретных точек), например полученных при решении других задач, в систему коорди нат O0Х0Y0Z0, удовлетворяющую (3.2). Для этого необходимо исполь зовать центроаффинное преобразование систем координат [122].

Преобразование системы координат O0'Х0'Y0'Z0', в которой опи сывается поверхность препятствий, с целью расположения начальной и конечной точек вдоль одной из осей координат (центроаффинное преобразование) выполняется по зависимостям, полученным с ис пользованием метода однородных координат, после их упрощения [122, 127].

Пусть имеются точки xн0' [xн0' yн0' zн0'] начала и цели (конца) пере xк0' мещения условного центра Y0=Y0' X0 ' груза с линейными коорди zн0' ' натами [xн0' yн0' zн0'] и [xк0' yк0' zк0' X zк0'] соответственно, задан xн ные в некоторой исходной [xк0' yк0' zк0'] системе координат xк O0'Х0'Y0'Z0' (рис. 3.2). Пере ход от исходной O0'Х0'Y0'Z0' Z0 Z0' к преобразованной O0Х0Y0Z системе координат будет Рис. 3.2. Центроаффинное преобразование системы координат O0'Х0'Y0'Z0' осуществляться поворотом (вид сверху, навстречу оси Y0') вокруг вертикальной оси Y0'.

Угол поворота ' будет равен '=atn((xк0'–xн0')/(zк0'–zн0')). (3.3) Точка с координатами x', y', z' в исходной системе координат O0'Х0'Y0'Z0' будет иметь в преобразованной системе координат O0Х0Y0Z0 следующие значения координат:

x=x'cos(')–z'sin(');

z= x'sin(')+z'cos(');

y=y'. (3.4) Подобным образом необходимо получить значения координат в преобразованной системе X0Y0Z0 для всех точек поверхности препят ствий. Затем в преобразованной системе координат необходимо сформировать ту же поверхность, но уже на новой равномерной дис кретной сетке X0Y0 с заданным шагом l=(xк0–xн0)/imax, (3.5) где imax – количество разбиений траектории на кусочно-линейные уча стки.

Для этого используется известный способ двухмерной табличной линейной интерполяции [65, 191, 193]. Интерполяция позволяет найти вертикальные координаты промежуточных точек вблизи расположен ных в пространстве узловых точек поверхности YПР(x,z).

Возникает также задача преобразования двух угловых координат груза ' и ' (углов поворота груза вокруг собственных осей Хg, Yg со ответственно), предварительно заданных в системе координат O0'Х0'Y0'Z0', в аналогичные угловые координаты и в преобразован ной системе координат X0Y0Z0.

Используя метод однородных координат [12, 127], сочетание двух угловых поворотов груза на углы ' и ' вокруг собственных осей координат OgХgYgZg можно представить в виде матрицы A' раз мером 44. Матрица A' определяется в результате определенной по следовательности перемножения матриц поворота системы координат груза OgХgYgZg вокруг соответствующих осей собственной системы координат, начальные направления которых совпадают с направле ниями осей системы координат O0'Х0'Y0'Z0':

A'=A'A', (3.6) где A', A' – матрицы поворота вокруг осей Хg и Yg соответственно, имеющие следующий вид [45, 127]:

0 sin ' 1 0 cos ' 0 0 cos ' sin ' 0 0 1 A ' = ;

A' =. (3.7) 0 sin ' cos ' 0 sin ' 0 cos ' 0 1 0 0 0 0 Отсюда cos ' sin ' sin 'sin ' cos ' cos 'sin ' A ' =. (3.8) sin 'cos ' sin ' cos 'cos ' 0 0 В то же время матрица поворотов A на углы и в системе ко ординат O0X0Y0Z0 может быть получена по тем же зависимостям под становкой в выражения (3.7), (3.8) значений и вместо ' и ':

A=AA. (3.9) Для определения иско xа' мых значений и предла гается наиболее простой в xа zаg= вычислительном отношении Xg X0 ' Y способ – использование пре ' zа образований координат век zа' X0 r тора Rag некоторой точки а а (рис. 3.3), принадлежащей Zg звену груза.

В качестве примера ис Z0' Z пользовались координаты r вектора Rag =[xag yag zag 1]T, Рис. 3.3. Определение угловых координат груза и в системе координат имеющие следующие значе O0Х0Y0Z0 (вид сверху, навстречу оси Y0) ния в собственной системе координат груза в УЛЕ:

xаg=0;

yаg=0;

zаg=1. (3.10) r При известных значениях ' и ' координаты вектора Rag могут быть перенесены в систему координат O0'Х0'Y0'Z0':

r v Ra ' = [ xa ' y a ' z a ' 1] = A 'Rag, T (3.11) а затем с использованием зависимостей (3.3), (3.4) – в систему коор динат O0Х0Y0Z0. В результате будут найдены численные значения ко ординат вектора, задающего положение точки а в системе O0Х0Y0Z0:


v Ra = [ xa y a z a 1]T. (3.12) Согласно (3.8) и (3.11), при подстановке в данные выражения и вместо ' и ' и при значениях координат точки а в собственной систем груза по (3.10) получены следующие зависимости:

xa= –sin;

ya= sin cos;

za=cos cos. (3.13) Отсюда =–arcsin(xa);

= arcsin(ya/cos). (3.14) Пуск Задание поверхности препятствий Y'ПР(x',z'), начальной и конечной точек положения груза: (xн0', yн0', zн0', н0', н0') и (xк0', yк0', zк0', к0', к0') '=atn((x – x )/(y – y )) n 1 n i=1:imax k=1: kmax x(i)=x'(i)cos(')–z'(j)sin(');

z(j)= x'(i)sin(')+z'(j)cos(');

y=y' xн0=xн0'cos(')–zн0'sin(');

zн0= xн0'sin(')+zн0'cos(');

yн0=yн0' xк0=xк0'cos(')–zк0'sin(');

zк0= xк0'sin(')+zк0'cos(');

yк0=yк0' l=(xк0–xн0)/imax Двухмерная табличная интерполяция YПР(x,z) Вычисление значений н0, н0 по н0', н0', используя выражения (3.8), (3.11), (3.3), (3.4), (3.14) Вычисление значений к0, к0 по к0', к0', используя выражения (3.8), (3.11), (3.3), (3.4), (3.14) Вывод результатов: YПР(x, z), (xн0, yн0, zн0, н0, н0), (xк0, yк0, zк0, к0, к0) Останов Рис. 3.4. Блок-схема алгоритма предварительной обработки исходных данных Последовательное использование выражений (3.8), (3.11), (3.3), (3.4), (3.14) с подстановкой значений н0', н0' для начальной точки, а затем к0', к0' для конечной точки положения груза позволяет полу чить значения н0, н0 и к0, к0 для соответствия условиям задачи (3.1).

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

После выполнения предварительной обработки данных (в случае ее необходимости) в неподвижной системе координат O0Х0Y0Z0 будет сформирована дискретная матрица высот препятствий YПР(i,k), где i, k – индексы координат x, z соответственно: i[1;

imax];

k[1;

kmax].

Линейные и угловые координаты груза заданы на равномерной дискретной сетке: i[1;

imax];

j[1;

jmax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax]. Индексы i, j, k соответствуют линейным перемещениям точки начала локальной системы координат груза соответственно вдоль осей X0, Y0, Z0, а индексы l, m – двум углам поворота груза, вокруг собственных осей соответственно (см. рис. 3.1). Задан u – шаг дис кретности угловых координат и.

В собственной локальной системе координат груза OgХgYgZg за v даны координаты множества точек { Rig }, ig[1;

cг] на поверхности объемного тела груза, определяющие его форму. Координаты точек [ ] v заданы векторами вида (R )ig = xig yig zig 1 T, где xig, yig, zig – ко ординаты точки ig в локальной системе координат груза.

Кроме того, в качестве исходных данных задачи выступают: lзап_г – запас расстояния в горизонтальном направлении, и lзап_в – запас рас стояния в вертикальном направлении, необходимые для построения полидистантной поверхности YЭ вокруг реальной поверхности пре пятствий YПР по методике, изложенной в разделе 3.3. Полидистантная поверхность YЭ используется во всех предложенных методиках поис ка оптимальной траектории.

В качестве целевой функции используются интегральные критерии оптимальности на основе линейных декартовых и угловых координат груза в точках его траектории. Известны такие интегральные критерии, как объем движения W, квадратичный функционал объема движения Wкв, среднее взвешенное длин линейных и угловых перемещений L [71, 120, 221]. Для груза, положение которого описывается пятью обобщенными координатами, функциональные зависимости определения перечислен ных критериев выглядят следующим образом:

W = 0 (c x x(t ) + c y y (t ) + c z z (t ) + c (t ) + c (t ))dt, t (3.15) где cx, cy, cz, с, с – весовые коэффициенты линейных и угловых ко ординат груза x, y, z,, соответственно;

x', y', z', ', ' – производ ные координат по времени;

t – время перемещения груза из начальной точки в конечную.

( ) Wкв = 0 c x x 2 (t ) + c y y 2 (t ) + c z z 2 (t ) + c 2 (t ) + c 2 (t ) dt ;

(3.16) t ) ( x (t ) + y (t ) + z (t ) + c 2 (t ) + 2 (t ) dt, L = t 2 2 (3.17) где c – весовой коэффициент угловых координат.

В качестве примера использовалось среднее взвешенное длин линейных и угловых перемещений (СВД) L. В случае дискретного представления траектории СВД Li1,j1 между двумя точками траекто рии с индексами i1 и j1 (3.17) может быть представлено в виде [38] Li1, j1 = (xi1 x j1)2 + ( yi1 y j1)2 + (zi1 z j1)2 + c ( i1 j1)2 + (i1 j1)2. (3.18) Полное выражение целевой функции отдельной траектории S для дискретного представления имеет вид [38] ( x x )2 + ( y y )2 + ( z z )2 + imax i 1 i 1 i i i i L=, (3.19) i = 2 + c ( i 1 ) + ( i i 1 ) 2 i где imax – число точек отдельной дискретной траектории.

Необходимо найти траекторию S* с оптимальным (минимальным) значением L* целевой функции L, представляющую собой траекторию перемещения из sнач в sкон:

L*=min {Lq }, q[1;

С]. (3.20) где {Lq} – множество значений целевой функции множества траекто рий {Sq}, представляющих собой дискретные траектории перемеще ния из sнач в sкон в виде смежных точек sнач, s2, s3, …, s(imax–1), sкон.

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

3.2. Обоснование критериев эффективности для сравнительной оценки методик и алгоритмов планирования траектории Для сравнительного анализа методик и алгоритмов планирования траекторий движения груза в среде с препятствиями необходимо обосновать критерии эффективности.

Известно, что лежащие в основе методик алгоритмы, разработан ные для решения одной и той же задачи, могут очень сильно отли чаться друг от друга по эффективности. В качестве критериев эффек тивности алгоритмов чаще всего используют такие показатели, как полноту, оптимальность, пространственную сложность, временную сложность и др. [34, 69, 74, 175, 205].

Полнота алгоритма гарантирует обнаружение существующего решения задачи. Оптимальность обеспечивает нахождение лучшего решения, чем все прочие возможные решения, по значению целевой функции. Пространственная сложность определяется объемом па мяти запоминающего устройства, необходимым для работы алгорит ма (а также задания исходных и/или выходных данных). Временная сложность зависит от быстродействия работы алгоритма [36, 39, 74, 132, 175, 225].

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

Все критерии также могут быть разделены по степени обобщения на глобальные (обобщенные) и локальные (частные).

Задача сравнения алгоритмов имеет практическое применение:

необходимо определить, насколько быстро алгоритмы реализуются при помощи средств вычислительной техники, сколько вычислитель ной памяти для них требуется и насколько они точны. Возможны два подхода к решению задачи сравнения алгоритмов: применение метода эталонных тестов (экспериментальный метод) и асимптотический анализ (аналитический метод) [74, 175].

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

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

снижение точности и недос товерность результатов сравнения при небольших объемах входных данных (причем понятие «небольших» объемов зависит от точных характеристик алгоритмов, конкурирующих с анализируемым);

не учитывается различная скорость доступа к элементам многомерных массивов в разных языках программирования и др. [35, 37, 39, 74, 132, 175, 225].

Известны очень эффективные с позиции асимптотического ана лиза алгоритмы (например, фибоначчиевы кучи), которые не исполь зуются на практике ввиду сложности программной реализации, боль ших значений констант, влияющих на общую сложность алгоритмов по сравнению с конкурирующими и т.д. [55, 57, 74, 175].

Трудно теоретически анализировать и т.н. «маленькие хитрости», т.е. некоторые малозначительные детали алгоритма, существенно влияющие на его эффективность. Окончательную оценку алгоритма и методики на его основе, как правило, можно дать лишь после апроба ции его в практических вычислениях [65].

В качестве частных количественных критериев метода асимпто тического анализа используются: асимптотическая временная слож ность, асимптотическая пространственная сложность и т.п. [35, 37, 39, 74, 132, 175, 225].

Иногда применяют асимптотический анализ алгоритмов для среднего случая вместо худшего, однако само определение «среднего»

варианта также затруднено для сложных алгоритмов и связано с субъективными оценками экспертов и аналитиков, которые должны принять определенные предположения по распределению наборов входных данных и функционированию алгоритма [57, 74, 175].

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

Недостаток метода эталонных тестов – возможную зависимость результатов сравнения от исходных данных задачи – предлагается компенсировать путем проведения достаточно большого числа расче тов (серии из n независимых вычислительных экспериментов) со сто хастическими значениями исходных данных с последующей стати стической обработкой полученных результатов [38, 88]. Вычисли тельные эксперименты при этом требуется выполнять на одном и том же оборудовании (одном ПК), алгоритмы реализовать на одном языке программирования. Метод эталонных тестов имеет большую прак тическую значимость по сравнению с методом асимптотического ана лиза.

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

Результат применения любого алгоритма для решения задачи, поставленной в разделе 3.1, может быть представлен в виде найден ной траектории S*: последовательности точек sp с координатами груза (xp, yp, zp, p, p), p[1;

imax] и значения целевой функции указанной траектории L*, определенного по (3.19).

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

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

Lусл= (L*/Lусл)100%, (3.21) где Lусл – условный глобальный оптимум решения задачи, определяе мый как минимальное значение из множества значений целевой функции, полученных при использовании различных методик, но для одних и тех же численных значений исходных данных задачи, Lусл=min{(L*)i}, i[1;

5], (3.22) здесь i – номер применяемой методики на основе: 1 – направленного волнового алгоритма;

2 – алгоритма роевого интеллекта;

3 – генети ческого подхода;

4 – алгоритма декомпозиции линейных и угловых координат;

5 – алгоритма вероятностной дорожной карты.

В работе [34] предложено разделение критериев оценки эффек тивности алгоритмов на три группы по целевому признаку, т.е. по на значению. Все критерии разделены на три группы: информационные, операционные и точностные [34].

Информационные характеристики определяют размер алгорит мов в пространстве, т.е. в запоминающей среде и каналах передачи информации средств реализации – в запоминающих устройствах ЭВМ и каналах устройств ввода-вывода данных машин. Операцион ные характеристики определяют реализуемость исследуемых алго ритмов во времени. Точностные характеристики определяют качество реализации алгоритмов на вычислительных средствах, а также высту пают как исходные данные для определения требований к параметрам (шаги квантования сетки координат и т. п.) задания исходных данных для расчета [34].

Соответственно пространственная сложность может быть отне сена к информационным критериям, временная сложность – к опера ционным критериям, полнота и оптимальность – к точностным кри териям.

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

Эти критерии имеют качественный характер [57, 74, 190, 220].

Алгоритм считается устойчивым по исходному параметру x, если решение y зависит от него непрерывно, т. е. малое приращение входной величины x приводит к малому приращению выходной величины y.

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

Данное определение вычислительной устойчивости заимствовано из теории автоматического управления и может быть применено к любому вычислительному алгоритму [2, 41, 54].

Алгоритм корректен, т.е. задача для вычислительного алгоритма считается поставленной корректно, если для любых значений исход ных данных из некоторого ограниченного множества ее решение су ществует, единственно и устойчиво по исходным данным [65, 74, 190].

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

Могут использоваться самые разнообразные частные количест венные критерии более низкого иерархического уровня по отноше нию к глобальным критериям устойчивости и сходимости, приме няемые для анализа соответствующих численных методов, например, скорость сходимости, критерий устойчивости по Ляпунову и т.д. [2, 41, 54].

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

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

1. Частные критерии, соответствующие глобальному критерию временной сложности: время расчетов Tp;

общее количество шагов (элементарных операций/битовых операций), выполняемых алгорит мом;

количество строк выполняемого кода и др.

2. Частные критерии, соответствующие глобальному критерию пространственной сложности: информационная длина исследуемого алгоритма M e ;

количество входных величин используемого алгорит ма;

количество выходных величин используемого алгоритма;

количе ство используемых в алгоритме констант;

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

объем информации, занимаемой ко дом программной реализации на носителе данных и др.

3. Частные критерии, соответствующие глобальному критерию оптимальности: максимальная абсолютная погрешность результи рующей величины алгоритма;

максимальная относительная погреш ность результирующей величины алгоритма;

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

4. Частные критерии, соответствующие глобальному критерию сходимости: скорость сходимости, интервал сходимости и др.

5. Частные критерии, соответствующие глобальному критерию устойчивости: критерий устойчивости по Ляпунову;

критерий устой чивости по Найквисту и др.

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

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

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

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

В табл. 3.1 приведены все критерии оценки эффективности алго ритмов с указанием наличия/отсутствия у каждого упомянутых клас сификационных признаков. Выделено 5 признаков классификации критериев, указанных в табл. 3.1: 1 – по степени обобщения;

2 – по характеру проведения исследований и получения результатов;

3 – по признаку математической природы;

4 – по признаку нали чия/отсутствия элементов вероятностного характера при задании ис ходных данных;

5 – по целевому признаку (назначению).

Используемые сокращения: МО – математическое ожидание;

ДИ – дисперсия. Знаком «+» показано наличие признака у критерия. На звания глобальных критериев выделены прописными буквами. Стро ки применяемых в настоящей монографии частных критериев выде лены затемнением.



Pages:     | 1 || 3 | 4 |   ...   | 9 |
 





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

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