Hamma bir vaqtda bir xil narsani bilmasligi mumkin

Kundalik hayotda ko'plab tizimlar bitta qaror qabul qiluvchi tomonidan boshqarilmaydi. Bir nechta odam, sensor, robot, boshqaruv markazi yoki dasturiy agent bir xil tizim bo'yicha qaror qabul qilishi mumkin.

Masalan:

Robotlar jamoasi bir xil omborda ishlashi mumkin.
Energiya tarmog'ida turli boshqaruv markazlari turli hududlarni kuzatishi mumkin.
Avtonom transport vositalari flotida har bir transport o'z sensorlarini ko'radi, lekin boshqa transport vositalarining ma'lumotini kechikish bilan oladi.
Mudofaa, aloqa yoki favqulodda vaziyatlarni kuzatish tarmog'ida turli kuzatuv nuqtalari turli ma'lumotlarga ega bo'lishi mumkin.

Bunday tizimlarda eng katta muammo shudir:

Har bir qaror qabul qiluvchi tizimning butunini ko'rmaydi.

Agent o'z o'lchovlarini darhol biladi, lekin boshqa agentlar ko'rgan ma'lumotlarni keyinroq o'rganishi mumkin. Ba'zi ma'lumotlar umumiy bo'ladi, ba'zilari shaxsiy qoladi. Bunday holatda yaxshi qaror qabul qilish faqat «nima ko'rdim?» savoliga emas, balki «boshqalar nima biladi, nima hali bilmaydi, nima kechikish bilan o'rganadi?» savoliga ham bog'liq.

Ushbu maqolaning asosiy muammosi aynan shudir.

POMDP nima degani?

Maqolaning asosiy tushunchalaridan biri POMDP'dir. Bu Partially Observable Markov Decision Process deganining qisqartmasi. O'zbek tilida «qisman kuzatiladigan Markov qaror jarayoni» deb tarjima qilish mumkin.

Buni soddalashtirsak:

Tizimning haqiqiy holati bor, lekin qaror qabul qiluvchi bu holatni to'liq ko'ra olmaydi. Buning o'rniga shovqinli yoki yetishmayotgan kuzatuvlarni oladi. Qaror qabul qiluvchi bu kuzatuvlar bilan tizim qaysi holatda bo'lishi mumkinligiga oid ishonch shakllantiradi va shunga ko'ra harakat tanlaydi.

Bitta qaror qabul qiluvchili POMDP'da bu allaqachon qiyin. Lekin ushbu maqolada muammo yanada murakkablashadi: bir nechta qaror qabul qiluvchi bor va har biri turli ma'lumotga ega.

Shuning uchun mavzu «markazlashmagan POMDP» ga aylanadi.

Kechikish bilan ma'lumot almashish nimani anglatadi?

Maqolada T-qadam kechikish bilan ma'lumot almashish o'rganiladi. Buning ma'nosi shudir:

Qaror qabul qiluvchi o'z yangi kuzatuvini darhol biladi. Biroq boshqa qaror qabul qiluvchilar bu ma'lumotni faqat T vaqt qadamidan keyin o'rganadi.

Masalan, T = 2 bo'lsa, bir agent hozir ko'rgan ma'lumot boshqalar uchun ikki qadamdan keyin umumiy ma'lumotga aylanadi.

Bunday holatda har bir agentning ma'lumoti ikki qismga bo'linadi:

Shaxsiy ma'lumot: Agent hozir biladigan, lekin boshqalar hali bilmagan ma'lumot.
Umumiy ma'lumot: Kechikish muddati tugagani uchun endi barcha agentlar biladigan ma'lumot.

Bu ajratish muhim. Chunki qaror qabul qiluvchi ham o'z yangi ma'lumotini, ham hammaning biladigan umumiy o'tmishini ishlatib qaror qabul qiladi.

Maqoladagi asosiy ma'lumot formulasi nimani aytadi?

Maqoladagi ma'lumot tuzilmasi sodda tarzda shunday o'qiladi:

Ik,t = Λk,t ∪ Δt(K)

Bu formulada:

Ik,t, k raqamli agentning t vaqtidagi umumiy ma'lumotidir.
Λk,t, o'sha agentning shaxsiy ma'lumotidir.
Δt(K), barcha agentlar umumiy baham ko'rgan kechikkan ma'lumotdir.

