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

7 7, и Л 9 8

САНКТ-ПЕТЕРБУРГСКИЙ ИНСТИТУТ ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ РОССИЙСКОЙ АН

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

КИНУНЕН Александр Иванович

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

СПЕЦИАЛЬНОСТЬ 05.13.16 — ПРИМЕНЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ, МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ И МАТЕМАТИЧЕСКИХ МЕТОДОВ В НАУЧНЫХ ИССЛЕДОВАНИЯХ

АВТОРЕФЕРАТ

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

САНКТ-ПЕТЕРБУРГ 1992

Работа выполнена в Санкт-Петербургском институте информатики и автоматизации Российской АН.

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

доктор технических наук, профессор ДОМАРАЦКИП Александр Николаевич

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

доктор физико-математических наук СОТНИКОВ Александр Николаевич кандидат технических наук ПАВЛОВ Владимир Анатольевич

Ведущая организация — Санкт-Петербургский электротехнический университет.

заседании специализированного совета Д 1)03.62.01 Санкт-Петербургского института информатики и автоматизации Российской АН по адресу: 199178, Санкт-Петербург, В. О., 14 линия, 39.

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

Защита состоится «

1992 г. в

часов на

Автореферат разослан :< 'й- " » ' 1992 г.

Ученый секретарь специализированного совета кандидат технических наук

В. Е. МАРЛЕЙ

