Захватные устройства

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

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

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

17. Коэффициент мехатронности и критерий совершенства мехатронной системы.

18. Проектирование следящих приводов роботов: краткая характеристика основных этапов.

19. Проектирование манипуляторов: основные этапы: краткая характеристика основных этапов.

20. Нейросетевое распознавание. Сеть Хопфилда. Сеть Хэмминга. Классификатор Гроссберга.

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

Структурная схема сети Хопфилда приведена на Рис. 6. Она состоит из единственного слоя нейронов, число которых является одновременно числом входов и выходов сети. Каждый нейрон связан синапсами со всеми остальными нейронами, а также имеет один входной синапс, через который осуществляется ввод сигнала. Выходные сигналы, как обычно, образуются на аксонах.

Рис. 6. Структурная схема сети Хопфилда.

Задача, решаемая данной сетью в качестве ассоциативной памяти, как правило, формулируется следующим образом. Известен некоторый набор двоичных сигналов (изображений, звуковых оцифровок, прочих данных, описывающих некие объекты или характеристики процессов), которые считаются образцовыми. Сеть должна уметь из произвольного неидеального сигнала, поданного на ее вход, выделить ("вспомнить" по частичной информации) соответствующий образец (если такой есть) или "дать заключение" о том, что входные данные не соответствуют ни одному из образцов. В общем случае, любой сигнал может быть описан вектором X = { x_i: i=0...n-1}, n – число нейронов в сети и размерность входных и выходных векторов. Каждый элемент x_i равен либо +1, либо -1. Обозначим вектор, описывающий k-ый образец, через X^k, а его компоненты, соответственно, – x_i^k, k=0...m-1, m – число образцов. Когда сеть распознáет (или "вспомнит") какой-либо образец на основе предъявленных ей данных, ее выходы будут содержать именно его, то есть Y = X^k, где Y – вектор выходных значений сети: Y = { y_i: i=0,...n-1}. В противном случае, выходной вектор не совпадет ни с одним образцовым.

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

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

(1)

Здесь i и j – индексы, соответственно, предсинаптического и постсинаптического нейронов; x_i^k, x_j^k – i-ый и j-ый элементы вектора k-ого образца.

Алгоритм функционирования сети следующий (p – номер итерации):

1. На входы сети подается неизвестный сигнал. Фактически его ввод осуществляется непо­сред­ственной установкой значений аксонов:

y_i(0) = x_i , i = 0...n-1, (2)

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

2. Рассчитывается новое состояние нейронов

, j=0...n-1 (3)

и новые значения аксонов

(4)

Рис. 7. Активационные функции.

где f – активационная функция в виде скачка, приве­денная на Рис. 7а.

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

Как говорилось выше, иногда сеть не может провести распознавание и выдает на выходе несуществующий образ. Это связано с проблемой ограниченности возможностей сети. Для сети Хопфилда число запоминаемых образов m не должно превышать величины, примерно равной 0.15•n. Кроме того, если два образа А и Б сильно похожи, они, возможно, будут вызывать у сети перекрестные ассоциации, то есть предъявление на входы сети вектора А приведет к появлению на ее выходах вектора Б и наоборот.

Рис. 8. Структурная схема сети Хэмминга.

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

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

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

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

, i=0...n-1, k=0...m-1 (5)

T_k = n / 2, k = 0...m-1 (6)

Здесь x_i^k – i-ый элемент k-ого образца.

Весовые коэффициенты тормозящих синапсов во втором слое берут равными некоторой величине 0 < e < 1/m. Синапс нейрона, связанный с его же аксоном имеет вес +1.

Алгоритм функционирования сети Хэмминга следующий:

1. На входы сети подается неизвестный вектор X = {x_i:i=0...n-1}, исходя из которого рассчитываются состояния нейронов первого слоя (верхний индекс в скобках указывает номер слоя):

, j=0...m-1 (7)

После этого полученными значениями инициализируются значения аксонов второго слоя:

y_j⁽²⁾ = y_j⁽¹⁾, j = 0...m-1 (8)

2. Вычислить новые состояния нейронов второго слоя:

(9)

и значения их аксонов:

(10)

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

3. Проверить, изменились ли выходы нейронов второго слоя за последнюю итерацию. Если да – перейди к шагу 2. Иначе – конец.

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

21. Сети на основе радиально-базисных функций. Обучение без учителя в нейросетевом распознавании образов.

Сеть радиально-базисных функций — искусственная нейронная сеть, которая использует радиальные базисные функции как функции активации.

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

Впервые сформулированы в 1988 Брумхедом и Лоу.

22. Самоорганизующаяся сеть Кохонена. Нейроэволюционное распознавания образов.

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

В [10] трёхмерная СКК (по 5 узлов на каждое измерение) применялась для уменьшения размерности локальных участков изображения 5х5 (размерность 25). Входное изображение отображается на один из 125 узлов, положение которого в трёхмерной решётке кодирует вектор выходного пространства. Три измерения СКК принимаются за три ключевых характеристики (features [10]). Такое преобразование обеспечило частичную устойчивость к изменению освещения, смещениям и искажениям, избавило от необходимости предварительной обработки изображения (преимущество – ускорение работы), а так же значительно ускорило процесс обучения и классификации, делая эту систему применимой в реальном времени (использовалась для распознавания лиц). Отмечено так же небольшое преимущество СКК перед методом анализа главных компонент, которое заключалось в более высокой точности последующей классификации на основе данных уменьшенной размерности.

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

В [9] применялись две различные архитектуры НСРБФ для распознавания лиц. На вход сети поступали предварительно извлечённые характеристики, полученные методом анализа главных компонент или коэффициенты вэйвлетных преобразований. В первой архитектуре количество выходов соответствовало количеству классов, во второй применялся коллектив сетей, каждая из которых была обучена распознавать только свой класс. Отмечены значительные преимущества классификации НСРБФ перед непосредственным сравнением ключевых характеристик.

В [15] применялись две различные архитектуры ансамблей НСРБФ для предварительной классификации изображений. На вход сети поступало изображение целиком, на выходах формировалась промежуточная классификация, которая затем подавалась на решающие деревья для контекстно-ориентированного распознавания изображений лиц (например: “найти все изображения определённого человека, где он в очках”). Различные сети в ансамблях первой архитектуры учились классифицировать изображения с различными типами изменений, второй – с одинаковыми, но количество нейронов менялось в процессе обучения. Решающий вывод делал “судья”, который принимал решение на основе голосования ансамбля сетей.

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

1. Конечно-автоматные графы. Определение, формализованная запись. Их использование для математического описания логических процессов.

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

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

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

· — множество состояний;

· — начальное состояние ;

· — множество заключительных состояний ;

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

Конечный автомат начинает работу в состоянии q₀, считывая по одному символу входной цепочки. Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Читая входную цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил цепочку x.

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

Содержание

[убрать]

· 1 Другие способы описания

· 2 Детерминированность

· 3 Автоматы и регулярные языки

· 4 Специализированные языки программирования

· 5 Разработка моделей с использованием конечных автоматов

· 6 Примечания

· 7 См. также

· 8 Литература

· 9 Ссылки

Другие способы описания[править | править вики-текст]

1. Диаграмма состояний ( или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой размеченный ориентированный граф, вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а метки дуг — символы, по которым осуществляется переход из одного состояния в другое. Если переход из состояния q₁ в q₂ может быть осуществлен по одному из нескольких символов, то все они должны быть надписаны над дугой диаграммы.

2. Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается состояние, в которое должен перейти автомат, если в данном состоянии он считал данный входной символ.

Детерминированность[править | править вики-текст]

Конечные автоматы подразделяются на детерминированные и недетерминированные.

Детерминированный конечный автомат

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

· Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Существуют переходы, помеченные пустой цепочкой ε	Из одного состояния выходит несколько переходов, помеченных одним и тем же символом

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

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

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

Автоматы и регулярные языки[править | править вики-текст]

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

Теорема Клини утверждает, что язык является регулярным тогда и только тогда, когда он допускается некоторым конечным автоматом, используемым в этом языке.

Специализированные языки программирования[править | править вики-текст]

· Язык последовательных функциональных схем SFC (Sequential Function Chart) — графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).

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

