УДК 621.87 : 51.74
,
Поиск оптимальной траектории ГРУЗА, ПЕРЕМЕЩАЕМОГО
АВТОКРАНОМ, в среде с произвольными препятствиями, с учетом координат угловой ориентации в трехмерном пространстве
Предложен способ решения задачи нахождения оптимальной траектории перемещаемого автомобильным краном груза в среде с произвольными препятствиями с учетом координат угловой ориентации груза в трехмерном пространстве.
Ключевые слова: автокран, препятствия, кратчайшая траектория, поиск траектории, координаты угловой ориентации.
При перемещении груза автомобильным краном могут возникать ситуации, когда между начальным и конечным требуемыми положениями груза находятся препятствия различных форм и размеров. Возможен обход препятствий поднятием груза над ними либо сбоку в горизонтальном направлении без поднятия, если высота препятствий достаточно велика или они вообще непреодолимы по высоте для данной конструкции автокрана. Из этого вытекает актуальность управления грузом в трех координатах пространства. Развитие автоматизированных систем управления кранами позволит перемещать груз по оптимальной траектории, обеспечивая минимизацию расстояния (а следовательно, повышение производительности) и одновременно плавность перемещения (ограничение первых двух производных по времени: скорости и ускорения).
При нахождении минимальной длины траектории перемещения груза, чтобы исключить его столкновение с препятствиями, применяют «раздувание» размеров препятствий на некоторую величину. Таким образом, кратчайшая траектория находится в среде с поверхностями, представляющими собой пространственные эквидистантные (равноудаленные) поверхности, соответствующие реальным поверхностям препятствий.
Общую задачу оптимизации траектории перемещения груза по всем 6 координатам, определяющим положение тела в пространстве, в ряде случаев можно разбить на 2 независимые подзадачи, решаемые отдельно: 1) оптимизация перемещения по 3 линейным координатам отдельной точки груза; 2) оптимизация перемещения груза по 3 угловым координатам поворота относительно заданной точки груза. Решить каждую из двух подзадач по отдельности можно намного проще, чем общую задачу. Такая декомпозиция возможна для грузов с примерно равными размерами в 3 (в некоторых случаях 2) измерениях (грузы равноосной формы) либо для компактных грузов любой (в том числе неравноосной) формы, но с ограниченными размерами. В этом случае будет получено решение, близкое к оптимальному.
Выполнение подзадачи 1 в описанном случае предполагает расчет и оптимизацию траектории перемещения характерной точки - начала координат системы груза - в среде с эквидистантными поверхностями-препятствиями, в эквидистантный радиус которых заложено расстояние от начала координат до наиболее удаленной точки периферии груза. Существуют традиционные подходы к решению задачи поиска минимальной длины траектории. Наиболее эффективны алгоритмы на взвешенных графах. Это относительно сложные алгоритмы [1]. Более простые алгоритмы не гарантируют, что найденная траектория будет кратчайшей.
Возможны разные подходы к созданию матрицы смежности графа, от эффективности и удачности выбора которых зависят точность и быстродействие алгоритмов поиска. Хорошие результаты поиска траектории точки были получены при реализации алгоритма создания матрицы смежности по «точкам видимости» на поверхностях препятствий, находящимся выше определенного уровня [2]. Соединялись только те вершины графа, которые «видимы» между собой. Траектория в пределах погрешности, создаваемой шагом дискретности сетки, приближалась к кратчайшей при любой форме поверхности препятствий.
Если габариты груза в трех измерениях сильно различаются между собой, то кратчайшая траектория движения точки груза уже не может гарантировать приближение к глобальному минимуму целевой функции. Траектория точки находится в среде с эквидистантными поверхностями, в то же время эквидистантный радиус служит для учета угловой ориентации груза относительно препятствий в момент их прохождения, которая переменна и заранее не известна. В этом случае необходимо решать сразу общую задачу.
При решении общей задачи интерес представляет оптимизация по целевой функции, учитывающей сразу все 6 координат тела в пространстве, например вида
(1)
где x, y,z, γ, ν, ω, – три линейные и три угловые координаты груза соответственно; k – весовой коэффициент для угловых координат.
Сформулирована задача: необходимо оптимально переместить тело произвольной формы из одного положения, заданного 6 координатами, в другое положение, с другими 6 координатами, с учетом препятствий произвольной формы. На каждую из координат груза могут быть наложены ограничения по предельным значениям. Данная задача может быть актуальна во многих прикладных областях, в том числе при перемещении грузов автокранами.
Целевая функция может быть задана в виде суммы расстояний (1), т. е. дискретно по отдельным точкам, расположенным, например, через равные промежутки вдоль одной из координатных осей (рис. 1). Если рассматривать 5 координат груза (за исключением X) в каждой точке пространства как отдельные переменные, каковыми они и являются (хотя и могут быть связаны между собой), то при количестве точек, равном 10, получим функцию 50 переменных и задачу условной оптимизации с линейными и нелинейными ограничениями на переменные в виде неравенств. Ограничения-неравенства могут накладываться на каждую переменную по отдельности (например, предельные ограничения), а также на группы по 5 переменных в каждой из 10 дискретных точек (ограничения, создаваемые эквидистантными поверхностями). Причем гиперповерхность целевой функции может иметь разрывы и пики в большом количестве, поскольку при пороговых значениях угловых координат груза линейные координаты вследствие ограничений, создаваемых препятствиями, могут меняться скачкообразно. На рис. 2 показано, как при достижении углом поворота груза некоторого порога минимальное предельное значение вертикальной координаты центра масс груза меняется скачкообразно.
а) б)
Рис. 1. Пример представления траектории груза, имеющего форму цилиндра, в виде дискретной последовательности расположений центра масс (средняя точка) через равные промежутки вдоль оси X: а – вид сбоку; б – вид сверху
Рис. 2. Скачкообразное изменение минимальной предельной координаты Z при достижении порогового значения углом γ (пример) |
Таким образом, условия для поиска глобального минимума традиционными методами самые неблагоприятные.
Известно, что гарантировать нахождение глобального минимума может перебор всех возможных сочетаний переменных с достаточно мелким шагом, но при подобном количестве переменных это невозможно, действует так называемое «проклятье размерности». Кроме того, заранее не известно, насколько мелким должен быть шаг [3].
Известны более быстрые современные алгоритмы оптимизации, такие, как «метод отжига», генетические алгоритмы и т. п. Однако они используют элементы случайности и поэтому могут найти единственно верное решение лишь с определенной вероятностью, которая зависит от времени поиска [4].
Детерминированные алгоритмы поиска кратчайшей траектории на взвешенных графах находят решение за достаточно короткий промежуток времени даже на графах большого размера [5]. Целесообразно использовать их и в данном случае, однако для этого необходимо подготовить матрицу смежности графа, вершины которого – отдельные положения груза со всеми его 6 координатами в разных точках рассматриваемой рабочей области пространства. Веса ребер графа в этом случае должны определяться как значения целевой функции (1) или подобной ей, учитывающей разность как линейных, так и угловых координат груза между двумя положениями.
Здесь, так же как и при поиске траектории движения точки, предлагается использовать в качестве вершин графа не все возможные положения груза (которые можно учесть с определенной дискретностью в 6-мерном пространстве собственных координат груза), а только те из них, в которых груз «касается» эквидистантной поверхности какой-либо своей точкой. Таким образом, в качестве вершин графа будут выступать те положения груза, при которых он приближается любой точкой своей поверхности к эквидистантной поверхности на достаточную величину. Соединенными будут только те вершины графа, которые «видимы» между собой. Для проверки условия «видимости» необходимо рассмотреть все промежуточные положения груза с определенной дискретностью между двумя вершинами графа, «видимость» или отсутствие «видимости» между которыми необходимо установить. В каждом из промежуточных положений 6 значений координат груза будут вычисляться способом линейной интерполяции, и для каждого промежуточного положения должно выполняться условие превышения любой точки поверхности груза над эквидистантной поверхностью.
Для уменьшения размеров матрицы смежности графа предлагается рассматривать только те положения груза, при которых его центр масс находится выше определенного уровня, например уровня нижней из двух точек положения центра масс начала/окончания пути.
Наибольшее время при реализации алгоритма занимает проверка условия «видимости» между узлами. Так, если учитывать узлы на горизонтальной сетке (рис. 1, б) с шагом дискретности в 1 м и для груза в форме цилиндра задать дискретность изменения двух угловых координат в 45°, а пределы изменения угловых координат –90…90°, то для рабочей области размером 10×10 м количество узлов графа может составить максимально 15125. Максимальное число узлов в графе возникает, когда вся поверхность в пределах рабочей области находится выше определенного уровня. В остальных случаях число узлов уменьшается. Например, для поверхности, приведенной на рис. 1, число узлов составляет 1628. Вычислительное время на проверку условия «видимости» составит в этом случае 168 с на компьютере средней производительности (Athlon+ 2.90 GHz), или 99 % от общего времени вычислений.
Даже при таком крупном шаге дискретности вычислительные затраты времени получаются значительными. Кроме того, формируется довольно грубая траектория, которую необходимо подвергнуть дальнейшей оптимизации.
Для этого предлагается использовать быстродействующий алгоритм локального поиска, или алгоритм «натягивания струны» [6]. Его суть заключается в том, что каждое из дискретных положений груза (9 положений из 11 в рассматриваемом примере (рис. 1), начальное и конечное исключаются как постоянные) последовательно подвергается коррекции с достаточно мелким шагом по 4 координатам с целью уменьшения значения целевой функции. При этом учитываются ограничения на координаты груза, создаваемые препятствиями. Можно провести аналогию с натягиванием нерастяжимой струны между препятствиями, но в нашем случае участвуют не только линейные, но и угловые координаты. Если повторить процедуру многократно для всех положений груза последовательно (со 2-го по 10-е положение несколько раз), то общая траектория как последовательность дискретных положений груза в конечном итоге минимизируется по целевой функции. Достоинством алгоритма «натягивания струны» является его быстродействие: для рассматриваемого примера при количестве итераций, равном 20, шаге дискретности линейных координат 0,03125 м и шаге дискретности угловых координат 0,0245 рад (≈ 1,4°) время вычислений составило около 5 с.
Поскольку результат поиска траектории на графе представляет собой несколько неравномерно расположенных положений груза, для получения положений груза через равные промежутки вдоль оси X (для последующего использования алгоритма «натягивания струны») использовался метод линейной интерполяции [6].
Описанный алгоритм «натягивания струны» является алгоритмом локального поиска, а именно реализацией циклического покоординатного спуска. Этот метод находит ближайший к начальному состоянию локальный минимум (максимум). При том условии, если начальное состояние поиска в ландшафте пространства состояний находится в самой глубокой «долине» (или «котловине», т. е. области искомого глобального минимума), алгоритм «натягивания струны» позволяет быстро прийти в глобальный минимум [6].
Таким образом, для нахождения оптимальной траектории перемещения тела в среде с произвольными препятствиями, предлагается использовать комбинированный алгоритм: поиск на взвешенном графе с целью нахождения грубого решения и попадания в самую глубокую «долину» (область глобального минимума) с последующим локальным поиском, реализуемым алгоритмом «натягивания струны».
Вычислительные эксперименты при различной форме поверхностей препятствий для груза, имеющего форму цилиндра, показали работоспособность предложенного алгоритма. Алгоритм может быть использован для поиска оптимальной траектории перемещения груза любой заданной формы при любой форме препятствий, заданной дискретно.
СПИСОК ЛИТЕРАТУРЫ
1. Богомолов, основы теории дискретных систем / , . – М.: Наука; Физматлит, 1997. – 368 c.
2. Щербаков, траектории перемещения груза автокраном в трехмерном пространстве с препятствиями / , // Вестн. Акад. воен. наук (спецвып– № 3 . – С. 270-273.
3. Powell, Warren B. Approximate Dynamic Programming: Solving the Curses of Dimensionality / Warren В. Powell. – New York: Wiley, 2007. – 488 p.
4. Панченко, алгоритмы: учеб.-метод. пособие / ; под ред. . – Астрахань: Астраханский университет, 2007. – 87 с.
5. Siek, J. G. The Boost Graph Library User Guide and Reference Manual / J. G. Siek, L.-Q. Lee, A. Lumsdaine. - Upper Saddle River; NJ:Pearson Education, 2002.
6. Черноруцкий, оптимизации в теории управления: учеб. пособие / . – СПб.: Питер, 2004. – 256 с.
Материал поступил в редколлегию 17.07.09.
