Вероятностные автоматы

Детерминированные автоматы S мы задавали совокупностью из пяти объектов: S (A, X, Y, d, l), где A = { a ₀, a ₁, a ₂,..., a_M } – множество внутренних состояний автомата, X = { x ₁, x ₂,…, x_F } – множество входных сигналов (входной алфавит), x_i – буква входного алфавита, Y = { y ₁, y ₂,…, y_G } – множество выходных сигналов (выходной алфавит), y _g – буква выходного алфавита,

d – функция переходов, обеспечивающая однозначный переход автомата в состояние a_s из состояния а_m под действием входного сигнала x_f, т.е. a_s = d [ a_m, x_f ],

l – функция выходов, определяющая однозначное значение выходного сигнала y_g в зависимости от состояния автомата а_m и входного сигнала x_f, т.е. y_g = l [ а_m, x_f ].

В работе Поспелова Д.А. «Вероятностные автоматы» рассмотрена более общая модель автомата, а именно: зная состояние автомата а_m и входной сигнал x_f, мы не можем с вероятностью равной 1 сказать, в каком состоянии окажется автомат в следующий момент времени, а также какой выходной сигнал он в этом случае вырабатывает. Однако мы можем указать вероятности наступления соответствующего события, а именно: зная состояние а_m и входной сигнал x_f, мы можем указать вероятности перехода автомата в состояния { а ₀, а ₁, …, а_m, …, а_M }, а также вероятности появления выходных сигналов

{ y ₁, y ₂ ,…,y_g, …, y_G }, т.е. задаем закон распределения вероятностей. Законы распределения задаются в виде следующих таблиц:

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

,, где,.

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

По аналогии с детерминированными автоматами, можно определить ВА Мили и Мура. ВА, у которых вероятности появления выходных сигналов (закон распределения) зависят лишь от состояний автомата, но не зависят от входных сигналов, называются ВА Мура. Если же вероятности появления выходных сигналов (закон распределения) зависят как от состояний автомата, так и от входных сигналов, имеем автомат Мили.

Рассмотрим некоторые частные случаи вероятностных автоматов. Может быть, что выходные сигналы автомата определяются детерминировано, а переходы автомата – случайно. Такие автоматы называются Y - детерминированными вероятностными автоматами. Если состояния определяются детерминировано, то имеем А - детерминированный вероятностный автомат.

Если в процессе функционирования автомата законы распределения вероятностей появления выходных сигналов и вероятности перехода автомата в новые состояния не меняются во времени, то такие ВА называются ВА с постоянной структурой.

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

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

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

Рис. 15.1

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

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

Рассмотрим У -детерминированный вероятностный автомат. Пусть автомат в некоторый момент времени t находится в состоянии а_m, выдал соответствующий этому состоянию выходной сигнал y_g и получил на вход сигнал поощрения. Тогда вероятность р _mm перехода из состоянии а_m в состояние а_m увеличиваются на некоторую величину, а все остальные вероятности в строке уменьшаются на / М. Если же автомат получает сигнал штрафа, то вероятность р _mm перехода из состоянии а_m в состояние а_m уменьшаются на некоторую величину, а все остальные вероятности в строке на увеличиваются на / М, чтобы сумма вероятностей осталась равной 1.

Возможен и другой принцип изменения вероятностей, при котором происходит учет предыстории поведения автомата. Если автомат в момент времени t перешел из состояния а_m в состояние а_к и в момент времени t + 1 получил сигнал «штраф», то вероятность р _mк заменяется на р _mк, где коэффициент больше 0 и меньше 1, а все остальные вероятности в строке изменяются на величину. Если же получил сигнал «нештраф», то вероятность р _mк величину, а все остальные уменьшаются на величину.

Можно менять вероятности в матрице перехода не только по строкам, но и по столбцам. Например, возможен следующий алгоритм. Если в момент времени t под влиянием входного сигнала x_f автомат перешел в состояние а_m и в момент времени t + 1 получил сигнал «штраф», то независимо от того, из какого состояния он перешел, все элементы m -го столбца в матрице переходов заменяются на (р _mm –) или р _mm, а все остальные вероятности изменяются аналогично тому, как это происходило при изменении вероятностей по строкам.

Подобные автоматы уже находят применение при управлении в сложных системах и дают больший эффект там, где раньше работали детерминированные автоматы.

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

Можно установить датчики на перекрестке, которые бы подсчитывали число машин (очередь), возникающее в данном направлении при красном свете светофора. Пусть на перекрестке стоит ВА компенсирующего типа, который имеет 2 состояния: включен красный свет вдоль главного направления и включен зеленый свет (рис. 15.2). Каждому состоянию однозначно соответствует выходной сигнал, т.е. автомат У -детерминированный. С датчиков поступают сигналы штрафа и нештрафа.

Рис. 15.2

Матрица переходов выглядит следующим образом:.

Пусть в начале все эти вероятности равны 0,5 и на главном направлении скопилось П₁ машин, а на другом – П₂. На вход автомата поступает сигнал = П₁ – П₂. Пусть > 0, т.е. на главном направлении больше машин. Тогда если автомат в момент времени t находился в состоянии «зеленом», перешел в состояние «зеленый» и получил сигнал нештраф, то вероятность р_зз (t +1) увеличивается, а вероятность р_зк (t +1) уменьшается: р_зк (t +1) = р_зк (t), р_зз (t +1) = 1– р_зк (t +1).

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

Вопросы к лекции 15: