Управление и оптимизация / Novikov - Refleksiya i upravleniye 2013

	Номер			Учет	Учет	Прогноз
				вероят-	поло-	поведе-	Информированность
	вари-			ности	жений	ния
	анта			обнару-	других	других
				жения	ПО	ПО
модель	III			НЕТ	ДА	НЕТ	Как в варианте I.
Кооперативная
							Дополнительно к вариан-
							ту II в каждый момент
	IV			ДА	ДА	НЕТ	времени каждый ПО
							должен знать текущие
							координаты всех осталь-
							ных ПО.
Рефлексивная	V			ДА	ДА	ДА	Как в варианте IV.
модель		ПО первого типа		ДА	НЕТ	НЕТ	Как в варианте II.
Адаптивная	VI	второго	типа	НЕТ	ДА	ДА	второго типа должен
							Дополнительно к вариан-
							ту I в каждый момент
							времени каждый ПО
		ПО					знать текущие координа-
							ты всех ПО первого типа.

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

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

Результаты имитационного моделирования. Рассмотрим сле-

дующую имитационную модель, реализованную в среде AnyLogic

к.т.н. В.О. Корепановым. Выберем K0 = 100, N = 7, ci = 0,25, p = 0.5,

361

δ = 0.03. Начальные положения ПО, ЦО, сенсоры и линии уровня суммарного «сигнала» изображены на Рис. 87.

Рис. 87. Начальное расположение ПО, ЦО (звездочка), сенсоры (треугольники) и линии уровня суммарного «сигнала» (2)

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

Рис. 88. Пример результатов группового проникновения через систему обороны для варианта II

362

На Рис. 89 для вариантов I и II приведены зависимости эффек- тивности K (здесь и ниже каждая точка на графике эффективности является результатом усреднения по 200 испытаниям) действий группы ПО от вероятности p уничтожения обнаруженного ПО. Естественно, с ростом вероятности уничтожения эффективность уменьшается.

100
90
80
70
60
50
40
30
20
10
0
0	0,05	0,1	0,15	0,2	0,25	0,3	0,35	0,4	0,45	0,5	0,55	0,6	0,65	0,7	0,75	0,8	0,85	0,9	0,95	1

Рис. 89. Зависимость эффективности K действий группы ПО от вероятности p уничтожения обнаруженного ПО

для вариантов I (тонкая линия) и II (жирная линия)

Видно, что переход от варианта I к варианту II, т. е. рост интел-

лектуализации ПО за счет их анализа вероятности уничтожения в v0 τ-окрестности текущего положения, существенно повышает эф- фективность преодоления системы обороны (например, при p = 0.5 эффективность увеличивается с 38 до 53 – примерно на 40 %)

Отметим, что варианты I-II и III-V не сравнимы между собой,

так как в последних учитывается взаимодействие ПО и вероятности их обнаружения выше. Поэтому приведем Рис. 90, содержащий для вариантов III-V зависимости эффективности K действий группы ПО от вероятности p (меняющейся в диапазоне от 0.4 до 0.6) уничтоже- ния обнаруженного ПО при α = 0.03 (в варианте V считается, что рефлексирующими является половина ПО).

363

50
48
46
44
42
40
38
36
34
32
30
0,4	0,42	0,44	0,46	0,48	0,5	0,52	0,54	0,56	0,58	0,6

Рис. 90. Зависимость эффективности K действий группы ПО от вероятности p уничтожения обнаруженного ПО

для вариантов III (пунктирная линия), IV (тонкая линия)

и V (жирная линия)

Видно, что, опять же, рост интеллектуализации ПО повышает эффективность преодоления системы обороны (вариант V является самым эффективным, далее идет вариант IV, затем вариант III).

На Рис. 91 приведена зависимость эффективности K действий группы ПО от значений параметра α, отражающего взаимовлияние ПО.

60
50
40
30
20
10
0
0	0,5	1	1,5	2	2,5	3

Рис. 91. Зависимость эффективности K действий группы ПО от значений параметра α

364

Обозначим через K* {0, 1, … , K0} число рефлексирующих агентов. График зависимости K(K*) при α = 0.25 приведен на Рис. 92.

41
40,5
40
39,5
39
38,5
38
37,5
37
36,5
0	10	20	30	40	50	60	70	80	90	100

Рис. 92. Зависимость эффективности K действий группы ПО

от числа рефлексирующих агентов K*

Видно, что с ростом доли рефлексирующих агентов эффектив- ность действий группы ПО увеличивается. Более того, «выживае- мость» рефлексирующих ПО выше – среднее число рефлексирую- щих ПО, достигших ЦО, больше, чем нерефлексирующих (причем в рассматриваемой имитационной модели, например, при 200 испыта-

ниях и равном числе рефлексирующих и нерефлексирующих агентов эта оценка статистически значима).