Разработка моделей с использованием конечных автоматов[править | править вики-текст]

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

1. Сети Петри. Определение, формализованная запись. Их использование для математического описания логических процессов.

Сети Петри

[править | править вики-текст]

Материал из Википедии — свободной энциклопедии

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Сети Петри — математический аппарат длямоделированиядинамических дискретных систем. Впервые описаныКарлом Петри в 1962 году.

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

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

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

Содержание

[убрать]

· 1 История

· 2 Динамика сети Петри

· 3 Виды сетей Петри

· 4 Анализ сетей Петри

· 5 Универсальная сеть Петри

· 6 Бесконечные сети Петри

· 7 См. также

· 8 Примечания

· 9 Литература

· 10 Ссылки

История[править | править вики-текст]

Сети Петри разрабатывались для моделирования систем с параллельными взаимодействующими компонентами. Сети Петри впервые предложил Карл Адам Петри. В докторской диссертации «Связь автоматов» он сформулировал основные понятия теории связи асинхронных компонент вычислительной системы^[1].

Динамика сети Петри[править | править вики-текст]

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

Виды сетей Петри[править | править вики-текст]

Некоторые виды сетей Петри:

· Временна́я сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку).

· Стохастическая сеть Петри — задержки являются случайными величинами.

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

· Цветная сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.

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

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

· WF-сети

Анализ сетей Петри[править | править вики-текст]

Основными свойствами сети Петри являются:

Пример траектории в сети Петри.

· ограниченность — число меток в любой позиции сети не может превысить некоторого значения K;

· безопасность — частный случай ограниченности, K=1;

· сохраняемость — постоянство загрузки ресурсов, постоянна. Где — число маркеров в i-той позиции, — весовой коэффициент;

· достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое;

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

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

Универсальная сеть Петри[править | править вики-текст]

В 1974 году Тилак Аджервала показал, что ингибиторная сеть Петри является универсальной алгоритмической системой. В монографии Котова В. Е. приведен набросок доказательства, указывающий правила кодирования ингибиторной сетью программы счетчикового автомата Минского. Питерсон Дж. приводит примеры других расширенных классов сетей Петри, являющихся универсальной алгоритмической системой: синхронных и приоритетных. Построенная в явном виде универсальная сеть Петри^[3] насчитывала несколько тысяч вершин и недавно была уменьшена до 56 вершин^[4].

Бесконечные сети Петри[править | править вики-текст]

Бесконечные сети Петри были введены для верификации вычислительных решеток и позволяют определять свойства сетей Петри для регулярных структур (линейная, древовидная, квадратная, треугольная, шестиугольная и гиперкуб^[5]) произвольного размера, полученных путем композиции типовых фрагментов.

1. Понятие о правильных сетях Петри. Понятие о дереве достижимых маркировок.

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

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

4.4.1. Свойства сетей Петри.

Позиция pÎP сети Петри N=(P,Т,I,O) c начальной маркировкой m является k-ограниченной, если m’(p)£k для любой достижимой маркировки m’ÎR(N,m). Позиция называется ограниченной, если она является k-ограниченной для некоторого целого значения k. Сеть Петри ограниченна, если все ее позиции ограниченны.

Позиция pÎP сети Петри N=(P,Т,I,O) c начальной маркировкой m является безопасной, если она является 1 - ограниченной.Сеть Петри безопасна, если безопасны все позиции сети.

Сеть Петри N=(P,Т,I,O) с начальной маркировкой m является сохраняющей, если для любой достижимой маркировки m’ÎR(N,m) справедливо следующее равенство.

