Назовем сетевым автоматом NA с p входами и q выходами следующий кортеж:
NA = <I, O, U, X, Z, f, h> (4.1)
где I = {i1, i2,…, ip} – множество входов;
O = {o1, o2,…, oq} – множество выходов;
U = {u1, u2,…, um} – входной алфавит;
X = {x1, x2,…, xn} – множество состояний;
Z = {z1, z2,…, zk} – выходной алфавит;
f: X´V®X – одношаговая переходная функция, где VÌU´I;
h: X´V®W – выходная функция, где WÌZ´O.
Элементы множеств V и W будем называть обобщенными входными и выходными алфавитами соответственно.
Введем дополнительно специальный символ e, который является элементом и входного и выходного алфавитов. Этот символ мы будем интерпретировать как пустой символ, который всегда присутствует на выделенном входе автомата, так что если в описании перехода из некоторого состояния присутствует входной символ e, тогда осуществляется соответствующий переход. Появление символа e в выходном канале означает, что на выход ничего не поступает. Здесь надо заметить, что полученный в результате автомат не является автоматом Мили, поскольку он не сохраняет длину отображения.
Далее при изображении графа сетевого автомата мы будем использовать следующую нотацию: через i.u будем обозначать символ входного алфавита uÎU, пришедший по входному каналу i Î I; через z.o будем обозначать символ выходного алфавита zÎZ, поступивший в выходной канал oÎO.
Введем теперь понятие сети автоматов как набора автоматов, объединенных своими входами и выходами и взаимодействующих путем передачи / приема символов своих выходных / входных алфавитов.
Назовем сетью автоматовL связный мультиграф:
L = (E, C), (4.2)
где E = {e1, e2,…, en} – множество вершин графа;
C = {c1, c2,…, cm} – множество направленных дуг, ci = (ej, ek).
Вершина графа интерпретируется как сетевой автомат, а дуга – как канал связи между автоматами, используемый для обмена элементами входных / выходных алфавитов.
Работа сети заключается в параллельном функционировании всех составляющих ее автоматов, поведение каждого из которых, в свою очередь, определяется его текущим состоянием, а также состоянием входных каналов.
Пусть теперь L = (E, C) – сеть автоматов, и пусть распределенная система состоит из подсистем, каждая из которых описывается конечным автоматом, так что M = {Mi} – множество моделей подсистем.
Тогда, если M Ì E, то
Lc = {Ec, Cc}, (4.3)
где Ec = E \ M, будем называть управляющей структурой для распределенной системы, представленной моделями {Mi}.
Ясно, что будучи соединенной с реальными подсистемами, управляющая структура обеспечит некоторое поведение подсистем, зависящее от топологии управляющей структуры и атрибутов сетевых автоматов, входящих в ее состав.
Рассмотрим простой пример. Пусть два робота Rb
1 и Rb
2 перекладывают детали из накопителя S на два конвейера С
1 и С
2 (рис. 4.1).
В соответствии с изложенным выше, роботы Rb1, Rb2 будем описывать как конечные автоматы
Rbi = (Ii, Oi, Ui, Xi, Zi, fi, hi), i=1,2 (4.4)
соследующимиатрибутами:
Ii ={i0}; Oi ={i0}; Ui ={g}; xi ={0, 1, 2}; Zi ={y, Y}, i = 1,2 (4.5)
Функции
fi и
hi задаются диаграммой, представленной на рис. 4.2. Каждый из роботов Rb
i воспринимает только одну команду «g», в результате которой он перемещается к накопителю S, захватывает деталь, переносит и устанавливает ее на конвейер С
i. Сигналы «y» и «Y» на выходе робота появляются тогда, когда он освобождает опасную зону и завершает выполнение одного цикла соответственно. Будем строить управляющую структуру в виде трех автоматов, два из которых (Reg
1 и Reg
2) являются логическими регуляторами роботов, а третий (Res) обеспечивает слежение за ресурсом.
На рис. 4.2 представлена топология управляющей структуры, а также диаграммы всех входящих в ее состав автоматов. Структура функционирует следующим образом. Регулятор каждого робота посылает запрос на занятие опасной зоны автомату-ресурсу. Если зона свободна, то этот запрос удовлетворяется, опасная зона переходит в состояние «занято» и регулятор посылает команду роботу начать транспортную операцию. После того, как робот выйдет из опасной зоны, он информирует об этом регулятор, который в свою очередь переводит опасную зону в состояние «свободно» и ждет окончания выполнения операции. Далее цикл повторяется. Приведенный выше способ координации является весьма эффективным средством для построения только централизованных систем управления. Действительно, если нижний уровень управляющей структуры представляет собой по сути дела логические регуляторы и может быть без труда ассоциирован с локальными системами управления, то верхние уровни обмениваются данными со всеми подсистемами, участвующими в выполнении задания, и потому являются фрагментом центральной системы управления.
Естественный способ преодоления этой трудности состоит в формировании одноуровневой управляющей структуры, т.е. такой, у которой число автоматов совпадает с числом подсистем, разрешив этим автоматам обмениваться данными непосредственно между собой, а не с верхним уровнем. Это, с одной стороны, приводит к усложнению довольно простого логического регулятора, а с другой стороны позволяет обойтись без центральной системы управления. На рис. 4.3 показана соответствующая архитектура системы управления (модули, не связанные с координацией, не показаны).
Рассмотрим сначала метод планирования задания для централизованной системы. Суть подхода состоит в выполнении двухшаговой процедуры:
Шаг 1. На основе методов искусственного интеллекта найти последовательность подзаданий, выполняемых каждой из подсистем и сформированных в терминах входных алфавитов подсистем.
Шаг 2. Преобразовать эти последовательности в управляющую структуру, которая обеспечит координацию исполнения сформированного задания.
Обсудим более детально эту процедуру. В качестве метода решения задачи планирования будем использовать исчисление предикатов первого порядка. Входная информация, необходимая для решения задачи планирования, состоит из следующих компонент, содержащих описание:
К1 – возможностей каждой из подсистем,
К2 – начального состояния,
К3 – задания,
К4 – универсальных свойств.
Компонента К1 включает набор предложений (правил), отражающих возможности каждой подсистемы изменять состояние внешней среды (перемещение объектов, получение информации об объектах и т.д.). Отличительной особенностью этой компоненты является наличие сколемовской функции, относящейся к одной из подсистем. Множество К2 включает факты, описывающие начальное состояние системы. Компонента К3 представляет собой формулировку задания. Множество К4 описывает универсальные свойства, не зависящие от подсистем, входящих в состав МРС (это множество может быть пусто). Элементы всех множеств представляют собой правильно построенные формулы (ППФ) в исчислении предикатов 1‑го порядка.
Задача планирования состоит в получении последовательности операторов, обеспечивающих выполнение цели. При этом для обеспечения максимально возможного распараллеливания процесса исполнения представим множество К1 в виде:
(4.6)где N – множество подсистем.
Таким образом, каждое подмножество К1i содержит только ППФ, отражающие возможности i‑ой подсистемы. После осуществления такого разбиения будем строить резолюции rij, и не-цели с элементами К1i настолько долго, насколько это возможно. Если этот процесс невозможно продолжить, оставаясь в К1i (это означает, что на этом этапе исполнения необходимо взаимодействие между подсистемами), строим резолюции с соседними подмножествами. Такой процесс обеспечит (в случае успеха) получение последовательности операторов, относящихся к каждой из подсистем, а также точек координации их взаимодействия. Далее полученные результаты используются для преобразования в управляющую структуру, обеспечивающую исполнение сформированного плана (рис. 4.4).
