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

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

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


Pages:   || 2 | 3 | 4 | 5 |   ...   | 9 |
-- [ Страница 1 ] --

М.С. Корытов

АВТОМАТИЗАЦИЯ СИНТЕЗА

ОПТИМАЛЬНЫХ ТРАЕКТОРИЙ

ПЕРЕМЕЩЕНИЯ ГРУЗОВ

МОБИЛЬНЫМИ ГРУЗОПОДЪЕМНЫМИ

КРАНАМИ В НЕОДНОРОДНОМ

ОРГАНИЗОВАННОМ

ТРЕХМЕРНОМ

ПРОСТРАНСТВЕ

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Сибирская государственная автомобильно-дорожная

академия (СибАДИ)»

М.С. Корытов АВТОМАТИЗАЦИЯ СИНТЕЗА ОПТИМАЛЬНЫХ ТРАЕКТОРИЙ ПЕРЕМЕЩЕНИЯ ГРУЗОВ МОБИЛЬНЫМИ ГРУЗОПОДЪЕМНЫМИ КРАНАМИ В НЕОДНОРОДНОМ ОРГАНИЗОВАННОМ ТРЕХМЕРНОМ ПРОСТРАНСТВЕ Монография Омск СибАДИ 2012 УДК 621.873.3 : 681.5 ББК 39.922.233 : 32.965 К 66 Рецензенты:

д-р техн. наук, проф. В.Н. Сорокин (ОмГТУ);

д-р техн. наук, проф. Д.И. Чернявский (ОмГТУ) Монография одобрена редакционно-издательским советом СибАДИ.

Корытов М.С.

К 66 Автоматизация синтеза оптимальных траекторий перемещения гру зов мобильными грузоподъемными кранами в неоднородном организован ном трехмерном пространстве : монография / М.С. Корытов. – Омск: СибАДИ, 2012. – 380 с.

ISBN 978–5–93204–621– Разработаны методики синтеза оптимальных траекторий перемещения объ екта-груза в неоднородном организованном трехмерном пространстве;

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

Табл. 8. Ил. 184. Библиогр.: 253 назв.

© ФБГОУ ВПО «СибАДИ», ISBN 978–5–93204–621– ОГЛАВЛЕНИЕ Введение................................................................................................................. 1. Анализ состояния вопроса в предметной области.................................... 1.1. Актуальность разработки методик и алгоритмов планирования траек тории перемещения объемных грузов грузоподъемными кранами в трех мерном пространстве с препятствиями. Тенденции развития грузоподъ емных кранов, их приборов безопасности и систем управления.................. 1.2. Обзор существующих САПР с функциями планирования и оптимизации траектории объектов.......................................................... 1.3. Современное состояние исследований в области оптимизации траекторий движения объектов в неоднородном организованном пространстве.................................................................................................. 2. Общая методика исследований планирования рабочих процессов мобильных грузоподъемных кранов в неоднородном организованном трехмерном пространстве.................................................................................. 2.1. Методика теоретических исследований планирования рабочих процессов мобильных грузоподъемных кранов в неоднородном орга низованном трехмерном пространстве....................................................... 2.2. Методика проведения экспериментальных исследований................ 3. Разработка методик планирования траектории перемещения объемного объекта-груза в дискретном пространстве его координат с учетом угловой ориентации и препятствий. Сравнительный анализ методик..................................................................................................................... 3.1. Постановка задачи планирования траектории перемещения грузо подъемным краном груза в пространстве его координат с учетом уг ловой ориентации и препятствий.................................................................. 3.2. Обоснование критериев эффективности для сравнительной оцен ки методик и алгоритмов планирования траектории.................................. 3.3. Методика построения полидистантных поверхностей вокруг ре альных поверхностей препятствий, заданных дискретно.......................... 3.4. Методика построения гиперповерхности минимальных значений вертикальных координат условного центра груза с учетом его угло вых координат.................................................................................................. 3.5. Методика дискретной локальной оптимизации заданной траекто рии в неоднородном организованном трехмерном пространстве............. 3.6. Методика планирования траектории на основе генетического подхода............................................................................................................. 3.7. Методика планирования траектории на основе модифицирован ного алгоритма роевого интеллекта.............................................................. 3.8. Методика планирования траектории на основе модифицирован ного алгоритма вероятностной дорожной карты........................................ 3.9. Методика планирования траектории на основе алгоритма деком позиции линейных и угловых координат..................................................... 3.10. Методика планирования траектории на основе модифицирован ного направленного волнового алгоритма................................................... 3.11. Сравнительный анализ алгоритмических и программных реали заций методик планирования траектории.................................................... 4. Разработка методик планирования траектории перемещения объемного объекта-груза в пространстве конфигураций грузоподъем ного крана с учетом угловой ориентации груза и препятствий.................. 4.1. Постановка задачи планирования траектории перемещения грузо подъемным краном груза в пространстве конфигураций грузоподъем ного крана с учетом угловой ориентации и препятствий........................... 4.2. Обоснование критериев эффективности перемещения груза в пространстве конфигураций грузоподъемного крана................................. 4.3. Методика определения управляемых координат грузоподъемного крана по известным координатам груза....................................................... 4.4. Методика проверки положения автомобильного крана в про странстве конфигураций по ограничению на устойчивость...................... 4.5. Методика дискретной локальной оптимизации заданной траекто рии в среде с препятствиями по критериям эффективности в про странстве конфигураций................................................................................. 4.6. Методика определения временной функции стоимости изменения управляемых обобщенных координат грузоподъемного крана................ 4.7. Методика определения энергетической функции стоимости изме нения управляемых обобщенных координат грузоподъемного крана..... 4.8. Методика планирования траектории в пространстве конфигура ций грузоподъемного крана на основе алгоритма вероятностной до рожной карты с ограничениями по устойчивости...................................... 4.9. Методика оптимизации технологических параметров рабочего процесса грузоподъемного крана по принятым критериям эффектив ности перемещения груза............................................................................... 4.10. Результаты исследования комплекса методик оптимизации тех нологических параметров рабочего процесса грузоподъемного крана по критериям эффективности, определяемым в пространстве конфи гураций............................................................................................................. 5. Разработка методик оптимизации параметров совмещенного рабочего процесса двух грузоподъемных кранов, перемещающих общий груз............................................................................................................... 5.1. Постановка задачи оптимизации технологических параметров со вмещенного рабочего процесса двух грузоподъемных кранов, пере мещающих общий груз................................................................................... 5.2. Обоснование критериев эффективности совмещенного рабочего процесса двух грузоподъемных кранов, перемещающих общий груз..... 5.3. Методика определения значений комплексных относительных критериев эффективности совмещенного рабочего процесса двух гру зоподъемных кранов, перемещающих общий груз..................................... 5.4. Методика проверки пересечения двух грузоподъемных кранов....... 5.5. Методика оптимизации технологических параметров совмещен ного рабочего процесса двух грузоподъемных кранов, перемещающих общий груз........................................................................................................ 5.6. Результаты исследования комплекса методик оптимизации техно логических параметров совмещенного рабочего процесса двух грузо подъемных кранов, перемещающих общий груз, по предложенным критериям эффективности.............................................................................. 6. Инженерные разработки. Результаты экспериментальных исследо ваний грузоподъемного крана........................................................................... 6.1. Обоснование информационных параметров процесса управления положением платформы грузоподъемного крана.