Kundalik til bilan:

Agentning qarori = o'z shaxsiy ma'lumoti + hammaning biladigan umumiy ma'lumoti asosida quriladi.

Bu sodda ko'rinadi, lekin ko'p agentli qaror muammolarida muhim ajratishdir. Chunki qaysi ma'lumot shaxsiy, qaysi biri umumiy ekanligini bilmasdan to'g'ri qaror modeli qurib bo'lmaydi.

Qaror strategiyasi nima degani?

Maqoladagi yana bir asosiy ifoda shudir:

Uk,t = γk,t(Ik,t)

Bu formulaning sodda ma'nosi:

Agentning harakati o'sha paytda egalik qilgan ma'lumotiga ko'ra tanlanadi.

Bu yerda:

Uk,t, k raqamli agentning t vaqtidagi harakatidir.
γk,t, agentning qaror strategiyasidir.
Ik,t, agentning o'sha paytdagi ma'lumot tuzilmasidir.

Ya'ni agent tasodifiy qaror qabul qilmaydi; qo'lidagi ma'lumotga ko'ra strategiya qo'llaydi.

Lekin muammo shudir: vaqt o'tishi bilan ma'lumot tarixi kattalashadi. Agar agent butun o'tmishni o'z holicha saqlashga majbur bo'lsa, muammo tezda hisoblanmaydigan holga keladi. Shuning uchun ma'lumotni siqish kerak.

Ma'lumotni siqish nima uchun muhim?

Qaror qabul qiluvchi barcha o'tgan kuzatuvlar, o'tgan harakatlar va boshqa agentlardan kechikish bilan kelgan barcha ma'lumotlarni saqlayotganini tasavvur qilaylik. Vaqt o'tishi bilan bu ma'lumot to'plami kattalashadi.

Bu ikki tomondan muammoli:

Birinchisi, qaror hisoblashi qiyinlashadi.
Ikkinchisi, strategiya ta'rifi kattalashayotgan o'tmishga bog'liq bo'ladi.

Klassik POMDP nazariyasida bu muammo «ishonch holati» bilan hal qilinadi. Qaror qabul qiluvchi butun o'tmishni saqlash o'rniga tizim qaysi holatda bo'lishi mumkinligiga oid ehtimollik taqsimotini saqlaydi.

Ushbu maqola ham shunga o'xshash g'oyani markazlashmagan tizimlarga ko'chirishga harakat qiladi. Lekin bu yerda bitta ishonch yetarli emas. Chunki har bir agent turli shaxsiy va umumiy ma'lumotga ega.

Tadqiqotning asosiy g'oyasi: uch qismli ma'lumot holati

Maqolaning eng muhim natijasi, har bir agent kechikishli ma'lumot tuzilmasini uch qismga siqishtira olishini aytishidir.

1. Shaxsiy posterior taqsimot
Agent o'z ma'lumotiga ko'ra tizimning haqiqiy holati va boshqa agentlar ko'rmagan shaxsiy ma'lumotlar haqida shakllantirgan ehtimollik ishonchidir.

Sodda til bilan:
«Mening ko'rganlarimga ko'ra tizim va boshqa agentlarning shaxsiy tomonlari haqida nima deb ishonaman?»

2. Umumiy posterior taqsimot
Barcha agentlarning umumiy ma'lumotiga ko'ra tizim haqida shakllangan umumiy ehtimollik ishonchidir.

Sodda til bilan:
«Hammamiz biladigan umumiy o'tmishga ko'ra tizim haqida umumiy taxminimiz nima?»

3. Agentning qisqa shaxsiy ma'lumot komponenti
Hali faqat agentning o'zida bo'lgan yangi shaxsiy ma'lumot qismidir.

Sodda til bilan:
«Hozir faqat men biladigan, lekin hamma hali o'rganmagan qisqa ma'lumot nima?»

Bu uchlik tuzilma, agentlarga cheksiz kattalashayotgan o'tmishga qaramay qaror ishlab chiqish imkonini beradigan nazariy siqishni taqdim etadi.

«Shaxsiy ishonch» va «umumiy ishonch» farqi nima?

Ushbu maqolani tushunishning eng muhim yo'li shaxsiy ishonch bilan umumiy ishonch farqini anglashdir.

Omborda ishlaydigan ikki robotni tasavvur qilaylik.

