close

Вход

Забыли?

вход по аккаунту

?

О конечных недетерминированных автоматах игрового типа.

код для вставкиСкачать
Вестник Воронежского института МВД России №4 / 2014
Н.В. Пешкова
О КОНЕЧНЫХ НЕДЕТЕРМИНИРОВАННЫХ
АВТОМАТАХ ИГРОВОГО ТИПА
ABOUT NONDETERMINISTIC FINITE AUTOMATA
GAME TYPE
Для описания ситуационных потоков теории конфликтов в данной работе
предложена модель, объединяющая теорию марковских цепей и теорию игр в виде конечного автомата. Проведена классификация автоматов малой размерности, предложен алгоритм получения точных аналитических выражений для среднего выигрыша
при использовании байесовских стратегий.
To describe the state flow in situational theory of conflict in this paper a model that
combines the theory of Markov chains and game theory as a state machine is proposed. A
complete classification of low-dimensional automata and exact analytical expressions for the
average Bayesian payoff are obtained.
1. Введение. Классическая теория конечных автоматов [1] предполагает работу
с детерминированным значением входного сигнала, для которого существует единственное состояние, в которое автомат может перейти из текущего состояния. Другими
словами автомат задается в виде пятерки
A  (s, x, y, f , g ) ,
где s — вектор состояний автомата, (x,y) — входной и выходной алфавиты соответственно, f — функция перехода и g — функция выхода. Естественным обобщением автомата является использование в качестве его аргументов случайных величин. Так, в
работе [2] М.О. Рабин ввел недетерминированные автоматы, в которых стохастической
матрицей задается функция перехода f. Дальнейшее обобщение было предложено в работе [3], где для автоматов выделялась читающая и пишущая части со своими функциями и областями значений. В работе [4] предложен конечный недетерминированный
автомат игрового типа, на вход которого подается последовательность стратегий игроков, а выходом являются платежные матрицы игр, соответствующих состояниям конечного автомата. Вероятностные характеристики автомата проявляются в случае, когда одним из игроков выступает природа, а ответные действия человека могут быть
244
Информатика, вычислительная техника и управление
рассчитаны с использованием, например, критерия Байеса. В статье [4] работой данного автомата моделировалась конкретная ситуация прорыва противопаводковой дамбы
во время аномального наводнения на р. Амур в 2013 году. В работе [5] данная схема
использовалась для ситуационного моделирования работы Зейской ГЭС в экстремальных ситуациях. В данных статьях системы имели 3 и 5 состояний соответственно, что
не позволило найти аналитическое решение поставленных задач, в связи с чем авторами применялись методы имитационного моделирования, реализованные с помощью
пакета Simulink Matlab. В работе [6] была проведена классификация всех возможных
состояний байесовских автоматов малой размерности (имеющих два состояния). Целью
данной статьи является классификация всех возможных состояний байесовских автоматов типа используемых в работе [4] (имеющих 3 состояния)


x12   y11 y12 
x
, 
, f , g  ,
(1)
A   ( s1 , s 2 , s3 ),  11
 x 21 x 22   y 21 y 22 


получение их точных аналитических решений и оптимальных выигрышей.
2. Теоретические основы модели. Очевидно, что аналитическое решение для
байесовского автомата (1) в общем виде проводится по следующей схеме.
1) По заданным входным сигналам автомата
g
S0
S1
S2
a0b0
c000
c001
c002
a0b1
c010
c011
c012
a1b0
c100
c101
c102
a1b1
c110
c111
c112
cтроятся платежные матрицы игр:
0
 c00
p( s 0 )   0
 c10
0

c01
,
0 
c11 
1
 c00
p( s1 )   1
 c10
1

c01
,
1 
c11 
2
 c00
p( s 2 )   2
 c10
2