...................................... 6.2. Разработка методики автоматического горизонтирования опорной платформы грузоподъемного крана с выносными опорами...................... 6.3. Экспериментальные исследования рабочего процесса стрелового гидравлического автокрана............................................................................ 6.4. Инженерные разработки и рекомендации по заземлению и повы шению устойчивости отдельно стоящего мобильного грузоподъемно го крана, а также созданию самоходного двухстрелового крана.............. Заключение............................................................................................................ Библиографический список............................................................................... ВВЕДЕНИЕ Совершенствование строительных и подъемно-транспортных машин с целью повышения их производительности, обеспечения лучшего качества выполнения строительно-монтажных и подъемно транспортных работ, снижения затрат на их производство, расшире ния технологических возможностей неразрывно связаны с вопросами технологической эксплуатации машин.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

на разработку методов геометрического модели рования проектируемых объектов, в частности неоднородного орга низованного пространства, в котором оптимизируется траектория пе ремещения груза ГПК.

1. АНАЛИЗ СОСТОЯНИЯ ВОПРОСА В ПРЕДМЕТНОЙ ОБЛАСТИ 1.1. Актуальность разработки методик и алгоритмов планирования траектории перемещения объемных грузов грузоподъемными кранами в трехмерном пространстве с препятствиями. Тенденции развития грузоподъемных кранов, их приборов безопасности и систем управления Оптимизация траектории перемещения объекта в неоднородном организованном пространстве по принятым критериям оптимально сти является фундаментальной научной проблемой.

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

Самоходные стреловые ГПК являются одним из наиболее рас пространенных средств механизации в промышленности и строитель стве, в складском хозяйстве, цехах машиностроительных предпри ятий, в портовых терминалах и т.д.

Можно выделить следующие тенденции развития самоходных ГПК и их систем управления [42, 75, 151, 178]:

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

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

2) расширение технологических возможностей и показателей ГПК: повышение грузоподъемности, увеличение размеров зоны, об служиваемой отдельным ГПК;

3) оптимизация движений разгона, торможения и скорости пе ремещения груза;

4) автоматизация рабочих процессов ГПК: исключение челове ка-оператора за счет установки и использования для автоматического перемещения грузов бортового устройства управления на базе микро процессоров или ПЭВМ.

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

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

