Ар ким бир эле учурда бир эле нерсени биле бербеши мүмкүн

Күнүмдүк жашоодо көптөгөн системаларды бир гана чечим кабыл алуучу башкарбайт. Бир нече адам, сенсор, робот, башкаруу борбору же программалык агент бир эле система боюнча чечим кабыл ала алат.

Мисалы:

Бир робот тобу бир эле кампада иштей алат.
Бир энергия тармагында ар кандай көзөмөл борборлору ар кандай аймактарды көзөмөлдөй алат.
Бир автоном унаа флотунда ар бир унаа өзүнүн сенсорлорун көрөт, бирок башка унаалардын маалыматтарын кечигип алат.
Бир коргоо, байланыш же кырсыкты көзөмөлдөө тармагында ар кандай байкоо пункттарында ар кандай маалымат болушу мүмкүн.

Бул система түрлөрүндөгү эң чоң көйгөй бул:

Ар бир чечим кабыл алган система баарын көрбөйт.

Бир агент өзүнүн өлчөмдөрүн дароо билет, бирок башка агенттер көргөн маалыматтарды кийинчерээк биле алат. Айрым маалыматтар жалпыга жеткиликтүү болуп калат, айрымдары жеке бойдон калат. Мындай учурда жакшы чечим кабыл алуу үчүн, болгону «мен эмнеге күбө болдум?» деген суроого эмес, «башкалар эмнени билет, эмнени азырынча биле элек, эмнени кечиктирип үйрөнөт?» деген суроого да таянуу керек.

Бул макаланын кызыгышкан негизги көйгөй так ушуга байланыштуу.

POMDP Ne Demek?

Makalenin temel kavramlarından biri POMDP’dir. Açılımı Partially Observable Markov Decision Process’tir. Türkçeye “kısmi gözlemlenebilir Markov karar süreci” olarak çevrilebilir.

Эгер биз бул жерди жөнөкөйлөштүрсөк:

Бир системанын чыныгы абалы бар, бирок чечим чыгарган адам бул абалды толугу менен көрө албайт. Анын ордуна ал ызы-чуу менен же толук эмес байкоолорду алат. Чечим чыгарган адам бул байкоолор менен системанын кайсы абалда болушу мүмкүн экенине ишеним жаратат жана ага ылайык аракет кылат.

Tek karar vericili POMDP’de bu zaten zordur. Ama bu makalede problem daha da zorlaşır: Birden fazla karar verici vardır ve her biri farklı bilgiye sahiptir.

Bu nedenle konu “merkezi olmayan POMDP” haline gelir.

Кечиктирилген Маалымат Бөлүшүү Эмне Дегенди Билдирет?

Макалада T-адам кечиктирилген маалымат бөлүшүү изилденет. Бул тви мындан турат:

Бир чечим чыгаруучу өзүнүн жаңы байкоосун дароо билет. Бирок башка чечим чыгаруучулар бул маалыматты болгону T убакыт кадамы өткөндөн кийин гана билишет.

Örneğin T = 2 ise, bir ajanın şu anda gördüğü bilgi diğerleri için iki adım sonra ortak bilgi haline gelir.

Бул учурда ар бир агенттин маалыматы экиге бөлүнөт:

Өзгөчө маалымат: Агенти азыр билген, бирок башкалар азырынча билбеген маалымат.
Жалпы маалымат: Кечигүү мөөнөтү бүткөндүктөн, бардык агенттер азыр билген маалымат.

Бул айырма маанилүү. Анткени чечим кабыл алуучу өзүнүн жаңы маалыматын да, баардыктын билген жалпы мурунку маалыматын да колдонуп чечим чыгарат.

Макаладагы Негизги Маалымат Формуласы Эмне Түшүндүрөт?

Макаладагы маалыматтын түзүлүшү жөнөкөй түрдө мындай окууга болот:

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

Бул формуладе:

Ik,t, k numaralı ajanın t anındaki toplam bilgisidir.
Λk,t, o ajanın özel bilgisidir.
Δt(K), tüm ajanların ortak paylaştığı gecikmiş bilgidir.

Күнүмдүк тилде:

Агенттин чечими = анын өзгөчө маалыматы + ар ким билген жалпы маалыматка негизделет.

Бул жөнөкөй көрүнөт, бирок көп агенттүү чечим проблемаларында маанилүү айырма болуп саналат. Анткени кайсы маалымат жеке, кайсы маалымат жалпы экенин билбестен туура чечим модели түзүлбөйт.

Чечим Стратегиясы Деген эмне?

Макаладагы дагы бир негизги билдирүү мындай:

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

Бул формуланын жөнөкөй мааниси:

Агенттин аракеттери ошол учурдагы билиміне ылайык тандалат.

Кайда:

Uk,t, k numaralı ajanın t anındaki eylemidir.
γk,t, ajanın karar stratejisidir.
Ik,t, ajanın o anki bilgi yapısıdır.

Демек, агент тандайын деген чечимди кокустан кабыл кылбайт; колундагы маалыматка таянып стратегияны колдонот.

Бирок маселе ушунда: убакыт өтүп бараткан сайын маалыматтардын тарыхы өсөт. Эгер агент бардык тарыхтын баарын өзлөрү менен алып жүрүүгө мажбур болсо, маселе тез эсептелбей калат. Ошондуктан маалыматтарды кысуу керек.

Маалыматты тыўыштыруу эмнеге маанилүү?

Бир чечим чыгаруучу бардык мурунку байкоолорун, мурунку аракеттерин жана башка агенттерден кечигип келип түшкөн бардык маалыматтарды сактайт деп ойлойлу. Убакыт өткөн сайын бул маалымат топтому өсөт.

Бул эки жагынан көйгөйлүү:

Биринчиден, чечимди эсептөө татаалданат.
Экинчиден, стратегиянын аныктамасы өсүп келе жаткан өткөнгө байланыштуу болуп калат.

Klasik POMDP teorisinde bu sorun “inanç durumu” ile çözülür. Karar verici tüm geçmişi saklamak yerine, sistemin hangi durumda olabileceğine dair bir olasılık dağılımı taşır.

Бул макала да окшош идеяни борборлоштурулбаган системаларга өткөрүүгө аракет кылат. Бирок бул жерде бир гана ишеним жетишсиз. Анткени ар бир агент ар кандай жеке маалыматка жана жалпы маалыматка ээ.

Иштөөнүн Негизги Ойу: Үч Бөлүктүү Маалымат абалы

Макаланын эң маанилүү жыйынтыгы, ар бир агент кечиктирилген маалымат түзүмүн үч бөлүктө кысып сала аларын айтуу болуп саналат.

1. Özel posterior dağılım
Агенттин өз билиминен системанын чыныгы абалы жана башка агенттер көрө албаган өзгөчө маалыматтар жөнүндө түзүлгөн мүмкүнчүлүккө негизделген ишеним.

Жөнөкөй айтып айтканда:
«Менин көргөндөрүмө караганда система жана башка агенттердин өзгөчө жактары жөнүндө эмнеге ишенем?»

2. Ortak posterior dağılım
Бардык агенттердин жалпы маалыматы боюнча системага байланыштуу түзүлгөн жалпы ыктымалдык ишеним.

Sade anlatımla:
«Бардыгыбыздын белгилүү жалпы өткөнүгүбүзгө ылайык, система жөнүндө жалпы божомобуз кандай?»

3. Ажанын кыска жеке маалымат компоненти
Агент дагы деле болгону өзүндө гана бар актуалдуу өзгөчө маалымат бөлүгү болуп саналат.

Sade anlatımla:
«Азыр учурда болгону мен билеткен, бирок баарыбыз дагы үйрөнө элек кыска маалымат кандай?»

Бул үчтүк түзүлүш, агенттерге чексиз өсүп жаткан өткөнгө карабастан чечим чыгаруусуна мүмкүндүк берген теориялык кыскартууну сунуштайт.

«Өзгөчө Ыйман» менен «Жалпы Ыймандын» айырмасы эмне?

Бул макаланы түшүнүүнүн эң маанилүү жолу, жеке ишеним менен жалпы ишенимдин айырмасын түшүнүү болуп саналат.