m’(p).

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

Уровень 0: Переход t обладает активностью уровня 0 и называется мёртвым, если он никогда не может быть запущен.

Уровень 1: Переход t обладает активностью уровня 1 и называется потенциально живым, если существует такаяm’ÎR(N,m), что t разрешён в m’.

Уровень 2: Переход t, обладает активностью уровня 2 и называется живым, если для всякой m’ÎR(N,m) переход t является потенциально живым для сети Петри N с начальной маркировкой m’.

Сеть Петри называется живой, если все её переходы являются живыми.

Задача достижимости: Для данной сети Петри с маркировкойm и маркировки m’ определить: m’ÎR(N,m)?

Задача покрываемости: Для данной сети Петри N с начальной маркировкой m и маркировки m’ определить, существует ли такая достижимая маркировка m”ÎR(N,m), что m">³m’.

(Отношение m"³m’ истинно, если каждый элемент маркировки m" не меньше соответствующего элемента маркировки m’.)

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

Сеть Петри N=(P,Т,I,O) с начальной маркировкой m и сеть Петри N’=(P’,Т’,I’,O’) с начальной маркировкой m’ эквивалентны, если справедливо R(N,m)=R(N’,m’).

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

Более слабым, по сравнению с эквивалентностью, является свойство включения, определение которого совпадает с определением эквивалентности, с точностью до замены = на Í.

4.4.2. Методы анализа.

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

4.4.2.1. Дерево достижимости.

Дерево достижимости представляет все достижимые маркировки сети Петри, а также – все возможные последовательности запусков ее переходов.

Пример 4.4. Частичное дерево достижимости маркированной сети Петри изображено на рисунке 4.10, а, а частичное дерево достижимости для трёх шагов построения имеет вид (рисунок 4.10, б).

Рисунок 4.10 а б

Для сети Петри с бесконечным множеством достижимых маркировок дерево достижимости является бесконечным. Сеть Петри с конечным множеством достижимых маркировок также может иметь бесконечное дерево достижимости (см. пример 4.4). Для превращения бесконечного дерева в полезный инструмент анализа строится его конечное представление. При построении конечного дерева достижимости для обозначения бесконечного множества значений маркировки позиции используется символ w. Также используются следующие ниже операции надw, определяемые для любого постоянного a.

w -- а = w; w + а = w; а < w; w £ w.

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

1. Если в дереве имеется другая вершина y, не являющаяся граничной, и с ней связана та же маркировка, m[x]=m[y], то вершина х становится дублирующей.

2. Если для маркировки m[х] ни один из переходов не разрешен, то x становится терминальной.

3. В противном случае, для всякого перехода tÎT, разрешенного в m[х], создаётся новая вершина z дерева достижимости. Маркировка m[ z ], связанная с этой вершиной, определяется для каждой позиции pÎP следующим образом:

3.1. Если m[х](p)=w, то m[z](p)=w.

3.2. Если на пути от корневой вершины к x существует вершина y с m[y]<m’ (где m’ – маркировка, непосредственно достижимая из m[ х ] посредством запуска перехода t) и m[ y ](p)<m’(p), то m[ z ](p)=w. (В этом случае последовательность запусков переходов, ведущая из маркировки m[ y ] в маркировку m’, может неограниченно повторяться и неограниченно увеличивать значение маркировки в позиции p.) В противном случае m[z](p)=m’(p).

4. Строится дуга с пометкой t, направленная от вершины x к вершине z. Вершина х становится внутренней, а вершина z – граничной.

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

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

Пример 4.5. Конечное дерево достижимости сети Петри.

Сеть Петри:

Конечное дерево достижимости:

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

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