Возможны также комбинированные варианты перемещения. Из этого вытекает актуальность управления грузом, перемещаемым ГПК, в трех координатах пространства [178].

Для выполнения при помощи ГПК некоторых видов монтажных, строительных и реконструкционных работ в условиях стесненной го родской застройки и производственных сооружений необходима же сткая отработка определенной траектории [178].

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

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

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

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

координатную защиту, также блокировкой приводов, при приближе нии звеньев крана к недопустимым областям пространства или ЛЭП [49, 50, 150, 176, 177].

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

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

1) построение плана оптимальной траектории перемещения ГПК груза в неоднородном организованном пространстве;

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

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

Для комплексной автоматизации ГПК необходимы следующие основные компоненты системы автоматического управления [151]:

1) рабочее оборудование (механическая система, гидравлический привод) и электрические устройства;

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

3) методики, алгоритмы и программное обеспечение для управ ления и контроля движением («отработка» спланированной траекто рии);

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

Пункты № 1 и частично № 4 уже присутствуют в виде самого ГПК, его приводов и приборов безопасности, в комплект которых входит ряд датчиков, регистрирующих параметры ГПК в течение все го рабочего цикла.

При этом необходимо отметить, что перспективными направле ниями развития и совершенствования уже использующихся приборов безопасности и регистраторов параметров ГПК в настоящее время яв ляются [47, 75, 76, 189]:

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

- оснащение ГПК устройствами беспроводной передачи данных типа Wi-Fi, Bluetooth, а также модемами типа GSM/GPRS с выходом в Интернет по сетям мобильной сотовой связи;

- оснащение ГПК бортовыми приемниками спутниковых сигна лов GPS/GLONASS;

- применение видеорегистрации (как вариант – лазерного скани рования) рабочей зоны, оборудования ГПК и груза.

В перспективе это должно привести к интеграции многофунк циональных микропроцессорных приборов и систем безопасности с системами управления ГПК [75, 76, 189].

а) б) в) Рис. 1.1. Приборы безопасности, используемые на ГПК: а – блок индикации ОГМ240 в кабине крановщика;

б – ОНК-140С с комплектом датчиков;

в – блок индикации ОНК-160С в кабине крановщика Используемые в настоящее время в обязательном порядке на стреловых самоходных ГПК системы безопасности типов ОНК-140С, ОНК-160С и ОГМ240 (рис. 1.1) на микропроцессорах, согласно Пра вилам ПБ 10-382-00, производят регистрацию следующего мини мального набора параметров: угла наклона стрелы, длины стрелы, уг ла поворотной платформы, давлений в поршневой и штоковой полос тях гидроцилиндра подъема стрелы [129, 170, 176, 177].

На основе измеренных значений перечисленных параметров вы числяется ряд других: фактические масса груза, вылет, грузовой мо мент [129, 170, 176, 177], которые выводятся на панель блока отобра жения индикации.

Перспективное оснащение ГПК бортовыми приемниками спут никовых сигналов GPS/GLONASS открывает возможность для гло бального спутникового позиционирования, т.е. пространственного (3D) контроля положения звеньев и груза ГПК с высокой точностью в реальном времени. Подобные системы уже широко используются на различных видах строительной, дорожной, горной и сельскохозяйст венной техники (автогрейдерах, бульдозерах, экскаваторах, катках, фронтальных колесных погрузчиках и др.) [20, 53, 183, 198, 250].

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

датчиков, алгоритмов вычислительной обработки сигналов) точность позиционирования (погрешность определения координат) составляет от 2–3 см до 1–6 мм [198, 250].

На рис. 1.2 в качестве примера приведены места установки эле ментов системы глобального спутникового позиционирования япон ского производителя Topcon 3Dxi на экскаваторе. Бортовой компью тер системы GX-60 имеет сенсорный дисплей, установлена операци онная система Windows XP, частота процессора 650 МГц. Поддержи вается беспроводная технология Bluetooth, имеются порты USB, Ethernet, RS-485, CAN и RS-232 с поддержкой USB-накопителей, ав томатическая регулировка подсветки. Система одновременно прини мает спутниковые сигналы GPS и GLONASS, что повышает точность позиционирования (технология GPS+) [183].

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

5 1 Рис. 1.2. Система 3D-управления экскаватором Topcon 3Dxi, места установки элементов системы на экскаваторе: 1 – датчики наклона;

2 – бортовой компью тер GX-60;

3 – радиоантенна;

4 – антенна GPS+;

