Robust optimal decision policies for servicing targets in acyclic digraphs

This paper considers a class of scenarios where targets emerge from some known location and move towards some unknown destinations in a weighted acyclic digraph. A decision maker with knowledge of the target positions must decide when preparations should be made at any given destination for their arrival. We show how this problem can be formulated as an optimal stopping problem on a Markov chain, which sets the basis for the introduction of the BEST INVESTMENT ALGORITHM. Our strategy prescribes when investments must be made conditioned on the target´s motion along the digraph. We establish the optimality of this policy and examine its robustness against changing conditions of the problem which allows us to identify a sufficient condition that determines whether the solution computed by the BEST INVESTMENT ALGORITHM remains optimal under changes in the problem data. Several simulations illustrate our results.