External Memory Value Iteration

All Papers

We propose a unified approach to disk-based search for deterministic, non-deterministic, and probabilistic (MDP) settings. We provide the design of an external Value Iteration algorithm that performs at most O(lG . scan(|E|) + tmax . sort(|E|)) I/Os, where lG is the length of the largest back-edge in the breadth-first search graph G having |E| edges, tmax is the maximum number of iterations, and scan(n) and sort(n) are the I/O complexities for externally scanning and sorting n items. The new algorithm is evaluated over large instances of known benchmark problems. As shown, the proposed algorithm is able to solve very large problems that do not fit into the available RAM and thus out of reach for other exact algorithms.