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

На правах рукописи

ОО5003418

КРОХМАЛЬ Олег Николаевич

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

Специальность: 05.13.01 - «Системный анализ, управление и обработка информации (технические науки)»

Специальность: 05.02.18 - «Теория механизмов и машин»

Автореферат - 1 ДЕК 2011

диссертации на соискание ученой степени кандидата технических наук

Курган-2011

005003418

Работа выполнена в Курганском образовательном учреждении высшего профессионального образования «Курганский государственный университет».

Научный руководитель:

Шестаков Александр Леонидович доктор технических наук, профессор

Тележкин Владимир Фёдорович доктор технических наук, профессор

Официальные оппоненты:

Бабичев Дмитрий Тихонович доктор технических наук, профессор

Ведущая организация:

ОАО «Специальное конструкторское бюро машиностроения», г. Курган

Защита состоится 22 декабря 2011 года, в 14 часов, на заседании диссертационного совета Д 212.298.03 при Южно-Уральском государственном университете по адресу: 454080, г. Челябинск, пр. им. В.И. Ленина, 76, ауд. 1001 (гл. корпус)

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета.

Автореферат разослан 17 ноября 2011 года.

Ученый секретарь

диссертационного совета Д 212.298.03

С.Г. Некрасов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

1. Выявлены новые объекты исследования - базовые кинематические цепи (БКЦ) и установлен принцип их строения как цепи диад с перекрывающимися обратными связями.

2. На основе принципа строения БКЦ разработан алгоритм обработки информации их математических моделей для их структурного анализа.

3. На основе структурных свойств БКЦ разработай алгоритм обработки информации их математических моделей для их структурного синтеза

4. Разработаны алгоритмы обработки информации математических моделей БКЦ для тестирования их на изоморфизм.

5. Проведем синтез всех возможных базовых кинематических цепей, состоящих из 5, 6, 7 и 8 диад. Составлен их электронный каталог - база данных. Получены новые ранее неизвестные базовые кинематические цепи.

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

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

2. Разработанный алгоритм синтеза базовых кинематических цепей и его программная реализация позволяют осуществлять синтез нензоморфных вариантов для создания базы данных с целью использования её для выбора подходящей БКЦ. Выбор БКЦ в соответствии с требуемыми условиями движения является важным начальным этапом при проведении структурного (структурно-параметрического) синтеза рычажных механизмов.

Апробация работы. Основные положения и результаты работы докладывались на: научной конференции студентов и аспирантов Курганского госуниверситета (Курган, 2005); научных семинарах Курганского госуниверситета (2005-2007); VI Международной научно-технической конференции «Динамика систем, механизмов и машин», посвященной 65-летию ОмГУ (г. Омск, 2007); VI Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (г. Санкт-Петербург, 2008); XX Международной конференции молодых ученых и студентов по современным проблемам машиноведения, посвященной 70-летию ИМАШ РАН (г. Москва, 2008); 13-м Всемирном конгрессе ИФТоММ (Мексика, г. Гуанахуато, 2011) На защиту выносятся:

- Алгоритм структурного анализа базовых кинематических цепей и его

реализация в виде компьютерной программы

- Алгоритм генерирования структурных схем базовых кинематических цепей,

разработанный на основе выявленных их структурных свойств и его реализация

в виде компьютерной программы

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

Результаты компьютерных экспериментов по структурному синтезу и анализу базовых кинематических цепей, состоящих из 4, 5, 6. 7 диад и применение этих результатов к кинематическому синтезу механизмов

Публикации. По результатам выполненных исследований и разработок опубликовано 11 печатных работ, в том числе в изданиях, включённых в перечень ВАК РФ

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка, состоящего из 112 наименований и приложений. Основная часть работы содержит: 151 страница, 64 иллюстрации, 30 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведен обзор существующих методов классификации, структурного анализа и синтеза механизмов. Представлены сведения о развитии таких методов начиная с 19 века до настоящего времени. Рассмотрены работы различных ученых, занимавшихся указанными вопросами, таких как Г. Монж, Р. Виллис, П.Л. Чебышев, Ф. Рело. П.О. Сомов, Л.В. Ассур, А.П. Малышев, И.И. Артоболевский, Н.С.Васильев, В.В. Добровольский, Г.Г. Баранов, О.Г. Озол, С.Н. Кожевников.

Далее рассмотрено современное состояние вопроса и основные тенденции развития. Проанализированы работы ученых, проводивших исследования в области структурного синтеза, структурного анализа механизмов: Ф. Фрейденштейна, Л. Добрянского, Ф. Грослн, М. Хуана, А. Сони. Е. 'Гаттла, К. Тишлера, Т. Мрутхюнджайа, В.М. Хаита, И.В. Ханга, Д. Сэна, М. Рагхаваиа, Ф. Харари, Т. Лу, К. Ю. X. Ли, И. Юна, Д. Уикера, А. Рэйчи, Р. Дабн. A. Pao, X. Баласубраманиана, А. Амбекара. В. Агавала, Э.Е. Пейсаха, Л.Т. Дворникова, А.И. Смелягина и др.

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

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

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

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

Задача отбора неизоморфных представителей из синтезированных графов БКЦ является неотъемлемой частью задачи структурного синтеза. Хотя выявление изоморфизма является типовой задачей теории графов и известно, что матрицы ■межности изоморфных графов различаются только порядком расположения •толбцов и строк, общего метода решения данной проблемы до настоящего времени ге существует. В дайной работе используются для исследования графов БКЦ на изоморфизм два метода. Первый метод (Мрутхюнджайа (Т.Б. МгшИушуауа), Рагхаван (М.Я. Яа^ауап)) основан на сравнении характеристических многочленов , 1атриц смежности вершин графов. Несмотря на то, что данный метод относительно прост и дает хорошие результаты, имеются сведения о том, что в некоторых случаях >го применение дает ошибочные результаты. С другой стороны, сведений об шибочности результатов применительно к графам структурных групп не имеется. . учетом вышесказанного необходимым является сопоставление результатов проверки графов на изоморфизм, осуществленной различными методами. Поэтому, втором был разработан второй оригинальный метод. Идея метода состоит в оэтапном сравнении параметров, характеризующих структуру графов БКЦ. На первых этапах применяются наиболее простые критерии наличия изоморфизма, не ребующие сложных и объемных вычислений. И только в случае, если их применение не дает однозначного ответа на вопрос об изоморфизме двух графов последовательно применяются более сложные и точные критерии.

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

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

