Скачать

Разработка и проектирование робота для разминирования

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

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

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

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

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

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

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


1 Роботехника

1.1 Что такое робот ?

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

Итак, когда же мы имеем дело с робототехнической системой, а когда просто с традиционной формой автоматики?

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

а) Человек вручную сгибает лист вперед-назад, пока не отломится кусок металлического листа.

б) Лист разрезается с помощью ручного инструмента.

1.2 Истоки робототехники

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

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

Примерно в 1500 г. Леонардо да Винчи построил для Людовика XII механического льва, который при въезде короля в Милан выдвигался, раздирал когтями грудь и показывал герб Франции. Такие постоянно усложняющиеся механические автоматы оставались модными и на протяжении последующих четырех столетий. Но слово «робот» вошло в английский язык лишь в начале двадцатого века после того, как появилась пьеса Карела Чапека «.R U. R.» (Россумские универсальные роботы). В пьесе «роботы» выращивались биологическим путем, и их нельзя было отличить от людей, разве что только по отсутствию эмоций. Сам термин был образован от чешского слова “работа”, означающего принудительный труд, и от слова «работник», означающего раб. Хотя эти создания в пьесе получили бы сегодня скорее название «андроиды», чем «роботы» (которые, как теперь считается, должны быть механическими), неправильное употребление этого слова стало повсеместным.

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

1. Робот не может причинить вред человеку или своим бездействием позволить причинить вред человеку.

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

3. Робот должен защищать себя, если это не нарушает первого или второго законов.

Хотя А. Азимов в то время и не осознавал, но именно тогда впервые появилось в печати слово «робототехника». Джо Энгельбергер, основатель фирмы «Юни-мейшн», считающийся отцом современной промышленной робототехники, отметил, что три закона А. Азимова до сегодняшнего дня остаются теми стандартами, которым при проектировании должны следовать специалисты по робототехнике.

1.3 Классификация роботов

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

Роботы с жесткой и изменяемой последовательностью перемещений. Устройства такого типа, действующие по принципу «взять-положить», хотя, строго говоря, не относятся к роботам, тем не менее часто называются роботами с жесткой последовательностью перемещений. Ход в каждом направлении движения по оси определен установкой механических жестких упоров, а датчики, как правило, представлены конечными выключателями, которые могут воспринимать только конечные точки, а не промежуточные. Такие устройства нельзя перепрограммировать на выполнение новой задачи. Они должны быть заново переналажены и отлажены, как традиционные автоматические механизмы.

Роботы с изменяемой последовательностью перемещений могут выполнять различные задачи или последовательности операций по новой программе. Однако в настоящее время созданы устройства типа «взять-положить», которые включают различные жесткие упоры по соответствующей программе. Например, у робота «МХУ Сеньер» фирмы «АСЕА» установлены на каждой оси семь упоров, каждый из которых может управляться по своей программе, что позволяет выполнять сложные последовательности. Кроме того, конечно, в промышленности всегда существует соблазн относить к роботам любые манипуляционные устройства типа «взять-положить».

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

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

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

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

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

Несмотря на все многообразие классификационных признаков, существуют «серые зоны». Например, один простой датчик еще не делает устройство роботом второго поколения. Необходимо, чтобы датчик значительно влиял на действия робота. Но что значит «значительно»? Более того, даже принятые определения отличаются друг от друга. Некоторые специалисты относят к первому поколению роботов устройства типа «взять-положить», так что все прочие типы робототехнических устройств оказываются передвинутыми на одно поколение «вверх».

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

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


2 Анализ технического задания

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

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

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

Основные характеристики робота:

Титановый сплав;

Литий-ионные батареи Roburoc;

Компьютеры (промышленные или с облегченной комплектацией);

Система технического зрения с ptu;

Набор модулей для ночного/дневного режимов работы;

Устройства беспроводной связи;

Лазерный сканер Sick® Lms;

Компьютеризованная навигационная система;

Приемник GPS;

Ультразвуковые датчики;

Датчики ускорения.

Технические параметры робота:

Высота: 160 см, Размах рук: 96 см ;

