Si kila mtu hawezi kujua kitu kimoja kwa wakati mmoja

Katika maisha ya kila siku mifumo mingi haisimamiwi na mtengenezaji wa uamuzi mmoja. Watu wengi, sensa, roboti, kituo cha udhibiti au wakala wa programu wanaweza kufanya maamuzi juu ya mfumo huo huo.

Kwa mfano:

Timu ya roboti inaweza kufanya kazi katika ghala moja.
Katika mtandao wa nishati vituo tofauti vya udhibiti vinaweza kufuatilia maeneo tofauti.
Katika floti ya magari ya kujiendesha kila gari linaona sensa zake lakini hupokea taarifa za magari mengine kwa kuchelewa.
Katika mtandao wa ulinzi, mawasiliano au ufuatiliaji wa maafa vituo tofauti vya uchunguzi vinaweza kuwa na taarifa tofauti.

Katika mifumo kama hii tatizo kubwa ni hili:

Kila mtengenezaji wa uamuzi haoni mfumo wote.

Wakala hujui mara moja vipimo vyake, lakini wanaweza kujifunza baadaye taarifa zilizoonekana na wakala wengine. Baadhi ya taarifa huwa za pamoja, nyingine hubaki za kibinafsi. Katika hali hii uamuzi mzuri hautegemei tu swali «nimeona nini?», bali pia «wengine wanajua nini, bado hawajui nini, na watapata nini kwa kuchelewa?»

Hili ndilo tatizo kuu linalolishughulikia makala hii.

POMDP inamaanisha nini?

Mojapo muhimu kati ya makala ni POMDP. Hii ni kifupi cha Partially Observable Markov Decision Process. Kwa Kiswahili inaweza kutafsiriwa kama «mchakato wa uamuzi wa Markov unaoweza kuchunguzwa kwa sehemu».

Tukisilisha:

Mfumo una hali halisi, lakini mtengenezaji wa uamuzi hawezi kuuona hali hiyo kikamilifu. Badala yake hupokea uchunguzi wenye kelele au unaokosekana. Kwa uchunguzi huo hujenga imani kuhusu hali ambayo mfumo unaweza kuwa nayo na kuchagua hatua ipasavyo.

Katika POMDP yenye mtengenezaji mmoja wa uamuzi hii tayari ni ngumu. Lakini katika makala hii tatizo linazidi kuwa gumu: kuna wengenezaji wengi wa uamuzi na kila mmoja ana taarifa tofauti.

Kwa hiyo mada inakuwa «POMDP isiyosanifiwa kati».

Kushiriki taarifa kwa kuchelewa kunamaanisha nini?

Makala inachunguza kushiriki taarifa kwa kuchelewa kwa hatua T. Maana yake ni hii:

Mtengenezaji wa uamuzi hujua mara moja uchunguzi wake mpya. Lakini wengine hujifunza taarifa hii tu baada ya hatua T za muda.

Kwa mfano, ikiwa T = 2, taarifa ambayo wakala mmoja anaiona sasa huwa taarifa ya pamoja kwa wengine hatua mbili baadaye.

Katika hali hii taarifa ya kila wakala hugawanywa kwa sehemu mbili:

Taarifa ya kibinafsi: Taarifa ambayo wakala anajua sasa lakini wengine bado hawajui.
Taarifa ya pamoja: Taarifa ambayo sasa wakala wote wanajua kwa sababu muda wa kuchelewa umeisha.

Mgawanyo huu ni muhimu. Kwa sababu mtengenezaji wa uamuzi hutumia taarifa yake mpya na pia historia ya pamoja inayojulikana na wote kufanya uamuzi.

Fomula kuu ya taarifa katika makala inasema nini?

Muundo wa taarifa katika makala unaweza kusomwa kwa urahisi hivi:

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

Katika fomula hii:

Ik,t ni jumla ya taarifa ya wakala wa nambari k kwa wakati t.
Λk,t ni taarifa ya kibinafsi ya wakala huyo.
Δt(K) ni taarifa iliyochelewa inayoshirikiwa na wakala wote.

Kwa lugha ya kila siku:

