Self-Triggered Optimal Servicing in Dynamic Environments With Acyclic Structure

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. The decision maker faces a timing tradeoff: early decisions mean more time for preparation at the cost of higher uncertainty in the target´s true destination while later decisions mean less uncertainty at the cost of having less time to prepare. We show how this problem can be formulated as an optimal stopping problem on a Markov chain. This sets the basis for the introduction of the best investment algorithm which prescribes when investments must be made conditioned on the target´s motion along the digraph. We establish the optimality of this prescription and examine its robustness against changes in the problem parameters, identifying sufficient conditions to determine whether the solution computed by the best investment algorithm remains optimal. Based on this analysis, we develop the self-triggered acquisition&decision algorithm that allows the decision maker, under partial knowledge of the parameter dynamics, to schedule in advance when to check if the control policy in its memory remains optimal and, if this test fails, when to recompute it. Finally, we obtain worst case lower bounds on the maximum time that can elapse under arbitrary parameter dynamics before the optimal solution must be recomputed. Simulations illustrate our results.