Бир кампада иштеген эки роботту элестетели.

Robot A, önünde bir engel gördü. Robot B henüz bunu bilmiyor. Ama ikisi de birkaç saniye önce paylaşılan harita bilgisini biliyor.

Бул учурда:

Жалпы ишеним, эки роботтун тең билген эски карта жана эски байкоолордон турат.
Robot A’nın özel inancı, kendi yeni engel gözlemini de içerir.
Robot B’nin özel inancı ise kendi gördüğü başka şeyleri içerir.

Robot A karar verirken hem ortak haritayı hem kendi yeni bilgisini kullanır. Fakat Robot B’nin henüz neyi bilmediğini de hesaba katmak gerekebilir.

Макаланын сунуштаган алкагы мындай татаал маалымат асимметрияларын математикалык жактан башкарууга аракет кылат.

Эмне үчүн динамикалык программалоо колдонулат?

Динамикалык программалоо — чоң чечим проблемаларын убакыттап бөлүп чечүүгө жардам берген ыкма. Бүгүнкү чечим келечекте болушу мүмкүн болгон чыгымдарга же кирешелерге таасир этет. Ошондуктан чечим проблемасы артка карап же кадам-кадам талданат.

Klasik tek ajanlı POMDP’de dinamik programlama, inanç durumu üzerinden yapılabilir. Bu çok önemlidir çünkü ajan tüm geçmişi değil, yalnızca güncel inanç durumunu kullanarak karar verir.

Бул макаланын салымы борборлоштурулбаган жана кечигип берилген маалымат бөлүшүү системаларында да окшош динамикалык программалоо түзүмүн орнотууга аракеттенүүсүндө

Ancak klasik yaklaşımdan farkı vardır: Tek bir ortak değer fonksiyonu yerine, her ajan için ayrı maliyet-devam fonksiyonları ve ayrı DP denklemleri kullanılır.

Neden Tek DP Denklemi Yetmeyebilir?

Мурдагы кээ бир изилдөөлөр бардык агенттер үчүн жалпы маалыматка негизделген бир эле динамикалык программалоо теңдемесин колдонууга аракет кылган.

Бул ыкма айрым өзгөчө учурларда натыйжалуу болушу мүмкүн. Бирок макалага ылайык, айрыкча узак мөөнөттүү кечигүү менен бөлүшүү учурларында бул бирдей теңдеменин маанилүү чектөөлөрү бар.

Анткени жалгыз жалпы маалымат теңдемеси ар бир агенттин өзгөчө маалыматын жана өзгөчө ишеничин жетиштүү деңгээде чагылдырбай калышы мүмкүн. Ошондой эле, айрым мурдагы ыкмаларда оптималдаштыруу түз аракет мейкиндиги ордуна стратегия мейкиндигинде жүргүзүлөт. Бул да проблеманы оорлотот.

Бул макала башка жолду сунуштайт:

Ар бир агент үчүн өз маалымат структурасына байланыштуу өзүнчө динамикалык программалоо теңдемесин түзүү.

Böylece her ajan kendi eylem uzayı üzerinde optimizasyon yapar. Bu, klasik POMDP dinamik programlamasına daha benzer bir yapı sağlar.

Decentralized Team Equilibrium Ne Demek?

Макаладагы маанилүү түшүнүктөрдүн бири - “decentralized sequential team equilibrium”. Бул өнөрдү жөнөкөй түрдө “борборсуз катарлуу команда тең салмагы” деп которсо болот.

Бул жердеги ой мындай:

Бир нече агент бар. Алардын баары жалпы командалык максатты өркүндөтүүгө аракет кылат. Бирок ар бири өзүнүн билиминин негизинде чечим кабыл алат.

Бир агенттин стратегиясы бааланууда, башка агенттердин стратегиялары туруктуу кармалат. Андан кийин бул агент өз стратегиясын жакшырта алабы, аны карашат.

Bu, oyun teorisindeki Nash dengesi fikrine benzer. Ancak önemli fark şudur: Burada ajanların ayrı çıkarları değil, ortak bir takım maliyeti veya takım hedefi vardır.