Примерный вес 160 кг (включая литий-ионные батареи;

Ширина шага: 200 мм( увеличение и уменьшение осуществляется с помощью ПК);

Скорость 0,5 м/с; (уменьшение регулируется компьютером)

Максимальный наклон корпуса: 79 градусов;

Грузоподъемность 65 кг;

Радиус поворота: 1 м;

Питание: 3 литий–ионовых батареи;

Время работы без перезарядки: 3-5 часов;

Влажность: 5-95% (без конденсации);

Моторы: 6 безщёточных электродвигателей;

Управление: джойстик с прямой передачей;

Оптические сенсоры (10 видеокамер)

Способен выдержать силу взрыва, эквивалентную 0,0005 килотонн тротила

Тепловые показатели:

- рабочая температура: 80°С

- температура окружающей среды: max 150°C, min -40°C.

Базовая комплектация:

12 безщёточных моторов с синхронизатором;

Зарядное устройство;

Джойстик управления;

Система аварийного останова (кнопочная, беспроводная);

Встроенный промышленный персональный компьютер (Linux, RTai, SynDEX);

Встроенный контроллер Motorola RSMPC 555;

Программное обеспечение управления:

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

ИЛИ библиотеки C++ Linux для управления из произвольного приложения linux+rtai на базовом компьютере;

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


2.1 Рука робота

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

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

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

2.2 Голова робота

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


2.3 Корпус робота

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

3.3 Программное обеспечение

Программное обеспечение предоставлено компанией Apple.

3.4 Пример шагающего аппарата

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

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


В нижней части конечности находятся три датчика усилия для измерения реакции силы ноги.

Основные характеристики шагающего аппарата:

· высота корпуса – 10 см;    · длина стороны – 17 см;

· общая масса – 21 кг; · размер конечности – 45,6 см;

· масса конечности – 2.8 кг; · масса корпуса с микропроцессором – 3,8 кг;

· скорость – около 0,4 км/ч; · полезная нагрузка – 5 кг;

· длина бедра – 20,4 см;       · длина голени – 25,2 см;

· поверхность касания конечности – 28,3 см2


3 Технические расчеты

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

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

Пусть положение системы координат описывает однородная матрица Н(t), размерностью (4x4):

где p – вектор, описывающий положение манипулятора, n, s и a – вектора нормали, перемещения и подхода соответственно. Оценка сочленения, соответствующая матрице H(t), зависит от структуры робота. Один из примеров решения для манипулятора PUMA представлен ниже.

Пусть H(t)=H(t1). Схват должен пройти последовательность узловых точек в декартовом пространстве: H(t1), H(t2)…H(tn) . Для построения траектории узловым точкам ставятся в соответствие векторы присоединенных координат (q11(t1), q12(t2), …,q1n(tn)),( q21(t1), q22(t2), …,q2n(tn)),…( q1n(t1), q2n(t2), …,qNn(tn)), где qji обозначает j-ю присоединенную переменную, соответствующую положению схвата в i-й узловой точке H(t). В данной процедуре построение траектории сочленения происходит для одного сочленения за один раз. Затем строится кубическая интерполяция траектории j-ой присоединенной переменной между точками qj1(t1), qj2(t2), …,qjn(tn). Индекс j в переменной qji не обязателен, поэтому qji ставим в соответствие qi.

Главная задача – построить траекторию j-ой присоединенной переменной во времени с использованием кубического полинома. Пусть t12<…n-2n-1n– моменты прохождения узловых точек. В начальный момент t=t1 и конечный момент t=tn заданы соответственно начальные qj1, vj1, aj1 и конечные qjn, vjn, ajn(положение, скорость и ускорение). Кроме того, значения присоединенной переменной qjk в моменты времени tk заданы для k=3,4,…,n-2. Однако, значения q2 и qn-1 не фиксированы: как уже говорилось, это необходимо для обеспечения непрерывности кинематических характеристик вдоль всей траектории.

Пусть Qji(t) – кубический полином, описывающий поведение j-й присоединенной переменной между узловыми точками Hi и Hi+1 и определенный на интервале (t1, ti+1). Задача состоит в “сшивке” между собой полиномов Qji(t) (i=1,2,…,n-1) так, чтобы они проходили через заданные узловые точки и обеспечивалась непрерывность положения, скорости и ускорения на всем интервале (t1, tn).

Поскольку Qji(t) – кубический полином, его вторая производная Q’’ji(t) должна быть линейной функцией времени t:

Q’’ji(t)=((ti+1-t)/hi)*Q’’ji(ti) + ((t-ti)/hi)*Q’’ji(ti+1),

i=1,…,n-1, (1)

j=1,…,N,

где hi= ti+1-t – время, затрачиваемое на прохождение i-го участка. Дважды интегрируя Q’’ji(t) и учитывая граничные условия Qji(ti)=qji и Qji(ti+1)=qi,i+1, получаем интерполирующую функцию следующего вида:

Qji(t)= ((Q’’ji(ti)/6hi)*(ti+1-t)3 + (Q’’ji(ti+1)/6hi)*(t-ti)3 +

+ (qj,i+1/hi – hiQ’’ji(ti+1)/6)(t-ti) + (qi,t/hi – hiQ’’ji(ti)/6)(ti+1-t) i=1,2,…,n-1,

j=1,2,…,N. (2)


Таким образом, для i=1,2,…,n-1, Qji(t) определены, если известны Q’’ji(ti) и Q’’ji(ti+1). На основании этого можно записать систему n-2 линейных уравнений относительно неизвестных Q’’ji(ti), i=2,…, n-1,(описание системы в приложении А):

A=, (3)

A==

=


Ленточная структура матрицы А позволяет легко определить неизвестную величину Q’’i(ti). В окончательном виде полиномы Qi’’(ti) выражаются временными интервалами hi и данными значениями присоединенных координат, скоростей и ускорений.

Доказательство единственного решения

Свойство 1: Задача интерполяции траектории имеет единственное решение, т.е. матрица А в уравнении (3) неособенная.

Доказательство: Известно, что hi – временные интервалы и должны быть положительны. Кроме того, в матрице А все строки, кроме 2 и n-3, удовлетворяют неравенству

, для строки i.                 (4)

а) Если h2 h1 и hn-2hn-1, строки 2 и n-3 также будут удовлетворять неравенству (4). Поэтому, матрица А становится строго диагональной и неособенной.

б) Если h1 > h2, выполняем строковую операцию вычитания (строка 1)x(h2 – h21/h2)/(3h1+2h2+ h21/h2) из строки 2 для исключения а21.