Третья глава диссертационной работы посвящена детальной разработке 1горитмов обработки информации математических моделей для структурного нализа и синтеза базовых кинематических цепей рычажных механизмов на сновании методов, изложенных в предыдущей главе. В качестве математических моделей БКЦ приняты их условные графические изображения, которые являются математическими объектами, т.е. графами. Аналитическое описание математических моделей осуществляется с помощью матриц смежностей вершин, !атриц инцидентности вершин и рёбер и цикловых матриц.

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

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

а) б)

Рис. 2 Блок-схема алгоритма: а) нахождения пути Гамильтона; б) обработки дополнительных условий при нахождении пути Гамильтона

Алгоритм обработки информации графовых моделей для структурного синтеза. Как отмечалось выше, при структурном синтезе БКЦ необходимо решать две важные задачи: а) генерирование всех возможных структурных схем; б) отбор из полученных структурных схем неизоморфных представителей. Соответственно, разработанный алгоритм структурного синтеза является комплексным и направлен на решение обеих задач.

Алгоритм предусматривает задание исходных данных для синтеза БКЦ. Такими данными является исходный граф -- дихотомическая цепь и его аналитическое описание - структурная матрица смежиостей. Исходный граф может состоять из любого числа последовательно соединенных диад. В качестве примера

на рис. 3 приведён граф, состоящий ш шести диад. В этом случае операция синтеза графа базовой цепи сводится к совмещению висячих вершин (7, 8, 9, 10, 11, 12, 13) исходного графа с его внутренними вершинами (1, 2, 3, 4, 5, 6), т.е. операция совмещения вершин является обратной к операции расщепления вершин. Исходному графу всегда можно сопоставить матрицу смежности (рис.4). Такая матрица содержит (2(1+1) столбцов и (1 строк, где с! - число диад исходного графа. В исходном графе пронумерованы сначала внутренние

1 2 4 3 5 6 13

глттг

7 8 9 10 И 12 Рис.3 - Исходный граф

вершины, затем висячие вершины. Матрица поэтому состоит из двух половин. В евой части матрицы расположены столбцы с номерами внутренних вершин, а в правой части с номерами висячих.

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

Из исходного графа можно получить как граф БКЦ, так и графы более 'ложных кинематических цепей. Имеет практический смысл синтезировать базовые кинематические цепи отдельно. Очевидно, что при этом на перемещение «1» в исходной матрице накладываются некоторые ограничения. Во-первых, в правой половине исходной матрицы всегда должно оставаться не менее четырех «1», ■оответствующих четырем внешним кинематическим парам, за исключение случая, когда исходных граф содержит три диады. Во-вторых, БКЦ должна быть .(неразделимой». В графе БКЦ все внутренние вершины охвачены обратными •вязями - это её признак, соответствующий тому, что понимается под термином шеразделнмая» для групп Ассура. Наличие обратных связей в БКЦ, перекрывающих все вершины в её графе, соответствует тому факту, что уравнения, вписывающие связи между вершинами в ней образуют единую систему уравнений, не распадающуюся на подсистемы, которые можно решать отдельно и

1 1 } 4 5 * - 8 » 11 11 12 и

1 X е. 1 X X X X X X

2 X х п 1 X X X X X

3 X X Е ! X X X X

4 X X Е 1 X X X

5 X X и 1 X X

б X X 1 1

Рис.4 Матрица исходного графа

последовательно друг за другом. В-третьих, в графе БКЦ не может быть двойных дуг. что означало бы наличие в кинематической цепи дублирующих звеньев. Поэтому в левой половине матрицы смежности графа БКЦ не должно быть «1», симметрично расположенных относительно главной диагонали.

Алгоритмы проверки полученных структур на изоморфизм. Как уже отмечалось, одной из основных задач при структурном синтезе является выявление возможного изоморфизма графов кинематических ценен. Для сравнения результатов и проверки их надёжности разработаны два алгоритма, в которых использованы два различных метода для проверки графов БКЦ.

Первый алгоритм для исследования графов БКЦ на изоморфизм разработан на основе известного метода сравнения коэффициентов характеристических многочленов полных матриц смежности рассматриваемых графов. Характеристический многочлен матриц имеет вид:

а0хл + а^""1 + а2х"*2 + ... + а П-|Х + а „, где а0, аь а2,..., а„ - коэффициенты, п - число вершин графа.

Коэффициенты вычисляются с помощью формул Бохера:

а„ = 1:

(1)

1 а

т Г

5 "" '

1,2,..., п,

(2)

где в, =Тг(Аг)

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

1 2 1 4 5 6 7 1 8 9

1 0 (1 0 1 1 1 и 0 0 :

2 0 и I 0 1 0 0 ! 1 о :

3 0 1 0 0 1 0 0 | 0 1

4 1 0 0 0 1 0 .....П.....0 о 1

5 1 1 1 1 0 0 0 | 0 0 ;

6 1 (1 0 0 0 0 0 \ 0 0 |

7 0 0 0 1 0 0 0 ! 0 о !

8 0 1 (1 0 0 0 о ; о 0 ;

9 0 0 1 0 0 0 0 | 0 0 !

Рис.5 - Граф БКЦ и его структурная матрица смежности вершин

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

х 1 Ох' 4х + 27х + 12х

4х + 5х,

х9 - 10х7 - 2х" + 25 х5 + 4х4 - 19х' - 2х2 + 4х.

Следовательно, графы неизоморфны.

..........".....|..........2............3.....I.....4.....1.....5......... 6........7 8 9 |

1 : о 1 ; о | о ! 1 I о о о |

2.....:.....1..........б.....:.....1......1.....б.....I.....I..........б.........о..........0..........0......1

3.....1.....0...........I......:.....О.....I......I I.....О..... О О I О I

4 , о о : I ! о М о о о I

5 I ~ О I I | О ~~б I 0~ О

6 I 1 0:00 О б б 0 б~~ I. 0 0 О I о о о о

а.....I.....б...........б.....*......I............б .....б.......б.......б б "о

9 о о ; о 1 о о б о б-

Рис.6 - Граф БКЦ и его структурная матрица смежности вершин

Второй алгоритм (рис. 7) выявления изоморфных графов БКЦ является омплексным. Алгоритм основан на методе непосредственного изучения труктуриых особенностей графов, а значит и самих кинематических цепей, федставленных данными графами.

Основные этапы разработанного метода следующие:

1. Оценка изоморфизма при помощи сравнения расширенных векторов тепеней вершин графов.

2. Оценка изоморфизма графов путем исследования окрестностей их вершин и разделения вершин на классы.

3. Оценка изоморфизма графов на основе изучения и сравнения их циклического строения.

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

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

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

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

По результатам сравнения признаков, описанных выше, делается вывод об изоморфизме (неизоморфизме) графов, без учета расположения висячих вершин. Такие вершины и инцидентные им ребра не оказывают определяющего влияния на внутреннюю структуру графа. Однако очевидно, что присоединение висячей вершины к той или иной внутренней вершине, тем ие менее, вносит изменения в структуру графа. Висячие вершины обладают специфическими свойствами, поэтому применение для изучения их расположения методов, описанных выше, оказывается неэффективным. В связи с этим предложен новый способ. Суть которого состоит в следующем. В каждом из исследуемых графов выделяются подграфы, содержащие только вершины, смежные с висячими вершинами. Далее определяется количество всех путей длины от 2 до п (где п - число вершин подграфа), исходящих из вершин различных классов. Для этого используется известное из теории графов свойство полной матрицы смежности А любого графа: при ее возведении в какую-либо степень, например т, получается матрица, каждый элемент ЛШ(У) которой представляет собой количество путей длины т, проведенных из вершины 1 в вершину].

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

Структурный анализ. Как уже отмечалось, разложение БКЦ в дихотомическую цепь соответствует нахождению Гамильтонова пути между внутренними вершинами. Для этих целей разработано специальное программное обеспечение, которое позволяет визуально вводить в компьютер и редактировать данные о структуре БКЦ и находить все возможные Гамильтоновы пути. При этом имеется возможность задания ограничений для решения различных задач анализа. В качестве объектов для компьютерных экспериментов по структурному анализу кинематических цепей были взяты схемы групп Ассура, приведенные в статье Э.Е. Пейсаха «Каталог восьмизвенных плоских групп Ассура», опубликованной в журнале «Теория механизмов и машин». №2, 2007, том 5. Параметры каждой группы посредством элементов интерфейса программы структурного анализа передавались в компьютер. После чего программа находила все возможные пути

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

ыше условиям. _

| НАЧЛЧ- ■ )

Не совпадают — Вычисляются н сравниваются расширенные векторы степеней вершин

1 Совпадают ;

Вычисляьжяи сравннваюня унифицированные матрицы сме^ност

Не совпадают 4

Не совпадают - Вычисляются а сравниваются с пиал I автоморф ньк вершин графов

Совпадают 1

Не совпадают " Определяется н сравнивается конщчюе строение графов

1 Совпадают *

Не совпадают ~ Определяется и сравнивается распоно-т^нне висячих вершин

СОЕП.1ДЯОГ

графьигюыомны

ГР.М'Ы НЕШОМОРФНЫ

1

КОНЕЦ

Рис.7 - Блок-схема алгоритма обработки информации о строении графов комбинированного метода проверки БКЦ на изоморфизм

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

Для всех БКЦ, соответствующих упомянутым выше группам Лссура, были получены варианты разложения.

Кроме того, эксперименты по разложению в дихотомическую цепь были проведены и для отдельных более сложных базовых кинематических цепей. Результаты анализа показали возможность разложения цепей. Таким образом, проведенные эксперименты подтверждают гипотезу о возможности разложения БКЦ в дихотомическую цепь. Этот факт даёт возможность использования результатов структурного анализа при выполнении кинематического анализа и кинематического синтеза плоских рычажных механизмов.

Структурный синтез. Разработанные алгоритмы и программное (Рис. 8, 9) обеспечение дали возможность провести компьютерные эксперименты по структурному синтезу базовых кинематических цепей. Синтез проводился из исходных графов, состоящих из 5, 6, 7 и 8 диад. Результаты показали, что цепей, синтезированных из исходного графа с 5 диадами, существует 18, из них 4 неизоморфны. Для 6 диад - 250, из них 27 неизоморфны. Для 7 диад ~ 4449, из них 250 неизоморфны, для 8 диад - 105068 из них 3865 неизоморфны.

Укажите параметы расчета Количество диад 6

Г Показывать матрица Г" Без''глухих''вершин № Только меизоморФные графы ;

Начать Отмена

Рис. 8 Окно ввода исходных данных для генерирования структур БКЦ

Рис. 9 - Результаты работы программы в виде графов, структурных матриц и

линейных графов

На основании результатов структурного синтеза составлен каталог-, Содержащий все возможные структурные схемы БКЦ, состоящих из 5, 6, 7 и 8 диад. ¡3 виду значительного количества таких структур каталог представлен в виде шектронной базы данных. Данный каталог постоянно расширяется. В настоящее l-ремя он содержит порядка 4000 структурных схем базовых кинематических цепей ,1 может быть использован в экспертных компьютерных системах.

Применение результатов структурного анализа для кинематического Синтеза шарнирного направляющего четырехзвеиника робота-манипулятора. рассмотренные теоретические исследования в рамках предлагаемого подхода имеют фактическое значение т.к. вопросы кинематического синтеза рычажных механизмов непосредственно связаны с их структурными свойствами. Это обстоятельство рассмотрено на примере синтеза направляющего механизма. 3 общем случае задача синтеза направляющего шарнирного четырехзвеиника (рис. ¡О), состоит в следующем. Имеется некоторая кривая у = f(x), которая может быть алана своим уравнением или таблицей значений её координат х и у. Требуется определить размеры звеньев и положение механизма, на шатуне которого имеется точка С, описывающая кривую, мало отличающуюся от заданной кривой на некотором участке или да всём протяжении. Подлежат определению следующие

тараметры: линейные - а, Ь, с, d, L, L2, L3, R и углы......W, а. Синтез направляющего

механизма проводится на основании передаточной функции диады.

Рис. 10 - Схема механизма, состоящего из двух диад

Структурный анализ показывает, что механизм состоит из двух последовательно соединённых диад CEF и ЕВА, без обратных связей, поэтому синтез выполняется последовательно для каждой диады отдельно. На первом этапе варьируются параметры L и W, а в результате квадратичного синтеза определяются параметры а и Ь. На втором этапе варьируются параметры L3 и а, а в результате квадратичного синтеза определяются параметры R и координаты точки А.

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

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

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

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

Положение входного звена (3-4-10) задаётся обобщённой координатой - углом (9+Фо). Требуется определить длины всех рычагов и углы начальных положений входного - фо и выходного -0о звеньев, таким образом, чтобы точка 0 двигалась по заданной траектории, описываемой заданной функцией 8=8(ф), а выходное звено (78-9) совершало врашателыюе движение в соответствии с заданным законом 0=0(ф) при фо<ф<ф„т-

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

Рис. 11 - Структурная схема механизма - а), его БКЦ - б) и разложение графа БКЦ в

