Värde iteration är en kraftfull men ineffektiv algoritm för Markov beslutsprocesser (MDPs) eftersom det sätter större delen av sin insats för att backa upp hela tillståndet utrymme, vilket visar sig vara onödigt i många fall. För att lösa detta problem har många strategier föreslagits. Bland dem är ILAO* och varianter av RTDP toppmoderna. Dessa metoder använder nåbarhetsanalys och heuristisk sökning för att undvika några onödiga säkerhetskopior. Men ingen av dessa metoder bygger den grafiska strukturen av staten övergångar i ett förbehandlingssteg eller använda den strukturella informationen för att systematiskt bryta ner ett problem, varigenom generera en intelligent backup sekvens av tillståndet utrymme. I den här artikeln presenterar vi två optimala MDP-algoritmer. Den första algoritmen, topological value iteration (TVI), detekterar strukturen av MDPs och backar upp tillstånd baserade på topologiska sekvenser. Den (1) delar upp en MDP i starkt anslutna komponenter (SCC) och (2) löser dessa komponenter sekventiellt. TVI överträffar VI och andra toppmoderna algoritmer i stor utsträckning när en MDP har flera, nästan lika stora SCC. Den andra algoritmen, fokuserad topologisk värde iteration (FTVI), är en förlängning av TVI. FTVI begränsar sin uppmärksamhet till anslutna komponenter som är relevanta för att lösa MDP. Specifikt använder den en liten mängd heuristisk sökning för att eliminera bevisligen suboptimala åtgärder. Denna beskärning gör det möjligt för FTVI att hitta mindre anslutna komponenter, vilket körs snabbare. Vi visar att FTVI överträffar TVI med en storleksordning, i genomsnitt över flera domäner. Förvånansvärt nog överträffar FTVI också i hög grad populära "heuristiskt-informerade" MDP-algoritmer som ILAO*, LRTDP, BRTDP och Bayesian-RTDP på många områden, ibland med så mycket som två storleksordningar. Slutligen karakteriserar vi den typ av domäner där FTVI utmärker sig - föreslår en väg till ett välinformerat val av lösare.
I den topologiska värde iteration (TVI) algoritm, stater separerades i starkt anslutna grupper, och effektiviteten förbättrades genom att lösa stat grupper sekventiellt REF.
Topological Value Iteration Algorithms
{'venue': 'Journal Of Artificial Intelligence Research, Volume 42, pages 181-209, 2011', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}