Uamuzi wa wakala = unaojengwa juu ya taarifa yake ya kibinafsi + taarifa ya pamoja inayojulikana na wote.

Hii inaonekana rahisi, lakini ni mgawanyo muhimu katika matatizo ya uamuzi yenye wakala wengi. Kwa sababu bila kujua taarifa ipi ni ya kibinafsi na ipi ni ya pamoja huwezi kuunda modeli sahihi ya uamuzi.

Mkakati wa uamuzi unamaanisha nini?

Neno lingine kuu katika makala ni hili:

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

Maana rahisi ya fomula hii:

Hatua ya wakala huchaguliwa kulingana na taarifa aliyonayo wakati huo.

Hapa:

Uk,t ni hatua ya wakala wa nambari k kwa wakati t.
γk,t ni mkakati wa uamuzi wa wakala.
Ik,t ni muundo wa taarifa wa wakala kwa wakati huo.

Yaani wakala hafanyi uamuzi kwa nasibu; hutumia mkakati kulingana na taarifa aliyonayo.

Lakini tatizo ni hili: historia ya taarifa hukua kadri muda unavyopita. Ikiwa wakala lazima abebe historia yote kama ilivyo, tatizo linakuwa lisilohesabika haraka. Kwa hiyo unahitaji kufinyaza taarifa.

Kwa nini kufinyaza taarifa ni muhimu?

Hebu tufikirie mtengenezaji wa uamuzi anahifadhi uchunguzi wote uliopita, hatua zote zilizopita na taarifa zote zilizofika kwa kuchelewa kutoka kwa wakala wengine. Kadri muda unavyopita mkusanyiko huu wa taarifa unakua.

Hili lina matatizo mawili:

Kwanza, kuhesabu uamuzi kunakuwa ngumu zaidi.
Pili, ufafanuzi wa mkakati utategemea historia inayokua.

Katika nadharia ya klasiki ya POMDP tatizo hili hutatuliwa kwa «hali ya imani». Badala ya kuhifadhi historia yote, mtengenezaji wa uamuzi hubeba usambazaji wa uwezekano wa hali ambazo mfumo unaweza kuwa nazo.

Makala hii pia inajaribu kuhamisha wazo kama hilo kwenye mifumo isiyosanifiwa kati. Lakini hapa imani moja haitoshi. Kwa sababu kila wakala ana taarifa tofauti ya kibinafsi na ya pamoja.

Wazo kuu la utafiti: hali ya taarifa ya sehemu tatu

Tokeo muhimu zaidi la makala ni kwamba kila wakala anaweza kufinyaza muundo wake wa taarifa wenye kuchelewa kuwa sehemu tatu.

1. Usambazaji wa posterior wa kibinafsi
Ni imani ya uwezekano ambayo wakala huunda kuhusu hali halisi ya mfumo na taarifa za kibinafsi ambazo wakala wengine hawakuiona, kulingana na taarifa yake mwenyewe.

Kwa lugha rahisi:
«Kulingana na nilichoona, ninaamini nini kuhusu mfumo na pande za kibinafsi za wakala wengine?»

2. Usambazaji wa posterior wa pamoja
Ni imani ya uwezekano ya pamoja kuhusu mfumo iliyoundwa kulingana na taarifa ya pamoja ya wakala wote.

Kwa lugha rahisi:
«Kulingana na historia ya pamoja tunayojua, makadirio yetu ya pamoja kuhusu mfumo ni nini?»

3. Sehemu fupi ya taarifa ya kibinafsi ya wakala
Ni sehemu ya taarifa mpya ya kibinafsi ambayo bado iko kwa wakala pekee.

Kwa lugha rahisi:
«Taarifa fupi ambayo sasa mimi pekee naijua lakini wengine bado hawajajifunza ni nini?»

Muundo huu wa sehemu tatu hutoa kufinyaza kwa nadharia kunachoruhusu wakala kutoa uamuzi bila kutazama historia isiyo na kikomo inayokua.

Tofauti kati ya «imani ya kibinafsi» na «imani ya pamoja» ni nini?

Njia muhimu zaidi ya kuelewa makala hii ni kutambua tofauti kati ya imani ya kibinafsi na imani ya pamoja.