дихотомическую цепь - в).

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

Расчёт показывает, что механизм имеет одну степень подвижности, следовательно, и одни входной рычаг. Выберем рычаг 8-9 в качестве входного.

Компьютерный структурный анализ БКЦ (рис. II) показал, что она может быть разложена в дихотомическую цепь 64 вариантами.

Для заданных условий движения механизма необходимо выбрать вариант разложения из вершимы 0, т.к. эта вершина является выходной и её закон движения

1еобходимо обеспечить. Для этой вершины существуют два варианта с входной ершиной 9. Выберем первый из них, представленный на рис. 11.

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

Обшая передаточная функция механизма составляется по результатам -труктурного анализа БКЦ из передаточных функции всех диад, входящих в его ■остав и является системой обыкновенных дифференциальных уравнений (ОДУ) относительно координат точек, в которых располагаются шарниры. В результате ешения ОДУ (задачи Коши) определяются траектории движения кинематических iap механизма.

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

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

ЗАКЛЮЧЕНИЕ

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

Теоретические исследования и компьютерные эксперименты, проведённые по езультатам теоретических исследований, позволяют сформулировать следующие ыводы и результаты:

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

2. Разработан алгоритм обработки информации для структурного анализа азовых кинематических цепей на основе их графовых моделей. Особенностью лгоритма является анализ возможных путей Гамильтона в графе с учётом собенностей строения БКЦ.

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