Получаем:

и

.


Из h1 >h2 следует, что . Поэтому матрица А эквивалентна строго диагональной матрице. Следовательно, уравнение (3) имеет единственное решение.

III.Описание траектории кубическими полиномами

В промышленности производительность зависит от скорости манипулирования робота. Для увеличения скорости работы манипулятора нужно минимизировать время движения вдоль заданной траектории. Задача оптимизации сводится к минимизации времени движения путем соответствующего выбора величин временных интервалов h1, h2,…, hn-1. с учётом ограничений присоединенных скоростей, ускорений, моментов и скоростей изменения ускорений. Для удобства примем:

VCj – ограничение по скорости для j-го сочленения,

wCj – ограничение по ускорению для j-го сочленения,

JCj – ограничение по скорости изменения ускорения для j-го сочленения.

Qji(t) – кубический полином, описывающий поведение j-й присоединенной переменной между узловыми точками i и i+1, т.е. между Hi и Hi+1 .

wji – ускорение в Hi; оно соответствует Qji’’(ti) если Qji(t) проходит через Hi в момент времени ti.

X=(h1, h2,…, hn-1),- вектор временных интервалов.

Задачу можно сформулировать следующим образом: минимизировать целевую функцию Т

при следующих ограничениях:


,          j=1,2,…, N,         i=1,2,…,n-1,

,                   j=1,2,…, N,         i=1,2,…,n-1,

,          j=1,2,…, N,         i=1,2,…,n-1.

Строгое представление этих ограничений представлено ниже.

а) Ограничение по скорости.

,          j=1,2,…, N,         i=1,2,…,n-1,

Дифференцируя равенство (2) и заменяя Qji’’(ti) и Qji’’(ti+1) соответственно на wji и wj,i+1, получаем:

Qji’(t)=wji/2hi*(ti+1-t)2 + wji+1/2hi*(t-ti)2 + (qj,i+1/hi – hiwj,i+1/6) – (qji/hi – hiwji/6),

Также Qji’’(t) можно представить как

Qji’’(t)= wj,i+1/hi*(t-ti) + wji/hi*(t-ti+1),

Скорость достигает своего максимального по абсолютной величине значения в одной из точек ti , ti+1 или , где и Qji’’()=0. Ограничение по скорости тогда принимает вид :


для i=1,2,…,n-1j=1,2,…,N, (6)

где

И

б) Ограничения по ускорению:

,                   j=1,2,…, N,         i=1,2,…,n-1,

Между двумя узловыми точками ускорение линейно зависит от времени. Поэтому максимальная абсолютная величина ускорения достигается в точке ti или в точке ti+1 и равна максимальной из величин .С учетом этого ограничение по ускорению принимает следующий вид:


,           j=1,2,…,N. (7)

в) Ограничение по скорости изменения ускорения:

,          j=1,2,…, N,         i=1,2,…,n-1.

Ограничение по скорости изменения ускорения можно представить в виде:

              j=1,2,…, N,         i=1,2,…,n-1. (8)

Пример возможного решения

Свойство 2: Задача оптимизации при наличии ограничений (6) - (8) всегда имеет решение.