Демек, системанын максаты «ар бирөө өзүнүн кирешесин максималдасын» эмес, «ар бир агент өзүнүн маалымат чегинде жалпы команда максаты үчүн эң жакшы жооп берсин» деген көз-караш болуп саналат.

Өзүнчө бөлүү принциби эмнени билдирет?

Makalede “separation principle”, yani ayrıştırma ilkesi önemli bir sonuç olarak ele alınıyor.

Классикалык көзөмөл теориясында бөлүп карауу принциби болжол менен мындай дейт:

Алгач тутумдун абалын болжо.
Андан кийин бул болжолу боюнча көзөмөл чечимин чыгар.

Демек, болжолдоо жана көзөмөл концептуалдык жактан бири-биринен айырмаланышы мүмкүн.

Бул макала борборсуз жана кечигүү менен маалымат бөлүшүү системаларында муну дагы жалпы версиясын сунуш кылууга аракет кылат.

Ар бир агент алды менен жеке жана жалпы маалымат абалдарын жаңыртат. Андан кийин чечимин ушул кысылган маалымат абалдарынын негизинде чыгарат.

Бул бул жагынан маанилүү:

Агентке чечим кабыл алуу үчүн бардык өткөн тагдырын көтөрүү керек эмес. Болжолдонгон маалымат абалдары статистикалык жактан жетиштүү колдонулушу мүмкүн.

Формулалар бизге эмнени үйрөтөт?

Макаладагы формулалар абдан техникалык көрүнгөнү менен, окурман үчүн үч негизги идеяны камтыйт.

Биринчиси: Ар бир агенттин билими жеке жана жалпы компоненттерге бөлүнөт.
Бул кечиктирилген бөлүштүрүүнүн математикалык эквиваленти.

Экинчиден: Ар бир агенттин аракеттери өзүнүн маалымат абалына байланыштуу.
Ошентип, чечим процессинин стратегиясы агенттин эмне билгенине гана чектелет.

Üçüncüsü: Özel ve ortak posterior dağılımlar Markov tarzı güncellenebilir.
Бул өткөндүн бүтүнүн көтөрүү ордуна учурдагы ишеним абалы менен ilerlemеге мүмкүндүк берет.

Ошондуктан формулалар жөн гана абстракттуу символдор эмес. Негизги максат — өнүгүп жаткан маалымат тарыхын кичирээк жана чечим кабыл алуу үчүн жетиштүү бөлүктөргө кыскартуу.

Изилдөө эмнени айтат?

Изилдөөнүн негизги билдирүүсү:

Борборлоштурулбаган, чектелген байкала турган жана кечигүү менен маалымат алмашуу системаларында ар бир агент чечим кабыл алуу үчүн керектүү маалыматты үч бөлүктүү структурага кысып салса болот.

Бул үч бөлүк:

• özel posterior dağılım,
• ortak posterior dağılım,
• кыска жеке маалымат айкалышы.

Araştırmacılar ayrıca bu bilgi durumlarıyla yeni dinamik programlama denklemleri kurulabileceğini ve bu denklemlerin klasik merkezi POMDP dinamik programlamasındaki bazı temel özellikleri koruduğunu savunuyor.

Бул өзгөчөлүктөрдүн бири – оптимизация стратегиялык мейкиндикте эмес, аракет мейкиндигинде жүргүзүлөт. Бул теориялык жактан маанилүү, анткени стратегиялык мейкиндик андан да чоң жана татаал.

Bir diğer önemli nokta, bilgi durumlarının Markov tipi güncellenebilmesidir. Bu da zamanla büyüyen veri geçmişi yerine daha yönetilebilir karar değişkenleri kullanılabileceğini gösterir.

Бул Эмне Үчүн Маанилүү?

Бул иш теориялык көрүнгөнү менен бүгүнкү технологиялар менен күчтүү байланышы бар.

Анткени көптөгөн заманбап системалар борборлоштурулган эмес:

Робот командасы биргеликте иштешет.
Автоном унаа флоттору маалымат бөлүшөт.
Энергия түйүндөрү аймактык башкаруу борборлору аркылуу башкарылат.
Таралган сенсордук тармактар айлана-чөйрөнү, кырсыктарды же коопсуздукту көзөмөлдөйт.
Көп агенттик жасалма интеллект системалары жалпы тапшырмаларды чечишет.