c01
.
2 
c11 
2) Для заданной вероятности поступления сигнала bk по критерию Байеса находятся оптимальные стратегии всех игр a m* . (Очевидно, что они не обязаны совпадать.)
3) Произведение a m* bk формирует входной сигнал (аргумент функции f),
определяющий изменение состояния системы на следующем шаге.
f
S0
S1
S2
a0b0
Sk1
Sk5
Sk9
a0b1
Sk2
Sk6
Sk10
a1b0
Sk3
Sk7
Sk11
a1b1
Sk4
Sk8
Sk12
Для упрощения записи мы далее будем пользоваться следующей системой обозначений. Т.к. рассматриваемый автомат имеет 3 состояния, то множество всех возможных переходов f образуют 3-ичную логическую функцию 3  2  12 переменных
2
245
Вестник Воронежского института МВД России №4 / 2014
(т.е. всего N  312  531441 автомат). Однако, поскольку теорема Нэша утверждает, что
любая конечная игра имеет решение в чистых или смешанных стратегиях, то множество различных автоматов Байеса уменьшается в 2 раза. Для удобства классификации
мы будем использовать только нулевые стратегии природы, учитывая, что для остальных автоматов решения можно получить переопределением номера стратегии и компонент платежной матрицы.
Например, функции
f
S0
S1
S2
a0b0
S0
S0
S1
a0b1
S1
S2
S2
a1b0
S0
S0
S1
a1b1
S1
S2
S2
соответствует последовательность
(s0 , s1 , s0 , s2 , s1 , s2 )  (010212) .
Stateflow диаграмма данной функции имеет вид, показанный на рис. 1.
[r<a0]
{f=f+c00}
{f=f+c01}
[b0==0]
[r<a1]
[r<a0]
{f=f+d01}
{f=f+e01}
{f=f+d00}
{f=f+e10}
[b2==0]
[b1==0]
{k=0; S0
f=0;} k++;
b0=0;
r=ml('rand(1)')
[b0==1]
[r<a1]
{f=f+dc11}
{f=f+c10}
S1
k++;
b2=0;
r=ml('rand(1)')
S2
k++;
b2=0;
r=ml('rand(1)')
[b2==1]
[b1==1]
[r<a1]
{f=f+e11}
{f=f+d11} [r<a1]
{f=f+d10}
{f=f+e10}
Рис. 1. Stateflow диаграмма Байесовского автомата (010212)
Здесь платежные матрицы нулевого состояния обозначены через p( s0 )  cik , первого
состояния — через p( s1 )  d ik , а второго состояния — через p( s 2 )  eik .
Для упрощения данную диаграмму мы представим в виде, приведенном на рис. 2.
0 1 0 2 1 2
S0
S1
S2
0 1 0 2 1 2
Рис. 2. Упрощенная Stateflow диаграмма автомата (010212)
246
Информатика, вычислительная техника и управление
Далее, используя свойства симметрии, данные автоматы можно объединить в
группы эквивалентных, имеющих одинаковые предельные состояния и средние выигрыши. Так, например, автоматы (000000,000001, 000002, …, 002222) являются эквивалентными. Аналогично эквивалентны автоматы
(010212)  (010221)  (012012)  (100212)  (012021)  (100221)  (102012) .
В результате мы получим 63  216 различных автоматов типа
(2)
i1i2 j1 j2 k1k 2  , где i1, i2 , j1, j2 , k1, k2  0,1,2 ; i1  i2 , j1  j2 , k1  k2 .
Дальнейшее сокращение количества рассматриваемых автоматов производится удалением тех из них, в которых функции перехода являются несущественными. Например,
для автомата (000022) последние 4 значения не являются существенными, поскольку
состояний S1 и S2 автомат не принимает по определению.
3. Аналитическое решение для автомата 000000. Поскольку автоматы из последовательности (000000, … , 002222) эквивалентны, то найдем точное решение для
первого из них. Данный автомат имеет функцию перехода
f
S0
S1
S2
a0b0
S0
S0
S0
a0b1
S0
S0
S0
a1b0
S*
S*
S*
a1b1
S*
S*
S*
и платежную матрицу нулевого состояния p(s0 )  cik . Здесь символом S* обозначены
переходы, несущественные при заданном выборе оптимальных стратегий. Допустим,
критерий Байеса предполагает оптимальным выбор нулевой стратегии a  a0 . Тогда
средний выигрыш игрока на первом шаге есть
m1  b0 c00  b1c01 , где b0  b1  1 .
Средний выигрыш игрока на 2-м шаге есть
m2  2b02 c00  2b0b1 (c00  c01)  2b12 c01 .
Далее
m3  3b03c00  3b02b1 (2c00  c01) 
*
 3b0b12 (c00  2c01 )  3b13c01,