5 – спутниковый приемник GPS+ а) б) г) в) д) Рис. 1.3. Лазерные наземные 3D-сканеры (а, б, в) и полученные при 3D сканировании графические отображения промышленных и строительных объектов в виде облака точек (г, д) (примеры) Применение видеорегистрации и лазерного сканирования рабо чей зоны, оборудования ГПК и груза (рис. 1.3), а также одновремен ное использование уже разработанных и действующих систем и тех нологий технического (компьютерного) зрения, создания на их основе цифровых 3D-моделей объектов архитектуры и строительства позво ляет создать цифровые модели рабочей области с препятствиями, звеньев оборудования и объемного тела груза, отслеживать изменения их взаимного расположения в реальном времени рабочего процесса [29, 30, 47, 73, 165, 168, 182, 239].

Лазерный 3D-сканер – это прибор, оснащенный высокоскорост ным безотражательным лазерным дальномером и системой изменения направления луча лазера – специальным поворотным зеркалом. Ла зерные 3D-сканеры принадлежат к категории активных систем скани рования. Они автоматически пульсирующим лучом лазера сканируют определенную область окружающего пространства и фиксируют вре мя, затрачиваемое световым лучем на преодоление двойного расстоя ния от лазера до сканируемой поверхности (аналогичный принцип используется в радиолокационных установках) [26, 29, 73, 168, 172, 239].

В настоящее время подобные приборы находят широкое приме рение во многих отраслях промышленности, геодезии, строительства и пр.;

применяются для съемки и изучения горного месторождения или карьера в маркшейдерском и горном деле, для создания точных моделей существующих объектов реконструкции в строительстве и архитектуре, получения цифровых 3D-моделей элементов конструк ций при выполнении съемок на промышленных предприятиях и во внутрицеховых помещениях [26, 29, 73, 168, 172, 214, 239].

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

Преимущества наземного лазерного сканирования перед конку рирующими технологиями оцифровки объектов трехмерного про странства [29, 134, 168, 172, 214]:

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

- очень высокая точность измерений;

- безопасность съемки опасных и труднодоступных объектов;

- беспроводная Wi-Fi связь с ПК.

Пределы заявленных технологических возможностей сущест вующих лазерных 3D-сканеров на текущий момент следующие [29, 134, 168, 172]:

- плотность точек лазерного сканирования может составлять от 0,25 мм до 1 м и более;

- обзорность сканеров может составлять максимально до 360° по горизонтали и до 300° по вертикали;

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

- дальность сканирования от 1 м до 2 км (максимально в ряде мо делей);

- погрешность определения координат точки по любой из трех осей неподвижной системы координат пространства (X0, Y0, Z0) – не более 6 мм при расстоянии до объекта менее 50 м и не более 50 мм при расстоянии до 2 км;

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

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

В результате 3D-сканирования формируется массив (т.н. облако) не связанных между собой точек (point cloud), каждая из которых имеет 3 пространственные координаты в неподвижной системе O0X0Y0Z0 и, в ряде моделей 3D-сканеров информацию о псевдоцвете.

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

Пуск 1 Ввод исходных данных:

Пуск 1 2 Ms(i1,j1), i1[1;

iскан];

j1[1;

3];

Ввод исходных данных: l Ms(i1,j1), i1[1;

iскан];

j1[1;

3];

i ymin;

l i=1;

i imax;

i=i+ i j i=1;

ijmax;

i=i+ j=1;

j jmax;

j=j+ k k k=1;

kkmax;

k=k+ k=1;

kkmax;

k=k+ YПР(i,k)=ymin Vox(i, j, k)= k k i j 8 i i i1=1;

i1iскан;

i1=i1+ i = Ms(i1, 1) l ;

9 i k = Ms(i1, 3) l i1=1;

i1iскан;

i1=i1+ i = Ms(i1, 1) l ;

Нет (iimax) j = Ms(i1, 2 ) l ;

(kkmax) k = Ms(i1, 3) l Да 11 Нет Ms(i1,2)YПР(i,k) (iimax) Нет (jjmax) Да (kkmax) YПР (i, k)=Ms(i1,2) Да i1 Vox(i, j, k)= 14 i Вывод результатов:

YПР Вывод результатов:

Останов Vox Останов а) б) Рис. 1.4. Блок-схемы алгоритмов преобразования облака точек результатов ла зерного сканирования: в матрицу поля высот препятствий (а) и в воксельную модель пространства (б) Для планирования траекторий перемещения ГПК объемных объ ектов-грузов в среде с препятствиями последнюю удобнее всего представлять в виде воксельной модели или даже при принятии опре деленных допущений в виде матрицы поля максимальных высот пре пятствий, занимающей на порядок меньше места в памяти ПК. Из вестны работы по преобразованию облака точек в 3D-модели город ской среды [223].

Однако для анализируемой проблемы оптимизации траектории груза ГПК не требуется столь высокая степень детализации простран ственных данных. Шаг дискретизации воксельной модели или сетки поля высот препятствий рабочей области l, учитывая значительные размеры последней (диаметр рабочей области может составлять до нескольких десятков метров в зависимости от марки, конструкции и типоразмера ГПК) и перемещаемых грузов, может быть принят отно сительно крупным, порядка 10–1 м.

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