Hebu tufikirie roboti mbili zinazofanya kazi katika ghala.

Robot A aliona kizuizi mbele yake. Robot B bado haijui hili. Lakini zote mbili zinajua taarifa ya ramani iliyoshirikiwa sekunde chache zilizopita.

Katika hali hii:

Imani ya pamoja inajumuisha ramani ya zamani na uchunguzi wa zamani unaojulikana na roboti zote mbili.
Imani ya kibinafsi ya Robot A pia inajumuisha uchunguzi wake mpya wa kizuizi.
Imani ya kibinafsi ya Robot B inajumuisha mambo mengine aliyoyaona.

Robot A inapofanya uamuzi hutumia ramani ya pamoja na taarifa yake mpya. Lakini inaweza pia kuhitaji kuzingatia Robot B bado haijui nini.

Mfumo unaopendekezwa na makala hujaribu kusimamia kwa njia ya hisabati upotofu huu mgumu wa taarifa.

Kwa nini programu ya nguvu inatumika?

Programu ya nguvu ni mbinu ya kugawanya matatizo makubwa ya uamuzi kwa hatua za muda. Uamuzi wa leo unaathiri gharama au faida zinazowezekana za baadaye. Kwa hiyo tatizo la uamuzi huchambuliwa kurudi nyuma au hatua kwa hatua.

Katika POMDP ya klasiki yenye wakala mmoja programu ya nguvu inaweza kufanywa kupitia hali ya imani. Hii ni muhimu sana kwa sababu wakala hufanya uamuzi kwa kutumia hali ya imani ya sasa, si historia yote.

Mchango wa makala hii ni kujaribu kuunda muundo kama huo wa programu ya nguvu pia katika mifumo isiyosanifiwa kati na yenye kushiriki taarifa kwa kuchelewa.

Lakini kuna tofauti na mbinu ya klasiki: badala ya kazi moja ya thamani ya pamoja, hutumika kazi za gharama-endelea tofauti na milinganyo tofauti ya DP kwa kila wakala.

Kwa nini mlinganyo mmoja wa DP unaweza kutoshi?

Baadhi ya utafiti wa awali ulijaribu kutumia mlinganyo mmoja wa programu ya nguvu unaotegemea taarifa ya pamoja kwa wakala wote.

Mbinu hii inaweza kufanya kazi katika baadhi ya hali maalum. Lakini kulingana na makala, hasa katika hali za kushiriki kwa kuchelewa kwa muda mrefu, mlinganyo huu mmoja una mapungufu muhimu.

Kwa sababu mlinganyo mmoja wa taarifa ya pamoja unaweza kushindwa kuwakilisha vya kutosha taarifa ya kibinafsi na imani ya kibinafsi ya kila wakala. Zaidi ya hayo, katika mbinu zingine za zamani uboreshaji hufanywa katika nafasi ya mkakati badala ya nafasi ya hatua moja kwa moja. Hii pia inazidisha tatizo.

Makala hii inapendekeza njia tofauti:

Kuunda mlinganyo tofauti wa programu ya nguvu unaohusiana na muundo wa taarifa wa kila wakala.

Hivyo kila wakala hufanya uboreshaji katika nafasi yake ya hatua. Hii inatoa muundo unaokaribia zaidi programu ya nguvu ya klasiki ya POMDP.

Decentralized Team Equilibrium inamaanisha nini?

Mojapo muhimu kati ya makala ni «decentralized sequential team equilibrium». Kwa urahisi inaweza kutafsiriwa kama «usawa wa timu wa mlolongo usiosanifiwa kati».

Wazo hapa ni hili:

Kuna wakala wengi. Wote wanajaribu kuboresha lengo la pamoja la timu. Lakini kila mmoja hufanya uamuzi kulingana na taarifa yake.

Mkakati wa wakala mmoja unapotathminiwa, mikakati ya wengine inashikiliwa thabiti. Kisha huangaliwa kama wakala huyu anaweza kuboresha mkakati wake au la.

Hii inafanana na wazo la usawa wa Nash katika nadharia ya michezo. Lakini tofauti muhimu ni hii: hapa sio maslahi tofauti ya wakala, bali gharama ya pamoja ya timu au lengo la timu.