Robot A oldida to'siq ko'rdi. Robot B buni hali bilmaydi. Lekin ikkalasi ham bir necha soniya oldin baham ko'rilgan xarita ma'lumotini biladi.

Bu holatda:

Umumiy ishonch ikkala robot ham biladigan eski xarita va eski kuzatuvlardan tashkil topadi.
Robot A ning shaxsiy ishonchi o'z yangi to'siq kuzatuvini ham o'z ichiga oladi.
Robot B ning shaxsiy ishonchi esa o'zi ko'rgan boshqa narsalarni o'z ichiga oladi.

Robot A qaror qabul qilganda ham umumiy xaritani, ham o'z yangi ma'lumotini ishlatadi. Lekin Robot B hali nimani bilmasligini ham hisobga olish kerak bo'lishi mumkin.

Maqola taklif qilgan ramka bunday murakkab ma'lumot asimmetriyalarini matematik jihatdan boshqarishga harakat qiladi.

Dinamik dasturlash nima uchun ishlatiladi?

Dinamik dasturlash katta qaror muammolarini vaqt qadamlariga bo'lib yechishga xizmat qiladigan usuldir. Bugungi qaror kelajakdagi ehtimoliy xarajatlar yoki foydalarga ta'sir qiladi. Shuning uchun qaror muammosi orqaga yoki qadam-baqadam tahlil qilinadi.

Klassik bitta agentli POMDP'da dinamik dasturlash ishonch holati orqali amalga oshirilishi mumkin. Bu juda muhim, chunki agent butun o'tmishni emas, faqat joriy ishonch holatini ishlatib qaror qabul qiladi.

Ushbu maqolaning hissasi markazlashmagan va kechikish bilan ma'lumot almashish bo'lgan tizimlarda ham shunga o'xshash dinamik dasturlash tuzilmasini qurishga harakat qilishidir.

Lekin klassik yondashuvdan farqi bor: bitta umumiy qiymat funksiyasi o'rniga har bir agent uchun alohida xarajat-davom funksiyalari va alohida DP tenglamalari ishlatiladi.

Nima uchun bitta DP tenglamasi yetmasligi mumkin?

Oldingi ba'zi tadqiqotlar barcha agentlar uchun umumiy ma'lumotga asoslangan bitta dinamik dasturlash tenglamasidan foydalanishga harakat qilgan.

Bu yondashuv ba'zi maxsus holatlarda ishlay oladi. Biroq maqolaga ko'ra, ayniqsa uzoqroq kechikish bilan almashish holatlarida bu bitta tenglamaning muhim cheklovlari bor.

Chunki bitta umumiy ma'lumot tenglamasi har bir agentning o'z shaxsiy ma'lumoti va shaxsiy ishonchini yetarlicha ifodalamay qolishi mumkin. Bundan tashqari ba'zi eski yondashuvlarda optimizatsiya to'g'ridan-to'g'ri harakat fazosi o'rniga strategiya fazosida amalga oshiriladi. Bu ham muammoni og'irlashtiradi.

Ushbu maqola boshqacha yo'l taklif qiladi:

Har bir agent uchun o'z ma'lumot tuzilmasiga bog'liq alohida dinamik dasturlash tenglamasi qurish.

Shunday qilib har bir agent o'z harakat fazosida optimizatsiya qiladi. Bu klassik POMDP dinamik dasturlashiga yaqinroq tuzilma beradi.

Decentralized Team Equilibrium nima degani?

Maqoladagi muhim tushunchalardan biri «decentralized sequential team equilibrium»dir. Buni sodda tarzda «markazlashmagan ketma-ket jamoa muvozanati» deb tarjima qilish mumkin.

Bu yerda g'oya shudir:

Bir nechta agent bor. Hammasi umumiy jamoa maqsadini yaxshilashga harakat qiladi. Lekin har biri o'z ma'lumotiga ko'ra qaror qabul qiladi.

Bir agentning strategiyasi baholanayotganda boshqa agentlarning strategiyalari qat'iy ushlab turiladi. Keyin bu agent o'z strategiyasini yaxshilay oladimi-yo'qmi tekshiriladi.

Bu o'yin nazariyasidagi Nash muvozanati g'oyasiga o'xshaydi. Lekin muhim farq shudir: bu yerda agentlarning alohida manfaatlari emas, umumiy jamoa xarajati yoki jamoa maqsadi bor.

