cs.GT cs.LO
Qualitative Multi Objective Reachability for Ordered Branching MDPs. We study qualitative multi objective reachability problems for Ordered Branching Markov Decision Processes (OBMDPs), or equivalently context free MDPs, building on prior results for single target reachability on Branching Markov Decision Processes (BMDPs). We provide two separate algorithms for "almost sure" and "limit sure" multi target reachability for OBMDPs. Specifically, given an OBMDP, mathcal A , given a starting non terminal, and given a set of target non terminals K of size k K , our first algorithm decides whether the supremum probability, of generating a tree that contains every target non terminal in set K , is 1 . Our second algorithm decides whether there is a strategy for the player to almost surely (with probability 1 ) generate a tree that contains every target non terminal in set K . The two separate algorithms are needed we show that indeed, in this context, "almost sure" not "limit sure" for multi target reachability, meaning that there are OBMDPs for which the player may not have any strategy to achieve probability exactly 1 of reaching all targets in set K in the same generated tree, but may have a sequence of strategies that achieve probability arbitrarily close to 1 . Both algorithms run in time 2 O(k) cdot mathcal A O(1) , where mathcal A is the total bit encoding length of the given OBMDP, mathcal A . Hence they run in polynomial time when k is fixed, and are fixed parameter tractable with respect to k . Moreover, we show that even the qualitative almost sure (and limit sure) multi target reachability decision problem is in general NP hard, when the size k of the set K of target non terminals is not fixed.