Автореферат (Рандомизированные алгоритмы в задачах мультиагентного взаимодействия)
Описание файла
Файл "Автореферат" внутри архива находится в папке "Рандомизированные алгоритмы в задачах мультиагентного взаимодействия". PDF-файл из архива "Рандомизированные алгоритмы в задачах мультиагентного взаимодействия", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст из PDF
Íà ïðàâàõ ðóêîïèñèÈâàíñêèé Þðèé Âëàäèìèðîâè÷ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÛÅ ÀËÃÎÐÈÒÌÛ Â ÇÀÄÀ×ÀÕÌÓËÜÒÈÀÃÅÍÒÍÎÃÎ ÂÇÀÈÌÎÄÅÉÑÒÂÈß01.01.09 äèñêðåòíàÿ ìàòåìàòèêà èìàòåìàòè÷åñêàÿ êèáåðíåòèêàÀÂÒÎÐÅÔÅÐÀÒäèññåðòàöèè íà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÑàíêò-Ïåòåðáóðã2016Ðàáîòà âûïîëíåíà â Ñàíêò-Ïåòåðáóðãñêîì ãîñóäàðñòâåííîì óíèâåðñèòåòå.Íàó÷íûé ðóêîâîäèòåëü:äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîð ÃÐÀÍÈ×ÈÍ Îëåã Íèêîëàåâè÷Îôèöèàëüíûå îïïîíåíòû:ÙÅÐÁÀÊΠÏàâåë Ñåðãååâè÷äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ÔÃÁÓÍ Èíñòèòóò ïðîáëåì óïðàâëåíèÿèì.
Â. À. Òðàïåçíèêîâà ÐÀÍ,ãëàâíûé íàó÷íûé ñîòðóäíèêÓÒÈÍÀ Íàòàëüÿ Âàëåðüåâíà,êàíäèäàò ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ÔÃÁÎÓ ÂÏÎ ¾Ñàíêò-Ïåòåðáóðãñêèéãîñóäàðñòâåííûé àðõèòåêòóðíî-ñòðîèòåëüíûéóíèâåðñèòåò¿,äîöåíòÂåäóùàÿ îðãàíèçàöèÿ:Ôåäåðàëüíîå ãîñóäàðñòâåííîå áþäæåòíîåîáðàçîâàòåëüíîå ó÷ðåæäåíèå âûñøåãîîáðàçîâàíèÿ ¾Ñàìàðñêèé ãîñóäàðñòâåííûéòåõíè÷åñêèé óíèâåðñèòåò¿Çàùèòà ñîñòîèòñÿ 2016 ãîäà â÷àñîâ íà çàñåäàíèè äèññåðòà-öèîííîãî ñîâåòà Ä 212.232.29 íà áàçå Ñàíêò-Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïî àäðåñó: 199178, Ñàíêò-Ïåòåðáóðã, 10 ëèíèÿ Â.Î., ä. 33/35, àóä.
74.Ñ äèññåðòàöèåé ìîæíî îçíàêîìèòüñÿ â Íàó÷íîé áèáëèîòåêå èì. Ì. Ãîðüêîãî ÑàíêòÏåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïî àäðåñó: 199034, Ñàíêò-Ïåòåðáóðã,https://disser.spbu.ru/files/disser2/Óíèâåðñèòåòñêàÿ íàá., ä. 7/9 è íà ñàéòådisser/WkmwNghWHB.pdfÀâòîðåôåðàò ðàçîñëàí 2016 ã.Ó÷åíûé ñåêðåòàðüäèññåðòàöèîííîãî ñîâåòà Ä 212.232.29,äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîðÂ.
Ì. ÍåæèíñêèéÎáùàÿ õàðàêòåðèñòèêà ðàáîòûÀêòóàëüíîñòü òåìû. ïîñëåäíåå âðåìÿ âñå áîëüøåå âíèìàíèå óäåëÿåòñÿ çà-äà÷àì ðàñïðåäåëåííîãî âçàèìîäåéñòâèÿ â ñåòÿõ è óïðàâëåíèÿ â ñåòåâûõ äèíàìè÷åñêèõ ñèñòåìàõ. Èíòåðåñ ê òåìàòèêå óïðàâëåíèÿ â äèíàìè÷åñêèõ ñåòÿõ âûçâàíïðèëîæåíèÿìè â ðàçëè÷íûõ îáëàñòÿõ, âêëþ÷àÿ, íàïðèìåð, îáìåí èíôîðìàöèåé âìíîãîïðîöåññîðíûõ ñåòÿõ, ëîãèñòè÷åñêèå ñåòè, ïðîèçâîäñòâåííûå ñåòè, ñåíñîðû èáåñïðîâîäíûå ñåòè, ñêîîðäèíèðîâàííîå äâèæåíèå ÁÏËÀ, ïîäâîäíûõ îáúåêòîâ è ìîáèëüíûõ ðîáîòîâ, ðàñïðåäåëåííûå ñèñòåìû óïðàâëåíèÿ ýëåêòðè÷åñêèõ ñåòåé, ñëîæíûå êðèñòàëëè÷åñêèå ðåøåòêè è íàíîñòðóêòóðíûå îáúåêòû.
 ðàáîòàõ ×. Àáäàëëû (C. Abdallah), Ð. Ï. Àãàåâà, Á. Ð. Àíäðèåâñêîãî, Ï. Àíòñàêëèñà (P. Antsaklis),Ä. Áàèëëåóëà (J. Baillieul), Ð. Â. Áåðäà (R.W. Beard), Ô. Áóëëî (F. Bullo, Ò. Âèêñåêà(T. Vicsek), Â. À. Âèòòèõà, Â. È. Ãîðîäåöêîãî, È. À. Êàëÿåâà, Ä. Êîðòåñà (J. Cortes),Ô.
Ëüþèñà (F. Lewis), À. Ñ. Ìàòâååâà, À. Ñ. Ìîðñà (A. S. Morse), Ð. Ì. Ìþððåÿ(R. M. Murray), Ð. Îëôàòè-Ñàáåðà (R. Olfati-Saber), Â. Ðåíà (W. Ren), Ã. À. Ðæåâñêîãî, Ã. Òàííåðà (H. Tanner), À. Ë. Ôðàäêîâà, Ì. Õóàíãà (M. Huang), Ï. Þ. ×åáîòàðåâà è äðóãèõ çàëîæåíû îñíîâû òåîðåòè÷åñêîãî îïèñàíèÿ ìåòîäîâ àíàëèçà è ñèíòåçà äåöåíòðàëèçîâàííîãî àäàïòèâíîãî ìóëüòèàãåíòíîãî óïðàâëåíèÿ, îáñóæäàþòñÿìíîãî÷èñëåííûå ïîòåíöèàëüíûå ïðàêòè÷åñêèå ïðèëîæåíèÿ â óïðàâëåíèè ñëîæíûìè ïðîèçâîäñòâåííûìè, ýíåðãåòè÷åñêèìè ñèñòåìàìè.Í.
Î. Àìåëèíà, Ä. Àðìáðóñòåð (D. Armbruster), À. Ãëàøåíêî, È. Ãðà÷åâ, Ñ. Èíîçåìöåâ, È. À. Êàëÿåâ, À. Ñ. Ìèõàéëîâ, Ñ. Ý. Ïàðñåãîâ, À. Â. Ïðîñêóðíèêîâ,Ï. Î. Ñêîáåëåâ, Ï. Ñ. Ùåðáàêîâ è äð. àêòèâíî èçó÷àëè àëãîðèòìû óïðàâëåíèÿâ ñåòÿõ, óçëû êîòîðûõ âûïîëíÿþò îïðåäåëåííûå äåéñòâèÿ ïàðàëëåëüíî. Ïîäîáíûå ñåòåâûå ñèñòåìû ïðèìåíÿþòñÿ â âû÷èñëèòåëüíûõ, ïðîèçâîäñòâåííûõ ñåòÿõ,ñåòÿõ îáñëóæèâàíèÿ, òðàíñïîðòíûõ è ëîãèñòè÷åñêèõ ñåòÿõ. Íåñìîòðÿ íà îáúåì ðàáîò ïî òåìàòèêå óïðàâëåíèÿ äåöåíòðàëèçîâàííûìè ñèñòåìàìè, óäîâëåòâîðèòåëüíûåðåøåíèÿ ïðåäëîæåíû äëÿ îãðàíè÷åííîãî êëàññà çàäà÷.
Òàêèå ôàêòîðû, êàê ïåðåêëþ÷åíèÿ òîïîëîãèè ñâÿçåé, ïîìåõè è çàäåðæêè ïðè èçìåðåíèè ñîñòîÿíèé àãåíòîâçíà÷èòåëüíî ïîâûøàþò ñëîæíîñòü ðåøåíèÿ çàäà÷. Äîñòàòî÷íî ïðîñòûå àäàïòèâíûå àëãîðèòìû ÷àñòî äåìîíñòðèðóþò óäîâëåòâîðèòåëüíóþ ïðîèçâîäèòåëüíîñòü, íîîñòàþòñÿ îòêðûòûìè âîïðîñû èõ òåîðåòè÷åñêîãî îáîñíîâàíèÿ è äîñòèæåíèÿ îïòèìàëüíîé ïðîèçâîäèòåëüíîñòè. Êàê ïðàâèëî, ïðè ïîñòàíîâêå çàäà÷è ïðåäïîëàãàåòñÿ,÷òî âñå çàäàíèÿ, âûïîëíÿåìûå ñèñòåìîé, îäèíàêîâî âàæíû äëÿ èñïîëíåíèÿ.Íà ïðàêòèêå âî âðåìÿ ðàáîòû ñèñòåìû îäíè çàäàíèÿ èìåþò áîëåå âûñîêóþ âàæ-3íîñòü, ÷åì äðóãèå. Ýòî ìîæåò áûòü âûçâàíî íåîáõîäèìîñòüþ âûïîëíåíèÿ ñèñòåìíûõ çàïðîñîâ äëÿ ïîääåðæàíèÿ ðàáîòû âñåé ñèñòåìû; íåêîòîðûå çàäàíèÿ ìîãóòèìåòü áîëåå âûñîêóþ ñðî÷íîñòü, â òî âðåìÿ êàê äëÿ äðóãèõ çàäàíèé âðåìÿ èõ âûïîëíåíèÿ â ñèñòåìå íå òàê êðèòè÷íî; ó ñèñòåìû ìîãóò áûòü íåñêîëüêî ãðóïï ïîëüçîâàòåëåé, êîòîðûì òðåáóåòñÿ ðàçíûé óðîâåíü îáñëóæèâàíèÿ.
 òàêèõ ñèòóàöèÿõäëÿ äèôôåðåíöèàöèè çàäàíèé ðàçíûõ êëàññîâ ââîäÿò ïðèîðèòåòû, êîòîðûå ó÷èòûâàþòñÿ ïðè ïðèíÿòèè ðåøåíèé îá î÷åðåäíîñòè âûáîðà çàäàíèé íà èñïîëíåíèå. ïîñëåäíåå âðåìÿ íàáèðàåò ïîïóëÿðíîñòü êîíöåïöèÿ èíòåðíåòà âåùåé ñîåäèíåíèÿ ðàçëè÷íûõ îáúåêòîâ â ñåòü äëÿ îðãàíèçàöèè èõ âçàèìîäåéñòâèÿ, ïðîâîäÿòñÿ ìíîãî÷èñëåííûå ýêñïåðèìåíòû ïî îðãàíèçàöèè âçàèìîäåéñòâèÿ ãðóïï ìîáèëüíûõ ðîáîòîâ, íàáëþäàåòñÿ âñå âîçðàñòàþùåå ïðèìåíåíèå áåñïèëîòíûõ ëåòàòåëüíûõàïïàðàòîâ, êàê â âîåííûõ, òàê è â ãðàæäàíñêèõ öåëÿõ. Ïåðå÷èñëåííûå òåíäåíöèè àêòóàëèçèðóþò ðàçðàáîòêó è ïðèìåíåíèå ìóëüòèàãåíòíîãî ïîäõîäà â óïðàâëåíèè ãðóïïîé îáúåêòîâ, ïîñêîëüêó, ñ îäíîé ñòîðîíû, ïîäîáíûìè ãðóïïàìè çà÷àñòóþíåýôôåêòèâíî óïðàâëÿòü öåíòðàëèçîâàííî, ñ äðóãîé îáúåêòû â òàêèõ ãðóïïàõñïîñîáíû ñàìîñòîÿòåëüíî îðãàíèçîâûâàòü è ïîääåðæèâàòü âçàèìîäåéñòâèå âíóòðèãðóïïû. ïîäîáíûõ ñèñòåìàõ óñòðîéñòâà, êàê ïðàâèëî, îáëàäàþò îãðàíè÷åííûì çàïàñîì ýíåðãèè, â ñâÿçè ñ ÷åì âñòàåò ïðîáëåìà îðãàíèçàöèè âçàèìîäåéñòâèÿ àãåíòîââ ñèñòåìå, ó÷èòûâàþùåãî ðàñõîäû íà îáìåí äàííûìè ïî ñåòè.Îáîçíà÷åííûå ïðîáëåìû è òåíäåíöèè ïîäòâåðæäàþò àêòóàëüíîñòü òåìû äèññåðòàöèîííîãî èññëåäîâàíèÿ.Öåëüþ ðàáîòûÿâëÿåòñÿ ðàçðàáîòêà è èññëåäîâàíèå àëãîðèòìîâ ïîâûøåíèÿýôôåêòèâíîñòè äåöåíòðàëèçîâàííîãî ïåðåðàñïðåäåëåíèÿ ìåæäó óçëàìè âû÷èñëèòåëüíîé ñåòè î÷åðåäåé çàäà÷ ñ ðàçíûìè óðîâíÿìè ïðèîðèòåòîâ â óñëîâèÿõ ïåðåìåííîé ñòðóêòóðû ñâÿçåé, ïîìåõ è çàäåðæåê ïðè ïåðåäà÷å èíôîðìàöèè.
Äëÿ äîñòèæåíèÿ ýòîé öåëè áûëè ïîñòàâëåíû è ðåøåíû ñëåäóþùèå çàäà÷è:1) èññëåäîâàòü ïðèìåíèìîñòü àëãîðèòìà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ ðåøåíèÿçàäà÷è äèôôåðåíöèðîâàííîãî êîíñåíñóñà â äåöåíòðàëèçîâàííîé âû÷èñëèòåëüíîé ñåòè ñ çàäàíèÿìè ðàçíûõ ïðèîðèòåòîâ â óñëîâèÿõ ñëó÷àéíî èçìåíÿþùåéñÿñòðóêòóðû ñâÿçåé, ïîìåõ è çàäåðæåê ïðè ïåðåäà÷å èíôîðìàöèè ïî êàíàëàìñâÿçè;2) îïòèìèçèðîâàòü âåëè÷èíó ðàçìåðà øàãà ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ,ïî êîòîðîìó ôóíêöèîíèðóåò ñèñòåìà â çàäàííûõ óñëîâèÿõ;43) èññëåäîâàòü ïðèìåíèìîñòü àëãîðèòìà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ ðåøåíèÿçàäà÷è äèôôåðåíöèðîâàííîãî êîíñåíñóñà ïðè íàëè÷èè óñðåäíåííûõ îãðàíè÷åíèé íà èñïîëüçîâàíèå ñâÿçåé âíóòðè ñåòè. Îïòèìèçèðîâàòü âåëè÷èíó ðàçìåðà øàãà ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ ïðè íàëè÷èè îãðàíè÷åíèé íàèñïîëüçîâàíèå ñâÿçåé âíóòðè ñåòè;4) ðàçðàáîòàòü ïàêåò ïðèêëàäíûõ ïðîãðàìì äëÿ ìîäåëèðîâàíèÿ ïðîöåññà ïåðåðàñïðåäåëåíèÿ çàäàíèé ðàçíûõ ïðèîðèòåòîâ ìåæäó àãåíòàìè â ñåòè.Ìåòîäû èññëåäîâàíèÿ.
 äèññåðòàöèè èñïîëüçóþòñÿ ìåòîäû òåîðèé èññëåäîâàíèÿ îïåðàöèé, óïðàâëåíèÿ, ãðàôîâ, âåðîÿòíîñòåé è ìàòåìàòè÷åñêîé ñòàòèñòèêè;ïðèìåíÿåòñÿ ñòîõàñòè÷åñêàÿ àïïðîêñèìàöèÿ, ðàíäîìèçèðîâàííûå àëãîðèòìû, èìèòàöèîííîå ìîäåëèðîâàíèå.Îñíîâíûå ðåçóëüòàòû.  õîäå âûïîëíåíèÿ ðàáîòû ïîëó÷åíû ñëåäóþùèå íàó÷íûåðåçóëüòàòû:1) ïðåäëîæåíà ðàíäîìèçèðîâàííàÿ ìîäèôèêàöèÿ àëãîðèòìà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ äîñòèæåíèÿ äèôôåðåíöèðîâàííîãî êîíñåíñóñà â âû÷èñëèòåëüíîéñåòè ñ çàäàíèÿìèíåñêîëüêèõ ïðèîðèòåòîâ â óñëîâèÿõ ñëó÷àéíîãî èçìåíåíèÿ ñâÿçåé, ïðè ïîìåõàõ è çàäåðæêàõ â êàíàëàõ ñâÿçè. Óñòàíîâëåíû óñëîâèÿ äîñòèæåíèÿ äèôôåðåíöèðîâàííîãî ñðåäíåêâàäðàòè÷åñêîãîε-êîíñåíñóñàâ ýòèõ óñëîâèÿõ.