Ya'ni tizimning maqsadi «har kim o'z foydasini maksimal qilsin» emas, «har bir agent o'z ma'lumot chegarasi ichida umumiy jamoa maqsadi uchun eng yaxshi javob bersin» yondashuvidir.

Ajratish printsipi nimani anglatadi?

Maqolada «separation principle», ya'ni ajratish printsipi muhim natija sifatida ko'rib chiqiladi.

Klassik boshqaruv nazariyasida ajratish printsipi taxminan shuni aytadi:

Avval tizim holatini taxmin qil.
Keyin bu taxminga ko'ra boshqaruv qarorini qabul qil.

Ya'ni taxmin va boshqaruv tushuncha jihatdan ajratilishi mumkin.

Ushbu maqola markazlashmagan va kechikish bilan ma'lumot almashish bo'lgan tizimlarda buning yanada umumiy versiyasini taqdim etishga harakat qiladi.

Har bir agent avval shaxsiy va umumiy ma'lumot holatlarini yangilaydi. Keyin qarorini bu siqilgan ma'lumot holatlari orqali qabul qiladi.

Bu quyidagi tomondan muhim:

Agent qaror qabul qilish uchun butun xom o'tmishni saqlashi shart emas. Taxmin qilingan ma'lumot holatlari yetarli statistika sifatida ishlatilishi mumkin.

Formulalar bizga nima o'rgatadi?

Maqoladagi formulalar juda texnik ko'rinsa ham, o'quvchi uchun uchta asosiy g'oya olib keladi.

Birinchisi: Har bir agentning ma'lumoti shaxsiy va umumiy komponentlarga bo'linadi.
Bu kechikish bilan almashishning matematik ifodasidir.

Ikkinchisi: Har bir agentning harakati o'z ma'lumot holatiga bog'liq.
Ya'ni qaror strategiyasi agent nimani bilishiga cheklangan.

Uchinchisi: Shaxsiy va umumiy posterior taqsimotlar Markov usulida yangilanishi mumkin.
Bu butun o'tmishni saqlash o'rniga joriy ishonch holati bilan yurishni imkon qiladi.

Shuning uchun formulalar faqat abstract belgilar emas. Asosiy maqsad kattalashayotgan ma'lumot tarixini qaror uchun yetarli bo'lgan kichikroq qismlarga qisqartirishdir.

Tadqiqot nima deydi?

Tadqiqotning asosiy xabari shudir:

Markazlashmagan, qisman kuzatiladigan va kechikish bilan ma'lumot almashish bo'lgan qaror tizimlarida har bir agent qaror uchun kerakli ma'lumotni uch qismli tuzilmaga siqishtira oladi.

Bu uch qism:

• shaxsiy posterior taqsimot,
• umumiy posterior taqsimot,
• qisqa shaxsiy ma'lumot komponenti.

Tadqiqotchilar shuningdek bu ma'lumot holatlari bilan yangi dinamik dasturlash tenglamalari qurilishi mumkinligini va bu tenglamalar klassik markaziy POMDP dinamik dasturlashidagi ba'zi asosiy xususiyatlarni saqlab qolishini ta'kidlaydi.

Bu xususiyatlardan biri optimizatsiyaning strategiya fazosida emas, harakat fazosida amalga oshirilishidir. Bu nazariy jihatdan muhim, chunki strategiya fazosi ancha kattaroq va murakkabroq.

Yana bir muhim nuqta ma'lumot holatlarining Markov tipida yangilanishi mumkinligidir. Bu vaqt o'tishi bilan kattalashayotgan ma'lumot tarixi o'rniga boshqariladiganroq qaror o'zgaruvchilaridan foydalanish mumkinligini ko'rsatadi.

Bu nima uchun muhim?

Ushbu tadqiqot nazariy ko'rinsa ham zamonaviy texnologiyalar bilan kuchli bog'liqlikka ega.

Chunki ko'plab zamonaviy tizimlar markaziy emas:

Robot jamoalari birgalikda ishlaydi.
Avtonom transport vositalari flotlari ma'lumot almashadi.
Energiya tarmoqlari mintaqaviy boshqaruv markazlari bilan boshqariladi.
Taqsimlangan sensor tarmoqlari muhit, favqulodda vaziyat yoki xavfsizlikni kuzatadi.
Ko'p agentli sun'iy intellekt tizimlari umumiy vazifalarda qaror qabul qiladi.

