Mobile robot navigation tasks are subject to motion stochasticity
arising from the robot's local controllers, which casts the
navigational task into a Markov decision process framework.  The MDP
may, however, be intractably large; in this work we consider the
prioritized package delivery problem which yields an exponentially
large state space.  We demonstrate that the bulk of this state space
is tied to a sub-problem that is an instance of the traveling
salesdroid problem and that exponential improvements in solution time
for the MDP can be achieved by addressing the TSP sub-problem
separately.  This process produces a suboptimal solution, but we show
that the degree of suboptimality can be controlled by employing more
effective TSP approximators.  The key contribution is the
demonstration that MDP solution techniques can substantially benefit
from careful application of well-understood deterministic optimization
techniques.