…
n
mn   Cnk b0nk b1k ((n  k )c00  kc01) .
k 0
Последняя формула легко вычисляется при помощи известных сумм
n
 Cnk b0k b1nk  1 ,
k 0
n
C
k 0
k nk k
n 0
1
b
b k  nb1 .
Тогда
mn  n(b0 c00  b1c01) ,
а приведенный средний выигрыш данного автомата равен
m
f 00  lim n  m1  b0 c00  b1c01 ,
n n
как и следовало ожидать для классической игры, использующей байесовские стратегии.
247
Вестник Воронежского института МВД России №4 / 2014
4. Аналитическое решение для автомата 222222. Поскольку автоматы из последовательности (220022, 220122, 220222, 221022, … , 222222) эквивалентны, то
найдем точное решение для первого из них. Данный автомат имеет функцию перехода
F
S0
S1
S2
и платежные матрицы
c
p( s0 )   00
 c10
a0b0
S2
S0
S2
a0b1
S2
S0
S2
a1b0
S*
S*
S*
a1b1
S*
S*
S*
c01 
,
c11 
d 01 
e 
d
e
 , p( s2 )   00 01  .
p( s1 )   00
 e10 e11 
 d10 d11 
.
Допустим, критерий Байеса предполагает оптимальным выбор нулевых стратегий для всех игр a *  a0 . Тогда, для упрощения записи и без потери общности переобозначим коэффициенты платежных матриц
(c0  c00 , c1  c01, d 0  d 00 , d1  d 01, e0  e00 , e1  e01) .
Средний выигрыш игрока на первом шаге есть
m1  b0 c0  b1c1 , где b0  b1  1 .
Далее
m2  b0 b0 (e0  c0 )  b1 (e1  c0 ) 
 b1 b0 (e0  c1 )  b1 (e1  c1 ) ,
