Shkencëtari zgjidh enigmën e teorisë së lojës gati 60-vjeçare

Për të kuptuar aftësinë e automjeteve autonome në lundrimin në kompleksitetin e rrugës, shkencëtarët shpesh përdorin teorinë e lojës – një degë e matematikës që merret me modelimin e sjelljes racionale të agjentëve ndërsa ata përpiqen të arrijnë objektivat e tyre.

Për vite, Dejan Milutinovic, një profesor i inxhinierisë elektrike dhe kompjuterike në UC Santa Cruz, ka bashkëpunuar me studiues të tjerë në një grup kompleks të teorisë së lojës, të njohur si lojëra diferenciale. Kjo fushë ka të bëjë me lojtarët në lëvizje. Ndër këto lojëra është loja e ndjekjes së murit, e cila ofron një kornizë relativisht të pakomplikuar për një skenar ku një ndjekës më i shpejtë synon të kapë një shmangës më të ngadaltë, i cili është i kufizuar të lëvizë përgjatë një muri.

Që kur kjo lojë u përshkrua për herë të parë gati 60 vjet më parë, ka pasur një dilemë brenda lojës – një grup pozicionesh ku mendohej se nuk ekzistonte asnjë zgjidhje optimale e lojës. Por tani, Milutinovic dhe kolegët e tij kanë vërtetuar në një punim të ri të botuar në revistën IEEE Transactions on Automatic Control se kjo dilemë e gjatë nuk ekziston në të vërtetë dhe prezantuan një metodë të re analize që dëshmon se ka gjithmonë një zgjidhje deterministe për murin. lojë ndjekjeje. Ky zbulim hap derën për zgjidhjen e sfidave të tjera të ngjashme që ekzistojnë në fushën e lojërave diferenciale dhe mundëson arsyetim më të mirë rreth sistemeve autonome siç janë automjetet pa shofer.

Teoria e lojës përdoret për të arsyetuar rreth sjelljes në një gamë të gjerë fushash, të tilla si ekonomia, shkenca politike, shkenca kompjuterike dhe inxhinieria. Brenda teorisë së lojës, ekuilibri Nash është një nga konceptet më të njohura. Koncepti u prezantua nga matematikani John Nash dhe përcakton strategjitë optimale të lojës për të gjithë lojtarët në lojë për ta përfunduar lojën me sa më pak keqardhje. Çdo lojtar që zgjedh të mos luajë strategjinë e tij optimale të lojës do të përfundojë me më shumë keqardhje, prandaj, lojtarët racionalë janë të gjithë të motivuar për të luajtur strategjinë e tyre të ekuilibrit.

Ky koncept zbatohet për lojën e ndjekjes së murit – një palë strategjike klasike të ekuilibrit Nash për dy lojtarët, ndjekësin dhe shmangësin, që përshkruan strategjinë e tyre më të mirë në pothuajse të gjitha pozicionet e tyre. Megjithatë, ekzistojnë një sërë pozicionesh midis ndjekësit dhe shmangësit, për të cilat analiza klasike nuk arrin t’i japë lojës strategjive optimale dhe përfundon me ekzistencën e dilemës. Ky grup pozicionesh njihet si një sipërfaqe singulare – dhe prej vitesh, komuniteti hulumtues e ka pranuar dilemën si fakt.

“Kjo na shqetësoi sepse menduam, nëse shmangësi e di se ka një sipërfaqe të vetme, ekziston një kërcënim që shmangësi mund të shkojë në sipërfaqen e vetme dhe ta keqpërdor atë,” tha Milutinoviç. “Shmangia mund t’ju detyrojë të shkoni në sipërfaqen e vetme ku nuk dini si të veproni në mënyrë optimale – dhe atëherë ne thjesht nuk e dimë se çfarë do të ishte implikimi i kësaj në lojëra shumë më të komplikuara.”

Kështu që Milutinovic dhe bashkëautorët e tij dolën me një mënyrë të re për t’iu qasur problemit, duke përdorur një koncept matematikor që nuk ekzistonte kur u konceptua fillimisht loja e ndjekjes së murit. Duke përdorur zgjidhjen e viskozitetit të ekuacionit Hamilton-Jacobi-Isaacs dhe duke prezantuar një analizë të shkallës së humbjes për zgjidhjen e sipërfaqes së vetme, ata ishin në gjendje të gjenin se një zgjidhje optimale e lojës mund të përcaktohet në të gjitha rrethanat e lojës dhe të zgjidhë dilemën.

Zgjidhja e viskozitetit të ekuacioneve diferenciale të pjesshme është një koncept matematikor që nuk ekzistonte deri në vitet 1980 dhe ofron një linjë unike arsyetimi rreth zgjidhjes së ekuacionit Hamilton-Jacobi-Isaacs. Tani dihet mirë se koncepti është i rëndësishëm për arsyetimin rreth problemeve të kontrollit optimal dhe teorisë së lojës.

Përdorimi i zgjidhjeve të viskozitetit, të cilat janë funksione, për të zgjidhur problemet e teorisë së lojës përfshin përdorimin e llogaritjes për të gjetur derivatet e këtyre funksioneve. Është relativisht e lehtë për të gjetur zgjidhje optimale të lojës kur zgjidhja e viskozitetit e lidhur me një lojë ka derivate të mirëpërcaktuar. Ky nuk është rasti për lojën e ndjekjes së murit dhe kjo mungesë e derivateve të mirëpërcaktuara krijon dilemën.

Në mënyrë tipike, kur ekziston një dilemë, një qasje praktike është që lojtarët të zgjedhin rastësisht një nga veprimet e mundshme dhe të pranojnë humbjet që vijnë nga këto vendime. Por këtu qëndron kapja: nëse ka një humbje, çdo lojtar racional do të dëshirojë ta minimizojë atë.

Pra, për të gjetur se si lojtarët mund të minimizojnë humbjet e tyre, autorët analizuan zgjidhjen e viskozitetit të ekuacionit Hamilton-Jacobi-Isaacs rreth sipërfaqes singulare ku derivatet nuk janë të mirëpërcaktuara. Më pas, ata prezantuan një analizë të shkallës së humbjeve në këto gjendje sipërfaqësore njëjëse të ekuacionit. Ata zbuluan se kur secili aktor minimizon shkallën e tij të humbjeve, ka strategji të mirëpërcaktuara të lojës për veprimet e tyre në sipërfaqen e vetme.

Autorët zbuluan se jo vetëm që kjo shkallë e minimizimit të humbjeve përcakton veprimet optimale të lojës për sipërfaqen e vetme, por është gjithashtu në përputhje me veprimet optimale të lojës në çdo gjendje të mundshme ku analiza klasike është gjithashtu në gjendje të gjejë këto veprime.

“Kur marrim analizën e shkallës së humbjes dhe e zbatojmë diku tjetër, veprimet optimale të lojës nga analiza klasike nuk ndikohen,” tha Milutinovic. “Ne marrim teorinë klasike dhe e shtojmë atë me analizën e shkallës së humbjes, kështu që një zgjidhje ekziston kudo. Ky është një rezultat i rëndësishëm që tregon se shtimi nuk është thjesht një rregullim për të gjetur një zgjidhje në sipërfaqen e vetme, por një kontribut themelor në teorinë e lojës.

Milutinoviq dhe bashkautorët e tij janë të interesuar të eksplorojnë probleme të tjera të teorisë së lojës me sipërfaqe të veçanta ku mund të zbatohet metoda e tyre e re. Punimi është gjithashtu një thirrje e hapur për komunitetin hulumtues për të shqyrtuar në mënyrë të ngjashme dilemat e tjera.