Доказательство. Пусть x ₀ корневая вершина. Поскольку имеется только конечное число непосредственно следующих за x ₀ вершин, но общее число вершин в дереве бесконечно, по крайней мере, одна из непосредственно следующих за x ₀ вершин должна быть корнем бесконечного поддерева. Выберем вершину x ₁непосредственно следующую за x ₀ и являющуюся корнем бесконечного поддерева. Теперь одна из непосредственно следующих за ней вершин также является корнем бесконечного поддерева, выберем в качестве такой вершины x ₂. Если продолжать этот процесс бесконечно, то получим бесконечный путь в дереве – x ₀, x ₁, x ₂,…, x _n,….

Лемма 4.2. Всякая бесконечная последовательность неотрицательных целых содержит бесконечную неубывающую последовательность.

Доказательство. Возможны два случая:

1. Если какой-либо элемент последовательности встречается бесконечно часто, то пусть x ₀ является таким элементом. Тогда бесконечная подпоследовательность x ₀, x ₀,…, x ₀,… является бесконечной неубывающей подпоследовательностью.

2. Если никакой элемент не встречается бесконечно часто, тогда каждый элемент встречается только конечное число раз. Пусть x ₀ — произвольный элемент последовательности. Существует самое большее x ₀ целых, неотрицательных и меньших, чем x ₀ (0,..., x ₀ - 1), причем каждый из них присутствует в последовательности только конечное число раз. Следовательно, продвигаясь достаточно долго по последовательности, мы должны встретить элемент x ₁, x ₁ ³ x ₀. Аналогично должен существовать в последовательности x ₂, x ₂ ³ x ₁, и т. д. Это определяет бесконечную неубывающую последовательность x ₀, x ₁, x ₂,…, x _n,….

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

Лемма 4.3. Всякая бесконечная последовательность n-векторов над расширенными символом w неотрицательными целыми содержит бесконечную неубывающую подпоследовательность.

Доказательство. Доказываем индукцией по n, где n — размерность векторного пространства.

1. Базовый случай (n=1). Если в последовательности имеется бесконечное число векторов вида <w>, то они образуют бесконечную неубывающую последовательность (так как справедливо w £ w). В противном случае бесконечная последовательность, образованная удалением конечного числа экземпляров <w>, имеет по лемме 4.2 бесконечную неубывающую подпоследовательность.

2. Индуктивное предположение. (Допустим, что лемма верна для n докажем её справедливость для n+1.) Рассмотрим первую координату. Если существует бесконечно много векторов, имеющих. в качестве первой координаты w, тогда выберем эту бесконечную подпоследовательность, которая не убывает (постоянна) по первой координате. Если только конечное число векторов имеют w в качестве первой координаты, то рассмотрим бесконечную последовательность целых, являющихся значениями первых координат. По лемме 4.2 эта последовательность имеет бесконечную неубывающую подпоследовательность. Она определяет бесконечную Последовательность векторов, которые не убывают по своей первой координате.

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

Докажем следующую теорему.

Теорема 4.1. Дерево достижимости сети Петри конечно.

Доказательство. Докажем методом от противного. Допустим, что дерево достижимости бесконечно. Тогда по лемме 4.1 (и так как число вершин, следующих за каждой вершиной в дереве, ограничено числом переходов m) в нём имеется бесконечный путь x ₀, x ₁, x ₂,…, исходящий из корня x ₀. Тогда m[ x ₀], m[ x ₁], m[ x ₂],… — бесконечная последовательность n-векторов. над NatÈ{w}, а по лемме 4.3 она имеет бесконечную неубывающую подпоследовательность m[ x _k0]£m[ x _k1]£m[ x _k2]£…... Но по построению дерева достижимости m[ x _i]¹m[ x _j] (для i¹j), поскольку тогда одна из вершин была бы дублирующей и не имела следующих за собой вершин. Следовательно, это бесконечная строго возрастающая последовательность m[ x _k0]<m[ x _k1]<m[ x _k2]…... Но по построению, так как m[ x _i]<m[ x _j] нам следовало бы заменить по крайней мере одну компоненту m[ x _j], не являющуюся w, на w в m[ x _j]. Таким образом, m[ x _k1] имеет по крайней мере одну компоненту, являющуюся w, m[ x _k2] имеет по крайней мере две w-компоненты, а m[ x _kn] имеет по крайней мере n w-компонент. Поскольку маркировки n-мерные, m[ x _kn] имеет во всех компонентах w. Но тогда у m[ x _kn+1] не может быть больше m[ x _kn]. Пришли к противоречию, что доказывает теорему.

