Исследование свойств механизма планирования действий
декларативно поставленных
задач в системе ГАММА-3
М.Ф. Степанов,
д.т.н., mfstepanov@mail.ru,
СГТУ, г. Саратов,
А.М. Степанов,
к.т.н.,
ripkilobyte@gmail.com,
ИПТМУ РАН,
А.Р. Салихова,
студ.,
СГТУ, г. Саратов,
Л.С. Михайлова
к.т.н.,
lsmixx@rambler.ru
ЭПИ МАМИ, г. Электросталь
Решение непроцедурно
поставленных задач требует привлечения методов искуственного
интеллекта. Однако методы планирования действий представляют собой ресурсоёмкие
процедуры. Система ГАММА-3 обладает возможностями решать задачи, как в
процедурной, так и в непроцедурной (декларативной) постановке. Для повышения
эффективности в качестве механизма планирования действий применяются
планирующие искусственные нейронные сети. В работе исследуются свойства
планирующих искусственных нейронных сетей.
The solution of nonproedural tasks demands use
of artificial intelligence methods. However methods of
planning of actions represent resource-intensive procedures. The GAMMA-3 system
possesses opportunities to solve problems, both in procedural, and in
nonprocedural (declarative) statement. The planning artificial neural networks are applied to increase of efficiency as a mekhanizm of planning of actions. In papers
properties of the planning artificial neural networks are investigated.
В системе ГАММА-3 в
качестве механизма планирования действий непроцедурно
(декларативно) поставленных задач используются искусственные нейронные сети
(ПИНС). В данной работе исследуются свойства ПИНС, важнейшим из которых
является сходимость решений. В связи с тем, что в качестве знаний о проблемной
области используются аксиоматические теории автоматических решений
формализованных задач теории автоматического управления [2], то необходимо
рассматривать вопрос разрешимости.
В составе ПИНС архивная
искусственная нейронная сеть (АИНС) используется как устройство памяти для
хранения решений, получаемых в решающей искусственной нейронной сети (РИНС) и,
следовательно, не оказывает влияния на сходимость процесса решения задачи в
планирующей искусственной нейронной сети в целом. Поэтому основное внимание
следует уделить исследованию поведения решающей искусственной нейронной сети.
Введем обозначения:
- состояние решающей
искусственной нейронной сети на i-м шаге решения задачи z;
- формулировка задачи z;
- исходные данные
задачи z;
- требуемый результат
задачи z;
- требования к
результату решения задачи z;
- условия применимости
задачи z;
- состояние
нейронов-данных (искомые результаты, требования к результатам, условия
применимости) решающей искусственной нейронной сети на k-м шаге;
- состояние
нейронов-операций решающей искусственной нейронной сети на k-м шаге;
- текущий план решения
задачи, построенный после k-го шага;
- формат записи собственной аксиомы теории решений,
- имя действия
(операции), описываемого аксиомой;
- функция,
возвращающая условия применимости аксиомы ;
- функция,
возвращающая исходные данные аксиомы ;
- функция, возвращающая
искомые результаты аксиомы ;
- функция,
возвращающая требования к результатам аксиомы;
- количество элементов
множества 
;
Æ - пустое множество;
, (
,
,
) - отображение, задающее состояния нейронов слоя «данные» в
соответствии с атрибутами задачи z;
,(
,
,
) - отображение, устанавливающее состояния нейронов слоя
«данные» в соответствии с состояниями нейронов слоя «операции»;
, (
) – отображение, устанавливающее состояния нейронов-операций
в соответствии с состоянием нейронов данных.
Множество начальных
состояний решающей искусственной нейронной сети, соответствующих задаче z определим как 
, где символы "[0]" обозначают векторы
соответствующей размерности с нулевыми элементами.
Заключительными назовем
состояния 
, достигнутые по окончании процесса поиска
решения задачи z.
Среди заключительных
выделим множество целевых состояний
|
|
|
,достижение которых свидетельствует об
успешном построении плана решения 
задачи z.
Достижение заключительных
состояний вида
|
|
|
,не являющихся
целевыми, свидетельствует об отсутствии решения задачи.
Сходимость процесса поиска
решения, применительно к планирующей искусственной нейронной сети, означает,
что для каждой задачи z, имеющей решение в
соответствующей аксиоматической теории решений, решающая искусственная
нейронная сеть перейдет из заданного начального состояния 
в соответствующее
целевое 
.
В связи с ограничениями на
объём работы доказательства большинства теорем будут опущены.
Теорема 1. Необходимым
условием решения задач планирующей искусственной нейронной сетью является
полнота в смысле Робинсона используемого фрагмента
многоуровневой аксиоматической теории автоматических решений формализованных
задач ТАУ.
Теорема 2. Достаточным условием сходимости процесса поиска решения задачи
планирующей искусственной нейронной сетью является полнота в смысле Робинсона
используемого фрагмента многоуровневой аксиоматической теории автоматических
решений формализованных задач ТАУ.
Разрешимость теорий решений
приводит к тому, что для задач имеющих решение оно будет найдено за конечное
число шагов поиска. В нашем случае необходимо показать, что использование ПИНС
не нарушает разрешимости МАТАРФЗ ТАУ. Это должно явиться следствием
особенностей организации РИНС и метода поиска решения задачи, реализованного в
ней.
Для обеспечения сохранения
разрешимости МАТАРФЗ ТАУ решающая искусственная нейронная сеть должна гарантировать
нахождение за конечное число шагов решения задачи, либо отказ, если оно не
существует. Поэтому докажем следующее утверждение.
Теорема 3. Заключительное состояние планирующей искусственной нейронной сети,
не являющееся целевым, достигается для задач, не имеющих решения за конечное
число шагов, равное увеличенному на единицу числу операций в используемом
фрагменте аксиоматической теории автоматических решений формализованных задач
ТАУ.
Теорема 4. Целевое
состояние планирующей искусственной нейронной сети для задач, имеющих решение,
достигается за конечное число шагов, не превышающее увеличенного на единицу
числа операций в плане решения задачи.
Рассмотрим некоторые из
возможных ситуаций в ходе решения задачи ПИНС.
Случай 1. Пусть решение
задачи z достигается применением операции,
описываемой аксиомой вида 
, где 
, 
, 
Æ=
, т.е. аксиома не содержит ни требований к результату, ни
условий применимости. Тогда протокол работы ПИНС (пошаговая запись состояний):
Шаг 0 (начальное
состояние): 
, 
, 
Æ, 
Æ.
Шаг 1: 
,
, 
=
=
Æ=т}, 
.
Шаг 2: 
, 
=Æ, 
=Æ, 
.
Поскольку 
≠Æ, 
=Æ, 
Æ, то решение получено.
При этом Nш=2=
+1=1+1=2. Следовательно, утверждение теоремы 4 справедливо
для данной ситуации.
Случай 2. Пусть решение задачи z
достигается применением операции, описываемой аксиомой вида 
, где 
, 
, 
=
≠Æ, т.е. аксиома не содержит
условий применимости. Пусть в аксиоматике теории решений имеется аксиома вида 
, где 
, 
.
Протокол работы ПИНС:
Шаг 0 (начальное состояние): 
, 
, 
Æ, 
Æ.
Шаг 1: 
, , , =
Æ}=
=Æ},.
Шаг 2: , 
, =
Æ}=
=Æ}, 
Шаг 3: 
, 
Æ, 
=Æ,
Поскольку 
≠Æ, 
=Æ, 
Æ, то решение получено. При
этом Nш=3=
+1=2+1=3. Следовательно, утверждение теоремы справедливо для
данного случая.
Случай 3. Пусть решение
задачи z достигается применением операции, описываемой
аксиомой вида 
, где , в аксиоматике теории решений имеются аксиомы вида:
, где , .
, где 
, 
.
Протокол работы ПИНС:
Шаг 0: , 
, Æ, Æ.
Шаг 1:
, , =
} ==Æ}, .
Шаг 2:
, 
=
=
, =
}= 
, 
.
Шаг 3: 
,
=
=Æ, =Æ,
.
Поскольку ≠Æ, =Æ, Æ, то решение получено. При
этом Nш=3<+1=4+1=4. Следовательно, утверждение теоремы справедливо для
данного случая.
Случай 4. Пусть задача z имеет постановку вида 
, где 
, 
, 
=Æ и существует набор аксиом
вида 
, 
, таких, что 
.
Протокол работы ПИНС:
Шаг 0 (начальное
состояние): ,
, Æ, Æ, .
Шаг 1:
,
,
=
}= 
=Æ}, 
.
Шаг 2: ,
=
=}=
=Æ},
.
Шаг 3: ,
=
,=
}=
=
=Æ},
. …
Шаг n-1: 
,
=
.
=
}=
=Æ},
.
Шаг n: 
,
=
,
=
}=
=Æ},
.
Шаг n+1: 
,
=Æ,
=
}=Æ,
.
Поскольку 
≠Æ, 
=Æ, 
Æ, то решение получено. При
этом Nш=n+1=
+1=n+1. Следовательно, утверждение теоремы справедливо для
данного случая.
Случай 5. Пусть задача z имеет постановку вида , где 
, 
, =Æ и существует набор аксиом
вида , .
Протокол работы ПИНС:
Шаг 0 (начальное
состояние): ,
, Æ, Æ, .
Шаг 1: ,
, 
=
}=
=
=Æ},
.
Шаг 2: ,
=Æ,
=}=Æ,
.
Поскольку ≠Æ, 
=Æ, Æ, то решение получено. При
этом Nш=2<
+1=n+1. Следовательно, утверждение теоремы справедливо для
данного случая.
Случай 6. Пусть задача z имеет постановку вида , где 
, 
, =Æ, 
, 
и существует набор аксиом
вида , таких, что 
, 
, 
, 
. Иначе говоря, решение задачи z
представляет собой бинарное дерево с ветвями длиной m.
Протокол работы ПИНС:
Шаг 0 (начальное
состояние): 
,
, Æ, Æ, .
Шаг 1: ,
,
=
}=
=Æ}, 
.
Шаг 2: 
,
=
,
=
}=
=Æ},
.
Шаг 3: 
, 
=
=
, 
=
}=
=
=Æ},
. …
Шаг m-1: 
,
=
=
,
=
}=
=Æ},
.
Шаг m: 
,
=
,
=
}=
=
=Æ},
.
Шаг m+1: 
,
=Æ,
=}=Æ,
.
Поскольку 
≠Æ, 
=Æ, 
=Æ, то решение получено. При
этом Nш=m+1<
+1=
+1=
. Следовательно, утверждение теоремы справедливо для данного
случая.
Рассмотрение других
ситуаций здесь не приведено в связи с более громоздкими выкладками.
В целом, легко видеть, что
рассмотренные случаи могут комбинироваться в произвольных сочетаниях, что,
очевидно, в целом охватывает всевозможные варианты представления
планов решения задач ТАУ.
Таким образом, утверждение
теоремы справедливо в целом.
В целом
используемый в РИНС метод поиска решений можно интерпретировать следующим
образом: решающая искусственная нейронная сеть возбуждается атрибутами
поставленной задачи и возвращается в исходное невозбужденное состояние (нулевое
состояние) лишь в случае нахождения плана решения поставленной задачи, что
является эффективно распознаваемым признаком. Оценку сложности алгоритма
работы РИНС при его моделировании на традиционной однопроцессорной ЭВМ даёт
Теорема 5.5. Изменение затрат времени на выполнение одного шага работы РИНС
ограничено сверху полиномом второй степени от изменения количества собственных
аксиом теории решений 
.
Доказательство. Докажем утверждение теоремы посредством оценки изменения количества
вычислительных операций (сложений и умножений), которые необходимо выполнить
для вычисления значения состояния нейронов выходного слоя РИНС, т.е.
нейронов-операций. Для простоты исключим из рассмотрения активационные
функции нейронов РИНС, каждая из которых вычисляется только один раз в течение
шага работы РИНС, внося, таким образом, не более, чем линейный
вклад в увеличение трудоемкости алгоритма работы РИНС. Введем
обозначения: o – вектор состояний нейронов-операций
РИНС; д – вектор состояний нейронов-данных РИНС; z – вектор исходных данных решаемой задачи; Wдz – матрица коэффициентов передачи синапсов от слоя
исходных данных задачи к слою нейронов-данных; Wдo -
матрица коэффициентов передачи синапсов от слоя нейронов-операций к слою
нейронов-данных; Woд - матрица коэффициентов передачи
синапсов от слоя нейронов-данных к слою нейронов-операций. С учетом
этого выходной сигнал РИНС можно определить следующим образом:
o = (Woд * д) – выход
нейронов-операций.
д = Wдz * z + Wдo * o – выход нейронов-данных.
o = Woд * Wдz * z + Woд * Wдo * o
o = Woдz * z + Woдo * o – обобщенная формула
Woдz = Woд * Wдz. Woдo = Woд
* Wдo.
Woдz : no
* nz ; Woдo : no * no – размерности матриц
весовых коэффициентов.
No ~ no
* nz + no * no – оценка количества арифметических операций (умножений и
сложений), необходимых для вычисления значения выхода нейронов-операций.
DNo
= (no + Dno) * nz + (no + Dno) * (no + Dno).
DNo
= no * nz + Dno * nz + no * no + 2*(no * Dno)
+ Dno*Dno .
DNo
~ O(Dno) + O(Dno2) = P2(Dno).
Таким образом, изменение
количества арифметических операций оценивается полиномом второй степени от
изменения количества нейронов-операций РИНС, что и требовалось доказать. Это
позволяет отнести алгоритм работы решающей искусственной нейронной сети к эффективным.
Работа выполнена при
финансовой поддержке РФФИ (проект 15-07-99684-а).
Литература
2.
Степанов М.Ф.
Автоматическое решение задач теории автоматического управления на основе
планирующих искусственных нейронных сетей // Нейрокомпьютеры: разработка и
применение, 2003. № 3 и 4. С. 27 – 44.