Yaani lengo la mfumo si «kila mtu aboreshe faida yake», bali «kila wakala atoe majibu bora zaidi kwa lengo la pamoja la timu ndani ya mipaka ya taarifa yake».

separation principle inamaanisha nini?

Katika makala «separation principle» inachukuliwa kama tokeo muhimu.

Katika nadharia ya klasiki ya udhibiti separation principle takriban husema hivi:

Kwanza kadiria hali ya mfumo.
Kisha fanya uamuzi wa udhibiti kulingana na makadirio hayo.

Yaani makadirio na udhibiti vinaweza kutenganishwa kwa dhana.

Makala hii inajaribu kutoa toleo la jumla zaidi la hili katika mifumo isiyosanifiwa kati na yenye kushiriki taarifa kwa kuchelewa.

Kila wakala kwanza husasisha hali za taarifa za kibinafsi na za pamoja. Kisha hufanya uamuzi kupitia hali hizi zilizofinyazwa za taarifa.

Hili ni muhimu kwa sababu hii:

Wakala hana haja kubeba historia yote ghafi ili kufanya uamuzi. Hali za taarifa zilizokadiriwa zinaweza kutumika kama takwimu za kutosha.

Formuli zinatuambia nini?

Ingawa formuli katika makala zinaonekana za kiufundi sana, zina mawazo matatu kuu kwa msomaji.

Kwanza: Taarifa ya kila wakala hugawanywa kuwa sehemu za kibinafsi na za pamoja.
Hii ni usemi wa hisabati wa kushiriki kwa kuchelewa.

Pili: Hatua ya kila wakala inategemea hali yake ya taarifa.
Yaani mkakati wa uamuzi umepunguzwa na kile wakala anachojua.

Tatu: Usambazaji wa posterior wa kibinafsi na wa pamoja unaweza kusasishwa kwa mtindo wa Markov.
Hii huruhusu kuendelea na hali ya imani ya sasa badala ya kubeba historia yote.

Kwa hiyo formuli si alama za dhahania tu. Lengo kuu ni kupunguza historia inayokua ya taarifa kuwa sehemu ndogo zinazotosha kwa uamuzi.

Utafiti unasema nini?

Ujumbe mkuu wa utafiti ni:

Katika mifumo ya uamuzi isiyosanifiwa kati, inayoweza kuchunguzwa kwa sehemu na yenye kushiriki taarifa kwa kuchelewa, kila wakala anaweza kufinyaza taarifa inayohitajika kwa uamuzi kuwa muundo wa sehemu tatu.

Sehemu hizi tatu ni:

• usambazaji wa posterior wa kibinafsi,
• usambazaji wa posterior wa pamoja,
• sehemu fupi ya taarifa ya kibinafsi.

Watafiti pia wanasema kwamba milinganyo mipya ya programu ya nguvu inaweza kuundwa na hali hizi za taarifa na kwamba milinganyo hii inaweza kudumisha baadhi ya sifa za msingi za programu ya nguvu ya POMDP ya kati ya klasiki.

Moja ya sifa hizi ni kwamba uboreshaji hufanywa katika nafasi ya hatua, si katika nafasi ya mkakati. Hii ni muhimu kwa nadharia kwa sababu nafasi ya mkakati ni kubwa na ngumu zaidi.

Nukta nyingine muhimu ni kwamba hali za taarifa zinaweza kusasishwa kwa mtindo wa Markov. Hii inaonyesha kwamba badala ya historia ya taarifa inayokua kwa muda, vinaweza kutumika vigezo vya uamuzi vinavyoweza kudhibitiwa zaidi.

Kwa nini hii ni muhimu?

Ingawa utafiti huu unaonekana wa kinadharia, una uhusiano mkubwa na teknolojia za kisasa.

Kwa sababu mifumo mingi ya kisasa si ya kati:

Timu za roboti hufanya kazi pamoja.
Floti za magari ya kujiendesha hushiriki taarifa.
Mitandao ya nishati husimamiwa na vituo vya udhibiti vya kikanda.
Mitandao ya sensa iliyosambazwa hufuatilia mazingira, maafa au usalama.
Mifumo ya akili bandia yenye wakala wengi hufanya uamuzi katika kazi za pamoja.