Приведем также результаты имитационного моделирования для адаптивной модели. Пусть вероятность уничтожения обнаруженного ПО равна 0,5. На Рис. 93 представлена зависимость числа ПО, достигших цели, от числа ПО второго типа (горизонтальные линии соответствуют на Рис. 89 эффективностям, равным соответственно 53,74 и 37,97) для двух случаев – когда все ПО движутся одновременно (нижняя кривая) и когда сначала оборону преодолевают ПО первого типа, а потом уже начинают двигаться ПО второго типа (верхняя кривая).

Видно, что 80 % ПО второго типа обеспечивают в рассматри- ваемом примере почти такую же эффективность, что и использова- ние только дорогостоящих ПО первого типа.

365

	55
	50
Эффективность	45
	40
	35
	0	10	20	30	40	50	60	70	80	90	100
					Число ПО второго типа

Рис. 93. Зависимость эффективности K действий группы ПО

от числа ПО второго типа

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

наделение ПО возможностью учета параметров системы обороны и прогнозирования и/или анализа поведения других ПО повышает

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

задачи придется оптимизировать баланс между этими критериями и собственно эффективностью проникновения через систему обороны.

Многообещающим представляется рассмотрение модификаций предложенных моделей за счет варьирования условий обнаруже- ния/поражения и процедур планирования ПО своих траекторий.

Например,	возможен следующий вариант. Обозначим через
R0(x, y) =	max r(q, w) – максимальный из рисков обнаружения

(q,w) s ( x,y )

отдельного ПО, находящихся на расстоянии, не большем D, от точки

(x, y); через N(x, y) = # {j | (xj, yj) Î s (x, y)} – число ПО, находящихся в D-окрестности точки (x, y). «Кооперативность» учтем следующим

образом: будем считать, что, если N(q, w) ³ Kmax (имеется «критиче-

366

ская масса»), то все ПО, находящиеся в области s (q, w), будут обна- ружены с вероятностью R0(q, w) и в случае обнаружения гарантиро- ванно уничтожены. Назовем эту модель моделью критической мас- сы. Введем следующее правило планирования подвижными объектами своих траекторий. В каждый период времени для ПО, находящегося в точке (x, y) проверяется условие N(u, v) ³ Kmax, где точка (u, v) определяется выражением (4). Если это условие не вы- полнено, то выполняется Шаг 1. Если условие N(u, v) ³ Kmax выпол- нено, то все ПО, находящиеся в области s (x, y), уничтожаются с вероятностью R0(x, y), а с вероятностью 1 – R0(x, y) продолжают движение. В данной модели рефлексирующий ПО может прогнози- ровать поведение других ПО и в случае, если он вычисляет, что в результате своих действий в соответствии с Шагом 2 он попадет в область, где окажется критическая масса ПО, то он стремится избе- жать попадания в эту область.

Перспективным также представляется:

1)рассмотрение синхронизации и/или минимизации времени поражения ЦО отдельными ПО;

2)введение зависимости вероятности обнаружения ПО от их числа и скорости;

3)введение зависимости вероятности уничтожения ПО от их числа, координат и/или скорости;

4)использование, быть может в качестве эвристик, известных результатов о свойствах оптимальных траекторий одиночных ПО;

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

6)исследование более сложных разбиений агентов на ранги рефлексии и учет их взаимной информированности;

7)получение аналитических решений для различных частных случаев задачи о диффузной бомбе.

367

4.26.2. Игра полковника Блотто

Игрой полковника Блотто (ИПБ) называется игра двух лиц, в которой игроки однократно, одновременно и независимо (не зная выбора оппонента) распределяют свои ограниченные ресурсы между конечным числом объектов (полей сражений или объектов защи- ты/нападения, одновременных конкурсов/аукционов, групп избира- телей и т.п. – см. обзор в [65]). Данная модель является канониче- ским (и одним из первых) примером приложения теории игр к военному делу [103].

Обозначим через N = {1, …, n} множество объектов, через x = (x1, …, xn) – действие первого игрока, через y = (y1, …, yn) – дей- ствие второго игрока, где xi ³ 0 (yi ³ 0) – количество ресурса, выде-

ленного первым (вторым) игроком на i-ый объект, i = 1,n . Ограни-

ченность ресурсов отражена условиями

(1) åxi £ Rx, å yi £ Ry.

i N i N

Аукционная модель. В рамках аукционной модели победу на объекте одерживает игрок, выделивший на него большее количество ресурсов (в случае равенства ресурсов каждый из игроков одержива- ет победу с вероятностью 1/2). Ценность i-го объекта для первого (второго) игрока обозначим через Xi (Yi). Тогда выигрыши игроков в аукционной модели будут определяться следующим образом:

(2) fx(x, y) = åXi I (xi	> yi ) +	1	åXi I (xi	= yi ) ,
i N		2	i N		1
	fy(x, y) = åYi I( yi			> xi ) +		åYi I(xi = yi ) ,
			i N		2	i N

