4)подход, при котором пространство возможных состояний объекта дискретно описывается явным образом как взвешенный граф (в виде матрицы весов или списка весов), а затем отдельным этапом осуществляется поиск кратчайшего пути на графе известными методами и алгоритмами поиска на графе (например, при помощи алгоритма Дейкстры);
5)подход, при котором используется неявное представление графа дискретных возможных состояний объекта (например, с помощью начального состояния и функции определения преемников). При этом процесс поиска оптимальной траектории совмещается с неявным представлением графа и не выделяется в отдельный этап.
Кроме того, все указанные подходы допускают возможность планирования траектории объемного объекта как во внешнем пространстве препятствий, так и в пространстве конфигураций какого-либо механизма (машины, в частности, ГПК). Также все они допускают возможность локализации найденной траектории, т.е. ее последующей локальной оптимизации.
Первым трем подходам (пп. 1–3) свойственны существенные не-
достатки и ограничения.
Недостатки подхода № 1: аналитическое описание пространства
спрепятствиями единой функцией не универсально, а в ряде случаев невозможно, например, при наличии нескольких отдельных объемных тел препятствий достаточно сложной формы. В большинстве случаев требуется упрощение формы препятствий, приводящее к дополнительной погрешности. Данный вопрос представляется темой отдельного научного исследования. Кроме того, в случае большого количества учитываемых координат объекта (более двух) возникает необходимость решения систем нелинейных дифференциальных уравнений высших порядков и громоздких дифференциальных уравнений с частными производными, что представляет определенные сложности.
Недостатки подхода № 2: достаточно детализированная траектория будет описываться слишком большим количеством переменных, оптимизация целевой функции которых займет неоправданно большое время. Так, например, при числе m учитываемых независимых переменных-координат объемного тела в пространстве в количестве 5 и разбиении траектории на 20 промежутков (n=20) получим целевую функцию 100 переменных.
Недостатки подхода № 3: неоптимальность генерируемой траектории с учетом препятствий, неизвестное заранее число шагов дис-
30
кретизации траектории, возможность достаточно крупных шагов дискретизации, затрудняющих восстановление промежуточных точек между ними, учитывая наличие препятствий. Одним из методов в рамках подхода № 3 является распространенный при поиске траекторий объектов метод потенциальных полей или потенциалов, однако он также не гарантирует нахождение оптимальной траектории и сопряжен со значительными вычислительными затратами [92, 210, 251].
Для наиболее эффективного решения поставленной в настоящей монографии задачи представляется целесообразным использовать подходы № 4 и 5, как более универсальные, и, в то же время, предоставляющие возможность использования эвристических данных о пространстве и объекте, которые могут значительно сократить время оптимизации. Примерами конкретных методик и алгоритмов в рамках данных подходов являются: метод рандомизации пространства (вероятностной дорожной карты, подход № 4), генетические алгоритмы, алгоритмы роевого интеллекта и разновидности волнового алгоритма (подход № 5).
Рассмотрим более подробно существующие методики и алгоритмы, которые применяются или потенциально могут применяться для планирования оптимальной траектории перемещения грузоподъемной машиной груза в пространстве с препятствиями.
Оптимизация траектории по обобщенным и составным критериям, а тем более многокритериальная оптимизация на сегодняшний день являются достаточно сложными проблемами даже при небольших объемах информации (малой размерности пространства и небольших размерах рассматриваемой области перемещений и груза). Для решения этих задач необходимо использование мощных современных технологий программирования и значительные вычислительные затраты, что ограничивает использование обобщенной и многокритериальной оптимизации траектории перемещения объемных объ- ектов-грузов в трехмерном пространстве в САУ ГПК.
Достаточно распространенный частный случай постановки задачи, во многих ситуациях допускающий использование в режиме реального времени, – минимизация траектории по критерию длины пути. Однако данная задача также не является тривиальной даже для двухмерного пространства.
К настоящему времени накоплено большое количество теоретических методов и алгоритмов планирования кратчайшей траектории движения объекта в пространстве с препятствиями. Задача поиска оптимальной траектории перемещения ГПК груза в пространстве может
31
решаться многими способами с применением различного математического аппарата.
Примем следующие допущения при описании задачи планирования оптимальной траектории перемещения ГПК груза в пространстве
спрепятствиями:
1.Задача поиска в случае заранее неизвестных препятствий сводится к последовательному решению ряда задач поиска траекторий среди статических препятствий, когда в каждый момент времени имеется квазистатическая карта этих препятствий.
2.Применяется интегральный критерий оценки и оптимизации траектории на основе линейных и угловых координат объекта (либо обобщенных координат механизма), который может быть как векторным, так и скалярным (например, линейная свертка или стратегия взвешенных сумм).
3.В случае применения векторного критерия оптимизации на все компоненты вектора целевой функции (частные критерии) могут быть наложены линейные ограничения сверху и снизу.
Втрехмерном евклидовом пространстве, являющемся частью многомерного функционального пространства поиска, задана ограниченная область поиска, в которую входят декартовы координаты начальной и конечной точек положения груза и в которой могут присутствовать препятствия произвольной формы и размеров. Препятствия могут быть заданы в виде аналитической функции либо в дискретном виде.
Необходимо найти траекторию, минимизирующую интегральную целевую функцию (функционал), зависящую от всех шести либо от части линейных и угловых координат груза (как вариант – от нескольких обобщенных координат механизма, реализующего перемещение объемного объекта-груза). Переменные целевой функции и сама целевая функция могут быть описаны явно (аналитическое выражение) либо заданы неявно, как, например, в случае поиска кратчайшего пути на графе.
Вслучае скалярного критерия оптимизации предполагается наличие нелинейной скалярной целевой функции, имеющей по крайней мере один экстремум в области поиска. В случае векторного критерия оптимизации применяется линейная свертка части компонент вектора при наложении линейных ограничений в виде неравенств на прочие компоненты.
Решением задачи планирования траектории является линия в многомерном пространстве, представляющая собой множество точек
32
положения груза при перемещении. Решение может быть получено в аналитическом виде (траектория как гладкая функция) либо дискретно в виде последовательности узловых точек на траектории.
Вчастных случаях размерность задачи может быть уменьшена исключением либо замораживанием значений некоторых угловых или линейных координат.
Для эффективного решения поставленной задачи требуется, чтобы методика или совокупность методик построения траектории были эффективными, т.е. быстрыми, достаточно точными, и удовлетворяли определенным предельным ограничениям на объем потребляемой машинной памяти в процессе реализации.
Классификационные признаки методик и алгоритмов поиска кратчайшей траектории перемещения объекта в пространстве с препятствиями. Все методики и алгоритмы поиска кратчайшей траектории могут быть разделены на группы по предложенным классификационным признакам, перечисленным ниже.
1. Размерность пространства положений объекта [234]:
1.1) методики поиска в двухмерном пространстве положений груза (например, поиск траектории движения точки на плоскости);
1.2) методики поиска в трехмерном пространстве положений груза (например, поиск траектории движения точки в пространстве; поиск в плоскости траектории движения проекции тела с одной допустимой вращательной степенью свободы);
1.3) методики поиска в четырехмерном пространстве положений груза (поиск траектории движения тела с одной допустимой вращательной степенью свободы в пространстве);
1.4) методики поиска в пятимерном пространстве положений груза (поиск траектории движения тела с двумя допустимыми вращательными степенями свободы в пространстве);
1.5) методики поиска в шестимерном пространстве положений груза (поиск траектории движения тела с тремя вращательными степенями свободы в пространстве);
…и.т.д.
Вчастных случаях к трем линейным измерениям Евклидова пространства добавляются один, два или три угла поворота груза относительно осей неподвижной системы координат. В случае рассмотрения пространства конфигураций машины (обобщенных координат механической системы, перемещающей груз), размерность пространства может быть еще больше.
33
2.Размерность внешнего геометрического пространства, в котором заданы препятствия:
2.1) методики, работающие с препятствиями, заданными в двухмерном пространстве (на плоскости);
2.2) методики, работающие с препятствиями, заданными в трехмерном пространстве.
3.Способ описания препятствий:
3.1) аналитическое (континуальное, непрерывное) описание препятствий в функциональном виде;
3.2) численное (дискретное) описание препятствий (массив значений высот в отдельных точках карты или в матрице поля высот препятствий; трехмерный массив занятых препятствиями и свободных узлов пространственной решетки или воксельная модель пространства и т.п.);
4. Способ поиска искомой траектории:
4.1. аналитический поиск (классические аналитические методи-
ки);
4.2.численный поиск траектории в виде вектора, состоящего из набора переменных, входящих в список аргументов целевой функции (численные методики оптимизации аналитической или дискретной функции);
4.3.численный поиск с использованием математического аппарата теории графов. Полученная траектория представляет собой последовательность точек, задающих положение груза в многомерном пространстве;
4.4.прочие численные методики поиска, не использующие набор переменных и явное представление в виде графов.
Кроме того, отдельные группы методов могут обладать набором своих, присущих только им, классификационных признаков, часть из которых будет рассмотрена ниже.
Рассмотрим более подробно способы поиска траектории (п. 4).
4.1.Аналитические методики используют классический аппарат бесконечно малых. Достоинством аналитических методов является возможность получения общего решения с произвольной точностью, которое позволяет составить полное представление о влиянии различных параметров на целевую функцию. Недостатки – отсутствие универсальных алгоритмов для произвольных расчетных случаев конфигурации препятствий, сложность алгоритмов, что делает аналитические методики неприменимыми для многих расчетных случаев.
34