Бул системаларда ар ким баарын бир заматта билбейт. маалымат жетишсиз, кечигип же болгону жергиликтүү болушу мүмкүн. Ошондуктан чечим кабыл алуу теориясы жөн гана борборлоштурулган системалар үчүн эмес, маалымат асимметриясы бар таратылган системалар үчүн да өнүктүрүлүшү керек.

Макаланын мааниси – бул татаал маселени андан ары туюктуураак кылган математикалык чөйрөнү сунуштоодо.

Dikkat Edilmesi Gereken Noktalar

Бул иштер түздөн-түз даяр программалык камсыздоо, роботторду башкаруу алгоритми же өнөр жайлык колдонуу эмес. Негизги салымы теориялык жана математикалык деңгээлде.

Биринчи кезекте, иш алдын ала басылма болуп саналат. Анын илимий кароодон өткөнүн болжолдоп болбойт.

Экинчиден, макала жалпы динамикалык программалоо теңдемелерин жана маалымат абалынын структураларын сунуштайт. Булар канчалык эффективдүү чыныгы чоң системаларда эсептөөгө колдонулушу өзүнчө изилдөө темасы болуп саналат.

Üçüncü olarak, merkezi olmayan POMDP problemleri zaten çok zor problem sınıflarıdır. Bilgi sıkıştırma yapısı teorik olarak önemli olsa da pratik algoritmalar için ek yaklaşık çözüm yöntemleri gerekebilir.

Төртүнчүдөн, иштөө командасынын тең салмактуулугу жана адам-адам оптималдуулук ыкмасы аркылуу ilerлейт. Бул ар дайым толук глобалдык команда оптималдуулугуна кепилдик бербеши мүмкүн; кээ бир кошумча шарттар талап кылынышы мүмкүн.

Бешинчи кезекте, чыныгы роботика, энергетика, коргоо, каржылык тармактар же жол кыймылы системаларына колдонулганда, модельдеги болжолдор, маалымат кечигүүлөрү, байланыш каталары жана коопсуздук чектери дагы каралышы керек.

Жыйынтык

Бул изилдөө көп агенттүү жана борборлоштурулбай башкаруу системаларында маанилүү суроого жооп издөөгө багытталат:

Бир агент бардык өткөнүн алып жүрбөй, толук жана кечигип келген маалымат менен кантип чечим кабыл ала алат?

Мақаланын сунуштаган жообу маалыматты үч негизги бөлүккө кысуу болуп саналат: агенттин жеке ишеними, ар бирөөнүн жалпы ишеними жана агенттин кыска жеке маалыматы.

Bu çerçeve, gecikmeli bilgi paylaşımı olan POMDP problemleri için yeni dinamik programlama denklemleri ve ayrıştırma ilkesi sunar. Çalışma doğrudan pratik uygulama iddiası taşımasa da, geleceğin robot ekipleri, dağıtık sensör ağları ve çok ajanlı yapay zekâ sistemleri için önemli bir teorik yön gösterir.

Бул жазуунун эң жөнөкөй билдирүүсү мындай:

Таралган системаларда жакшы чечим кабыл алуу бардык нерсени билүүдөн эмес; ким эмне билерин туура кыскача билдирүүдөн өтүшү мүмкүн.

Булак жана ыкма эскертмеси

Bu içerik, Charalambos D. Charalambous, Umarbek Guvercin ve Seddik Djouadi tarafından hazırlanan “Private & Common Information States in Decentralized Team Equilibrium via Dynamic Programming for POMDPs with Delayed Sharing” başlıklı akademik çalışmadan yararlanılarak Verianla editoryal formatında özgün olarak hazırlanmıştır.

Çalışma arXiv üzerinde yayımlanmış preprint niteliğindedir. İçerik bilgilendirme ve eğitim amacı taşır. Kontrol sistemleri, robotik, kritik altyapı, savunma teknolojileri, finansal sistemler veya profesyonel mühendislik uygulamaları için teknik danışmanlık yerine geçmez.