Optimal and Scalable Black-Start Planning via Dynamically Factored Markov Decision Processes

Post-disaster power restoration is essential for ensuring the continuity of critical infrastructure, emergency response, and societal functions. A key challenge in this process is the black-start problem, which involves restoring a power grid from a complete shutdown under uncertainty about component failures. Traditional approaches often employ Markov decision processes (MDPs) to model this stochastic decision-making problem. However, their scalability is severely limited by the exponential growth of the state space. To address this challenge, we propose a factored MDP (FMDP) framework that exploits the structural decomposition of power systems to enable an efficient divide-and-conquer solution strategy. The core idea is to dynamically partition the system after each transition by analyzing dependencies between state variables and eliminating those associated with finalized components. Our method provably preserves optimality while significantly reducing computational complexity. Experimental results demonstrate exponential reductions in state count and solution time compared to conventional MDP-based techniques, improving the scalability of black-start planning for real-world systems.