|
Constraint Graph: Power Supply Restoration
This is a picture of the logical structure of a problem
arising in the course of reconfiguring an electrical power
grid to resupply all non-faulty lines after a short
circuit has caused a circuit breaker to trip off. The
specific problem, here in a form suitable for a finite
domain constraint solver, is to find a plan - a sequence
of opening and closing of switches - at the end of which
the faulty line is isolated and the rest are fed. This is
only a small part of the real problem, which involves
interleaving diagnosis and planning, and must also take
account of loads on the lines, priority customers and so
forth.
Here is an account of the PSR problem, which serves as
a benchmark in both the AI planning and the diagnosis
communities.
The constraint graph shows areas of very tight clustering,
associated in the problem representation with calculation
of which lines or switches are upstream or downstream from
which others, and areas of much looser connection
representing the fluents saying which switches are open
and which are closed in the possible successive states.
For the drawing, the lines are made partially transparent
so as not to obscure the nodes. This results in darker
colour where there are many lines on top of each other or
where they represent relatively strong constraints. The
colours of the dots are assigned in accordance with the
names of the variables, thus corresponding to quantities
that play different roles in the problem and the search
for a solution.
|
|