Jorge Cortés

Professor





Self-triggered optimal servicing in dynamic environments with acyclic structure
C. Nowzari, J. Cortés
IEEE Transactions on Automatic Control 58 (5) (2013), 1236-1249


Abstract

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 trade-off: 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 \algoinvest 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 \algoinvest remains optimal. Based on this analysis, we develop the \algoselftrigger 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. Several simulations illustrate our results.

pdf   |   ps.gz

Mechanical and Aerospace Engineering, University of California, San Diego
9500 Gilman Dr, La Jolla, California, 92093-0411

Ph: 1-858-822-7930
Fax: 1-858-822-3107

cortes at ucsd.edu
Skype id: jorgilliyo