В блок-схемах предложенных алгоритмов использованы сле дующие условные обозначения: Ms – матрица результатов лазерного сканирования (координат облака точек) размером [iскан3];

iскан – об щее число точек облака отдельного сканирования;

YПР (i, k) – отдель ный элемент матрицы поля высот препятствий [YПР] с индексами i, k, задающими положение точки поля по двум горизонтальным осям (X0, Z0 соответственно) неподвижной системы координат O0X0Y0Z0 с ша гом l;

Vox(i, j, k) – отдельный элемент массива воксельной модели пространства с индексами i, j, k, задающими положение точек про странства по осям X0, Y0, Z0 соответственно неподвижной системы ко ординат O0X0Y0Z0 с шагом l;

ymin – определенное начальное значение элементов матрицы поля высот препятствий [YПР].

Реализация беспроводного автоматического считывания инфор мации посредством технологий Wi-Fi, Bluetooth и модемов типа GSM/GPRS по сетям мобильной сотовой связи позволит осуществ лять, в том числе дистанционно, управление совмещенным рабочим процессом двух или нескольких ГПК, перемещающих общий груз.

Таким образом, для полного выполнения п. 4) условий комплекс ной автоматизации ГПК (стр. 11) [151] дополнительно необходимо осуществить:

1) глобальное позиционирование движущихся элементов обору дования ГПК и груза в реальном времени с использованием системы GPS/GLONASS;

2) видеорегистрацию и/или лазерное сканирование рабочей зоны с препятствиями, оборудования ГПК и груза с использованием лазер ных наземных 3D-сканеров;

3) оцифровку результатов видеорегистрации и/или лазерного сканирования рабочей зоны с препятствиями и груза и создание мо делей пространства по предложенным алгоритмам преобразования облака точек (см. рис. 1.4).

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

Для выполнения п. 3 условий комплексной автоматизации ГПК (стр. 11) в настоящее время разработаны многочисленные методики и алгоритмы для обеспечения движения ГПК груза по заданной траек тории. Они позволяют автоматически стабилизировать положение груза и управлять его движением, т.е. осуществлять «отработку» за данной траектории, в том числе при наличии случайных возмущаю щих воздействий. Используются такие приемы, как применение спе циальных схем подвеса, различных стабилизационных платформ, же сткого подвеса, стабилизация движения при помощи управляющих алгоритмов систем автоматического управления на основе традици онной булевой и нечеткой логики и др. [6, 17, 48, 144, 145, 179, 200].

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

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

1.2. Обзор существующих САПР с функциями планирования и оптимизации траектории объектов Функции автоматизированного планирования и/или оптимизации траектории движения объектов (планирования и/или оптимизации пу ти) присутствуют как в ряде традиционных универсальных САПР ми рового уровня, так и в некоторых специализированных САПР.

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

1) специализированные САПР – трассировщики печатных плат;

2) универсальные САПР различного уровня, в которых (либо в их приложениях/расширениях) в качестве одной из дополнительных ча стных специфических функций присутствует функция планирования и оптимизации пути в определенной предметной области;

3) специализированные ГИС-системы пространственного анализа данных рельефа поверхности Земли;

4) игровые «движки» (middleware-программы, специализирован ные вычислительные ядра, или библиотеки подпрограмм), предназна ченные для быстрого поиска некоторых неоптимальных в общем слу чае гладких траекторий движения игровых персонажей при условии непересечения с препятствиями;

5) специализированные научные и инженерные САПР, предна значенные для автоматизированного планирования и оптимизации траектории движения объектов.

Рассмотрим примеры наиболее эффективных и распространен ных представителей САПР перечисленных пяти групп.

1. К специализированным САПР, предназначенным для автома тической топологической трассировки печатных плат, относятся про дукты: TopoR компании Эремекс (РФ), OrCAD компании Cadence Design Systems (США), PROTEUS VSM компании Labcenter Electronics (Великобритания), Altium Designer компании Altium Limited (Австра лия) и многие другие [167, 180, 185].

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

2. Проектирование кабельных и/или трубопроводных систем с функцией автоматического прокладывания (трассировки) электро проводов (трубопроводов) в трехмерном пространстве с препятствия ми присутствует в ряде приложений/расширений универсальных САПР: AutoCAD Plant 3D компании Autodesk (США), Autodesk Inventor Routed Systems Suite, Bentley AutoPLANT компании Bentley Systems (США), SolidWorks Routing компании Dassault Systemes (Франция), Model Studio CS Трубопроводы – расширение САПР AutoCAD, разработанное компанией CSoft (Россия), КОМПАС-3D Трубопроводы 3D компании Аскон (Россия) и др. При этом миними зируется длина пути электропровода (трубопровода), в ряде продук тов дополнительно возможно задание определенного минимального расстояния до препятствий [139, 143, 152, 185].

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