Katika mifumo hii kila mtu haelewi kila kitu kwa wakati mmoja. Taarifa inaweza kuwa na upungufu, kuchelewa au kuwa ya ndani tu. Kwa hiyo nadharia ya uamuzi inapaswa kuendelezwa si tu kwa mifumo ya kati, bali pia kwa mifumo iliyosambazwa yenye upotofu wa taarifa.

Umuhimu wa makala ni kutoa mfumo wa hisabati unaofanya tatizo hili gumu kuwa na mpangilio zaidi.

Mambo ya kuzingatia

Utafiti huu si programu tayari, algoriti ya udhibiti wa roboti au matumizi ya viwandani moja kwa moja. Mchango wake kuu uko katika kiwango cha kinadharia na hisabati.

Kwanza, utafiti ni preprint. Haipaswi kuchukuliwa kuwa umepitia tathmini ya rika.

Pili, makala inatoa milinganyo ya jumla ya programu ya nguvu na miundo ya hali ya taarifa. Jinsi yanavyoweza kutumika kwa ufanisi katika mifumo mikubwa halisi kwa upande wa hesabu ni mada tofauti ya utafiti.

Tatu, matatizo ya POMDP isiyosanifiwa kati tayari ni daraja ngumu sana. Ingawa muundo wa kufinyaza taarifa ni muhimu kwa nadharia, huenda ikahitajika mbinu za ukaribu wa ziada kwa algoriti za vitendo.

Nne, utafiti unaendelea kupitia usawa wa timu na mbinu ya uboreshaji wa mtu kwa mtu. Hii inaweza kumaanisha kuwa haitoi dhamana ya uboreshaji kamili wa timu kwa kila hali; huenda ikahitajika masharti ya ziada.

Tano, kabla ya kutumia katika roboti, nishati, ulinzi, mitandao ya kifedha au mifumo ya usafiri, lazima uchunguzwe kwa makini dhana za modeli, kuchelewa kwa taarifa, makosa ya mawasiliano na mipaka ya usalama.

Hitimisho

Utafiti huu unatafuta jibu kwa swali muhimu katika mifumo ya uamuzi yenye wakala wengi na isiyosanifiwa kati:

Wakala anaweza kufanya uamuzi vipi kwa taarifa isiyokamilika na iliyochelewa bila kubeba historia yote?

Jibu linalopendekezwa na makala ni kufinyaza taarifa kuwa sehemu tatu kuu: imani ya kibinafsi ya wakala, imani ya pamoja ya wote na taarifa fupi ya kibinafsi ya wakala.

Mfumo huu unatoa milinganyo mipya ya programu ya nguvu na separation principle kwa matatizo ya POMDP yenye kushiriki taarifa kwa kuchelewa. Ingawa utafiti huidai matumizi ya moja kwa moja, unaonyesha mwelekeo muhimu wa kinadharia kwa timu za roboti za baadaye, mitandao ya sensa iliyosambazwa na mifumo ya akili bandia yenye wakala wengi.

Ujumbe rahisi zaidi wa maandishi haya ni:

Katika mifumo iliyosambazwa uamuzi mzuri huenda usitoke kwa kujua kila kitu, bali kwa muhtasari sahihi wa nani anajua nini.

Kumbuka ya chanzo na mbinu

Maudhui haya yametayarishwa kwa njia ya kipekee katika muundo wa uhariri wa Verianla kwa kutumia utafiti wa kitaaluma «Private & Common Information States in Decentralized Team Equilibrium via Dynamic Programming for POMDPs with Delayed Sharing» uliotayarishwa na Charalambos D. Charalambous, Umarbek Guvercin na Seddik Djouadi.

Kazi inachukuliwa kuwa preprint iliyochapishwa kwenye arXiv. Maudhui ni kwa taarifa na elimu. Hayachukui nafasi ya ushauri wa kiufundi kwa mifumo ya udhibiti, roboti, miundombinu muhimu, teknolojia za ulinzi, mifumo ya kifedha au matumizi ya uhandisi wa kitaalamu.