Ïîëó-÷åíà îöåíêà îòêëîíåíèÿ çíà÷åíèé íà óçëàõ â ñåòåâîé ñèñòåìå îò êîíñåíñóñíîãîçíà÷åíèÿ;2) ïîëó÷åíà îöåíêà îïòèìàëüíîãî ðàçìåðà øàãà àëãîðèòìà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ ñèñòåìû â óñëîâèÿõ ñëó÷àéíîãî èçìåíåíèÿ ñâÿçåé, ïîìåõ è çàäåðæåêâ êàíàëàõ ñâÿçè;3) ïðåäëîæåíà ðàíäîìèçèðîâàííàÿ ìîäèôèêàöèÿ àëãîðèòìà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ çàäà÷è äîñòèæåíèÿ äèôôåðåíöèðîâàííîãî êîíñåíñóñà â ñèñòåìåñ çàäàíèÿìè ðàçíûõ ïðèîðèòåòîâ ïðè íàëè÷èè ñòîèìîñòíûõ îãðàíè÷åíèé íàèñïîëüçîâàíèå ñâÿçåé äëÿ ïåðåäà÷è èíôîðìàöèè âíóòðè ñèñòåìû. Ïîëó÷åíàîöåíêà îïòèìàëüíîãî ðàçìåðà øàãà àëãîðèòìà ëîêàëüíîãî ãîëîñîâàíèÿ ïðèòàêèõ îãðàíè÷åíèÿõ;4) ðàçðàáîòàí ïàêåò ïðèêëàäíûõ ïðîãðàìì äëÿ ìîäåëèðîâàíèÿ ïðîöåññà ïåðåðàñïðåäåëåíèÿ çàäàíèé ðàçíûõ ïðèîðèòåòîâ ìåæäó àãåíòàìè â ìóëüòèàãåíò-5íîé ñåòè â óñëîâèÿõ ñëó÷àéíîãî èçìåíåíèÿ ñâÿçåé, ïîìåõ è çàäåðæåê â êàíàëàõñâÿçè.Íàó÷íàÿ íîâèçíà.
Âñå îñíîâíûå íàó÷íûå ðåçóëüòàòû äèññåðòàöèè ÿâëÿþòñÿ íîâûìè.Òåîðåòè÷åñêàÿ öåííîñòü è ïðàêòè÷åñêàÿ çíà÷èìîñòü.Òåîðåòè÷åñêàÿ öåí-íîñòü ðåçóëüòàòîâ çàêëþ÷àåòñÿ, âî-ïåðâûõ, â ïðåäëîæåíèè îñíîâàííîé íà àëãîðèòìå ëîêàëüíîãî ãîëîñîâàíèÿ ðàíäîìèçèðîâàííîé óïðàâëÿþùåé ñòðàòåãèè äëÿ ðåøåíèÿ çàäà÷è äèôôåðåíöèðîâàííîãî êîíñåíñóñà è ïîëó÷åíèè óñëîâèé åå ðàáîòîñïîñîáíîñòè â ìóëüòèàãåíòíîé ñèñòåìå, îáëàäàþùåé èçìåíÿþùåéñÿ ñòðóêòóðîé ñâÿçåé,ïðè íàëè÷èè ïîìåõ è çàäåðæåê ïðè ïåðåäà÷å äàííûõ âíóòðè ñèñòåìû.