3. К третьей группе относятся ГИС-системы: AutoCAD Map 3D компании Autodesk, Гис Zulu компании Политерм (Россия), ArcGIS компании ESRI (США), свободная кроссплатформенная система Quantum GIS на площадке SourceForge, системы GRASS, gvSIG с от крытым исходным кодом, 2ГИС и многие другие [10, 67, 68, 130].

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

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

4. Отдельную группу программных продуктов, которые могут быть классифицированы как специализированные САПР с функциями планирования и оптимизации траектории объектов, составляют т.н.

игровые middleware-«движки» с функциями поиска свободных от столкновения путей: SpirOps AI французской компании SpirOps, Kynapse AI компании Autodesk, NavPower AI компании BabelFlux (США), PathEngine одноименной французской компании и др. [207, 236, 240, 248]. Необходимо отметить, что функции игровых «движ ков» не ограничиваются планированием траекторий отдельных игро вых персонажей и позволяют моделировать движение больших групп персонажей совместно.

Планируемая траектория Игровой персонаж Препятствия Рис. 1.5. Пример планирования траектории от дельного игрового персонажа в игровом уровне с препятствиями при помощи Autodesk Kynapse Наиболее известный и распространенный игровой middleware «движок» Kynapse компании Autodesk, предназначенный для реали зации искусственного интеллекта (AI) в играх, позволяет осуществ лять поиск пути юнитов (игровых персонажей) на карте и на сложном трехмерном ландшафте с препятствиями (рис. 1.5) [207].

Другой распространенный «движок» для поиска гладких траек торий движения юнитов в различных играх, NavPower, позволяет ав томатически генерировать полигональные навигационные сетки над всеми проходимыми для юнита поверхностями уровня, используя геометрию уровня в качестве исходных данных [236].

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

Расширение «движка» NavPower FlightPak позволяет планиро вать движение летающих и плавающих в игре объемных объектов юнитов в трехмерном пространстве со множеством выпуклых объем ных тел препятствий [236].

PathEngine – еще одна компьютерная программа, подпрограмм ное обеспечение (англ. middleware), предназначенное для реализации поиска пути в трехмерном пространстве. PathEngine поставляется в виде SDK и используется как составной компонент других программ ных продуктов [240].

В основном перечисленные возможности middleware-«движков»

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

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

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

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

Однако среди них также преобладают специализированные САПР, предназначенные для решения специфических задач. К подоб ным САПР относятся, например, программные комплексы планиро вания движений большегрузных грузовых автомобилей больших раз меров по городским магистралям AutoTURN канадской фирмы Transoft Solutions [208], PathPlanner R4 шведской фирмы SIMTRA [247], а также планирования траекторий движения самолетов по тер ритории аэродрома и взлетно-посадочным полосам PathPlanner A уже упомянутой фирмы SIMTRA [247].

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

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

Необходимо отметить специализированный САПР VIZMO, разра ботанный в Parasol Laboratory, Department of Computer Science Texas A&M University (США) [206].

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

Используются подходы и методики на основе рандомизации про странства: вероятностной дорожной карты (PRM, Probabilistic Road Map), быстро развертываемых случайным образом деревьев пути (RRT, Rapidly-Exploring Random Tree), поиска на графах, локальной оптимизации [206].

По данным переписки с разработчиками, VIZMO является «за крытым», некоммерческим САПР, допускается его использование лишь сотрудниками университета Texas A&M University, вследствие чего ограничена возможность его практического использования. По указанной причине невозможно провести оценку эффективности ис пользуемых в VIZMO алгоритмов и методик, а также использовать данный продукт для решения поставленных задач.

САПР eM-Workplace PC (старое название ROBCAD), входящий в пакет решений для трехмерного моделирования, анализа и автомати зированной подготовки производства Tecnomatix компании Siemens PLM Software (отдел департамента Siemens Industry Automation не мецкого концерна Siemens AG), предназначен для разработки, симу ляции, оптимизации, анализа и off-line программирования роботизи рованных и автоматизированных технологических процессов. Инст румент предоставляет платформу для оптимизации процессов и рас чета времени цикла [28, 218, 242, 243].

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

Генерируемые траектории в среде со сложным расположением препятствий также не оптимальны по геометрической целевой функ ции, отсутствует возможность оптимизации с учетом угловых коор динат перемещаемого объекта. Другим достаточно существенным не достатком eM-Workplace является большая сложность установки и на стройки САПР на ПК, необходимость предварительной установки другого специализированного ПО (БД Oracle и др.) и его ручной на стройки путем создания собственной базы данных Tecnomatix с напи санием пользовательских скриптов программ.

Наибольшей функциональностью с точки зрения поставленных в настоящей монографии задач обладает коммерческий САПР Kite французской фирмы KINEO C.A.M. [231, 233].


