Onödiga återvändsgränder är vanliga i många probabilistiska planeringsproblem, t.ex. När åtgärder kan misslyckas eller när de drivs under resursbegränsningar. Ett viktigt mål i sådana inställningar är MaxProb, som bestämmer den maximala sannolikhet med vilken målet kan uppnås, och en politik som uppnår denna sannolikhet. Men algoritmer för MaxProb probabilistisk planering är allvarligt underskattade, i den mån det finns få bevis för vad det empiriska tillståndet i konsten faktiskt är. Vi täpper till denna klyfta med en omfattande empirisk analys. Vi designar och utforskar ett stort utrymme av heuristiska sökalgoritmer, systematiserar kända algoritmer och bidrar med flera nya algoritmvarianter. Vi anser att MaxProb, liksom svagare mål som vi döper AtLeastProb (kräver att uppnå ett givet mål probabilty tröskel) och CaProb (kräver att beräkna maximal mål sannolikhet upp till en given noggrannhet). Vi undersöker både det allmänna fallet där det kan finnas 0-lönecykler, och det praktiskt taget relevanta specialfallet av acyklisk planering, såsom planering med en begränsad åtgärd-kostnadsbudget. Vi utformar lämpliga termineringskriterier, sökalgoritmvarianter, slutbeskärningsmetoder med hjälp av klassiska planeringsheuristik och nodurvalsstrategier. Vi utformar ett riktmärkessvit bestående av mer än 1000 instanser anpassade från IPPC, resursbegränsad planering och simulerade penetrationstest. Vår utvärdering klargör state of the art, karakteriserar beteendet hos ett brett spektrum av heuristiska sökalgoritmer, och visar på betydande fördelar med våra nya algoritmvarianter.
För både exakta och approximerade algoritmer för VaR med en tröskel, state of the art kan hittas i REF.
Goal Probability Analysis in Probabilistic Planning: Exploring and Enhancing the State of the Art
{'venue': 'J. Artif. Intell. Res.', 'journal': 'J. Artif. Intell. Res.', 'mag_field_of_study': ['Computer Science']}