4.4.2.2. Анализ свойств сетей Петри на основе дерева достижимости.

Анализ безопасности и ограниченности. Сеть Петри ограниченна тогда и только тогда, когда символ w отсутствует в ее дереве достижимости.

Присутствие символа w в дереве достижимости (m[ х ](p)=w для некоторой вершины x и позиции p) означает, что для произвольного положительного целого k существует достижимая маркировка со значением в позиции p, большим, чем k (а также бесконечность множества достижимых маркировок). Это, в свою очередь, означает неограниченность позиции p, а следовательно, и самой сети Петри.

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

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

Анализ покрываемости. Задача покрываемости требуется для заданной маркировки m' определить, достижима ли маркировка m"³m'. Такая задача решается путём простого перебора вершин дерева достижимости. При этом ищется такая вершина х, что m[ x ]³m'. Если такой вершины не существует, то маркировка m' не является покрываемой. Если она найдена, то m[ x ] определяет покрывающую маркировку для m' Если компонента маркировки m[ x ], соответствующая некоторой позиции p совпадает с w, то конкретное её значение может быть вычислено. В этом случае на пути от начальной маркировки к покрывающей маркировке имеется повторяющаяся последовательность переходов, запуск которой увеличивает значение маркировки в позиции p. Число таких повторений должно быть таким, чтобы значение маркировки в позиции p превзошло или сравнялось с m'(p).

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

Доказательство очевидно.

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

4.4.2.3. Матричные уравнения.

Другой подход к анализу сетей Петри основан на матричном представлении сетей Петри и решении матричных уравнений. Альтернативным по отношению к определению сети Петри N в виде (P,T,I,O) является определение сети N в виде двух матриц D ^- и D ⁺, представляющих входную и выходную функции I и O. Пусть каждая из матриц D ^- и D ⁺ имеет m=êTê строк (по одной на переход) и n=êPê столбцов (по одному на позицию).

Матричный вид сети Петри N=(P,T,I,O) задаётся парой (D ^-, D ⁺), где

D ^-[k,i] = ^{^} #(p_i,t_k) – кратность дуги, ведущей из позиции p_i в переход t_k.

D ⁺[k,i] = # ^{^} (p_i,t_k) – кратность дуги, ведущей из перехода t_k в позицию p_i,

для произвольных 1£k£m, 1£i£n.

Пусть e[k] — m-вектор, k-тый элемент которого равен 1, а остальные равны 0. Переход t_k, 1£k£m, в маркировке m разрешен, если m³e[k]× D ^-. Результатом запуска разрешённого перехода t_k в маркировке m является следующая ниже маркировка m’:

m’=m - e[k]× D ^- + e[k]× D ⁺==m + e[k]× D,

где D =(D ⁺ - D ^-) — составная матрица изменений.

1. Два подхода к построению управляющих автоматов. Методы синтеза управляющих автоматов (УА) (аппаратные, программные)

Существует два принципиально разных подхода к проектированию микропрограммного автомата (управляющего устройства): использо­вание принципа схемной логики и использование принципа программи­руемой логики.

В первом случае в процессе проектирования подбирается некоторый набор цифровых микросхем (обычно малой и средней степени интегра­ции) и определяется такая схема соединения их выводов, которая обес­печивает требуемое функционирование (т.е. функционирование процессора определяется тем, какие выбраны микросхемы и по какой схеме выполнено соединение их выводов). Устройства, основанные на таком принципе схемной логики, способны обеспечивать наивысшее быстродействие при заданном типе технологии элементов. Недостаток этого принципа построения процессора состоит в трудности использо­вания БИС и СБИС. Это связано с тем, что при использовании схемного принципа каждый разрабатываемый процессор окажется индивидуаль­ным по схемному построению и потребует изготовления индивидуаль­ного типа БИС. Тогда выпускаемые промышленностью БИС окажутся узкоспециализированными, число выпускаемых типов БИС будет боль­шим, а потребность в каждом типе БИС окажется низкой. Выпуск многих типов БИС малыми сериями по каждому типу для промышлен­ности окажется экономически невыгодным.

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