4. Разработан метод и алгоритм обработки информации структурных матриц БКЦ для комплексного исследования их изоморфизм. Предложенный метод и алгоритм основаны на выявленных закономерностях структурных матриц БКЦ.

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

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

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

НАУЧНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Крохмаль О.Н. Разработка алгоритма и компьютерной программы структурного синтеза групп Ассура // Сборник научных трудов аспирантов и соискателей Курганского государственного университета, Курган, 2005. С.22-23.

2. Свидетельство об отраслевой регистрации разработки №. гос. per. 50200401242, «Геометрический синтез плоского шарнирного четырехзвениого направляющего механизма» (SFLMGP) // Крохмаль Н.Н., Крохмаль О.И. / Дата регистрации 27.10.2004.

3. Свидетельство № 5351 об отраслевой регистрации разработки, «Программа структурного синтеза групп Ассура» (Synthesis) // Крохмаль Н.Н., Крохмаль О.Н./ Дата регистрации 21.11.2005.

4. Крохмаль О.Н., Крохмаль Н.Н., Дрововозов ГЛ. Программное обеспечение для изучения задачи синтеза кинематических цепей рычажных механизмов. -Известия Челябинского научного центра, вып. 4(34), 2006.

5. Крохмаль О.Н., Крохмаль Н.Н. Изучение задачи структурного синтеза кинематических цепей рычажных механизмов с помощью компьютерного моделирования // Динамика систем, механизмов и машин: Сб. материалов VI Междунар. науч.- техн. конф. - Омск: ОмГТУ, 2007. Кн.З. С.53-57.

6. Крохмаль Н.Н., Крохмаль О.Н. Структурный анализ кинематических цепей рычажных механизмов. - Вестник Курганского госуниверситета, 2008.

7. Крохмаль Н.Н., Крохмаль О.Н. Структурный синтез кинематических цепей иажных механизмов. - Вестник Курганского госуниверситета, 2008.

8. Крохмаль О.Н. Разработка методов анализа и синтеза групп Ассура на нове их диадного представления // Высокие технологии, фундаментальные следования, промышленность: Сб. материалов VI Междунар. науч.- практич. конф. СПб, 2008.

9. Крохмаль О.Н. Разработка методов анализа и синтеза групп Ассура на нове их диадного представления // Сб. материалов XX Международной интернет-иентированной конференции молодых ученых и студентов. - М., 2008.

10. Крохмаль Н.Н., Крохмаль О.Н. Метод оптимизационного кинематического нтеза плоских рычажных механизмов на примере восьмизвенного механизма. -естник ЮУрГУ, серия машиностроение», выпуск, 17 № 11(228), 2011 год.

11. Krokhmal N.N., Krokhmal O.N. Structural analysis and synthesis of Assur oups based on their topological properties. Proceedings of 13th World Congress on the MM. - Mexico, Guanajuato, 2011.

Подписано в печать 10.11.11. Формат 60x80 1/16. Печать трафаретная. Усл. печ. л. 0,95. Уч. изд. л. 1. Тираж 100 экз. Заказ 312

Редакционно-издательский центр КГУ 640669, г. Курган, ул. Гоголя, 25 Курганский государственный университет

ВВЕДЕНИЕ.

ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ СТРУКТУРНОГО АНАЛИЗА И СИНТЕЗА КИНЕМАТИЧЕСКИХ ЦЕПЕЙ РЫЧАЖНЫХ МЕХАНИЗМОВ.И

1.1 Развитие методов классификации, структурного анализа и синтеза механизмов.И

1.2 Современное состояние вопроса и основные тенденции развития.

1.3 Постановка задач, исследования.

ГЛАВА 2 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СТРУКТУРНОГО АНАЛИЗА И СИНТЕЗА БАЗОВЫХ КИНЕМАТИЧЕСКИХ ЦЕПЕЙ РЫЧАЖНЫХ

МЕХАНИЗМОВ.

2.1 Структурный анализ и синтез базовых кинематических цепей.

2.1.1 Основные допущения и соотношения, принимаемые при»анализе базовых кинематических цепей-.

2.1.2 Топологические свойства базовых кинематических цепей.

2.1.3 Структурный.синтез базовых кинематических цепей.

2.2 Выводы по главе.

ГЛАВА 3 АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ДЛЯ СТРУКТУРНОГО АНАЛИЗА И СИНТЕЗА БАЗОВЫХ КИНЕМАТИЧЕСКИХ ЦЕПЕЙ

3.1 Алгоритм структурного анализа базовых кинематических цепей.

3.2 Алгоритм генерирования всех возможных базовых кинематических цепей.

3.3 Алгоритм проверки графов кинематических цепей на изоморфизм с использованием характеристических многочленов их матриц смежности.

3.4 Алгоритм комплексного метода исследования графов кинематических цепей на изоморфизм.

3.5. Выводы по главе.

