Model predictive control for dynamic unreliable resource allocation

In this paper, we consider a class of unreliable resource allocation problems where resources assigned may fail to complete a task, and the outcomes of past resource allocations are observed before new resource allocations are selected. The resulting temporal allocation problem is a stochastic control problem, with a state space and control space that grow exponentially in cardinality with the number of tasks. We introduce an approximation by enlarging the admissible control space, and show that this approximation can be solved exactly and efficiently. The approximation is used in a model predictive control (MPC) algorithm. For single resource problems, the MPC algorithm completes over 98% of the task value completed by an optimal dynamic programming algorithm in over 1000 randomly generated problems. On average, it achieves 99.5% of the optimal performance while requiring over 6 orders of magnitude less computation.