🤖 AI

Long-term Power Grid Planning via Answer Set Programming

This paper proposes the first automated approach using Answer Set Programming (ASP) to optimize long-term power grid planning, demonstrating its effectiveness in handling complex topological and combinatorial constraints through experiments on both synthetic and real-world data.

Original authors: Antonio Ielo, Francesco Doria, Sandra Castellanos-Paez, Marco Maratea, Francesco Percassi, Mauro Vallati

Published 2026-05-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Antonio Ielo, Francesco Doria, Sandra Castellanos-Paez, Marco Maratea, Francesco Percassi, Mauro Vallati

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, intricate web of roads connecting a city's main power plants (the "primary stations") to thousands of local neighborhoods (the "secondary stations"). This isn't just a static map; it's a living, breathing system where electricity flows through specific paths. Sometimes, a road needs to be built, an old one removed, or a traffic light (a switch) changed to reroute traffic.

The Problem: The "Forever" Roadmap
Power companies face a huge challenge: they need to plan how this road network should evolve over the next 30 years. They have a "Start" map (where the grid is today) and a "Target" map (where they want it to be in the future).

The tricky part is that they can't just jump straight to the Target. They have to take a series of steps to get there. Every single step along the way must be safe and functional.

No Dead Ends: Every neighborhood must always have a power source.
No Loops: Electricity shouldn't be circling around in a circle between two power plants; it needs to flow in a straight line from source to home.
Backup Plans: If a main power plant fails, the system must be able to instantly reroute power from a different plant without blacking out any homes.
No Traffic Jams: No neighborhood can be connected to too many roads (overloading the local transformer) or too few (leaving it vulnerable).

Currently, experts draw these step-by-step plans by hand. It's like trying to solve a giant, multi-dimensional puzzle where every move you make must keep the picture intact. If you make a wrong move, the whole system could crash. Because the stakes are so high and the math is so complex, this process is slow and relies entirely on human intuition.

The Solution: The "Logic Chef"
The authors of this paper introduced a new tool based on Answer Set Programming (ASP). Think of ASP as a super-smart "Logic Chef."

Instead of a human trying to guess the next move, you give the Chef two things:

The Start Recipe (the current grid).
The Target Recipe (the future grid).
A Rulebook (the safety laws: no loops, must have backups, etc.).

The Chef then automatically figures out the perfect sequence of cooking steps (adding lines, removing lines, or flipping switches) to transform the Start Recipe into the Target Recipe. The magic is that the Chef checks every intermediate step to ensure the dish is still edible (safe) before moving to the next step.

How It Works (The Magic Trick)
The paper describes three main "moves" the Chef can make:

Add a Road: Build a new power line.
Remove a Road: Tear down an old line.
Flip a Switch: Change a line from "open" (off) to "closed" (on), or vice versa, to reroute power.

The Chef is also allowed to make multiple moves at once (parallel planning), as long as those moves don't interfere with each other. This is like a construction crew working on different parts of the city simultaneously, speeding up the process significantly.

The Results: Faster and Smarter
The researchers tested this "Logic Chef" on:

Fake Cities: They created computer-generated power grids of various sizes.
Real Cities: They used anonymized data from a real French power grid.

What they found:

It Works: The Chef successfully found valid step-by-step plans for grids that are as complex as the ones human experts deal with daily.
It's Fast: For some real-world scenarios, it found solutions in under 30 minutes.
Parallel is Better: When the Chef was allowed to make multiple non-conflicting moves at the same time, it solved problems much faster and handled larger, more complex grids than when it was forced to make one move at a time.
Optimization: The Chef didn't just find a solution; it tried to find the best solution (the one with the fewest total moves), which saves money and effort.

In a Nutshell
This paper presents the first automated way to plan the long-term evolution of power grids using a logic-based computer program. It takes the heavy lifting of figuring out safe, step-by-step transitions from human experts to a computer, ensuring that the power grid never loses its safety rules while it grows and changes over decades. The system proved it could handle real-world complexity, offering a faster, more reliable way to design the future of our energy networks.

Technical Summary: Long-term Power Grid Planning via Answer Set Programming

Problem Definition

The paper addresses the Long-term Power Grid Planning (LPP) problem, a critical task for Distribution System Operators (DSOs). This process involves defining a sequence of physical interventions (line additions, removals, and switch operations) to evolve a current power grid configuration into a desired target configuration over an extended horizon (typically up to 30 years).

The core challenge lies in ensuring that every intermediate configuration generated during this evolution remains operationally valid. Unlike static planning or short-horizon reconfiguration, LPP must satisfy a complex set of topological and combinatorial invariants at every step of the transition. These constraints include:

Radiality: The closed network must be acyclic, with each secondary substation supplied by exactly one primary substation.
Reconfigurability (Fault Tolerance): The network must allow for the restoration of radiality via switching operations in the event of the failure of any primary node.
Degree Compliance: Secondary substations must maintain a specific number of connections (typically 2 or 3).
Irreversibility and Feasibility: Only lines present in the target network can be added, and only lines absent from the target can be removed. These operations are irreversible.