ГЛАВА 4 ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ И КОМПЬЮТЕРНЫЕ ЭКСПЕРИМЕНТЫ ПО СТРУКТУРНОМУ АНАЛИЗУ И СИНТЕЗУ БАЗОВЫХ КИНЕМАТИЧЕСКИХ ЦЕПЕЙ.

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

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

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

4.4 Применение результатов структурного анализа на примере кинематического синтеза восьмизвенного механизма.

4.5 Выводы по главе.

Актуальность; исследования: Современные технологии нуждаются в системном подходе при выполнении проектных работ различных технических устройств. Это связано с обработкой большого массива информации;, относящейся', прежде всего к. структуре,, проектируемого технического устройства; Рычажные механизмы находят широкое применение во многих областях современных технологий?— робототехнике, мехатронике,. являющихся основой автоматизированных линий; различных производств. Основош системного- проектирования« рычажных механизмов являются* их структурный; анализ и синтез. Для? создания такой основы необходимы системные знания о структурных свойствах изучаемого объекта — кинематических цепях рычажных механизмов: В?настоящее время)однимшз распространённых: методов; структурного анализами синтеза механизмов является? метод Ассура - Артоболевского: Базовым понятием этого метода является кинематическая цепь,, обладающая» определенными; структурными свойствами, (группа; Ассура); Практика проектирования показывает, что актуальной является: фундаментальная« задача изучения« закономерностей строения« самих, структурных групп и.разработка на этой основе алгоритмов и программного обеспечения для их анализа и синтеза. Характерной особенностью? этой задачи- является то, что- её решение требует обработки большого объёма информации.

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

Наиболее перспективным с этой? точки зрения- представляется' применение в качестве теоретической основы таких методов, математической теории графов, что подтверждается; в частности, возросшим в последнее время; интересом к данному разделу математики именно- применительно; к целями структурного3 анализа! и синтеза? механизмов; При« таком подходе любые кинематические: цепи? могут быть представлены в виде сравнительно простой математической; модели — графа- Если; учесть, что» любому графу может быть, сопоставлено его матричное! описание, то? можно? сказать, что применение таких-; моделей? является^ наиболее эффективным с точки? зрения построения алгоритмов.

При решении задачи структурного синтеза рычажных, механизмов следует выделить два-основных этапа:

1. Генерирование: всех; структур (кинематических цепей); отвечающих определенным критериям;

2. Отбор из полученных структур неизоморфных представителей

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

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

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

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

Объектом исследования являются» базовые кинематические цепи, обладающие- характерными структурными; свойствами и являющиеся составными компонентами рычажных механизмов-промышленных роботов и манипуляторов.

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

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

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

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

Научная новизна диссертационной работы заключается в следующем:

1. Выявлены новые объекты исследования - базовые кинематические цепи (БКЦ) и установлен принцип? их строения* как» цепи диад с перекрывающимися обратными связями.

2. На основе принципа строения- БКЦ. разработан алгоритм, обработки информации их математических моделей для их структурного анализа.

3. На основе структурных свойств БКЦ разработан алгоритм обработки информации их математических моделей для их структурного синтеза,

