-
Notifications
You must be signed in to change notification settings - Fork 1
Algorithms
The toolbox provides a collection of algorithms for Markov Decision Processes and Partially Observable Markov Decision Processes with resource constraints. On this page we provide an overview of the high-level architecture of the algorithms, and we provide specific information about the algorithms that have been implemented.
Algorithms for Markov Decision Processes with constraints implement the CMDPAlgorithmFiniteHorizon interface. This interface provides a general skeleton which ensures that the input and output format of the algorithms is consistent. Each algorithm takes a CMDPInstance object as an input, and returns an array with an MDPSolutionFinite object for each agent. This structure is depicted in the figure below. More information about instance objects is available here, and more information about solution objects can be found here.
add figure
The column generation algorithm is a conditional preallocation method which has been introduced by Yost and Washburn (2000). The algorithm iteratively generates policies and adds the corresponding columns to a linear program. The algorithm derives a probability distribution over deterministic policies using this linear program, which it eventually returns as a solution.
Class: algorithms.mdp.colgen.ColGenFiniteHorizon
Supported constraints: budget, instantaneous
Number of agents: n
Parameters: tolerance which is used to determine whether the dual prices of the linear program have converged
Solution returned: probability distribution over deterministic policies
Literature: Yost, K. A., & Washburn, A. R. (2000). The LP/POMDP Marriage: Optimization with Imperfect Information. Naval Research Logistics, 47(8), 607–619.
The linear program for Constrained MDPs defines a stochastic policy which represents a conditional preallocation. The algorithm itself only initializes the linear program, and derives the stochastic policy from the solution after solving the linear program. More information about linear programs for Constrained MDPs can be found in a book by Altman (1999).
Class: algorithms.mdp.constrainedmdp.ConstrainedMDPFiniteHorizon
Supported constraints: budget, instantaneous
Number of agents: n
Parameters: none
Solution returned: stochastic policy
Literature: Altman, E. (1999). Constrained Markov Decision Processes. CRC Press.
The deterministic preallocation algorithm in the toolbox uses the same linear program as discussed above, except that it introduces additional binary variables to enforce that resource constraints are never violated. Similar variables have been used in algorithms by Wu and Durfee (2010) and De Nijs et al. (2018).
Class: algorithms.mdp.deterministicpreallocation.DPFiniteHorizon
Supported constraints: budget, instantaneous
Number of agents: n
Parameters: none
Solution returned: stochastic policy
Literature: Wu, J., & Durfee, E. H. (2010). Resource-Driven Mission-Phasing Techniques for Constrained Agents in Stochastic Environments. Journal of Artificial Intelligence Research, 38, 415–473.
De Nijs, F., Spaan, M. T. J., & De Weerdt, M. M. (2018). Preallocation and Planning under Stochastic Resource Constraints. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (pp. 4662–4669).
The dynamic constraint relaxation algorithm proposed by De Nijs et al. (2017) is a hybrid algorithm that bridges the gap between conditional preallocation methods and deterministic preallocation methods. Rather than enforcing that resource constraints are respected at all times, the algorithm computes a solution for which the resource constraint violation probability is (empirically) bounded by a given parameter alpha. The algorithm uses either Column Generation or the CMDP linear program as a subroutine, which have been discussed above.
Class: algorithms.mdp.dynamicrelaxation.DynamicRelaxation
Supported constraints: budget, instantaneous
Number of agents: n
Parameters: tolerance on constraint violation probability (alpha), factor used for constraint relaxation (beta)
Solution returned: probability distribution over deterministic policies (with column generation), stochastic policy (with CMDP linear program)
Literature: De Nijs, F., Walraven, E., De Weerdt, M. M., & Spaan, M. T. J. (2017). Bounding the Probability of Resource Constraint Violations in Multi-Agent MDPs. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (pp. 3562–3568).
Algorithms for Partially Observable Markov Decision Processes with constraints implement the CPOMDPAlgorithmFiniteHorizon interface. This interface provides a general skeleton which ensures that the input and output format of the algorithms is consistent. Each algorithm takes a CPOMDPInstance object as an input, and returns an array with a POMDPSolutionFinite object for each agent. This structure is depicted in the figure below. More information about instance objects is available here, and more information about solution objects can be found here.
add figure
The Column Generation algorithm for Constrained POMDPs (CGCP) proposed by Walraven and Spaan (2018) enhances the scalability of the original column generation algorithm by integrating tailored approximate POMDP algorithms. The algorithm uses point-based value iteration to generate the policies, and these policies are converted to a finite state controller before the corresponding column is added to the linear program. Similar to the MDP variant of the algorithm, which we discussed above, CGCP derives a probability distribution over policies from the linear program, which it returns as a solution.
Class: algorithms.pomdp.cgcp.CGCP
Supported constraints: budget
Number of agents: n
Parameters: tolerance which is used to determine whether the dual prices of the linear program have converged, time limit subproblem solver, amount of time by which time limit subproblem solver is increased upon convergence, minimum number of iterations required with an objective increase before increasing time limit subproblem solver
Solution returned: probability distribution over deterministic policies
Literature: Walraven, E., & Spaan, M. T. J. (2018). Column Generation Algorithms for Constrained POMDPs. Journal of Artificial Intelligence Research, 62, 489–533.
The Constrained Approximate Linear Programming (CALP) algorithm by Poupart et al. (2015) formulates a Constrained POMDP as a Constrained MDP defined in terms of belief states rather than states. The algorithm searches iteratively for additional beliefs, which it uses to expand the Constrained MDP model. This model is solved using the standard linear program for Constrained MDPs, as discussed above.
Class: algorithms.pomdp.calp.FiniteCALP
Supported constraints: budget
Number of agents: 1
Parameters: maximum number of new beliefs added in an iteration, maximum number of iterations, tolerance on reachability probability for the belief search
Solution returned: stochastic finite state controller
Literature: Poupart, P., Malhotra, A., Pei, P., Kim, K.E., Goh, B., & Bowling, M. (2015). Approximate Linear Programming for Constrained Partially Observable Markov Decision Processes. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (pp. 3342–3348).
The ConstrainedPlanningToolbox has been developed by the Algorithmics group at Delft University of Technology, The Netherlands. Please visit our website for more information.