(

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

ГЛ. АКТУАЛЬНОСТЬ. Опыт разработки и эксплуатации станков с ЧПУ и манипуляционных роботов позволяет их рассматривать как "манипуляционпое адаптивное программируемое технологическое оборудование" (МАПТО), действующее в составе "проблемных технологических комплексов" (ПТК). Многономенклатурность производства, требование ритмичности и гибкости при сохранении качества продукции в условиях технологических возмущений требуют применения МАПТО с широким диапазоном охватываемых ПТК. Однако большинство задач системы программирования МАПТО, относящихся к области "искусственного интеллекта", не решаемы в реальном времени на существующих вычислительных средствах. Поэтому промышленные системы либо ограничиваются конкретными ПТК, либо не позволяют проблемное технологически эффективное программирование ("универсальные" системы). Исследовательские системы, строимые на основе аппарата исчисления предикатов, требуют сверхмощных нерентабельных вычислительных средств. Поэтому актуальна разработка рентабельной системы программирования МАПТО, настраиваемой на конкретные ПТК и эффективно сочетающей автоматический подход с автоматизированным. Однако широкое разнообразие технологий делает построение "всеобъемлющей" системы проблематичным.

1.2. ЦЕЛЬЮ РАБОТЫ является вццеление класса актуальных ГГГК и построение его обобщенной математической модели, рентабельно реализуемой и позволяющей формировать автоматизирований модели конкретных ПТК: автоматизирований модифицируемые по мере эксплуатации; с автоматизированной постановкой задания; на этапе трансляции задания, не в реальном времени - с автоматической оптимизацией исполнительной программы, включая оптимальную обработку возмущений.

1.3. МЕТОДЫ ИССЛЕДОВАНИЯ основаны на использовании теорий формальных грамматик, сетей Петри, графов, математической логики.

1.4. НАУЧНАЯ НОВИЗНА.

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

1.4.2. Для описания грамматик модели разработаны две "расширенные нормальные формы Бэкуса", позволяющие задавать сетевые ограничения на порядок вывода и моделировать возмущения. Доказаны теоремы о свойствах грамматик и их соотношении с КС-грамматикой.

1.4.3. Разработаны макетные нотации модели и задания и реализована макетная система программирования МАПТО.

1.4.4. Разработан, исследован и программно реализован алгоритм эвристической оценки сложности метода динамического программирования при построении оптимальной цепочки на сети достижения.

1.5. ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Разработанная модель может быть использована в произвольной технологической области выбранного класса. Макетная система может быть использована при создании производственных систем программирования станков с ЧПУ и манипу-ляционных роботов. Алгоритм эвристической оценки и его реализация могут быть использованы при работе с сетями достижения.

1.6. АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертационной работы докладывались: на научно-технической конференции "Комплексно-автоматизированные производства и их компоненты", Санкт-Петербург, октябрь 1990; на семинаре лаборатории специализированных микропроцессорных систем и сетей СПИИРАН, ноябрь 1991.

1.7. ПУБЛИКАЦИИ. По материалам диссертации опубликовано 5 научных работ.

1.8. СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертационная работа состоит из: введения, четырех глав (93 страницы машинописного текста), приложений на 49 страницах, списка литературы (73 наименования), II рисунков, 4 таблиц.

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

Во ВВЕДЕНИИ дано определение МАПТО и ПТК, описана структура системы управления МАПТО и подходы к ее построению.

ОПРЕДЕЛЕНИЕ. "Проблемный технологический комплекс" (ПТК) -комплекс технологического оборудования для исполнения технологических процессов проблемной области. "Манипуляционное адаптивное программируемое технологическое обрудование" (МАПТО) - автоматическая машина с перепрог'раммируемьгм устройством программного управления, с манипуляторами для оснащения инструментами и с набором каналов для подключения сенсоров и инструментов.

2.1. В ПЕРВОЙ ГЛАВЕ сформулирована цель работы.

Проанализированы недостатки существующих подходов к программированию МАПТО: языки последовательного управления не позволяют автоматически оптимизировать исполнительную программу; процедур-ность языков формулирует задание в форме "как сделать", а не "что получить"; "универсальные" языки оперируют в терминах команд непосредственного управления МАПТО, перенасыщая задание нетехнологическими данными; системы проблемного программирования не могут достаточно оперативно перестраиваться на другие ПТК.

Система программирования МАПТО, автоматически настраивающаяся на ПТК, должна автоматически: строить формальную модель ПТК; принимать задание в терминах модели; формировать подцели задания и

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

Сформулирована ЦЕЛЬ РАБОТЫ: вьщеление класса актуальных технологических областей и построение обобщенной модели 1ГГК, позво-лянцей формировать модели конкретных ГГГК: с проблемной постановкой задания; модифицируемые по мере эксплуатации; не в реальном времени, при трансляции задания - с автоматическим построением технологически оптимальной исполнительной программы, включая оптимальную обработку возцущений.

ПОСТУЛАТ I (актуальный класс ПТК).

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

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

ОПРЕДЕЛЕНИЕ. "Сеть достижения" - конечный простой ориентированный ациклический граф где V- вершины, понимаемые как "исполняемые узлы", - дуги локальных ограничений: узел можно исполнять, только если исполнены все узлы, из которых в данный ведут дуги.

Рассмотрены существующие виды технологической оптимизации

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

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

2.2. Во ВТОРОЙ ГЛАВЕ даются обобщения нормальной формы Бэкуса (НФБ), исследуются ее свойства и строится модель ПТК.

ОПРЕДЕЛЕНИЕ (специальный случай КС-грамматики).

1) КС-грамматика - "левосторонне структурированная", если ее правила имеют вид:

А = В1 ... В2 или

А *= В1 I В1 В2 I .... I В1...В1 В2 или

А = В1 А I В2, при этом А не выводится из В1,...,В2.

2) КС-грамматика - "правосторонне структурированная", если ее правила имеют вид:

А = В1 . В2 или

А = В1 I В1 В2 I ... Г В1 В2...В2 или

А = А В1 I В2, при этом А не выводится из В1,...,В2.

3) Левосторонне или правосторонне структурированная КС-грамма-

тика называется "односторонне структурированной".

ОПРЕДЕЛЕНИЕ (первое обобщение НФБ). "Первой расширенной НФБ" (1№ФБ) называется представление правила в виде

А = ВИЙ5Й... шйцк],

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