Если временные интервалы h1,…, hn-1 ….………., тогда, в соответствии со свойством 1 I-го раздела w2, w3,…, wn-1 определяются однозначно. Однако, ограничения по скорости, ускорению и скорости изменения ускорения могут не удовлетворять требованиям. В этом случае временные интервалы {h1,…, hn-1} могут быть увеличены для придания ограничениям значений, удовлетворяющих требованиям. Для этого представим Qi(t) исходным полиномом присоединенной переменной, определённым на временном интервале (ti, ti+1)=(ti, ti+hi). Если все временные интервалы увеличить в соответствии с так, что новые временные интервалы станут равными , тогда, в соответствии с (5) новое ускорение wi* будет определено как wi*=wi/. Таким образом, полином Qi(), определенный на интервале ()=(), будет представлен новым полиномом Q*i(). Первая, вторая и третья производные от Q*i() будут иметь вид (1/)Qi’(), (1/)Qi’’() и (1/)Qi’’’() соответственно. Предположим


, (9)

, (10)

, (11)

и

, (12)

Если временной интервал hi заменен на hi для i=1,2,…,n-1, тогда величины скорости, ускорения и скорости изменения ускорения будут уменьшены коэффициентами соответственно. Эти изменения обеспечат скорость, ускорение и скорость изменения ускорения значениями, отвечающими требованиям.называется коэффициентом возможного регулирования. Процедура, выполняющая приведение некорректных величин к удовлетворяющему виду называется преобразователь возможного решения (ПВР). В итоге, процедура имеет вид:

1) Вычисление в уравнениях (9)-(12).

2) Замещение временных интервалов (h1, h2,…, hn-1) на ().

3) Замещение wj,2, wj,3,…, wj,n-1 на соответственно. j=1,2,…, N.

Алгоритм оптимизации

Матрица А(Х) определена как вектор временных интервалов между выбранными узлами, т.е. (h1, h2,…, hn-1). Основной задачей Х является представление Т(Х) и соответствует (h1+h2+…+hn-1). Сначала выбирается n – максимальное количество вершин Хi , (i=1,2,…, n), для формирования исходного многогранника. Пусть Xg и Xs имеют максимальное и минимальное значения функции. Предположим, что Хn+1 – центроид многогранника, не включая Хg. Вычисляется это так:

. (13)

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

1)Отображение: Отображение Xg через центроид вычисляется следующим образом:

Xn+2=Xn+1+a(Xn+1-Xg), (14)

где а>0 – коэффициент отображения. Отметим, что все элементы Xn+2 являются временными интервалами. Для того, чтобы все интервалы были положительными, коэффициент а должен быть правильно определен. Сначала, примем его равным 1. Если какой-нибудь элемент Xn+2 будет отрицательным, то коэффициент следует уменьшить. Пусть Xp=(). Для а=1 Xn+2 приобретает вид:

Xn+2=2Xn+1-Xg= ().

Все элементы должны быть положительными, т.е. для всех i. Еслидля какого-либо i, тогда уменьшаем коэффициент а.

Из (14) получаем . Если , тогда . Следовательно, коэффициент а должен быть меньше, чем , чтобы был положительным. Учитывая все выше сказанное, коэффициент а может быть определен как:

, (15)

где 0<<1 выбрана для того, чтобы убирать Xn+2 от границы, где хотя бы один элемент Xn+2 = 0.

2) Растяжение: Растянуть вектор (Xn+2-Xn+1) можно следующим образом:

Xn+3=Xn+1+(Xn+2-Xn+1),                                                                           (16)

где >1 – коэффициент растяжения. Для того, чтобы значения всех элементов Xn+3 были положительными, этот коэффициент должен быть определен следующим образом:

,                                                (17)


где 0<<1.

3) Сжатие: Сжать вектор (Xg-Xn+1) можно следующим образом:

Xn+4=Xn+1+(Xg-Xn+1),                                                                   (18)

где 0<<1 – коэффициент сжатия.

4) Уменьшение: Уменьшить все вектора (Xi-Xs), i=1,2,…,n, деля их пополам начиная с Xs можно следующим образом:

,     i=1,2,…,n,                                                 (19)

До начала поиска выберем n – максимальное количество вершин многогранника. Пусть qj,1, qj,3,…, qj,n-2, qj,n - присоединенные переменные, соответствующие положению схвата в j-й узловой точке. Из-за особенностей 2-ой и n-1 точек, qj,2 и qj,n-1 еще не определены. Временно они определены как qj,2=(qj,1+qj,3)/2 и qj,n-1=(qj,n-2+qj,n)/2. Таким образом, нижняя граница вектора временных интервалов оценивается как:

, (20)

Первая вершина Х10 вычисляется как , если нам подходит, или обозначается как подходящая вершина, преобразованная процедурой (ПВР) из . Для вычисления остальных (n-1) вершин {}, вычисляются как:


, (21)

где

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

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