Содержание к диссертации
Введение
ГЛАВА 1 Анализ особенностей планирования траекторий движения многозвенного манипулятора, из заданной начальной конфигурации к цели 12
1.1. Анализ особенностей многозвенных манипуляторов 13
1.2. Анализ известных подходов к решению задачи планирования траекторий движения многозвенных манипуляторов 21
1.3. Анализ возможностей использования эволюционных методов при поиске траекторий движения многозвенных манипуляторов 32
1.4. Цели и задачи диссертационной работы 39
1.5. Выводы к первой главе 41
ГЛАВА 2 Разработка метода планирования траекторий движения многозвенного манипулятора из заданной начальной конфигурации к цели в сложном трехмерном пространстве на основе генетического подхода 43
2.1. Формализация задачи планирования траектории движения многозвенного манипулятора 44
2.2. Разработка метода планирования траекторий многозвенного манипулятора на основе генетического подхода 59
2.3. Разработка алгоритма планирования траекторий движения на основе предлагаемого метода 65
2.4. Выводы ко второй главе 73
ГЛАВА 3. Разработка методов планирования траекторий на основе генетического подхода с модификациями, а также алгоритмического и программного обеспечения 74
3.1. Разработка метода планирования траекторий движения многозвенного манипулятора на основе комбинирования генетического подхода и метода имитации отжига 75
3.2. Разработка метода планирования траекторий движения многозвенного манипулятора на основе генетического подхода с
использованием метода репульсивного роя частиц 83
3.3 Разработка общей структуры моделирующего комплекса и
программных средств для реализации предложенных методов 95
3.4. Выводы к третьей главе 103
Глава 4. Исследование эффективности предложенных методов планирования траекторий движения на основе компьютерного моделирования 104
4.1. Разработка методического обеспечения для исследования ;; работоспособности и эффективности предложенных методов планирования траекторий 105
4.2. Анализ результатов проверки работоспособности и эффективности предложенных методов 113
4.3. Направления дальнейших исследований 119
4.4. Выводы к четвертой главе 120
Заключение 121
Литература 123
Приложение 147
- Анализ особенностей многозвенных манипуляторов
- Анализ известных подходов к решению задачи планирования траекторий движения многозвенных манипуляторов
- Формализация задачи планирования траектории движения многозвенного манипулятора
- Разработка метода планирования траекторий движения многозвенного манипулятора на основе комбинирования генетического подхода и метода имитации отжига
Введение к работе
Многозвенные манипуляторы, как правило, используются для повышения эффективности работы робота в пространстве с множеством препятствий, так как позволяют получать различные конфигурации робота без смещения конца исполнительного механизма от цели. Такие манипуляторы могут применяться в медицине (хирургические операции с минимальным повреждением кожных покровов, эндоскопия, лапароскопия и т.д.), космической промышленности (монтаж/демонтаж сложных деталей, съемка параметров и т.д.), проверка состояния труднодоступных частей машины в технике, различных производственных системах. Их используют для проведения космических и подводных исследований, для работы с вредными веществами и радиоактивными материалами.
Исследования, посвященные способам планирования траекторий движения робототехнических систем различных классов, можно найти в работах отечественных и зарубежных ученых (Ю.Г. Козырева, П.Д. Крутько, Ф.М.Кулакова, А.В. Тимофеева, С.Ф. Бурдаков, Б.Г. Ильясова, В.И. Васильева, P.Bohner, S. Cameron, К. Fu, S. Ma, A. McLean, I. Kobayashi, U. Rembold, H.Woern, F. Binwen, E. Cheung, Y. Konishi, C. Lin, Y. Nakamura и других). В них получены алгоритмы, обеспечивающие планирование траекторий для относительно небольшого числа звеньев (не более 10). Улучшение методов решения задачи планирования траекторий, расширение условий применимости алгоритмов планирования траекторий создает предпосылки для построения более эффективных систем управления многозвенными манипуляторами.
Основными трудностями, возникающими при разработке алгоритмов планирования траекторий движения многозвенных манипуляторов, являются:
-большое количество звеньев. Для определения конфигурации манипулятора необходимо рассчитать тем или иным способом собственные переменные каждого звена манипулятора, а также учесть ограничения, связанные с физической структурой манипулятора;
-сложность рабочего пространства. Манипуляторы рассматриваемого класса предназначены, как правило, для выполнения работы в пространствах с большим количеством препятствий.
Для преодоления данных трудностей в последнее время широко используются интеллектуальные методы, которые, в ряде случаев, позволяют получить решение рассматриваемой задачи без применения сложных вычислений. В этой области, в частности, предложены эвристический рекурсивный алгоритм, генетический подход и комбинирование генетического подхода с парадигмой экспертной системы [35,56]. Данные исследования проведены для манипулятора типа "слайдер", который изначально находится в сложенной конфигурации и постепенно выдвигается к цели из определённой точки в двумерном пространстве.
Неисследованными являются интеллектуальные методы
планирования траекторий движения многозвенных
манипуляторов с учётом начальной конфигурации в трехмерном пространстве, предусматривающие обход препятствий и уклонение от столкновений с ними, а также обеспечивающие приемлемое значение показателей качества.
Цель работы
Целью работы является исследование и разработка методов и алгоритмов планирования траектории движения многозвенного манипулятора из начальной конфигурации к цели на основе эволюционных методов поиска, в условиях сложного, комплексного трехмерного рабочего пространства и избыточного числа звеньев.
Задачи исследования.
Для достижения цели в работе поставлены и решены следующие задачи:
1) разработать методы планирования траектории движения
многозвенного манипулятора в сложном трёхмерном
пространстве с учётом начальной конфигурации на основе:
генетического подхода;
комбинирования генетического подхода и метода имитации отжига;
комбинирования генетического подхода и метода репульсивного роя частиц;
2)разработать алгоритмическое обеспечение для реализации предложенных методов планирования траекторий движения многозвенных манипуляторов;
3)разработать программное обеспечение для реализации предложенных методов планирования траекторий движения многозвенных манипуляторов на моделирующем комплексе и средства визуализации результатов решения задач;
4) исследовать эффективность предложенных методов, алгоритмов и программного обеспечения системы планирования траекторий движения многозвенного манипулятора в сложном трехмерном рабочем пространстве.
Методика исследования
В работе использовались методы разработки
интеллектуальных систем, генетических алгоритмов, имитации
отжига, репульсивного роя частиц. В работе также учитываются
основные положения робототехники, применяются методы
анализа кинематики и динамики манипуляторов. При разработке
программного обеспечения применялись объектно-
ориентированный подход, методы машинной графики.
Результаты, выносимые на защиту
На защиту выносятся:
1) методы планирования траекторий движения
многозвенного манипулятора в сложном трехмерном
пространстве с учётом начальной конфигурации на основе:
генетического подхода;
комбинирования генетического подхода и метода имитации отжига;
комбинирования генетического подхода и метода репульсивного роя частиц;
алгоритмическое обеспечение для реализации предложенных методов планирования траекторий многозвенных манипуляторов;
программное обеспечение для реализации предложенных методов планирования траекторий многозвенных манипуляторов;
методика и результаты исследования работоспособности и эффективности предложенных методов планирования траекторий движения многозвенных манипуляторов, алгоритмов и программного обеспечения.
Научная новизна
Новыми являются разработанные и исследованные автором:
1) Методы планирования траекторий движения
многозвенного манипулятора в сложном трехмерном
пространстве с учётом начальной конфигурации на основе:
генетического подхода. Новизна предложенного метода состоит в интерпретации генетического подхода для задачи планирования траекторий движения многозвенного манипулятора в условиях сложного трёхмерного рабочего пространства. В данной интерпретации в отличие от известных работ генетические операторы работают с телесными углами, целевая функция отображает расстояние между окончанием последнего звена манипулятора и целью, а также учитывается проверка на допустимость движения из одной конфигурации'в другую без столкновения с препятствиями.
комбинирования генетического подхода и метода имитации отжига. Новизна предложенного метода состоит в комбинировании генетического подхода и метода имитации отжига для улучшения эффективности поиска траектории движения;
комбинирования генетического подхода и метода репульсивного роя частиц. Новизна предложенного метода состоит в комбинировании генетического подхода и метода репульсивного роя частиц для улучшения эффективности поиска траектории движения;
2) алгоритмы планирования траекторий движения
многозвенного манипулятора в условиях сложного трехмерного
рабочего пространства с учётом начальной конфигурации на основе предложенных методов с использованием:
генетического подхода;
комбинирования генетического подхода и метода имитации отжига;
комбинирования генетического подхода и метода репульсивного роя частиц;
3) методика оценки качественных и количественных показателей работоспособности и эффективности алгоритмов поиска траекторий в сложном трехмерном рабочем пространстве. Новизна методики состоит в том, что для новой задачи сформулирована методика проверки работоспособности и
f і
эффективности по принципу одноцелевого и многоцелевого поиска.
Практическая значимость и внедрение результатов
Практическую значимость имеют полученные автором следующие результаты:
реализация предложенных алгоритмов в компьютерной моделирующей среде и программное обеспечение для IBM PC, обладающее средствами визуализации и позволяющее производить исследования работоспособности и эффективности предложенных алгоритмов;
методика и результаты компьютерного тестирования, позволяющие оценить качественные и количественные показатели эффективности алгоритмов планирования траекторий движения в сложном трехмерном рабочем пространстве;
разработанное программное обеспечение моделирования и планирования траекторий движения многозвенного манипулятора зарегистрировано в реестре программ для ЭВМ
Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.
Внедрение и связь исследования с научными программами
Работа выполнена в рамках гранта РФФИ № 06-08-01180-а
"Интеллектуальные методы поиска траекторий многозвенных
манипуляторов", гранта РФФИ № 06-07-89228-а, хоздоговорной
темы "Исследование и разработка интеллектуальных технологий
поддержки принятия решений и управления". Основные
результаты диссертационной работы используются в виде
программного обеспечения в научно-производственной фирме
"РД-Технология" и в учебном процессе на кафедре ВМиК
УГАТУ. *
Апробация и публикации
Основные положения, представленные в диссертационной работе докладывались, обсуждались и получили положительную оценку на различных международных конференциях, посвященных проблемам моделирования, системам обработки информации и управления, использованию робототехнических систем, в частности, на Международной научно-технической конференции CSIT05 (Уфа, Ассы, 2005), CSIT'07 (Уфа, Красноусольск 2007), 2-й региональной зимней школе-семинаре аспирантов и молодых учёных (Уфа, 2007).
Результаты работы отражены в 16 публикациях. Из них 2 в рецензируемых журналах из списка ВАК.
Благодарности
Автор выражает благодарность доценту кафедры ВМК, канд. техн. наук. Г.Р. Шахмаметовой за полезные консультации
по вопросам методов и алгоритмов планирования траекторий движения многозвенного манипулятора.
Объем и структура работы
Диссертация состоит из введения, 4 глав, заключения, списка литературы из 185 наименований и приложения, иллюстрирующего примеры разработанных манипуляторов в лабораториях различных странах мира. Объем основной части диссертации составляет 108 страниц.
Анализ особенностей многозвенных манипуляторов
Данный раздел посвящен анализу особенностей многозвенных манипуляторов. Определяются общие свойства данного класса манипуляторов, которые позволят распространить полученные результаты на другие манипуляторы данного класса. Приводятся примеры многозвенных манипуляторов, разрабатываемых в различных исследовательских лабораториях. Особенности многозвенных манипуляторов и их применение Промышленный робот — это автоматическая машина, стационарная или передвижная, состоящая из исполнительного устройства в виде манипулятора, имеющего несколько степеней подвижности, и перепрограммируемого устройства программного управления для выполнения в производственном процессе двигательных и управляющих функций [15].
Манипулятор - совокупность пространственного рычажного механизма и системы приводов, осуществляющая под управлением программируемого автоматического устройства или человека-оператора действия (манипуляции), аналогичные действиям руки человека [27].
Промышленные роботы предназначены для замены человека при выполнении основных и вспомогательных технологических операций в процессе промышленного производства.
Промышленные роботы широко применяются для решения различных технологических задач. Промышленные роботы в настоящее время широко используются для таких операций, как сварка, термическая резка, загрузка и разгрузка технологического оборудования, покраска, сборка, контроль и дозирование, сортировка, упаковка и маркировка.
Кроме того, эти устройства незаменимы при выполнении работ в космосе, под водой, в химически активных средах. Таким образом, промышленные роботы являются важными составными частями современного промышленного производства [27].
В промышленности манипуляторы используются в специально адаптированной среде, которая известна заранее.
Широкое применение манипуляторов в сложных средах невозможно, так как используемые манипуляторы не имеют достаточной гибкости для надежного выполнения задачи. Недостаточная гибкость обычных манипуляторов обусловлена небольшим числом степеней свободы. Из-за ограничений окружающего пространства задача позиционирования манипулятора может быть вообще не решена или решена, но только с несколькими альтернативными конфигурациями. Вычисление этих конфигураций представляет собой сложную задачу, которая должна быть решена до выполнения перемещения манипулятора. В сложных внешних условиях точно и эффективно манипулировать очень трудно, так как алгоритмы планирования слишком сложны, чтобы обеспечить обобщение данных сенсоров непосредственно во время движения.
Избыточные манипуляторы, как правило, используются для повышения эффективности работы в пространстве с множеством препятствий, так как позволяют получать различные конфигурации робота без смещения конца исполнительного механизма от цели и максимизировать угол сервиса. Такие манипуляторы могут применяться в медицине (хирургические операции с минимальным повреждением кожных покровов, зондирование и т.д.), космической промышленности (монтаж/демонтаж сложных деталей, съемка параметров и т.д.), проверка состояния труднодоступных частей машины в технике, различных производственных системах. Их используют для проведения космических и подводных исследований, для работы с вредными веществами и радиоактивными материалами [40,48,58].
Избыточные манипуляторы обладают некоторыми свойствами, отсутствующими у обычных манипуляторов.
Когда механическая система, такая как манипулятор, имеет большее количество независимых звеньев (входных данных), чем это необходимо для определения позиции исполнительного механизма или положения при ориентировании (выходные данные), она может быть обозначена как избыточно действующая система или кинематически избыточная система. Для определения позиции для каждого звена в 3-хмерном пространстве требуется 6 переменных (X,Y,Z, крен, тангаж, рыскание). Робот (манипулятор) должен иметь, по меньшей мере, 7 степеней свободы.
Анализ известных подходов к решению задачи планирования траекторий движения многозвенных манипуляторов
Один из способов использования редундантности (от англ. redundant - избыточный) манипулятора [83] - это разделение задач на одновременно выполняемые подзадачи и определение приоритета каждой из них. Когда невозможно одновременное выполнение всех подзадач, предпочтительнее сначала выполнить наиболее важные подзадачи, используя все требуемые степени свободы, а затем менее важные подзадачи с использованием оставшихся степеней свободы манипулятора. Рассмотрим задачи манипулирования, обозначенные как re Л", т 6. В этом случае, кинематика робота может быть выражена: При реализации движения робота различают три особенности:
1. Все движения г, которые пролегают в подпространстве R(J) ER " (размерность пространства J(9)) реализуются обобщенными скоростями $sR" (рис.1.5(a)). Следовательно, R(J) будет называться пространством манипуляций и обозначаться S„,=R(J).
2. Дополнительные обобщенные скорости 9, которые находятся в подпространстве N(J)eR" (нулевое пространство ./(#)), не влияют на требуемые движения, так как они направлены к нулевому вектору в подпространстве R(J) (рис. 1.5(6)). Результат дополнительного движения - другие внутренние конфигурации робота. Следовательно, N(J) называется редундантным пространством SII=N(J).
3. Комбинация предыдущих двух особенностей дает возможность маневрировать в ограниченном пространстве. Эта способность широко используется для предотвращения столкновений с препятствиями в пространстве.
Уравнение 2 имеет множество решений в. Используя метод псевдоинверсии, получаем: в=Г(в) г+{1п-Г{в)Г{в))и (1.3) где J+ eRn,m - псевдоинверсия J{6), Ія - «-мерная единичная матрица, и u&R" - произвольный вектор. Первый член уравнения (1.3) - это проекция вектора г наименьшей площади на подпространство 5,. Второй член является ортогональной проекцией произвольного вектора и на редундантное подпространство SR=N(J). В специальных случаях для системы из двух роботов результаты уравнения (1.3) представляют собой 12 требуемых обобщенных скоростей.
Предположим, что задача манипулирования может быть разделена на две подзадачи с разными приоритетами, и обозначим г, eRm - переменная манипуляции с высоким приоритетом, r2 eRmi- переменная с низким приоритетом. Также как и в случае одной задачи кинематика механизма может быть выражена: п=т (1.4) v n = Jt(e)0 (/=1,2) (1.5) где Jl(0) = dfllde&Rm,tn - матрица Якобиан /-переменной манипуляции и 0eR", (и=12).
Также как и в случае с одной задачей, подпространства SMi называются пространствами манипуляций, а подпространства 5 - редундантными пространствами, где /=1,2. Эти пространства показаны графически на рис. 1.6. Перепишем уравнение (3) для г=г,: e=J r {ln-J Jx}u (1.6) и подставим формулу (1.6) в формулу (1.2) с г = r2: Гг=Л{АЧ+(4 АЧН (1.7)
Возьмем наименьшие квадраты решений формулы (1.7) и после матричных преобразований получим следующее уравнение; e = jyri + J1\r2-J2j;n) + {In-J Ji){Il!-J1+J2)v (1.8) где J2 а/2(/я -У,V,) и v - произвольный вектор. Эта формула подробно рассматривается на рис. 1.6 [83]. на подпространство В, где величина (r2-J2Jl+ г,) является искомой величиной второй переменной манипуляции, модифицированной вследствие воздействия первого элемента. Третий элемент - это ортогональная проекция произвольного вектора v на подпространство С. Подпространства А, В и С обозначены на рис. 1.6. Аналогичным образом задача может быть решена для большего количества подзадач.
Метод обратных преобразований, рассматриваемый в работах [85,105], основан на разрешении уравнений, образующихся при преобразовании координат начальной точки к координатам конечной точки путем умножения их на матрицы преобразований. Матрицы преобразований строятся, исходя из матриц элементарных поворотов и элементарного сдвига, составленных для системы углов. Матрица преобразования строится для каждого звена отдельно, и обеспечивает переход начальной точки в конечную для данного звена, таким образом, последовательно умножив вектор обобщенных координат на матрицы преобразований всех звеньев, мы получим координаты конечной точки или (если собственные углы звеньев не известны) уравнения перевода координат.
Решая эти уравнения при известных начальной и конечной точках (или матрице манипулятора, которая описывает положение схвата), можно получить множество решений, описывающих набор собственных углов каждого звена, и, следовательно, конфигурацию манипулятора.
Основным достоинством метода является высокая точность, а основным недостатком - математическая сложность и относительно большое время вычислений.
Формализация задачи планирования траектории движения многозвенного манипулятора
Кинематика - раздел механики, изучающий движение без учета причин, вызывающих движение. [64] Предметом кинематики манипулятора является аналитическое описание геометрии движения манипулятора относительно некоторой заданной абсолютной системы координат.
В кинематике манипулятора выделяют прямую и обратную задачи [40, 42, 48, 52].
Прямая задача кинематики: Для конкретного манипулятора по известному вектору присоединенных углов - обобщенных координат я(0=( (( г(0 — «(О)7" и заданными геометрическими параметрами звеньев (п - число степеней свободы) определить положение и ориентацию исполнительного механизма манипулятора относительно абсолютной системы координат (Рис 2.1).
Здесь {А1} - множество траекторий манипулятора, {А док} множество локальных траекторий манипулятора, {Д#,}- смещения звеньев манипулятора в обобщённых координатах, {U ynp} управляющие сигналы, {#,}- траектории движения манипулятора в обобщённых координатах.
Традиционные методы решения этих задач для обычных (не избыточных) манипуляторов основаны на применении матричной алгебры [48]. Прямая задача кинематики сводится к определению матрицы однородного преобразования, задающей связь между системой координат исполнительного механизма и абсолютной системой координат. Обратная задача кинематики может быть решена различными методами. К числу наиболее часто используемых относятся методы матричной алгебры (метод обратных преобразований) и геометрический подход [48]. Все эти методы связаны с большим количеством сложных вычислений, что делает их практически непригодными при управлении многозвенным манипулятором в реальном режиме времени.
Динамика манипулятора исследуется на основе математического описания действующих на манипулятор сил и моментов, которые определяются в виде уравнений динамики движения, и могут быть получены применением традиционных методов Лагранжа-Эйлера или Ньютона-Эйлера [48, 52].
В предыдущем разделе была рассмотрена математическая модель манипулятора, состоящего из звеньев-отрезков прямых, которая позволяет рассчитать координаты каждого звена, тем самым, решая прямую задачу кинематики. Реальный же манипулятор представляет собой более сложный объект, зависящий от многих физических показателей.
В рамках рассматриваемой задачи манипулятор характеризуется следующими показателями: геометрические параметры звеньев (длина, ширина и высота звена); число звеньев; расположение начального звена (база манипулятора) (координаты начала 1-го звена); начальная конфигурация манипулятора; кинематические ограничения (максимальные углы поворота относительно предыдущего звена). Рассмотрим модель звена. Введем следующие обозначения: М- манипулятор; Gn- звено манипулятора М, занимающее n-ное место от начала (базы) манипулятора. L1-L3 -отрезки прямых, задающие параметры звена манипулятора. а;- поворот звена относительно предыдущего.
Звено, в общем случае может, быть описано как прямоугольный параллелепипед, параметры которого задаются отрезками прямых (LI, L2, L3) (рис 2.4).
Разработка метода планирования траекторий движения многозвенного манипулятора на основе комбинирования генетического подхода и метода имитации отжига
Метод имитации отжига основывается на имитации физического процесса образования веществом кристаллической структуры с минимальной энергией при охлаждении [73].
При медленном остывании металла, соседние кристаллы сливаются друг с другом. Если охлаждение происходит достаточно медленно, то кристаллы становятся очень большими. Окончательное распределение молекул представляет состояние с очень низкой энергией, и металл при этом будет очень твердым.
Начиная с состояния с высокой энергией, молекулы в конце концов достигают состояния с очень низкой энергией. На пути к конечному положению, они проходят множество локальных минимумов энергии. Каждое сочетание кристаллов образует локальный минимум. Кристаллы могут объединяться друг с другом только за счет временного повышения энергии системы, чтобы затем перейти к состоянию с меньшей энергией [73].
Огромным преимуществом метода отжига является свойство избегать "ловушки" в локальных минимумах оптимизируемой функции, и продолжить поиск глобального минимума. Это достигается за счет принятия не только изменений параметров, приводящих к уменьшению значения функции, но и некоторых изменений, увеличивающих ее значение, в зависимости от т.н. температуры Т - характеристики моделируемого процесса. Чем выше температура, тем большие "ухудшающие" изменения (аналогичные случайным флуктуациям в нагретом веществе) допустимы, и больше их вероятность. Еще одним преимуществом является то, что даже в условиях нехватки вычислительных ресурсов для нахождения глобального минимума, метод отжига, как правило, выдает весьма неплохое решение (один из локальных минимумов).
Метод отжига служит для поиска глобального минимума некоторой функции f(x), заданной для некоторого пространства S, дискретного или непрерывного. Элементы множества S представляют собой состояния воображаемой физической системы ("энергетические уровни"), а значение функции f в этих точках используется как энергия системы Е = f(x).
Находясь в состоянии при некоторой температуре, следующее состояние системы выбирается в соответствии с заданным порождающим семейством вероятностных распределений G{x,T). После генерации нового состояния х1 = G(X,T), система с вероятностью h(AE,T) переходит к следующему шагу в состояние х1, в противном случае процесс генерации х1 повторяется. Здесь А обозначает приращение функции энергии f(xl)-f(x). Величина h(AE,T) называется вероятностью принятия нового состояния. Как правило, в качестве функции h(AE,T) выбирается либо точное значение соответствующей физической величины h(AE,T) = - 1+ехр(Л/Г) либо приближенное значение h(AEJ) = Qxp{-AE/T) Вторая формула используется наиболее часто. При её использовании h(AE,T) оказывается больше единицы в случае и тогда соответствующая вероятность считается равной . Таким образом, если новое состояние даёт лучшее значение оптимизируемой функции, то переход в это со стояние произойдет в любом случае. Итак, конкретная схема метода отжига задается следующими параметрами: Выбором закона изменения температуры Т(к), где к- номер шага; выбором порождающего семейства распределений G{x,T)\ (выбором функции вероятности принятия h(AE,T). Блок-схема метода отжига приведена на рис. 3.1. Алгоритм: 1. Случайным образом выбирается начальная точка х eS Текущее значение энергии Е устанавливается в значение дх у 2. к-я итерация основного цикла состоит из следующих шагов: а) Сгенерировать новую точку xl = G(x,T(k)); б) вычислить значение функции в ней Е1 =f{x1) , в) сгенерировать случайное число а из интервала [0; 1]; г) если a h(El-E,T(k)), то установить x r-xl,E r-El и перейти к следующей итерации. Иначе повторить шаг (а), пока не будет найдена подходящая точка х1.
Метод имитации отжига оказывается особенно удачным для полимодальных комбинаторных задач с очень большим количеством возможных решений. Экспериментально установлено, что эффективность метода имитации отжига при поиске траекторий движения многозвенных манипуляторов составляет около 70%, предложено комбинирование метода имитации отжига и метода на основе генетического подхода с целью улучшения качества поиска.