Как показал анализ продукта Kite на ознакомительной 30 дневной полнофункциональной версии, он позволяет сравнительно быстро планировать неоптимальные траектории перемещения объем ных тел произвольной формы в трехмерном пространстве с произ вольно же заданными препятствиями [231, 233]. Получаемая траекто рия в большинстве случаев расположения препятствий существенно не оптимальна по геометрическому критерию длины пути при любых сочетаниях настроек поиска, предоставляемых САПР (рис. 1.7). Вре мя нахождения такой существенно не оптимальной траектории отно сительно велико даже в элементарных случаях и составляет от 5 до нескольких десятков секунд и более в зависимости от задаваемых на строек планировщика (метод планирования, локальной оптимизации и др.) на компьютере средней производительности (AMD Athlon X2 Dual Core Processor 5600+2,90 ГГц).

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

Рис. 1.7. Траектории объемного объекта-цилиндра, спланированные в САПР Kite при одних и тех же начальных условиях задачи (тестовый пример, окно программы) с одинаковыми настройками Компрессор Рис. 1.8. Планирование свободной от столкновений траектории компрессора при его монтаже в сбороч ный узел силовой установки в САПР Kite (окно программы) В случае последующей локальной оптимизации найденной неоп тимальной траектории, которая возможна только по степеням свобо ды перемещаемого объемного тела, время нахождения оптимизиро ванной траектории существенно возрастает. Локальная оптимизация в случае неоптимальности исходной неоптимизированной траектории также не дает получения глобального минимума целевой функции, если исходная неоптимизированная траектория попадает в область локального минимума.

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

Не описаны также применяемые алгоритмы и методики. Из настроек программы (пунктов меню) можно сделать вывод, что для планирования траекто рий, так же как и в VIZMO, применяются подходы и методики на основе рандо мизации пространства: ве роятностной дорожной Рис. 1.9. Планирование движений манипулято карты (PRM, Probabilistic ра в среде с препятствиями в САПР Kite, фраг мент окна программы Road Map), быстро развер тываемых случайным об разом деревьев пути (RRT, Rapidly-Exploring Random Tree), поиска на графах, локальной оптимизации. Генерируемые траектории в подав ляющем большинстве случаев существенно неоптимальны. Кроме то го, эти неоптимальные траектории имеют случайный характер, т.е.

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

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

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

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

Теоретической базой исследований послужили работы отечест венных ученых в области планирования траекторий, управления ма нипуляционными роботами и поиска целей на графах состояний: С.Л.

Зенкевича, А.А. Кобринского, А.Е. Кобринского, А.С. Ющенко, К.С.

Яковлева, Е.А. Берзина, С.Д. Штовбы и др. Среди зарубежных уче ных: Steven M. LaValle, E.W. Dijkstra, N. M. Amato, G. Sanchez, N.

Deo, P. E. Hart, J. Pearl, R. E. Korf, L.E. Kavraki, G. Syswerda, D.

Whitley, J. H. Holland, R. Geraerts, X. Nguyen, J. Borenstein, I. Ulrich, M. Dorigo, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Stuart J. Russel, Peter Norvig, George F. Luger и др. [74, 138, 140, 141, 175, 199, 210, 212, 215, 217, 219, 221, 224, 228, 229, 230, 232, 234, 237, 244, 251].

Рассматриваются в основном объекты, обладающие двумя (ана лог перемещение точки на карте) или тремя (аналог перемещение точки в пространстве) степенями свободы. В зарубежной и отечест венной научной литературе недостаточно полно и подробно освещена проблема разработки эффективных алгоритмов и методик оптимиза ции траектории перемещения объемного объекта произвольной за данной формы с учетом его угловых координат в неоднородном орга низованном трехмерном пространстве с произвольным расположени ем и формой препятствий. Доступные для ознакомления по данной тематике материалы ограничиваются неглубоким (на уровне концеп ции, общей приблизительной схемы действий) описанием, не позво ляющим практически решать поставленную задачу [74, 138, 140, 141, 175, 199, 210, 212, 215, 217, 219, 221, 224, 228, 229, 230, 232, 234, 237, 244, 251].

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

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

Анализ научно-технической литературы по рассматриваемой проблематике позволил выделить несколько общих подходов, кото рые могут быть применены и применяются для решения поставлен ной задачи планирования и оптимизации траектории в многомерном пространстве с учетом как линейных, так и угловых координат объ емного тела груза [74, 138, 140, 141, 175, 199, 210, 212, 215, 217, 219, 221, 224, 228, 229, 230, 232, 234, 237, 244, 251]:

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

2) дискретное представление искомой траектории в виде nm не зависимых переменных-координат объекта как n множеств из m учи тываемых координат объемного тела (m координат механизма) в n от дельных последовательных точках траектории с дальнейшим решени ем задачи оптимизации функции nm переменных известными мето дами оптимизации целевых функций при неявном описании послед них;

