Preallocation and Planning under Stochastic Resource Constraints

When flexible electrical loads share remaining network capacity, the exact capacity available is usually not known in advance. Furthermore, there may be periods where there is no communication possible. Last week Frits de Nijs (as first author) submitted the final (camera-ready) version of a paper with Matthijs Spaan and me for AAAI 2018 where we describe how to deal with such stochastic resource constraints when communication is unreliable.

Our proposed methods compute coordinated policies for a number of sequential decisions that are taken without further communication, while aiming to meet common stochastic time/history-dependent resource limits in expectation. These methods are extensions of two known deterministic preallocation algorithms that compute policies for a given plan horizon by allocating resources to agents a priori: a mixed-integer linear program by Wu and Durfee (2010) that guarantees not violating the resource constraint, and a so-called Constrained Markov Decision Process (CMDP) formulation by Altman (1999) that allows stochastic policies and only guarantees that the expected consumption is not more than the amount available. Extensive experiments on two completely different domains show that both our extensions take more time to compute than their original versions, but lead to simultaneously fewer violations of the constraint and more efficient executions. Furthermore we show that more frequent replanning and communication further improves results.

de Nijs, F., Spaan, M., & de Weerdt, M. (2018). Preallocation and Planning under Stochastic Resource Constraints. In Proceedings of the 32th AAAI Conference on Artificial Intelligence.

• 
•