4. Разработаны алгоритмы обработки, информации математических моделей БКЦ( для тестирования их на изоморфизм.

5. Проведен синтез всех возможных базовых кинематических цепей, состоящих из 5, 6, 7 и 8 диад. Составлен их электронный каталог - база данных. Получены новые ранее неизвестные базовые кинематические цепи.

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

1. Разработанный алгоритм и программное обеспечение позволяют осуществлять структурный анализ БКЦ. Такой анализ является первым необходимым-этапом при выполнении кинематического анализа и синтеза кинематических цепей роботов и манипуляторов, что продемонстрировано на конкретных примерах.

2. Разработанный алгоритм синтеза базовых кинематических цепей и его программная реализация позволяют осуществлять синтез неизоморфных вариантов для создания базы-данных с целью1 использования её для выбора подходящей БКЦ. Выбор БКЦ в соответствии с требуемыми условиями движения является важным начальным этапом при проведении структурного (структурно-параметрического) синтеза рычажных механизмов.

Апробация работы. Основные положения и результаты работы докладывались на: научной' конференции' студентов и аспирантов Курганского госуниверситета (Курган, 2005); научных семинарах Курганского госуниверситета (2005-2007); VI Международной научно-технической конференции «Динамика' систем, механизмов и машин», посвященной, 65-летию ОмГУ (г. Омск, 2007); VI Международной научно-практической' конференции «Исследование, разработка и применение высоких технологий в промышленности» (г. Санкт-Петербург, 2008); XX Международной конференции МОЛОДЫХ ученых И( студентов по современным проблемам машиноведения, посвященной* 70-летию*ИМАШ РАН (г. Москва, 2008); 13-м Всемирном конгрессе ИФТоММ (Мексика, г. Гуанахуато, 2011)

Результаты компьютерных экспериментов по структурному синтезу и анализу базовых кинематических цепей, состоящих из 4, 5, 6, 7 диад и применение этих результатов к кинематическому синтезу механизмов манипуляторов

Апробация работы. Основные результаты работы докладывались на: научной конференции студентов и аспирантов Курганского госуниверситета; научных семинарах кафедры «Детали машин» Курганского госуниверситета;

- VI Международной научно-технической конференции, посвященной 65-летию ОмГу (г. Омск, 2007)

- VI Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (г. Санкт-Петербург,2008);

- XX Международной конференции молодых ученых и студентов по современным проблемам машиноведения, посвященной 70-летию ИМАТТТ РАН (Москва, 2008)

- 13-ом Всемирном конгрессе ИФТоММ (Мексика, Гуанахуато, 2011)

На защиту выносятся:

- Алгоритм^ обработки информации математических моделей для структурного анализа базовых кинематических цепей'и его реализация в виде компьютерной программы

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

- Метод и« алгоритмы, обработки информации* математических моделей для проверки базовых кинематических цепей на' изоморфизм и его реализация в виде компьютерной программы.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка, состоящего из 112 наименований, и приложений. Общий объем работы:151 страниц, 64 иллюстраций, 30 таблиц.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

Теоретические исследования и компьютерные эксперименты, проведённые по результатам теоретических исследований, позволяют сформулировать следующие выводы и результаты:

1. Введено понятие базовой- кинематической цепи (БКЦ) на основе установленного структурного свойства базовых кинематических цепей, а именно наличия обратных перекрывающихся1 связей в системе диад.

2. Разработан алгоритм обработки информации для структурного анализа базовых кинематических цепей на основе их графовых моделей. Особенностью алгоритма является анализ возможных путей Гамильтона1 в графе с учётом особенностей строения БКЦ.

3. Разработан алгоритм генерирования всех возможных^ базовых кинематических цепей1 плоских рычажных механизмов, образованных из исходного графа, содержащего заданное число диад.

4. Разработан метод и алгоритм обработки информации структурных матриц БКЦ для комплексного исследования их изоморфизм. Предложенный метод и алгоритм основаны на выявленных закономерностях структурных матриц БКЦ.

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

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

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

1. Чебышев П. Л. Собрание сочинений: В 2т. - СПб, 1907.

2. Сомов П.О. О степенях свободы кинематической цепи. СПб:, 1888.

3. Сомов П.О. Кинематика подобно изменяемой системы. СПб:, 1900.

4. Ассур Л.В. Исследование плоских стержневых механизмов с точки зрения их структуры и классификации.- М.:: Изд-во АН СССР, 1952.

5. Малышев А.П. Анализ и синтез механизмов с точки зрения их структуры.//Изв. Томского технолог. Ин-та.- 1929. Вып. 44.

6. Артоболевский И.И. Теория пространственных механизмов. — М.; Л.: ОНТИ НКТПСССР, 1937.

7. Артоболевский И.И. К вопросу о структуре и классификации кинематических цепей с замкнутым; контуром. — Изв. АН СССР. ОТН, 1939, вып.4.8 . Добровольский В.В., Артоболевский И.И. Структура и классификация механизмов. -М.; Л.: Изд. АН СССР, 1939.

8. Добровольский В.В. Классификация механизмов. М.: Изд. ОТН АН СССР, 1939.

9. Добровольский В.В. Теория механизмов. М.: Машгиз, 1943.

10. Добровольский В.В. Теория механизмов с двумя и более степенями свободы // Тр. Московского Станкина. — 1939, Т.4.

11. Добровольский В.В. Плоские механизмы с поступательными парами //Тр. ВВА: Сборник науч. тр. 1937. -№18.

12. Добровольский В.В. О точках Бурместера в сферическом движении // Прикладная математика и механика. Т.9. — 1945. — №6.

13. Добровольский В.В. Система механизмов. -М.: Машгиз, 1943.

14. Баранов Г.Г. Курс теории механизмов и машин. М.: Машгиз, 1958

15. Баранов Г.Г. Классификация, строение, кинематика и кинетостатика механизмов с парами первого рода // Труды семинара по теории машин и механизмов. 1952. - Т.2, вып. 46. — С.15-39

16. Т.Н. Davies, F.R.E Crossley. Structural analysis of plane linkages by frank's condensed notation // Journaliof Mechanisms, 1966.

17. F. Freudenstein, L. Dobrjanskyj. On a theory of type synthesis of mechanisms // In Proceedings of 11th International Congress of Applied Mechanics, Berlin, 1964.19: F.R.E. Crossley. Developments in Theoretical and Applied Mechanics . Vol. 2, 1965.

18. L.S. Woo. Type synthesis of plane linkages // Journal of Engineering for Industry, 1967.

19. F. Freudenstein. The basic concepts of Polya's theory of enumeration with applications to structural classification of mechanisms // Journal of Mechanisms, 1967.

20. Ml Huang, A.H: Soni. Application of linear, and nonlinear graphs in structural synthesis of kinematic chains // Journal'of Engineering for Industry, 1973.

21. E.R. Tuttle, S.W. Peterson, J.E. Titus. Enumeration of basic kinematic chains using the theory of finite groups // Journal of Mechanisms, Transmissions and Automation in Design, 1989.

22. E.R. Tuttle, S.W. Peterson, J.E. Titus. Further applications of group theory to the enumeration and structural analysis of basic kinematic chains // Journal'of Mechanisms, Transmissions and Automation in Design, 1989.

23. Дворников JI.T. Начала теории структуры механизмов. Учебное пособие. -Новокузнецк, СибГГМА, 1994.

24. Дворников JI.T. Опыт структурного синтеза механизмов. — Теория механизмов и машин, №2 (4), 2004. Т.2. С.3-17.

25. C.R. Tishler, А.Е. Samuel, К.Н. Hunt. Kinematic chains for robot hands-I: Orderly number synthesis // Mechanism and Machine Theory, 1995.

26. C.R. Tishler, A.E. Samuel, K.H. Hunt. Kinematic chains for robot hands-II: Kinematic constraints, classification, connectivity and actuation // Mechanism and Machine Theory, 1995.

27. T.S. Mruthyunjaya. Structural1 synthesis by transformation of binary chains // Mechanism and Machine Theory, 1979.

28. W.M; Hwang, Y.W. Hwang. An algorithmfor the detection of degenerate kinematic chains // Mathematical and Computer Modelling, 1991.

29. L.C. Schmidt, H. Shetty, S.C. Chase. A graph grammar approach for structure synthesis of mechanisms. Journal of Mechanical Design, Transactions of the ASME, 2000.

30. A.C. Rao, P.B. Deshmukh. Computer aided structural synthesis of planar kinematic chains obviating the test for isomorphism // Mechanism and Machine Theory, 2001.

31. Ковалев М.Д. О структурных группах Ассура. Теория механизмов и машин, №1 (7), 2006. Т.4. С. 18-26:

32. N.I: Manolescu; A unitary method for construction of the kinematic plane chains and plane mechanism with different degrees of mobility // Revue Roumaine des Sciences Techniques, Serie de Macanique Appliquee, 1964.

33. T.H: Davies. An extension of Manolescu's classification of planar kinematic chains and mechanisms of mobility M > 1 using graph theory // Journal1 of Mechanisms, 1968.

34. D. Sen, T.S. Mruthyunjaya. The question of minimax loop-size in planar homogeneous kinematic chains // Mechanism and Machine Theory, 1996.

35. T.S. Mruthyunjaya, M.R. Raghavan. Structural5 analysis of kinematic chains and mechanisms based on matrix representation // Journal of MechanicabDesign, Transactions of the ASME, 1990.

36. F. Harary, H.S. Yan. Logical foundations of kinematic chains: graphs, line graphs and hyper graphs // Journal of Mechanical Design, Transactions of the ASME, 1990.

37. T. Liu, C.H. Yu. Identification and classifications of multi degree-of-freedom and multi-loop mechanisms // Journal of Mechanical Design, Transactions of the ASME, 1995.

38. C.R. Tishler, A.E. Samuel, K.H. Hunt. Kinematic chains for robot hands-II: Kinematic constraints, classification, connectivity and actuation // Mechanism-and Machine Theory, 1995.

39. H.J. Lee, Y.S. Yoon. Algorithmto identify the types of degrees of freedom in kinematic chains // JSME International Journal, 1996.

40. J.J. Uicker and-A. Raicu. A method for identification and recognition of equivalence of kinematic chains // Mechanism and Machine Theory, 1975.

41. H.S. Yan and W.M. Hwang. A method for the identification of planar linkage chains // Journal of Mechanisms 1983 :

42. H: S Yan, A. S. Hall, Linkage Characteristic Polynomials: Definitions, Coefficients by Inspection, ASME J: Mech. Des., 103 (3) (1981) 578- 584

43. T. S. Mruthyunjaya, A Computerized Methodology for Structural Synthesis of Kinematic Chains: Part 2-Application to Several Fully or Partial Known Cases, Mech. Mach. Theory, 19 (6) (1984) 497-505.

44. T. S. Mruthyunjaya, A Computerized Methodology for Structural Synthesis of Kinematic Chains: Part 3-Application to New-Case of 10-Link, Three-freedom Chains, Mech. Mach. Theory, 19 (6) (1984) 507-530

45. P. R. He, W. J. Zhang, Q. Li„ Some Further Development on the Eigensystem Approach for Graph Isomorphism Detection, J. Franklin lnst., 342 (2005) 657673

46. T.S. Mruthyunjaya and H.R. Balasubramanian. In quest of a reliable and efficient computational test for detection of isomorphism in kinematic chains // Mechanism and Machine Theory, 1987.

47. R.K. Dubey and A.C. Rao. New characteristic polynomial: A reliable index to detect isomorphism between kinematic chains // In Proceedings of the National Conference on Machine and Mechanism, pp. 36-40, IISG, Banglore, 1985.

48. A.G. Ambekar and V.P. Agrawal. On canonical numbering of kinematic chains and isomorphism problem: Max code // In ASME Mechanisms Conference, 1986.

49. A.G. Ambekar and V.P. Agrawal. Canonical numbering of kinematic chains and'isomorphism problem: Min code // Mechanism and1 Machine Theory, 1987.

50. C.S. Tang and T. Liu. The degree code a new mechanism identifier // Journal of Mechanical Design, Transactions of the ASME, 1993.

51. J.T. Kim andB.M. Kwak. An-algorithm of topological ordering for-unique representation of graphs. Journal of Mechanical Design, Transactions of the ASME// 1992.

52. J.K. Shin and S. Krishnamurty. On identification and canonical .numbering of pin jointed kinematic chains // Journal'of Mechanical Design, Transactions of the ASME, 1994.

53. A.C. Rao. Comparison of plane and spatial kinematic chains for structural error performance using pseudo-hamming distances // Indian Journal.of Technology, 1988

54. A.C. Rao and D. Varada Raju. Application of the hamming number technique to detect isomorphism among kinematic chains and inversions // Mechanism and Machine Theory, 1991.

55. A. C. Rao, C. N. Rao, Loop Based Pseudo Hamming Values-1 Testing Isomorphism and Rating Kinematic Chains, Mech. Mach. Theory, 28 (1) (1992) 113-127.

56. A. C. Rao, C. N. Rao, Loop Based Pseudo Hamming Values-2 Inversions, Preferred Frames and Actuator, Mech. Mach. Theory, 28 (1) (1992) 129-143

57. J. K., Chu, W. Q., Cao, Identification of Isomorphism Among Kinematic Chains and Inversions Using Link's

58. Adjacent Chain Table, Mech. Mach. Theory, 29(1) (1994) 53-58.

59. A. C. Rao. Application of Fuzzy Logic for the Study of Isomorphism, Inversions, Symmetry, Parallelism and Mobility nr Kinematic Chains, Mech. Mach. Theory, 35(8) (2000), 1103-1116

60. P. R. He, W. J. Zhang, Q. Li, A New Method for. Detection of Graph Isomorphism Based on the Quadratic Form, ASME J. Mech. Des., 125 (3) (2003) 640-642.

61. Z. Y. Chang, C. Zhang, Y.H. Yang, Y. X. Wang, A New Method to Mechanism Kinematic Chain Isomorphism .Identification, Mech. Mach. Theory, 37(4) (2002) 411-417.

62. F. G. Kong, Q. Li, W. J. Zhang; An Artificial^ Neural Network Approach to Mechanism Kinematic Chain Isomorphism Identification, Mech. Mach. Theory, 34 (2) (1999) 271-283.

63. R. P. Sunkari, C. Linda, Schmidt, Reliability and Efficiency of the Existing Spectral Methods for Isomorphism Detection: ASME J. Mech: Des. 128 (6) (2006)1246-1252.

64. H. Ding, Z. Haung, The Establishment of the Canonical^ Perimeter Topological Graph of Kinematic Chains and Isomorphism Identification. ASME J. Mech. Des. 129 (9) (2007) 915-923.

65. A. Dargar, A. Hasan, A., R.A. Khan, Application of Link Adjacency Values to Detect Isomorphism among Kinematic Chains. Int. J. Mech. and Mate, in Design, 6, (2010) 157-162.

66. Крохмаль Н.Н. Анализ и синтез рычажных механизмов на основе изучения их структурных, свойств: Монография: — Курган: Изд-во Курганского гос. ун-та, 2003.

67. Крохмаль Н.Н., Крохмаль О.Н. Структурный анализ кинематических цепей рычажных^механизмов. Вестник Курганского госуниверситета, 2008.

68. Крохмаль Н.Н. Структурный;анализ и синтез групп Ассура. //Известия: вузов. Машиностроение, 2002. № 7. С.24-30.

69. Крохмаль Н:Щ Крохмаль50;Н1Структурный анализ кинематических цепей рычажных механизмов. — Вестник Курганского госуниверситета; 2008.

70. Пейсах Э.Е. Метод идентификации структурных схем рычажных механизмов.- Проблемы машиностроения и надежности машин, РАН; Москва, 1995,№5, с 18-23. '78; Горбатов В.А. Фундаментальные основы дискретношматематикт — М;:: Наука-Физматлит, 1999.

71. Липский В. Комбинаторика для программистов. М».: Мир, 1988.

72. Пейсах Э.Е. Каталог восьмизвенных плоских групп Ассура. — Теория механизмов и машин, №2, 2007, Т.5. С. 15-27.

73. Свидетельство № 5351 об отраслевой регистрации разработки, «Программа структурного синтеза групп Ассура»-(Synthesis) // Крохмаль Н.Н., Крохмаль О.Н./ Дата регистрации 21.11.2005.

74. Артоболевский И.И. Механизмы в современной технике. Рычажные Механизмы: В 7т.- М.,. 1970.- Т. 1

75. Новгородцев В.А. Некоторые вопросы оптимального проектирования-механизмов при помощи ЭВМ// Теория механизмов и машин. — Харьков: Выща школа. Изд-во при Харьк. ун-те, 1979: Выш27. — С. 104-111.

76. Черкудинов С. А. Синтез плоских шарнирно-рычажных. механизмов. М.: Изд-во академишнаук СССР, 1959. - 323 с:

77. Харжевський В. О. Синтез-важільних прямолінійно-напрямних механізмів та механізмів, із зупинкою вихідної ланки? на базі шарнірного чотириланкового механізму: Дис. . канд. техн. наук: 05.02.02. -Хмельницький 2004. - 262 с.

78. Пейсах.Э.Е., Нестеров В:А. Система проектирования-плоских рычажных механизмов. М:: Машиностроение, 1988. - 232 с.

79. Кіндрацький Б., Сулим Г. Сучасний стан і проблеми багатокритеріального синтезу машинобудівних конструкцій (огляд) // Машинознавство. — Львів. — 2002. №10. - С.26-40.

80. Боголюбов А.Н. Развитие проблем механики машин. — К.: Наукова думка, 1967.-291с.

81. Блох3. ПІ. Приближенный синтез механизмов. — М.: Машгиз, 1948—172 с.

82. Alt Н. Uber Totlagen des Gelenkvierecks // Zeitschr fur angewandte Mathematik Und Mechanik, 1925. Bd.Y. - S.337-346

83. Sarkisyan, Y. L., Gupta, K. C., Roth. B.Kinematic geometry associated with the least square approximation of a given motion. ASME Journal ofEngineering for Industry, 95: 503-510; 1973.

84. Gupta, K. G., Roth. B. A general approximation theory for mechanism synthesis . ASME Journal of Applied mechanics, 42: 451-457, 1975

85. Ravani, B., Roth, B:. Motion synthesis using kinematic mappings. ASME Journal of mechanisms, Transmissions, and Automation in Design, 105:460-467, 1983'

86. Yao, J., Angeles, J. . Computation- of all optimum1 dyads in the approximate synthesis of planar linkages for rigid-body guidance.- Mechanism and Machine Theory, 35: 1065-1078, 2000

87. Wandling G. R, Qamhiyah; P. E., Flugrad; A., Donald; R. Application of spatial Fourier transforms to the synthesis of the motion generation mechanisms In: Proc. 0/DETC'OO, Baltimore, Maryland, U.S.A DETC2000/ MECH-14191, 2000

88. Ullah; I., Kota, S.Optimal synthesis of mechanisms for path- generation using Fourier descriptors and global search methods. ASME Journal of Mechanical design, 119: 504-510; 1997

89. Kong, F., Zou, H. A new method for path mechanism, synthesis. Journal of Shanghai- Jiaotong University, 30(12): 8-12, 1996

90. Vasiliu, A., Yannou. B.Dimensional.synthesis of planar mechanisms using neural networks: application, to path generator linkages. Mechanism and Machine Theory, 36: 299^310, 2001

91. Blaschke, W. Ebene kinematik, Munchen, 1956

92. Bottema, O., Roth, B. Theoretical Kinematics, North-Holland, Amsterdam, 19791021 Dudgeon, D. E., Mersereau, R. M'., Multidimensional Digital Signal Processing. Prentice-Hall, Englewood Cliffs, New Jersey, 1984

93. Castro, J. L., Mantas, C. J., Benitez, J. M. Neural networks with acontinuous squashing function in the output are universal approximators . Neural Networks, 13: 561-563, 2000

94. Proceedings of 12th World Congress, on the TMM. France, Beanson, 2007.

95. Крохмаль H.H., Крохмаль 0:H. Метод оптимизационного кинематического синтеза« плоских рычажных механизмов на примере восьмизвенного. механизма: Вестник ЮУрГУ, серия машиностроение», выпуск, 17 №11(228), 2014'год

96. Крохмаль Н.Н. Кинематический* анализ, групп Ассура в связи с их структурными-свойствами // Известия Челябинского научного центра УрО РАН, 2003 .-№1(18). С.1-6.

97. СПРАВКА об использовании результатов диссертационной работы Крохмаля О.Н.

98. Диссертационная работа Крохмаля О.Н. посвящена разработке новых эффективных методов анализа и синтеза рычажных механизмов.

99. Предполагается внедрить результаты диссертационной работы в практику конструкторской работы отдела.1. Начальник отдела расчётов5Х1. О F ¥ ® ¡MI №tññl1.terna tl &nal Federation let the Promotion c! blechjnttm and МэсЫл« Scicnee

100. Professor Krokhmaf Oleg Kurgan State University Kurgan, Russia Mar 7, 2011

101. Dear Professor Krokhmal Oleg

102. Prof. Marco Ceccarelh, LARM: Laboratory of Robotics and Mechatronics, DiMSAT, University of Cassino, Via Di Biasio 43, 03043 Cassino (Fr), Italy, Tel +39-0776-2993663. Fax +39-0776-2993989, Email: ceccare!li@unicas it

103. Prof. Yoshihiko Nakamura. Department of Mechano-lnformatics, University of Tokyo. 7-3-1 Hongo, Bunkyo-ku. Tokyo 113-8656, Japan, Tel +81-3-5841-6379, Fax +81-3-5841-7916 Email: nakamura@ynl.tu-tokyo.ac jp

104. Prof. Carios S. López-Cajún, Facultad de ingeniería, Universidad Autónoma de Querétaro, Cerro las Campanas sin, 76010 Santiago de Querétaro. QRO, México, Tel + 52-442-1921200-6049, Fax + 52-4421921200-6003 Email- cajun@uaq.mx

105. Dr Joe Rooney, Faculty of Mathematics, Computing and Technology, The Open University, Milton Keynes, MK7 6AA United Kingdom, Tel: +44 (0)1908 652979 Fax: +44 (0)1908 654052 Email: j rooney@open ac uk1. Dr Oleg N Krokhmal

106. The State Educational Institutionof Higher Professional Education1. Kurgan State University640669 Gogol Street 251. Kurgan1. RUSSIA16 April 2011j Dear Dr Krokhmal,

107. Dr J Roonev IFToMM Treasurer.1. EXECUTIVE COUNCIL