Bu tizimlarda hamma hamma narsani bir vaqtda bilmaydi. Ma'lumot yetishmaydi, kechikadi yoki faqat mahalliy bo'lishi mumkin. Shuning uchun qaror qabul qilish nazariyasi faqat markaziy tizimlar uchun emas, ma'lumot asimmetriyasiga ega taqsimlangan tizimlar uchun ham rivojlantirilishi kerak.

Maqolaning ahamiyati shu qiyin muammoni yanada tartibli qiladigan matematik ramka taqdim etishidadir.

E'tibor berish kerak bo'lgan nuqtalar

Ushbu tadqiqot to'g'ridan-to'g'ri tayyor dastur, robot boshqaruv algoritmi yoki sanoat qo'llanmasi emas. Asosiy hissasi nazariy va matematik darajada.

Birinchidan, tadqiqot preprintdir. Hakam bahosidan o'tgan deb faraz qilinmasligi kerak.

Ikkinchidan, maqola umumiy dinamik dasturlash tenglamalari va ma'lumot holati tuzilmalarini taqdim etadi. Ularning katta haqiqiy tizimlarda hisoblash jihatidan qanchalik samarali qo'llanilishi alohida tadqiqot mavzusidir.

Uchinchidan, markazlashmagan POMDP muammolari allaqachon juda qiyin muammo sinflaridir. Ma'lumotni siqish tuzilmasi nazariy jihatdan muhim bo'lsa ham, amaliy algoritmlar uchun qo'shimcha yaqinlashuv usullari kerak bo'lishi mumkin.

To'rtinchidan, tadqiqot jamoa muvozanati va shaxs-shaxs optimal yondashuvi orqali yuradi. Bu har holatda to'liq global jamoa optimalini kafolatlash degani bo'lmasligi mumkin; ba'zi qo'shimcha shartlar kerak bo'lishi mumkin.

Beshinchidan, haqiqiy robotika, energiya, mudofaa, moliyaviy tarmoq yoki transport tizimlariga qo'llashdan oldin model taxminlari, ma'lumot kechikishlari, aloqa xatolari va xavfsizlik chegaralari alohida o'rganilishi kerak.

Xulosa

Ushbu tadqiqot ko'p agentli va markazlashmagan qaror tizimlarida muhim savolga javob qidiradi:

Agent butun o'tmishni saqlamasdan yetishmayotgan va kechikishli ma'lumot bilan qanday qaror qabul qila oladi?

Maqola taklif qilgan javob ma'lumotni uch asosiy qismga siqishdir: agentning shaxsiy ishonchi, hammamizning umumiy ishonchi va agentning qisqa shaxsiy ma'lumoti.

Bu ramka kechikish bilan ma'lumot almashish bo'lgan POMDP muammolari uchun yangi dinamik dasturlash tenglamalari va ajratish printsipini taqdim etadi. Tadqiqot to'g'ridan-to'g'ri amaliy qo'llanma da'vo qilmasa ham, kelajakdagi robot jamoalari, taqsimlangan sensor tarmoqlari va ko'p agentli sun'iy intellekt tizimlari uchun muhim nazariy yo'nalish ko'rsatadi.

Ushbu matnning eng sodda xabari shudir:

Taqsimlangan tizimlarda yaxshi qaror qabul qilish hamma narsani bilishdan emas; kim nimani bilishini to'g'ri umumlashtirishdan o'tishi mumkin.

Manba va usul eslatmasi

Bu kontent Charalambos D. Charalambous, Umarbek Guvercin va Seddik Djouadi tomonidan tayyorlangan «Private & Common Information States in Decentralized Team Equilibrium via Dynamic Programming for POMDPs with Delayed Sharing» nomli akademik ish asosida Verianla tahririy formatida mustaqil tayyorlangan.

Ish arXiv'da chop etilgan preprint hisoblanadi. Kontent ma'lumot va ta'lim maqsadida tayyorlangan. Boshqaruv tizimlari, robototexnika, muhim infratuzilma, mudofaa texnologiyalari, moliyaviy tizimlar yoki professional muhandislik qo'llanmalari uchun texnik maslahat o'rnini bosmaydi.