Current practices rely heavily on manual expert knowledge and iterative adjustments, which limits reproducibility, scalability, and the systematic exploration of alternative investment trajectories. Existing methods like Mixed Integer Linear Programming (MILP) struggle with purely combinatorial properties like radiality, while standard planning languages find graph invariants cumbersome to express.

Methodology

The authors propose the first automated approach to solve LPP using Answer Set Programming (ASP), a declarative logic programming paradigm well-suited for knowledge-intensive combinatorial problems.

Formalization

The power grid is modeled as an undirected edge-labeled graph $G(V, E, \lambda)$ , where nodes represent primary and secondary stations, and edges represent lines labeled as "open" or "closed." The problem is defined as computing a sequence of action sets $(A_0, \dots, A_n)$ that transform an initial graph $G$ into a target graph $G_T$ , such that every intermediate state $G_i$ satisfies the DSO rules.

The authors define three types of actions:

Edge Addition: Adding a new edge to the open network.
Edge Removal: Removing an existing open edge.
Edge Switching: Swapping the state of two edges adjacent to the same secondary station (closing an open line and opening a closed one).

Crucially, the framework supports parallel planning, allowing non-interfering actions (those affecting disjoint sets of edges) to be executed simultaneously within a single time step.

ASP Encoding

The solution utilizes the CLINGO solver. The encoding models the evolution of the network over discrete time steps $t$ . Key components include:

State Representation: Predicates track the status of edges (open/closed) at each time step.
Action Generation: Choice rules generate valid sequences of additions, removals, and switches, constrained by buildable and removable edge sets.
Constraint Enforcement:
- Radiality: Enforced by ensuring the closed network is a forest rooted at primary nodes (no cycles between primaries, all secondaries connected to exactly one primary).
- Reconfigurability: Enforced by verifying that every secondary node has a redundant path to a different primary node via the open network.
- Degree Compliance: Aggregates count the degree of secondary nodes, enforcing bounds $[2, 3]$ .
Optimization: Weak constraints are used to minimize the total number of actions and the plan length (lexicographically).

The approach supports both sequential ( $|A_i|=1$ ) and parallel ( $|A_i| \ge 1$ ) execution modes.

Key Contributions

First ASP-based Automation: This work presents the first approach to automate long-term power grid planning capable of handling all necessary grid topological constraints.
Expressive Modeling: The authors demonstrate that ASP can elegantly encode complex graph-theoretic invariants (radiality, reconfigurability) that are difficult to express in planning languages or MILP.
Parallel Execution Framework: The encoding supports parallel action execution, which the authors show significantly reduces the effective search space and plan length compared to sequential approaches.
Validation on Real Data: The approach is validated on both synthetic instances and real-world data derived from the French distribution network, a scale comparable to daily expert operations.

Experimental Results

The authors conducted experiments using the CLINGO solver on a 64-bit Linux machine with a 30-minute timeout per instance.

Synthetic Instances: The study evaluated 175 synthetic instances ranging from 8 to 50 nodes.
- Parallel vs. Sequential: Parallel planning consistently solved more instances than sequential planning. The "compression" of solution length via non-interfering actions resulted in smaller logic programs and faster solving times.
- Search Strategy: For parallel plans, an exponential search strategy (progressively expanding the time horizon) outperformed bounded search, solving significantly more instances. Conversely, for sequential plans, bounded search was more effective.
- Scalability: The approach successfully solved instances up to 50 nodes, with the largest real-world instances (approx. 40 nodes) being comparable to those handled by human experts.
Real-World Instances: Using anonymized data from a French urban network (2 primary nodes, varying secondary nodes), the system solved instances with up to 42 nodes.
- Runtime: Runtimes were comparable to synthetic instances of similar size.
- Optimality: For several solved instances, the system proved the optimality of the parallel plans.
- Validation: Solutions were validated by an automated tool and visually reviewed by domain experts, who confirmed consistency with DSO planning rules and topological comparability to expert-generated solutions.

Significance and Claims

The paper claims that the proposed ASP-based approach offers a viable, automated alternative to the currently manual, expert-driven process of long-term power grid planning. By successfully solving instances of a size comparable to those managed by human experts, the method demonstrates the expressive power of ASP for modeling complex infrastructure constraints.

The authors emphasize that their solution addresses the "major bottleneck" of identifying feasible evolution strategies in a large combinatorial space. They position the work as a foundational step toward intelligent decision-support tools that can complement human expertise, improve reproducibility, and systematically explore investment trajectories. The paper remains modest regarding immediate industrial deployment, noting that future work is required to improve scalability further via domain-specific heuristics and to adapt to additional infrastructure-specific requirements (e.g., budget limits, component immutability).