ОПРЕДЕЛЕНИЕ. "Иерархическая грамматика" (И-грамматика)- это приведенная ациклическая грамматика с IРНФБ-правилами.

Теорема I. Класс И-грамматик совпадает с классом односторонне структурированных приведенных КС-грамматик.

Следствие. Классы левосторонне и правосторонне структурированных КС-грамматик совпадает.

Модель ПТК строится как грамматика "обобщенных" правил вывода (при этом "выводимым" считается символ в левой части правила, а "выводящими" - символы в правой части) на множестве "проблемных типов объектов". Правила реализуются "проблемными действиями" и делятся на "технологические" (действие использует исполнительные органы ПТК) и "логические" (вычислительное действие). Терминальные типы моделируют константы задания. Нетерминальные разбиты на "технологические" (обрабатываемые объекты) и "исполняющие" (по числу исполнительных органов ПТК). Технологические возмущения воздействуют на правила и по способу учета разбиты на два класса. "Стратегическое": если вызвано незнанием реального состояния выводящего объекта и это состояние может быть определенодо исполнения правила, грамматика должна содержать "пред-правила установочной адаптации к объекту"; если реальное состояние выводящего объекта целесообразно определять при исполнении правила, правило содержит дополнительные выводящие типы - параметры "текущей адаптации к объекту"; если возмущение неустранимо данными способами,

грамматика содержит "пост-правила обработки сбойного объекта". "Фатальное": в грамматике нет правил обработки.

ПОСТУЛАТ 2 (источники технологических возмущений).

Возмущения имеют три источника возникновения: недопустимая терминальная константа, неизвестное/недопустимое значение объекта технологического типа, неизвестное/недопустимое значение объекта исполняющего типа.-

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

Для моделирования качества объектов типы разбиты на "подтипы".

ОПРЕДЕЛЕНИЕ. "Разбиение типа i. на подтипы" - это пятерка

{i,m), su), р(о,ш(,

где:

H(i)~ конечное множество "характеристик" объектов типа i

S(i) - конечное множество "состояний характеристик" из

P(i)= {/>£ : L= i . И ^ - конечное множество предикатов на

sah

Ш={Ш,Ш, ...Ad) I - конечное множество "подтипов": £(?) - объект еще не выведен и все рг- пока истинны ("неопределенный" подтип)*, ¿(0) - объект выведен и все р; истинны ("качественный" подтип)! ¿(0 (£=1...И) - объект еще не выведен, но p¿ уже ложен ("сбойный" подтип).

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

Частные случаи разбиения на подтипы:

£ - терминальный тип. Н(^) содержит одну характеристику. $(i) - множество значений объектов. P(.i) содержит один предикат - "допустимость значения объекта". Объект может иметь подтипы:¿(?) -значение неизвестно, -£(0) - значение допустимо, ¿(1) - значение

недопустимо.

■£ - нетерминальный тип, выводимый логическим правилом. Согласно постулату 2, возмущения не действуют. Ц{Ь) и5Ш пусты. Все объекты имеют подтип ¿(0).

- нетерминальный, тип, выводимый технологическим правилом. и5(^) не пусты. Объект может быть одного из нескольких под-типов:/(0),£(?),...

ОПРЕДЕЛЕНИЕ (второе обобщение НФБ). Пусть Е1 и Е2 - конечные множества соответственно "технологических" и "исполняющих" типов, разбитых на подтипы. "2РНФБ-правилом" называется запись (I)

Ш — т)№о...т{) ...ДП(о...тп) = г.лВИ*) [¿Ш ъ.л ВкШ1Ш I,. I Дф).. ДпШ

где:

А, В1.~Вк - конечное непустое множество типов из Е1; Д1...ДЛ - конечное (возможно, пустое) множество типов из Е2;

символы "ъ" означают "служебные скобки" и могут принимать парно сбалансированные значения {...}, или "пусто" (отсутствие скобок);

запись получаемая из (I) удале-

нием скобок, исполняющих типов и номеров подтипов, есть ШФБ-правило и называется "идеализацией 2ГОФБ-правила";

запись (I) понимается как правило, требующее выводящие подтипы ,Дц^п)к выводящее любой из

"вариантов

А(о)АЦо)..,Ап(0)>а(т)Д1(т1)...Да(тц).