До сих пор речь шла о построении управляющих устройств процес­соров. Теперь рассмотрим условия для широкого использования БИС в операционных устройствах процессоров. Можно построить операцион­ное устройство с таким набором узлов и такой схемой их соединения, которые обеспечили бы решение разнообразных задач. Задача, решае­мая подобным универсальным операционным устройством, определя­ется тем, какая микропрограмма хранится в управляющем устройстве. Таким образом, независимо от решаемой задачи может быть использо­вано одно и то же операционное устройство. Благодаря тому, что по­требность в таких устройствах окажется высокой, они могут быть построены с использованием БИС. использованием принципа схемной логики, а операционное устройст­во выполняется в виде устройстаа, специализированного для решения конкретной задачи.

Процессор, построенный на одной или нескольких БИС, называется микропроцессором.

Набор БИС, обеспечивающих построение цифровых устройств, об­разует микропроцессорный комплект (МПК). Он позволяет совместно со сравнительно небольшим числом микросхем средней и малой степени интеграции создавать миниатюрные вычислительные устройства для разнообразных применений.

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

Цифровые автоматы

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

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

Несмотря на то что реальные автоматы могут иметь несколько входов и выходов, на каждом из которых в дискретные моменты времени (определяемые тактом работы) образуются сигналы, соот­ветствующие лог.О и лог.1, в абстрактной теории удобно рассматри­вать автоматы с одним входом и одним выходом. Возможность такого рассмотрения заключается в следующем. Пусть число реаль­ных входов равно двум. Так как на каждом входе может быть лог.О или лог.1 у автомат оказывается под воздействием в каждый тактовый момент одного из четырех входных сигналов: jc, = (0,0), х2 = (0,1), хг = (1,0), хА = (1,1), jc,, х2, jc3, jc4 — отдельные значения переменной X.

Аналогично несколько реальных выходов приводятся к одному вы­ходу Функционирование цифрового автомата происходит на трех множествах:

множестве возможных входных сигналов jc,, jc2,

множестве внутренних состояний а0, ах,..., ак\

множестве возможных выходных сигналов У1,У2 •••

Одно из состояний является начальным (состояние а^, и перед нача­лом работы автомат всегда устанавливается в это состояние. Работа автомата определяется следущими функциями: функцией переходов, функцией выходов, определяющей зависимость выходного сигнала автомата y(t) от состояния автомата a(t) и входного сигнала х(г):

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

Задание автомата Мили в виде таблицы переходов и выходов пред­ставлено в табл. 4.1. Здесь в клетках, расположенных на пересечении столбцов текущего состояния автомата строками текущего значения входного сигнала указываются следующее состояние (состояние в следующем такте) и значение выходного сигнала (напри­мер, функционирование этого же автомата в форме графа представлено на рис.. Граф состоит из узлов, отождествляемых с состояниями автомата. Связи между узлами показывают переходы автомата из одно­го состояния в другое под воздействием входных сигналов. На каждой связи указывается формируемый на выходе автомата сигнал. Задавая произвольное входное слово в виде последовательности сигналов Х| можно определять соответствующее выходное слово для данного автомата:

входное слово х, х2 х2 х, х2 х, х, х2...

состояние автомата а0 а0 ах а2 а3 а0 а0 ах аъ аъ

выходное слово ух у2 ух ух ух ух у2 у2 у3...

Пример задания автомата Мура в форме таблицы переходов и выхо­дов показан в табл.. Соответствующий этому автомату граф приве­ден на рис

Поиск по сайту: