Optimal control in Markov decision processes via distributed optimization
This work provides a scalable solution for optimal control in large-scale stochastic systems, which is crucial for applications like robotics, but the approach is incremental as it applies existing distributed optimization techniques to a known problem.
The paper addresses scalability issues in optimal control synthesis for stochastic systems by proposing a distributed optimization algorithm that decomposes large Markov decision processes into interacting sub-systems, enabling efficient linear programming solutions. The method is demonstrated on robotic motion planning examples.
Optimal control synthesis in stochastic systems with respect to quantitative temporal logic constraints can be formulated as linear programming problems. However, centralized synthesis algorithms do not scale to many practical systems. To tackle this issue, we propose a decomposition-based distributed synthesis algorithm. By decomposing a large-scale stochastic system modeled as a Markov decision process into a collection of interacting sub-systems, the original control problem is formulated as a linear programming problem with a sparse constraint matrix, which can be solved through distributed optimization methods. Additionally, we propose a decomposition algorithm which automatically exploits, if exists, the modular structure in a given large-scale system. We illustrate the proposed methods through robotic motion planning examples.