Пример. Простейший автомат поведения льва.

Двухточечная краевая задача

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

Используем метод прогонки для решения системы ДУ:

Собираем коэффициенты при :

Собираем свободные члены:

В точке :

Поскольку , то

Это задача Коши, которую надо решать в обратном времени.

Решение этого однородного линейного ДУ с граничным условием, равным точке покоя есть точка покоя:

С учетом этого

Тогда уравнение замкнутой системы (управляемой):

Уравнение для имеет квадратичную правую часть. Это уравнение Риккати (Riccati).

– симметричная матрица

Если заменить на , то система остается управляемой, но управление становится немного хуже.

Тогда получим субоптимальное управление:

Для линеаризованной системы управления (или ) является оптимальным (субоптимальным).

Поскольку , то (или ), то для нелинейной системы получаем

(или ),

КОЛЛОКВИУМ по 3 лекциям

Лекция №4.

2.3. Дискретно-детерминированные модели (F-схемы). Конечные автоматы

Особенности дискретно-детерминированного подхода рассмотрим на примере использования в качестве математического аппарата теории автоматов. Теория автоматов — это раздел теоретической кибернетики, в котором изучаются математические модели — автоматы. На основе этой теории система представляется в виде автомата, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени. Понятие «автомат» варьируется в зависимости от характера конкретно изучаемых систем, от принятого уровня абстракции целесообразной степени общности.

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами:

­ конечным множеством X входных сигналов (входным алфавитом);

­ конечным множеством Y выходных сигналов (выходным алфавитом);

­ конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний);

­ начальным состоянием z₀, ;

­ функцией переходов ;

функцией выходов .

F-схема:

при t=0, 1, 2, ..., z(t), x(t), y(t).

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

Обозначим состояние, а также ВХОДНОЙ и выходной сигналы, соответствующие t-му такту при t=0, 1, 2, ..., через

z(t), x(t), y(t). При этом, по условию, z(0)=z_o, a z(t) €Z, x(t) € X, y(t) €Y.

Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t=0, 1, 2, ... дискретного времени F-автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени t=0 он всегда находится в начальном состоянии z(0)=z_o . В момент t, будучи в состоянии z(t), автомат способен воспринять на входном канале сигнал x(t) €X и выдать на выходном канале сигнал , переходя в состояние , z(t) €Z, y(t) € Y. Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного алфавита Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние z₀, по­

давать в некоторой последовательности буквы входного алфавита х(0), x(1), x(2),..., т. е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у(0), y(1), у(2), ..., образуя выходное слово.

Таким образом, работа конечного автомата происходит по следующей схеме: в каждом t-м такте на вход автомата, находящегося в состоянии z(t), подается некоторый сигнал x(t), на который он реагирует переходом в (t+1)-м такте в новое состояние z(t + 1) и выдачей некоторого выходного сигнала. Сказанное выше можно описать следующими уравнениями:

для F-автомата первого рода, называемого также автоматом Мили,

,

,

для F-автомата второго рода

,

,

Автомат второго рода, для которого

, ,

т. е. функция выходов не зависит от входной переменной x(t),

называется автоматом Мура.

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

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

Способы задания: табличный, графический, матричный.

1. Табличное задание автомата - задание таблиц переходов и выходов. Строки такой таблицы - входные сигналы, столбцы - выходы (состояния).

Входной алфавит: "антилопа", "охотник".

Внутренние состояния: "сытый", "голодный".

Выходной алфавит: "съесть", "спать", "убежать"

Таблица переходов:

Рассмотрим для примера табличное задание автомата Мили.

xi	zk
z0	z1	…	zk
Переходы
x1 x2 … xl	(z0,x1) (z0,x2) … (z0,xl)	(z1,x1) (z1,x2) … (z1,xl)	… … … ..	(zk,x1) (zk,x2) … (zk,xl)
Выходы
x1 x2 … xl	ψ(z0,x1) ψ(z0,x2) … ψ(z0,xl)	ψ(z1,x1) ψ(z1,x2) … ψ(z1,xl)	… … … ..	ψ(zk,x1) ψ(zk,x2) … ψ(zk,xl)

Таблица переходов для автомата Мура:

xi	zk
ψ(z0)	ψ(z1)	…	ψ(zk)
z0	z1	…	zk
x1 x2 … xl	(z0,x1) (z0,x2) … (z0,xl)	(z1,x1) (z1,x2) … (z1,xl)	… … … ..	(zk,x1) (zk,x2) … (zk,xl)

2. При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал х_к вызывает переход из состояния z_i в состояние z_j, то на графе автомата дуга, соединяющая вершину z_i с вершиной z_j, обозначается х_к. Для того, чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производится так: если входной сигнал х_к действует на состояние z_i то, согласно сказанному, получается дуга, исходящая из z_i и помеченная х_к; эту дугу дополнительно отмечают выходным сигналом . Для автомата Мура аналогичная разметка графа такова: если входной сигнал х_к, действуя на некоторое состояние автомата, вызывает переход в состояние z_j, то дугу, направленную в z_j и помеченную х_к, дополнительно отмечают выходным сигналом .

Граф автомата Мили:

Граф автомата Мура:

ПРИМЕРЫ:

Пример табличного задания F-автомата Мили с тремя состояниями:

Автомат Мура с 5 состояниями:

Графы для наших двух примеров будут выглядеть так:

1. При решении задач моделирования систем часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица , строки которой соответствуют исходным состояниям, а столбцы — состояниям перехода. Элемент , стоящий на пересечении i-й строки и j-ro столбца, в случае автомата Мили соответствует входному сигналу х_к, вызывающему переход из состояния z_i в состояние Z_j, и выходному сигналу y_s, выдаваемому при этом переходе. Для автомата Мили, рассмотренного выше, матрица соединений имеет вид

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

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

Рассмотрим асинхронный автомат (F - схему) Мура:

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

2.4. Дискретно-стохастические модели (P-схемы). Вероятностные автоматы

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

Рассмотрим множество G, элементами которого являются всевозможные пары (x_i z_s), где x_i и z_s — элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции и , что с их помощью осуществляются отображения G->Z и G->Y, то говорят, что F= <Z, X, Y, , > определяет автомат детерминированного типа.

G = {(x_i, z_s), x_i X, z_s Z},

X – подмножество входных сигналов,

Z – подмножество внутренних состояний.

Если существуют : G->Z; : G->Y,

то F= <Z, X, Y, , ψ > определяет автомат детерминированного типа.

Более общий случай:

Пусть Φ = {(x_k, y_j), x_k X, y_j Y}, Y – помножество выходов.

Любой элемент из G индуцирует на Φ некоторый закон распределения вида:

- вероятности перехода автомата в состояние z_k и появления на выходе сигнала y_j, если он был в состоянии z_s и на его вход в этот момент поступил сигнал x_i.

P=<Z,X,Y,B> - вероятностный автомат (P-автомат).

=> вероятностный автомат Мили

=> вероятностный автомат Мура