I detta dokument tar vi med oss tekniker från verksamhetsforskning för att ta itu med problemet med att välja optimala åtgärder inom delvis observerbara stokastiska domäner. Vi börjar med att introducera teorin om Markov beslutsprocesser (mdps) och delvis observerbara mdps (pomdps). Vi skisserar sedan en ny algoritm för att lösa pomdps o linje och visar hur, i vissa fall, en nite-minne controller kan extraheras från lösningen till en pomdp. Vi avslutar med en diskussion om komplexiteten i nding exakta lösningar för pomdps och om vissa möjligheter för nding approximativa lösningar. Tänk på problemet med en robot som navigerar i en stor byggnad. Roboten kan förflytta sig från korridorkorsning till korsning och kan göra lokala observationer av sin värld. Dess åtgärder är dock inte helt tillförlitliga. Ibland, när den har för avsikt att röra sig, stannar den där den är eller går för långt; ibland, när den har för avsikt att vända, går den över. Den har liknande problem med observation. Ibland ser en korridor ut som ett hörn; ibland ser en T-korsning ut som en L-korsning. Hur kan en sådan felsökt robot navigera, även med en karta över korridorerna? I allmänhet måste roboten komma ihåg något om sin historia av handlingar och observationer och använda denna information, tillsammans med sin kunskap om den underliggande dynamiken i världen (kartan och annan information), för att upprätthålla en uppskattning av dess läge. Många tekniska applikationer följer detta tillvägagångssätt, med hjälp av metoder som Kalman lter 10] för att upprätthålla en löpande uppskattning av robotens rumsliga osäkerhet, uttryckt som en ellipsoid eller normal distribution i Cartesian utrymme. Detta tillvägagångssätt duger dock inte för vår robot. Dess osäkerhet kan vara diskret: det kan vara nästan säker på att det är i nordöstra hörnet av antingen den fjärde eller den sjunde oors, även om det medger en chans att det är på ft oor, också. Sedan, med tanke på en osäker uppskattning av dess läge, roboten måste bestämma vilka åtgärder som ska vidtas. I vissa fall kan det vara tillräckligt att ignorera osäkerheten och vidta åtgärder som skulle vara lämpliga för den mest sannolika platsen. I andra fall kan det vara bättre för roboten att vidta åtgärder för att samla in information, till exempel söka efter ett landmärke eller läsa skyltar på väggen. I allmänhet kommer den att vidta åtgärder som uppfyller båda syftena samtidigt.
Även nuvarande tekniker som hanterar delvis observerbara Markovbeslutsprocesser (POMDP) är mycket nära detta tillvägagångssätt REF ].
Planning and Acting in Partially Observable Stochastic Domains
{'venue': 'Artif. Intell.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}