Graph Planning with Expected Finite Horizon
  Graph planning gives rise to fundamental algorithmic questions such as
shortest path, traveling salesman problem, etc. A classical problem in discrete
planning is to consider a weighted graph and construct a path that maximizes
the sum of weights for a given time horizon $T$. However, in many scenarios,
the time horizon is not fixed, but the stopping time is chosen according to
some distribution such that the expected stopping time is $T$. If the stopping
time distribution is not known, then to ensure robustness, the distribution is
chosen by an adversary, to represent the worst-case scenario.
  A stationary plan for every vertex always chooses the same outgoing edge. For
fixed horizon or fixed stopping-time distribution, stationary plans are not
sufficient for optimality. Quite surprisingly we show that when an adversary
chooses the stopping-time distribution with expected stopping time $T$, then
stationary plans are sufficient. While computing optimal stationary plans for
fixed horizon is NP-complete, we show that computing optimal stationary plans
under adversarial stopping-time distribution can be achieved in polynomial
time. Consequently, our polynomial-time algorithm for adversarial stopping time
also computes an optimal plan among all possible plans.