…
n'
b0 (c0  (n'k )e0  ke1  
mn   Cnk' b0n ' k b1k 
,
k 0
 b1 (c1  (n'k )e0  ke1 
где n'  n  1 .
mn  m1  ( n  1 )a0e0  a1e1  .
Вычисляя сумму, получим и приведенный средний выигрыш данного автомата
m
f 222222  lim n  b0 e0  b1e1 .
n n
5. Аналитическое решение для автомата 022222. Поскольку автоматы из последовательности (020022, 020122, 020222, 021022, … , 200022, 200122, … , 202222) эквивалентны, то найдем точное решение для первого из них. Данный автомат имеет
функцию перехода
f
a0b0 a0b1 a1b0 a1b1
S0
S0
S2
S*
S*
S1
S0
S0
S*
S*
S2
S2
S2
S*
S*
248
Информатика, вычислительная техника и управление
и компоненты векторов оптимальных стратегий
p( s0 )  c0 k  (c00 , c01 )  (c0 , c1 ),
p( s1 )  d 0 k  (d 00 , d 01 )  (d 0 , d1 ),
p( s2 )  e0 k  (e00 , e01 )  (e0 , e1 ).
Введем обозначения
0  b0 c0  b1c1 ,
1  b0 e0  b1e1
и определим средний выигрыш игрока на первом шаге как
m1  0 .
Тогда
m2  (b0  1)0  b11 ,
m3  (b02  b0  1)0  (3  b02  b0  1)1 ,
…
n 1


mn   b0k  0   n   b0k 1 .
k 0
k 0


Вычисляя сумму, получим

(b n  1)
(b n  1) 
1
mn  0
 0   n  0
b1
b1 

и приведенный средний выигрыш данного автомата
m
f 022222  lim n  1 .
n n
6. Аналитическое решение для автомата 22**00. Обозначим знаком * любые значения из множества {0,1,2}. Поскольку автоматы из последовательности
(1100**, … , 22**00) эквивалентны, то найдем точное решение для последнего из них.
Данный автомат имеет следующую функцию перехода:
n 1
f
S0
S1
S2
a0b0
S2
S*
S0
a0b1
S2
S*
S0
a1b0
S*
S*
S*
a1b1
S*
S*
S*
Определяя средний выигрыш игрока на первом шаге как
m1  0 ,
получим
m2  0  1,
m3  20  21,
…
mn  (n  1)(0  1 )
249
Вестник Воронежского института МВД России №4 / 2014
и приведенный средний выигрыш данного автомата
m
f 22**00  lim n   0  1 .
n n
7. Аналитическое решение для автомата 02**20. Поскольку автоматы из последовательности (02**20, 20**20, 02***02, 20**02) эквивалентны, то найдем точное
решение для первого из них. Данный автомат имеет следующую функцию перехода:
f
S0
S1
S2
a0b0
S0
S*
S2
a0b1
S2
S*
S0
a1b0
S*
S*
S*
a1b1
S*
S*
S*
Последовательность выигрышей
m1   0 ,
m2  (1  b0 )0  b11 ,
…
mn  (1  (n  1)b0 )0  (n  1)b11
дает приведенный средний выигрыш данного автомата
m
f 02**20  lim n  b0  0  b11 .
n n
8. Аналитическое решение для автомата 010202. В заключение представим
аналитическое решение для байесова автомата, использовавшегося в работе [4] при ситуационном моделировании прорыва противопаводковой дамбы во время ЧС природного характера. Данный автомат имеет функцию перехода
f
S0
S1
S2
a0b0
S0
S0
S0
a0b1
S1
S2
S2
a1b0
S*
S*
S*
a1b1
S*
S*
S*
и компоненты векторов оптимальных стратегий
p( s0 )  c0 k  (c00 , c01 )  (c0 , c1 ),
p( s1 )  d 0 k  (d 00 , d 01 )  (d 0 , d1 ),
p( s2 )  e0 k  (e00 , e01 )  (e0 , e1 ).
Введем обозначения
0  b0 c0  b1c1 , 1  b0 d 0  b1d1 , 2  b0 e0  b1e1
и определим средний выигрыш игрока на первом шаге как
m1  0 .
Тогда последовательность
m2  (b0  1)0  b11 ,
m3  (1  2b0 )0  (1  b02 )1  (1  2b0  b02 )2 ,
250
Информатика, вычислительная техника и управление
…
m n  (1  ( n  1)b0 )0  (1  ( n  3)b0  ( n  2)b02 )1  ( n  2)(1  2b0  b02 ) 2 дает приведенный средний выигрыш данного автомата
m
f 010202  lim n  b0 0  b0b11  b12 1 .
n n
9. Выводы. Полная классификация неэквивалентных байесовых автоматов вида
(2) может быть проведена следующим образом. Из 216 имеющихся автоматов 36 типа
00*** являются тривиальными и решаются стандартными методами теории матричных
игр. Для каждого автомата типа 11**** найдется эквивалентный, вида 22****. Аналогично для каждого автомата типа 01**** найдется эквивалентный, вида 02****. Тогда
из всех автоматов типа 01**** остаются следующие:
01
1200
2200
1201
2201
1202
2202
1211
2211
1212
2212
1222
2222
Аналогично можно сказать и про 1, 2 и 4 строку автоматов типа 11****.
11
1200
2200
1201
2201
1202
2202
1211
2211
1212
2212
1222
2222
Среди автоматов типа 12*** можно выделить следующие эквивалентные:
0001  0200, 0002  0100, 0011  2200, 0012  1200, 0022  1100 ,
0101  0202, 1111  2222, 0111  2202, 0112  1202, 0122  1102 ,
0211  2201, 0212  1201, 0222  1101,1112  1222, 2212  1211 .
В результате мы получили 57 неэквивалентных автоматов. Для некоторых из
них в данной работе было найдено явное аналитическое решение. Для остальных автоматов решения будут представлены в следующих работах.
ЛИТЕРАТУРА
1. Brauer W. Automaten theorie. Stuttgart: Teubner, 1984. — 496 p.
2. Rabin M.O. Probabilistic automata // Information and control. 1963, N.6, P.230—245.
3. Ginsburg S. The mathematical theory of context-free-language. NY: McGraw-Hill,
1966. — 326 p.
4. Думачев В.Н., Пешкова Н.В., Калач А.В., Чудаков А.А. Ситуационное моделирование прорыва противопаводковой дамбы во время аномального наводнения на
Дальнем Востоке летом 2013 г. // Вестник Воронежского института ГПС МЧС России.
— 2013. — №4(9). — С.35-39.
5. Думачев В.Н., Пешкова Н.В., Калач А.В., Чудаков А.А. Ситуационное моделирование работы Зейской ГЭС во время аномальных наводнений // Вестник Воронежского института ГПС МЧС России. — 2014. — №2(11). — С.18—25.
251
Вестник Воронежского института МВД России №4 / 2014
6. Думачев В.Н., Пешкова Н.В. О конечных игровых автоматах Байесовского
типа // Системы управления и информационные технологии. — 2014. — №3(57). —
С. 12—15.
REFERENCES
1. Brauer W. Automaten theorie. Stuttgart: Teubner, 1984. — 496 p.
2. Rabin M.O. Probabilistic automata // Information and control. 1963, N.6, P.230—245.
3. Ginsburg S. The mathematical theory of context-free-language. NY: McGraw-Hill,
1966. — 326 p.
4. Dumachev V.N., Peshkova N.V., Kalach A.V., Chudakov A.A. Situatsionnoe modelirovanie proryiva protivopavodkovoy dambyi vo vremya anomalnogo navodneniya na Dalnem Vostoke letom 2013 g. // Vestnik Voronezhskogo instituta GPS MChS Rossii. — 2013.
— #4(9). — S.35—39.
5. Dumachev V.N., Peshkova N.V., Kalach A.V., Chudakov A.A. Situatsionnoe modelirovanie rabotyi Zeyskoy GES vo vremya anomalnyih navodneniy // Vestnik Voronezhskogo instituta GPS MChS Rossii. — 2014. — №2(11). — S.18—25.
6. Dumachev V.N., Peshkova N.V. O konechnyih igrovyih avtomatah Bayesovskogo
tipa // Sistemyi upravleniya i informatsionnyie tehnologii. — 2014. — №3(57). — S.12—15.
СВЕДЕНИЯ ОБ АВТОРЕ
Пешкова Надежда Владимировна. Адъюнкт кафедры высшей математики.
Воронежский институт МВД России.
E-mail: peshckova.nadejda@yandex.ru
Россия, 394065, Воронеж, проспект Патриотов, 53. Тел. (473) 2005-216.
Peshkova Nadezhda Vladimirovna. Post-graduate cadet.
Voronezh Institute of the Ministry of the Interior of Russia.
Work address: Russia, 394065, Voronezh, Prospect Patriotov, 53. Tel. (473) 2005-216.
Ключевые слова: автоматная модель; недетерминированные автоматы; байесовский автомат;
аналитическое решение; вероятностные характеристики.
Key words: automaton model; nondeterministic finite automata; Bayesian automaton; analytical solution; probabilistic characteristics.
УДК 519.713: 351.74
252
Документ
Категория
Без категории
Просмотров
7
Размер файла
413 Кб
Теги
типа, конечный, недетерминированных, игрового, автомата
1/--страниц
Пожаловаться на содержимое документа