Примеры 2РНФБ-правил из модели РТК электродуговой сварки:

изделие(О) = [исходная.точка(0)[1:^ <шов(0)[1:*])>

конечная.точка(0)[1:1

шов(0,1,2) манипулятор(0,1,2) горелка(ОД) =

{ начальная.точка(0)£1:1] участок(0)[1:/] ^

манипулятор(О) горелка(О) ток(0,1) = ток(?)[1:1]

ОПРЕДЕЛЕНИЕ. "Вариативная иерархическая грамматика" (ВИ-грамма-тика) с начальным типом "н" - это четверка Г(н) = {н, в, BI, В2]

где:

н - начальный тип, разбитый на подтипы: н(?) ,н(0),... ,н(т),' в - 2РНФБ-правило вывода типа "н": н(0,...,т) и1(0,...ml)...ик(0,...,тп) = •ь..ът1(0) р1у1]т,..ъ rk(0)pk:jk] ъ..ъ и1(0)...ня(0)', BI = £г(т1). ,Г(т(:) I - ВИ-грамматика с начальными типами соответственно т1,...,тк',

В2 = {{ГГ( Н(с) ): £ -I... т] ,

{гг(и1(0 ): i=l...miif... , (гт(ииМ):

"вспомогательные" ВИ-грамматики (возможно, пустые), обрабатывающие сбойные подтипы типов Н и и1...иП: обрабатываемый подтип является терминальным для вспомогательной грамматики.

Дополнительно накладывается условие,: приведенная грамматика идеализаций правил ("идеализация ВИ-грамматикиг) есть И-грамматика. Теорема 2 (свойства ВИ-грамматики)

Для всякого типа приведенная грамматика его выводящих правил также есть ВИ-грамматика. Сбойный подтип - нефатальный, только если его вспомогательная грамматика не пуста. Нефатальный подтип -циклический. Обработка нефатального подтипа локализуется в соответствующей вспомогательной ВИ-грамматике и возврат в основную ВИ-грамматику возможен только после успешной обработки подтипа. ОПРЕДЕЛЕНИЕ "Моделью ПТК" называется тройка М = { Г(н), Д, Ф }

где:

Г(н) - ВИ-грамматика с начальным технологическим типом "н" (ее правила называются "обобщенными");

Д = | ТД, лд I - конечное множество "реализующих действий":

"технологические" (ТД) и "логическое" (лд);

Ф - однозначное отображение технологических правил грамматики в ТД, логических - в лд (сопоставление правил и действий).

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

ОПРЕДЕЛЕНИЕ. "Конкретизированное правило" - это НФБ-правило, получаемое следующим преобразованием обобщенного правила: выводимый тип заменен на объект этого типа; диапазоны выводящих типов заменены на допустимые количества объектов этих типов; выдержано соотве^твие скобкам обобщенного правила: если использовались пустые скобки, порядок записи соответствующих выводящих объектов определяет порядок их вывода; если использовались скобки на множестве соответствующих выводящих объектов дополнительно задана сеть достижения (возможно, пустая); если использовались скобки

порядок вывода соответствующих выводящих объектов произволен.

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

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

ОПРЕДЕЛЕНИЕ. "Заданием для ПТК" называется четверка 3 = {нк, ВКО, ВК1, С}

где:

нк - объект начального типа;

ВКО - дерево конкретизированных правил, выводящее нк;

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

С: объединение(ВКО,ВК1)#—К - функция технологических затрат исполнения последовательностей конкретизированных правил (символ означает операцию построения' всех допустимых последовательностей правил, К - множество вещественных чисел).

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

Задание изоморфно сети Петри с метками и ругами, раскрашенными подтипами объектов. Переходы моделируют конкретизированные правила, места - подтипы выводимых объектов. Сеть структурирована: основой является ациклический синхроАф, изоморфный сети достаже-ни^конкретизированных правил вывода подтипа 0 начального объекта из объекгов подтипов 0 (вывод без возмущений) - как объединение дерева ВКО и всех сетей достижения внутри правил дерева ВКО; для всякого нефатального подтипа всякого объекта существует подсеть обработки; всякий фатальный подтип всякого объекта входит в специальный переход "аварийное завершение работы сети"; места исполняющих объектов - циклические: дуга из места выходит в правило, в котором объект участвует, и возвращае.тся из правила в это место.

Для получения оптимальной программы необходимо при трансляции

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

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

2.3. В ТРЕТЬЕЙ ГЛАВЕ разработан и исследован алгоритм эвристической оценки сложности метода динамического программирования при построении оптимальной цепочки на сети достижения (Т- общее количество анализируемых цепочек), т.к. стандартная оценка

Тстандартное = У1• (И-(У1~1) •2 /г'г) , где и- количество узлов сети, излишне завышена при непустой сети.

Для оценки значения.Т сеть индуктивно разложена на уровни: я уровню С отнесены все узлы, становящиеся разрешенными после исполнения всех узлов предццущих уровней. Введены усредненные параметры сети: Л. - общее количество узлов; к - количество уровней;

- количество узлов по уровням 1...к); ~ "¡-'ощ-

• • » »

ность" уровня относительно уровня (ЩмJ^<Jз )' количество

дуг из уровня ji в уровень приведенное к ¿^ , - "ключ"

уровня д : количество дуг, входящих в уровень ^ , приведенное к

£. . Значение Т ищется как суша количеств цепочек, анализиру-«/

емых по шагам метода динамического программирования: п.

(I)

Значения Т^* (' =1.. .П) вычисляются рекуррентно. Множество построенных на шаге £ цепочек разбивается на классы, нумеруемые мультииндексами вида тт= т*)} ), где /- номер шага,

^ - номер уровня последнего узла в цепочке, количество узлов уровня Б в цепочке (5=1...К),/тт/= С - количество узлов в цепочке. Пусть Т(ют.)- количество всех построенных цепочек класса тт, а 1{(тгп)- количество перспективных в них. Имеем:

|гтл) хи

Полагается, что для каждого класса выполнено соотношение

И)

т.е. расширение цепочки на уровень 5 было возможно, только если она имела достаточное количество узлов уровней 1...3-1. Класс \Пт породит множество классов

тт' = ( Щ

по всем уровням 5, для которых выуполнено строгое неравенство в (4). Количество цепочек класса ттпри расширении класса тт есть:

Т Т( мт —> тт') -

Перспективной в среднем будет одна из цепочек:

И и (мт-*мт') = ТТ(мт ')/т^

Цепочки класса тт'могут также получиться при расширении цепочек другого классатт\с уровня, отличного от 5). Поэтому

Т(тт')= ¿Е* Т7(мм->мт') (7)

и (шг') ТТ(тм _тп^ (8)

Алгоритм расчета значения Т выглядит следующим образом: Шаг I. Начальное состояние расчета: иш = (1:1,0,... ,0:1),

тI = 1Л1 = е1 , / = 2.

Шаг ¿. По всем классам • /г)//^, полученным на шаге нахожде-

ние всех расширений тт-*пт' всех порождений классов кя'и всех значений ТТ()и/и-»я"«ф Т(*/«),Т,; (формулы 2,4,5,7), Штт')и

(формулы 3,6,8). Наращивание шага1=£+1. Если ¿£П, возврат на *

"Шаг £". Иначе нахождение Т по формуле (I). Конец алгоритма.

Алгоритм дает точное значение Т в двух крайних случаях: сеть пустая (Т=Тстандартное) или строго линейная (Т=Й). Алгоритм реализован программно (ПЭВМ РСДТ/АТ, язык Турбо-Паскаль) и его

результаты достаточно хорошо согласуются с реальной сложностью метода: в большинстве случаев погрешность не превышает 100д-20С$. Приведены сводные результаты тестирования алгоритма на 1200 случайных сетях при п=1...14. Оценена сложность алгоритма:(К - общее количество анализируемых классов):

к < е ^ ¿,45 •

где е - основание натуральных логарифмов. Т.к. основание экспоненты невелико (1.45), при практических значениях /2, -когда сам метод работает приемлемое время, алгоритм работает достаточно быстро: в среднем в 3-4 раза быстрее метода.

2.4. В ЧЕТВЕРТОЙ ГЛАВЕ разработаны макетные нотации модели и задания. Задание основано на ЛИСП-нотации и ближе к форме "что получить", чем к "как сделать". Описан макетный пакет программ, реализующий трехуровневую систему программирования МАПТО: уровень 3 - формирование/корректировка модели (текстовый редактор), верификация модели (модуль

VERIFY), уровень 2 - формирование/коректи-ровка задания (текстовый редактор), уровень I - трансляция задания в программу на языке Паскаль, дополненном конструкциями контроля и обработки возмущений (модуль TRANbL), Пакет работает на ПЭВМ РСДТ/АТ, написан на языке Паскаль и проверен на контрольной модели одноманипуляторного FTK электродуговой сварки.

2.5. В ПРИЛОЖЕНИЯХ I...6 приведены тексты контрольной модели и результаты работы макетной системы программирования.

3. ОБЩИЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ.

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

МАПТО. Получены следующие основные результаты:

3.1. Введено понятие МАПТО и ПТК как обобщение понятий "станок с ЧПУ", "манипуляционный робот" и РГК. Проанализированы недостатки существующих подходов к программированию МАПТО и ПТК, сдеркиваицие применение МАПТО. Вьщелен класс актуальных ПТК.

3.2. Модель ПТК построена на основе аппарата формальных грамматик. Формируемые на ее основе модели конкретных ПТК позволяют: модификацию по мере эксплуатации, проблемную постановку задания, при трансляции задания - автоматическую оптимизацию исполнительной программы по выбранному технологическому критерию, включая оптимальную обработку технологических возцущений.

3.3. Для описания грамматики модели разработаны две "расширенные нормальные формы Бэкуса", позволяющие учитывать технологические особенности вывода. Доказаны теоремы о свойствах грамматик и их соотношении с КС-грамматиками.

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

•3.5. Создана макетная реализация системы программирования МАПТО, которая может быть использована при создании производственных систем программирования станков с ЧПУ и роботов.

3.6. Разработан и исследован алгоритм эвристической оценки сложности метода динамического программирования при построении оптимальной цепочки на сети достижения. Алгоритмреализован программно.

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

I. А.Ю.Каргашин, А.И.Кинунен, В.З.Шестопалов. Математическое и программное обеспечение робототехнического комплекса точечной контактной сварки. - М: Препринт ИПМ им. М.В.Келдыша АН СССР,1986

- 1У -

2. А.И.Кинунен. Метод установочной адаптации сварочного промышленного робота с помощью трех опорных точек на изделии. -Л: Препринт ЛИИАН СССР 91, 1989

3. А.И.Кинунен. Язык обучения сварочного промышленного робота. - Л: Препринт ЛИИАН СССР 92, 1989

4. А.И.Кинунен. Архитектура задачно-ориентированной системы программирования сварочного промышленного робота. - Л: Препринт ЛИИАН СССР 103, 1989

5. А.И.Кинунен. Многопользовательская система управления автоматическим складским комплексом. Тезисы доклада. - "Комплексно-автоматизированные производства и их компоненты". Материалы научно-практической конференции 23-24 октября 1990 г. -Л: ЛДНТП, 1991