где I(×) – функция-индикатор. Более общим является случай, когда ограничения типа (1) отсутствуют, но из выигрыша (2) вычитаются затраты, монотонные по суммарному количеству использованного игроком ресурса.

Случаи n = 1 и n = 2 являются тривиальными. Действительно, при n = 1 побеждает игрок, обладающий бóльшим количеством ресурса (в случае равенства ресурсов победа каждого равновероят- на). При n = 2 оптимальной стратегией каждого игрока является

приоритетное выделение ресурса на наиболее ценный для него объект.

368

Простейшим является симметричный (Xi = Yi, i Î N, Rx = Ry) ва- риант дискретной (ресурсы игроков дискретны) игры полковника Блотто, являющейся матричной игрой (с нулевой суммой).

Вероятностная модель. В вероятностной модели ИПБ вероят-

ность px(xi, yi) победы первого игрока на i-ом объекте не зависит от других объектов и «пропорциональна» количеству выделенного им на этот объект ресурса и «обратно пропорциональна» взвешенной сумме ресурсов, выделенных на этот объект обоими игроками, на- пример:

			α	(x )ri
	(3) px(xi, yi) =		i		i		, py(xi, yi) = 1 – px(xi, yi),
		α	(x )ri		+ ( y	)ri
		i	i		i			αi
	где ri Î (0; 1], αi > 0, px(xi					= 0, yi = 0) =				. Содержательно, коэф-
								αi +1

фициенты {αi} позволяют соизмерять эффективности использования игроками ресурсов на одном и том же объекте.

Выигрыши игроков в вероятностной модели определяются как математическое ожидание суммарного выигрыша, то есть следую- щим образом:

(4) Fx(x, y) = åXi px (xi , yi ) , Fy(x, y) = åYi py (xi , yi ) .

i N i N

Равновесием Нэша в чистых стратегиях (x*, y*) является пара векторов, удовлетворяющих условиям (1), таких, что " (x, y), удов- летворяющих условиям (1), выполнено

(5) Fx(x*, y*) ³ Fx(x, y*), Fy(x*, y*) ³ Fy(x*, y).

Вероятностная модель в определенном смысле «проще», чем аукционная – единственным равновесием Нэша для случая Xi = Yi = Сonst, ri = 1, αi = 1, i Î N, Rx ¹ Ry является использование игроками чистых стратегий, заключающихся в равном распределе- нии имеющихся у них ресурсов между объектами (см. обзор и ссыл-

ки в [65, 103]).

При Xi = Yi = Vi, αi = ri = 1, i Î N выражения для равновесных действий и выигрышей примут вид (см. обзор и ссылки в [65, 103]):

(6) xi* = VVi Rx , yi* = VVi Ry , i Î N,

369

*	*		R	x	*	*	Ry
(7) Fx(x	, y ) =				V, Fy(x	, y ) =		V,
			Rx + Ry				Rx + Ry
	n
где V = åVi		, то есть игроки делят свой ресурс пропорционально

i=1

ценности объектов и получают выигрыш, пропорциональный их суммарным ресурсам. Отметим, что при этом равновесные действия каждого из игроков зависят только от «их собственных» параметров

– так, например, действия первого игрока x* не зависят от суммарно- го количества ресурса Ry у второго игрока и т.п.

Стратегическая рефлексия в ИПБ. Рассмотрим аспекты стра-

тегической рефлексии для ИПБ. Пусть Xi = Yi = Vi, αi = ri = 1, i N, тогда равновесные действия игроков и их выигрыши в рамках веро- ятностной модели определяются выражениями (6) и (7) соответст- венно. Использование концепции равновесия Нэша, как прогнози- руемого устойчивого исхода некооперативной игры, подразумевает, что параметры игры являются общим знанием. ИПБ в рамках веро- ятностной модели описывается, во-первых, кортежем (N, Rx, Ry, {Vi}), включающим множество объектов, ограничения на ресурсы игроков и ценности объектов для игроков. Во-вторых, необходимо задать «правила игры» – вероятности выигрыша (3) и целевые функции (4), стремление к максимизации которых отражает рациональность поведения игроков. Условно можно считать, что информационная рефлексия соответствует отсутствию общего зна-

ния относительно количеств ресурсов игроков и ценностей для них объектов, а стратегическая рефлексия – относительно принципов принятия игроками решений.

Из выражения (7)	следует, что, в частности, если Ry > Rx, то
i N выполнено x*	< y* , то есть по критерию (2) первый игрок
i	i

проигрывает второму игроку на всех объектах. Рациональный игрок при этом может задуматься, правильно ли он действует, и, быть может, пересмотреть свои принципы принятия решений.

Обозначим через BRx(y) = (u1 y1 + ε, …, un yn + ε) – вектор наи- лучшего в смысле критерия (2) ответа первого игрока на выбор вторым игроком вектора действий y, где n-мерный вектор u = (u1,…, un) является решением следующей задачи о ранце:

370