Об игровой задаче поиска движущихся объектов для модели полумарковского типа

Розглянуто проблему переслідування на багатовимірній цілочисленній решітці у випадку, коли положення та швидкість втікача утворюють процес напівмарківського типу. Отримано формулу перехідної ймовірності для вкладеного марківського ланцюга. Знайдено формулу перехідної ймовірності для неоднорідного ма...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2006
Автори:	Дзюбенко, К.Г., Чикрий, A.A.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2006
Назва видання:	Проблемы управления и информатики
Теми:	Проблемы динамики управляемых систем
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/206888
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Об игровой задаче поиска движущихся объектов для модели полумарковского типа / К.Г. Дзюбенко, A.A. Чикрий // Проблемы управления и информатики. — 2006. — № 5. — С. 5-15. — Бібліогр.: 1 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-206888
record_format	dspace
spelling	irk-123456789-2068882025-09-27T00:10:45Z Об игровой задаче поиска движущихся объектов для модели полумарковского типа Про ігрову задачу пошуку рухомих об’єктів для моделі напівмарківського типу On game problem of search for moving objects for а model of semi-Markovian type Дзюбенко, К.Г. Чикрий, A.A. Проблемы динамики управляемых систем Розглянуто проблему переслідування на багатовимірній цілочисленній решітці у випадку, коли положення та швидкість втікача утворюють процес напівмарківського типу. Отримано формулу перехідної ймовірності для вкладеного марківського ланцюга. Знайдено формулу перехідної ймовірності для неоднорідного марківського ланцюга, що описує положення втікача. Виведено формулу для ймовірності невиявлення до заданого моменту часу. Як приклад для спеціального виду розподілу стратегій переслідуваного розглянуто оптимізацію ймовірності виявлення до моменту 2. A pursuit problem on multidimensional integer lattice is considered for the case when position and velocity of the evader constitute a process of semiMarkovian type. A formula for transition probability of the embedded Markov chain is obtained. А formula is found for the transition probability for the nonhomogenous Markov chain that describes motion of the evader. А formula is derived for the probability of nondetection before certain moment of time. Optimization of the probability of detection before moment 2 for a special type of distribution of the evader’s strategies is considered as an example. 2006 Article Об игровой задаче поиска движущихся объектов для модели полумарковского типа / К.Г. Дзюбенко, A.A. Чикрий // Проблемы управления и информатики. — 2006. — № 5. — С. 5-15. — Бібліогр.: 1 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/206888 518.9 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Проблемы динамики управляемых систем Проблемы динамики управляемых систем
spellingShingle	Проблемы динамики управляемых систем Проблемы динамики управляемых систем Дзюбенко, К.Г. Чикрий, A.A. Об игровой задаче поиска движущихся объектов для модели полумарковского типа Проблемы управления и информатики
description	Розглянуто проблему переслідування на багатовимірній цілочисленній решітці у випадку, коли положення та швидкість втікача утворюють процес напівмарківського типу. Отримано формулу перехідної ймовірності для вкладеного марківського ланцюга. Знайдено формулу перехідної ймовірності для неоднорідного марківського ланцюга, що описує положення втікача. Виведено формулу для ймовірності невиявлення до заданого моменту часу. Як приклад для спеціального виду розподілу стратегій переслідуваного розглянуто оптимізацію ймовірності виявлення до моменту 2.
format	Article
author	Дзюбенко, К.Г. Чикрий, A.A.
author_facet	Дзюбенко, К.Г. Чикрий, A.A.
author_sort	Дзюбенко, К.Г.
title	Об игровой задаче поиска движущихся объектов для модели полумарковского типа
title_short	Об игровой задаче поиска движущихся объектов для модели полумарковского типа
title_full	Об игровой задаче поиска движущихся объектов для модели полумарковского типа
title_fullStr	Об игровой задаче поиска движущихся объектов для модели полумарковского типа
title_full_unstemmed	Об игровой задаче поиска движущихся объектов для модели полумарковского типа
title_sort	об игровой задаче поиска движущихся объектов для модели полумарковского типа
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2006
topic_facet	Проблемы динамики управляемых систем
url	https://nasplib.isofts.kiev.ua/handle/123456789/206888
citation_txt	Об игровой задаче поиска движущихся объектов для модели полумарковского типа / К.Г. Дзюбенко, A.A. Чикрий // Проблемы управления и информатики. — 2006. — № 5. — С. 5-15. — Бібліогр.: 1 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT dzûbenkokg obigrovojzadačepoiskadvižuŝihsâobʺektovdlâmodelipolumarkovskogotipa AT čikrijaa obigrovojzadačepoiskadvižuŝihsâobʺektovdlâmodelipolumarkovskogotipa AT dzûbenkokg proígrovuzadačupošukuruhomihobêktívdlâmodelínapívmarkívsʹkogotipu AT čikrijaa proígrovuzadačupošukuruhomihobêktívdlâmodelínapívmarkívsʹkogotipu AT dzûbenkokg ongameproblemofsearchformovingobjectsforamodelofsemimarkoviantype AT čikrijaa ongameproblemofsearchformovingobjectsforamodelofsemimarkoviantype
first_indexed	2025-09-27T01:12:52Z
last_indexed	2025-09-28T01:09:21Z
_version_	1844468002225913856
fulltext	© К.Г. ДЗЮБЕНКО, A.A. ЧИКРИЙ, 2006 Проблемы управления и информатики, 2006, № 5 5 ПРОБЛЕМЫ ДИНАМИКИ УПРАВЛЯЕМЫХ СИСТЕМ УДК 518.9 К.Г. Дзюбенко, A.A. Чикрий ОБ ИГРОВОЙ ЗАДАЧЕ ПОИСКА ДВИЖУЩИХСЯ ОБЪЕКТОВ ДЛЯ МОДЕЛИ ПОЛУМАРКОВСКОГО ТИПА Рассматривается динамическая задача поиска на m-мерной целочисленной сетке с вероятностью обнаружения за фиксированное время как критерием каче- ства. В отличие от [1], убегающий имеет динамику полумарковского типа. Оп- тимизация процесса поиска сводится к исследованию минорантной и мажорант- ной игр. Пусть N и Z — множества всех натуральных и целых чисел соответственно, },0{0 NN = ZZZ m = ... — m-кратное прямое произведение множества це- лых чисел ).1( m Таким образом, в евклидовом пространстве mR выделена це- лочисленная сетка ,mZ по которой передвигаются скачками преследователь и убегающий, переходя из состояния в состояние в дискретные моменты времени .0Nt Пусть ),(tx ,0Nt и ),(ty ,0Nt — случайные последовательности, опи- сывающие положения преследующего и убегающего соответственно в момент t. Перенумеруем все возможные состояния из mZ для преследователя и убегающего: }.,{},{ NjyNixZ ji m == В дальнейшем будем отождествлять ix и i, jy и j, ., Nji  Вероятность нахож- дения преследователя в состоянии ix в момент t обозначается :)(tpi ),)(()( ii xtxPtp == ,Ni .0Nt Имеют место соотношения ,0)( tpi ,Ni ;0Nt ,1)( 1 =  =i i tp .0Nt Назовем распределенным состоянием преследователя вектор-столбец =)(tp ....)),(...,),(( T 1 tptp n= Будем считать, что закон изменения состояния преследова- теля задается равенством ),()1()1( tptUtp +=+ ,...,1,0=t где )(tU — стохасти- ческая переходная матрица со счетными множествами строк и столбцов. Ее эле- менты играют роль параметров управления и удовлетворяют условиям ,0)( 1 tuii ,, 1 Nii  ;0Nt (1) ,1)( 11 1  = = i ii tu ,Ni .0Nt (2) 6 ISSN 0572-2691 Вероятность нахождения убегающего в состоянии jy в момент t обозначает- ся :)(tq j ),)(()( jj ytyPtq == ,Nj  .0Nt При этом ,0)( tq j ,Nj  ;0Nt .,1)( 0 1 Nttq j j =  = Назовем распределенным состоянием убегающего вектор-столбец =)(tq ....)),(...,),(( T 1 tqtq n= Будем считать, что закон изменения состояния убегающего задается равенством ),()()1( tqtVtq =+ ,...,1,0=t где )(tV — стохастическая переходная матрица со счетными множествами строк и столбцов. Ее элементы играют роль параметров управления и удовлетворяют условиям ,0)( 1 tv jj ,, 1 Njj  ;0Nt (3)   = = 11 1)( j jj tv 1 , ,Nj  .0Nt (4) Пусть ijr — вероятность обнаружения убегающего преследователем, если преследователь находится в состоянии i, а убегающий — в состоянии j. Будем считать, что )(twij — совместная вероятность пребывания в момент t преследующего в ,)( ixtx = убегающего в jyty =)( и необнаружения убегающего преследующим до момента t ).,,( Njit  Положим ),0()0()0( jiij qpw = ., Nji  Эти величины априорно известны. Тогда ,)()()1)(()1( 1111 , tvturtwtw jj ji iiijijji  −=+ .0Nt (5) Условимся, что )(0 tW — вероятность обнаружения убегающего преследова- телем до момента времени t. Тогда ,)()( 1 0 , 0   − = = t s ji ijij swrtW .Nt  (6) Вектор ),()1()( tytyt −+= ,0Nt назовем скоростью убегающего в момент времени t. Пусть AI — индикатор события A (равен 1 в случае выполнения собы- тия A, 0 — в противном случае). Рассмотрим две последовательности случайных величин: ,:min 1 )}()1({         ==  = − k t ttn nIkt ,1n — момент n-й смены скорости убегающим 0( 0 t по предположению); ,))(),(( 1 nnnnn tttty −= + ,0Nn — время движения убегающего, начиная с момента ,nt из положения )( nty с посто- янной скоростью )( nt до момента 1+nt (следующей смены скорости). Предположим, что заданы не зависящие от n условные распределения веро- ятностей, удовлетворяющие следующим соотношениям: Проблемы управления и информатики, 2006, № 5 7 ),,)(/)((),( ttytytPyg nnn ==== ,, mZy  ,0Nt ;0Nn (7) .,,,, ),),((),)(,)(/))(),(((),,( 00 NnNtNlZy lvyPtttytylttyPlvyf m nnnnnnn  ======= (8) Таким образом, ),,( lyf  — безусловное распределение случайной величи- ны ),(  yn для любого .0Nn Случайный процесс ),(sz ,0s называется полумарковским, если суще- ствует случайная последовательность ,n ,0Nn такая, что: 1) 0n для любого ;0Nn 2) распределение n не зависит от n и зависит лишь от значений )( nsz и )( 1+nsz ,( 1 0  − = = n k kns );Nn 3) )(sz постоянны для ),,[ 1+ nn sss ;0Nn 4) ),( nsz ,Nn — однородная марковская цепь (называемая вложенной марковской цепью). В рассматриваемой модели полумарковскими не являются ни последователь- ность положений убегающего ),(ty 0Nt (она кусочно-линейна), ни последова- тельность скоростей убегающего (она кусочно-постоянна, но ее вложенная после- довательность ),( nt ,0n вообще говоря, не является марковской). Тем не ме- нее случайный процесс )),(),(( tty  ,0Nt и последовательность ,n ,0Nn удовлетворяют условиям, близким к полумарковским: 1) 0n для любого ;0Nn 2) для любого n распределение n не зависит от n и зависит лишь от значе- ний )( nty и )( nt ,( 1 0  − = = n k knt );Nn 3) )(t постоянны для ),,[ 1+ nn ttt ;0Nn 4) )(ty изменяются линейно со скоростью )( nt для ),,[ 1+ nn ttt ;0Nn 5) )),(),(( nn tty  ,0Nn — однородная марковская цепь. Свойства 1)–4) следуют из определений. Докажем свойство 5). Пусть  — евклидова норма в .mZ Утверждение 1. В предположениях (7), (8) вложенная последовательность )),(),(( nn tty  ,0Nn — однородная марковская цепь. Для любого 0Nn и для любых ,m k Zy  ,m k Z ,1,0 += nk переходная вероятность этой цепи при 0n имеет вид === ++++ )),())(),((/),())(),((( 1111 nnnnnnnn yttyyttyP );,(,, 11 1 ++ +           − = nn n nn nn yg yy yf при 0=n — ).,()),())(),((/),())(),((( 11}{1111 1 ++=++++ === + nnyynnnnnnnn ygIyttyyttyP nn 8 ISSN 0572-2691 Доказательство. В условиях утверждения при 0n имеем: ==== ++++ ),0),,())(),((/),())(),((( 1111 nkyttyyttyP kkkknnnn = == === = ++++ ),0),,())(),((( ),0),,())(),((),,())(),((( 1111 nkyttyP nkyttyyttyP kkkk kkkknnnn ===== ++++ ),0),,())(),((,)(/)(( 1111 nkyttyytytP kkkknnnn = == ===  ++ ),0),,())(),((( ),0),,())(),((,)(( 11 nkyttyP nkyttyytyP kkkk kkkknn ===== ++++ ),0),,())(),(/())(/)((( 1111 nkyttyytytPP kkkknnnn = == ===+  ++ + ),( ),0),,())(),((( ),0),,())(),((,( 11 1 nn kkkk kkkknnnn yg nkyttyP nkyttyyyP ).,(,,1,0),,( ))(),(()),())(),(( 11 1 1 // ++ + +           − =     −==     =         =  − = nn n nn nnkk kknnnn n nn n yg yy yfnky ttyytty yy PP При любом 0Nn аналогичное рассуждение верно и для условной вероят- ности для событий моментов nt и :1+nt === ++++ )),())(),((/),())(),((( 1111 nnnnnnnn yttyyttyP .),(,, 11 1 ++ +           − = nn n nn nn yg yy yf Тем самым доказаны и марковское свойство, и однородность цепи. Случай 0=n рассматривается аналогично, но учитывается, что ====+ + ),0),,())(),((,( 1 nkyttyyyP kkkknnnn .),0),,())(),(((}{ 1 nkyttyPI kkkkyy nn === =+ Соответственно в конечной формуле вместо          −  + n nn nn yy yf 1 ,, появля- ется .}{ 1 nn yyI =+ ■ Обозначим ),,(  yt случайное время от момента последней смены скорости для убегающего, находящегося в момент t в состоянии y и движущегося со ско- ростью v. Тогда для любых ,, Nji  :0Nt ===+= ))(/)1(()( 11 jjjj ytyytyPtv  = =−=−==+= l s jjjjjjjj syyytPsyyytytyytyP 0 .)),,(()),,(,)(/)1(( 111 (9) Проблемы управления и информатики, 2006, № 5 9 Положим для краткости ,)1( 11 jjsjj syysa −+= (10) . 11 jjjj yyb −= (11) Найдем выражения для вероятностей, входящих в (9). Для любых 0, Nst  )( st  имеем: ==−==+ )),,(,)(/)1(( 11 syyytytyytyP jjjjj ,)()(/)()1(( 111 syyystysyyystyP jjjjjj −−=−−−=+−= =−−−−=  })),)(({}({ 11 0 syysyyystt jjjjj n nn  = −==− −==−=− =     0 0 )),((),)(( )),((),)(,)(( 111 1111 n jjsjjnnsjj n jjsjjnnsjjjj sbaPsttastyP sbaPsttastybstP . ),)(( ),)((),)(/)(( 0 0 1 111     −== −==−=== = n nsjjn n nsjjnnsjjnjjn sttatyP sttatyPsttatybtP Выше учитывалось, что: 1) события },{ sttn −= 0Nt , несовместны; 2) события },)(,)({ 11 sttastybst nsjjjj −==−=− и }),({ 11 sba jjsjjn  не- зависимы; 3) события },)({ 1 sttasty nsjj −==− и }),({ 11 sba jjsjjn  независимы; 4)   += = 1 ),,()),(( 1111 sl jjsjjjjsjjn lbafsbaP не зависит от n. Используя определение ),,( yg получаем, что ,),()),,(,)(/)1(( 1111 jjsjjjjjjj bagsyyytytyytyP ==−==+ ,st  ., 0Nst  (12) Итак, одна из неизвестных вероятностей, входящих в (9), найдена. Далее, для любых 0, Nst  :)( st  =                 −−−−== ==−    0 }),)(({}{ )),,(( 11 1 n jjjjjnn jjj syysyyysttP syyytP .),,()()),(()( 0 10 1111     += −==−== n sl jjsjjn n jjsjjnn lbafsttPsbaPsttP Таким образом,     += −===− 0 1 .),,()()),,(( 111 n sl jjsjjnjjj lbafsttPsyyytP (13) 10 ISSN 0572-2691 В дальнейшем для удобства записи потребуются следующие обозначения: ,)...,,()( 10 −= nn  ,)...,,()( 10 −= nn  ,)...,,()( 10 −= nyyny  :)...,,{( 10 −= nnV },1,0, −= nkZ m k ,,1,0,:)...,,()( 1 0 10         =−==  − = − n k kknn tnkNtT },1,0,,:)...,,{())(),(( 110 −=+== +− nkyyZyyynnY kkkk m knn  ,Nn .Nt  Тогда для любых 0, Nst  :)( st  +=         −=+=−= = − = − = =  =   }{ 1 1 0 }{}{ 0 ))(),(()( ts st n n k kkktsts n n IstttyPIIsttP   − = −−−− −  ===+ st n nnnn stTn ts ttyttyPI n 1 11110000 )()( }{ )))(),((...,,))(),(((     − =  −  = =   += st n Vn stTn nnYny tsts n n n yyPII 1 )( )()( 0 ))(),(()( }{}{ ))0((    .))(,)(/),(())(/)(( 1 0     ===== − = kk n k kkkkkkkkkk tytyyPytytP Первые два равенства получены из определений случайных величин ),,( n последнее равенство получено повторным применением формулы полной вероят- ности. Учтем, что ==== ))(,)(/))(),((( kkkkkkkk tytyttyP =======   =0 )(),)(,)(/))(),((( t kkkkkkkkkk ttPtttytyttyP ),,,()(),,( 0 kkk t kkkk yfttPyf ===   = .0Nk Итак, для всех 0, Nst  :)( st  +=−= =  =  }{}{ 0 )( tsts t k IIsttP  − =− − = = 1 0 0 ))(),(()()()()(1 .),,(),())0(( n k kkkkk nnYnystTnVn st n yfygyyP nnn  (14) Осталось подставить (14) в (13), (13) и (12) — в (9), учесть (10) и (11), чтобы получить формулу для переходной вероятности неоднородной марковской цепи, описывающей положение убегающего. Проблемы управления и информатики, 2006, № 5 11 Утверждение 2. В предположениях (7) и (8) для всех ,0Nt для всех Njj 1, переходная вероятность для положения убегающего имеет вид +     −−+      −−+= =  += =   }{}{ 1 0 ),,)1(( ),)1(()( 11 111 tsts sl jjjj jjjj t s jj IIlyysyysf yysyysgtv .),,(),())0(( 1 0 0 ))(),(()()()()(1         =  − =− − = n k kkkkk nnYnystTnVn st n yfygyyP nnn  (15) Подстановка (15) в (5) приведет к формуле для вероятности необнаружения до момента .1+t Утверждение 3. В предположениях (7) и (8) для всех ,0Nt для всех ,1i ,1 Nj  совместная вероятность необнаружения убегающего преследователем до момента 1+t и пребывания в момент 1+t преследователя в , 1i x убегающего — в , 1j y имеет вид −−+−=+  = ),)1(()()1)(()1( 11111 0, jjjj t s iiijij ji ji yysyysgturtwtw +     −−+      =  +=  }{}{ 1 ),,)1(( 11 tsts sl jjjj IIlyysyysf .),,(),())0(( 1 0 0 ))(),(()()()()(1         =  − =− − = n k kkkkk nnYnystTnVn st n yfygyyP nnn  Рассмотрим задачи оптимизации вероятности обнаружения к моменту 2: ),2(maxmin 0 )0()0( W uv =+ ),2(minmax 0 )0()0( W vu =− где согласно (5) и (6) .)0()0()1)(0()0()2( 1010110000 1100 0000 00 ,,,, 0 jjiijijiji jiji jiji ji vurrwrwW −+=  Введем обозначение для симплексного множества, построенного по данному подмножеству натуральных чисел:         ===  Ak kkkk sAksAksNksAS 1;,0;,0:},{)( для любого .NA  Используем следующий известный факт. Лемма. Пусть 0klc для всех ;, Nlk  ,,,0:}{ NlkxxX klkl      = .,1     = l kl Nkx Тогда .maxmax ,}{ kl lk k l klkl Xx cxc kl  =  При этом доставляющие 12 ISSN 0572-2691 максимум значения аргумента }{ * klx описываются соотношениями )),((* kLSxk  ,Nk  где множество },max:{maxarg)( kl l klkl l cclckL === .Nk  Применяя лемму, получаем следующее утверждение. Утверждение 4. При ограничениях (1), (2) на ),(U (3), (4) на )(V выполнено ).0()1()0(max)0()2(max 10 10 110000 0 1 00 0000 ,, 0 )0( jj jj jijiji i iji jiji u vrrwrwW  −+= (16) При этом доставляющие максимум управления преследователя описываются соотношениями ,))),0(,(()0( 00 * 0 NiviISui  где ),0()1()0(maxarg))0(,( 10 10 110000 1 , 0 jj jj jijiji i vrrwviI  −= .0 Ni  )))0(,(( 0 viIS — это множество лучших ответов преследователя на стратегию убегающего. Минимизация выражения (16) по )0(v в общем случае связана с за- труднениями, поэтому ограничимся случаем управлений убегающего с распреде- лениями специального вида. Пример. Рассматривается преследование на плоскости )2( =m со следую- щими распределениями вида (7), (8) для убегающего: ,)5,0(),( }{}{ 21 EE IaaIyg  −+= ,, 2Zy  (17) где )},0,1(),0,1{(1 −=E )},1,0(),1,0{(2 −=E ];5,0,0[a ,),,( 1−= lqplyf ,Nl  ., 2Zy  (18) Подставляя (17) и (18) в (15), получаем: −+=  = −− ))5,0(()( 0 }{}{ 21111 t s EyyEyyjj jjjj IaaItv       += − =  −  = − =+      1 1 )( )()( 0}{}{ 1 ))0((( 2 0 sl st n Vn stTn Zy tsts l n n yyPIIqp   +     −    −+= =     −+ = = −− − − =    }{}{ 0 }{}{ 1 1 0 }{}{ 1 ))5,0(( )))5,0(( 2111 21 tsts t s s EyyEyy n k EE II p p qIaaI qpIaaI jjjj k kk =                     − −− −  − = = −−++ st n nnNn nstnnnnn i ii pq n st aa nnnn n 1 , 4321 0 4321 1 1 )5,0( !!!! ! −+= −− ))5,0(( }{}{ 2111 EyyEyy jjjj IaaI Проблемы управления и информатики, 2006, № 5 13 =                       − −− −+−+++  − = − =  st n n nsts t s ts t p q n st aaaappIp 10 }{ 1 1 )))5,0()5,0(( ))5,0(( }{}{ 2111 EyyEyy jjjj IaaI −− −+= =               ++  − = −−1 0 1 1 t s st tt p q p p q p ))5,0(( }{}{ 2111 EyyEyy jjjj IaaI −− −+= =         − − + p p p q p t t t 1 1 1 ,)5,0( }{}{ 2111 EyyEyy jjjj IaaI −− −+= ,0Nt ., 1 Njj  Эти выкладки, с одной стороны, подтверждают интуитивное представление о виде переходной вероятности в данном случае, с другой, являются определенной проверкой для выражения (15). Итак, ,)5,0()( }{}{ 21111 EyyEyyjj jjjj IaItv −− −+= ,0Nt ,, 1 Njj  .,, ),)5,0(()()1()()1( 110 }{}{ , 2111111 NjiNt IaaIturtwtw EyyEyy ji iiijijji jjjj  −+−=+ −− (19) Выражение )2(0W принимает вид ).)5,0(( )0()1()0()0()2( }{}{ ,,,, 0 201101 10 1100 110000 00 0000 EyyEyy ii jiji jijiji ji jiji jjjj IaaI urrwrwW −− −+ −+=  Используем соотношение (19) совместно с (16) для нахождения :+ +== + 00 0000 , 0 )0()0( )0()2(maxmin ji jiji uv rwW ).)5,0(()1)(0(maxmin }{}{ ,]5,0,0[ 201101 10 110000 0 1 EyyEyy jj jijiji i ia jjjj IaaIrrw −−  −+−+  Пусть минимум в выражении для + достигается при некотором значении a параметра распределения скорости убегающего (это значение априорно из- вестно): ).)5,0(()1)(0(maxminarg }{}{ ,]5,0,0[ 201101 10 110000 0 1 EyyEyy jj jijiji i ia jjjj IaaIrrwa −−  −+−=  Тогда доставляющие минимакс управления преследователя и убегающего описываются соотношениями: ,)5,0()0( }{}{ 20110110 EyyEyyjj jjjj IaIav −− −+= ;, 10 Njj  )),(()0( 0 * 0 iISui  ,0 Ni  14 ISSN 0572-2691 где ),)5,0(()1)(0(maxarg)( }{}{ , 0 201101 10 110000 1 EyyEyy jj jijiji i jjjj IaIarrwiI −− −+−=  .0 Ni  Теперь приступим к рассмотрению :− +=  00 0000 , 0 )0( )0()2(min ji jiji v rwW =−+−+ −−   ))5,0()(0()1)(0(min }{}{ ,,,]5,0,0[ 20110110110000 1100 EyyEyyiijijiji jijia jjjj IaaIurrw     +−+= −   }{ ,,,]5,0,0[, 20110110000 110000 0000 )0()1()0(5,0min)0( Eyyiijijiji jijiaji jiji jj Iurrwrw     −−+ − }{ ,,, 10110110000 1100 )0()1)(0( Eyyiijijiji jiji jj Iurrwa .)0()1)(0( }{ ,,, 20110110000 1100         −− − Eyyiijijiji jiji jj Iurrw Последнее выражение линейно по a, минимум достигается при 0=a либо при ,5,0=a поэтому +=  00 0000 , 0 )0( )0()2(min ji jiji v rwW     −+ − ,)0()1)(0(min 2 1 }{ ,,, 10110110000 1100 Eyyiijijiji jiji jj Iurrw .)0()1)(0( }{ ,,, 20110110000 1100     − − Eyyiijijiji jiji jj Iurrw Тогда +== − 00 0000 , 0 )0()0( )0()2(minmax ji jiji vu rwW     −+ − ,)0()1)(0(minmax 2 1 }{ ,,,)0( 10110110000 1100 Eyyiijijiji jijiu jj Iurrw .)0()1)(0( }{ ,,, 20110110000 1100     − − Eyyiijijiji jiji jj Iurrw Максимизация последнего выражения затруднена, требует использования численных методов. Проблемы управления и информатики, 2006, № 5 15 К.Г. Дзюбенко, А.О. Чикрій ПРО ІГРОВУ ЗАДАЧУ ПОШУКУ РУХОМИХ ОБ’ЄКТІВ ДЛЯ МОДЕЛІ НАПІВМАРКІВСЬКОГО ТИПУ Розглянуто проблему переслідування на багатовимірній цілочисленній решітці у випадку, коли положення та швидкість втікача утворюють процес напівмар- ківського типу. Отримано формулу перехідної ймовірності для вкладеного мар- ківського ланцюга. Знайдено формулу перехідної ймовірності для неоднорідно- го марківського ланцюга, що описує положення втікача. Виведено формулу для ймовірності невиявлення до заданого моменту часу. Як приклад для спеціаль- ного виду розподілу стратегій переслідуваного розглянуто оптимізацію ймовір- ності виявлення до моменту 2. K.G. Dzyubenko, A.A. Chikriy ON GAME PROBLEM OF SEARCH FOR MOVING OBJECTS FOR А MODEL OF SEMI-MARKOVIAN TYPE A pursuit problem on multi-dimensional integer lattice is considered for the case when position and velocity of the evader constitute a process of semi-Markovian type. A formula for transition probability of the embedded Markov chain is obtained. А formula is found for the transition probability for the nonhomogenous Markov chain that describes motion of the evader. А formula is derived for the probability of non-detection before certain moment of time. Optimization of the probability of de- tection before moment 2 for a special type of distribution of the evader’s strategies is considered as an example. 1. Чикрий А.А., Дзюбенко К.Г. Билинейные марковские процессы поиска движущихся объек- тов // Проблемы управления и информатики. — 1997. — № 1. — С. 92–107. Получено 26.05.2006

Об игровой задаче поиска движущихся объектов для модели полумарковского типа

Репозитарії

Схожі ресурси