3) получение искомой траектории как дискретной последова тельности промежуточных точек, генерируемых при оптимизации це левой функции m переменных (m учитываемых координат объемного тела или m координат механизма) известными методами оптимизации (например, симплекс-методом);

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

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

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

Первым трем подходам (пп. 1–3) свойственны существенные не достатки и ограничения.

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

Недостатки подхода № 2: достаточно детализированная траек тория будет описываться слишком большим количеством перемен ных, оптимизация целевой функции которых займет неоправданно большое время. Так, например, при числе m учитываемых независи мых переменных-координат объемного тела в пространстве в количе стве 5 и разбиении траектории на 20 промежутков (n=20) получим це левую функцию 100 переменных.


Недостатки подхода № 3: неоптимальность генерируемой тра ектории с учетом препятствий, неизвестное заранее число шагов дис кретизации траектории, возможность достаточно крупных шагов дис кретизации, затрудняющих восстановление промежуточных точек между ними, учитывая наличие препятствий. Одним из методов в рамках подхода № 3 является распространенный при поиске траекто рий объектов метод потенциальных полей или потенциалов, однако он также не гарантирует нахождение оптимальной траектории и со пряжен со значительными вычислительными затратами [92, 210, 251].

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

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

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

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

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

К настоящему времени накоплено большое количество теорети ческих методов и алгоритмов планирования кратчайшей траектории движения объекта в пространстве с препятствиями. Задача поиска оп тимальной траектории перемещения ГПК груза в пространстве может решаться многими способами с применением различного математиче ского аппарата.

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

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

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

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

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

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

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

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

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

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

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

1. Размерность пространства положений объекта [234]:

1.1) методики поиска в двухмерном пространстве положений гру за (например, поиск траектории движения точки на плоскости);

1.2) методики поиска в трехмерном пространстве положений гру за (например, поиск траектории движения точки в пространстве;

по иск в плоскости траектории движения проекции тела с одной допус тимой вращательной степенью свободы);

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

1.4) методики поиска в пятимерном пространстве положений гру за (поиск траектории движения тела с двумя допустимыми враща тельными степенями свободы в пространстве);

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

…и.т.д.

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

2. Размерность внешнего геометрического пространства, в ко тором заданы препятствия:

2.1) методики, работающие с препятствиями, заданными в двух мерном пространстве (на плоскости);

2.2) методики, работающие с препятствиями, заданными в трех мерном пространстве.

3. Способ описания препятствий:

3.1) аналитическое (континуальное, непрерывное) описание пре пятствий в функциональном виде;

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

трехмерный массив занятых препятствиями и свобод ных узлов пространственной решетки или воксельная модель про странства и т.п.);

4. Способ поиска искомой траектории:

4.1. аналитический поиск (классические аналитические методи ки);

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

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

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

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

Рассмотрим более подробно способы поиска траектории (п. 4).

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

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

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

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

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

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

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

4.2. Поиск траектории в виде вектора, состоящего из набора пе ременных, входящих в список аргументов целевой функции при яв ном аналитическом описании последней, проводится при помощи численных методов оптимизации [13, 21, 22, 32, 66, 146, 153, 191, 197]. При этом значение целевой функции вычисляется на каждом шаге оптимизации при помощи отдельного вычислительного алго ритма. На переменные целевой функции, которые для данной задачи являются одновременно координатами объекта в пространстве пре пятствий, накладываются нелинейные ограничения в виде неравенств.

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

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

Задача удовлетворения ограничений в англоязычной литературе встречается под названием Constraint Satisfaction Problem – CSP [222, 237].

Численные методики оптимизации для задачи поиска траектории классифицируются по следующим признакам:

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

- применение элементов случайного поиска (детерминированные, стохастические или вероятностные и комбинированные методики);

- вид целевой функции и ограничений (линейное программирова ние и нелинейное программирование);

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

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

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

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

метод барьерных функций;

метод прямого поиска с возвратом;

метод возможных направлений;

метод множителей;

методики случайного спуска (метод Монте-Карло, алгоритм «Лас-Вегас» и др.);

метод имитации отжига;

эволюционные методики оптимизации и т.д.

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

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

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

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

Траектория Препятствия Y Y 6 Y5 5 Y Y Y Y5 Y Y4 Y Y1 Y X X X1 X X Y1 X2 X X5 X б) а) X X X X Рис. 1.10. Задание переменных (пример в плоскости): а – в абсолютных значениях;

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

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

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

4.3. Численный поиск на графах считается универсальным и эф фективным инструментом поиска по простоте алгоритмической и вы числительной реализации, сочетанию скорости вычислений и дости гаемой точности [11, 16, 43, 51, 56, 74, 137, 149, 181, 188, 216, 234].

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

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

оптимальности;

временной сложности;

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



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





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

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