Supply Restoration in Power Distribution Systems A benchmark for AI planning under uncertainty This benchmark, which is derived from a significant real-world case, is both simple to understand and easily scalable. The goal is to reconfigure the distribution network to resupply a maximum of consumers affected by the faults. Due to sensor and actuator uncertainty, the location of the faulty areas and the current network configuration are only partially observable. This makes the problem very challenging.

Our description of power distribution systems and of the supply restoraration problem is based on work done in 1994-1996 in the framework of a contract between IRISA and the French electricity utility EDF. Participants in this contract were Marie-Odile Cordier and Sylvie Thiébaux on the IRISA side, and Isabelle Delouis, Olivier Jehl and Jean-Paul Krivine on the EDF side.

• The most complete description is given in (Thiébaux and Cordier, ECP-01). The description is informal, however.

Power supply restoration system:

• SyDRe, a supply restoration system which handles all aspects of the benchmark is described in (Thiébaux et. al, UAI-96). See also software section.

Planners having a go at the benchmark:

• MBP, a planner based on symbolic model-checking, is the first to have taken on the benchmark. It handles the partial observability aspects of the benchmark, but not the numerical and cost optimisation aspects. This is reported in (Bertoli et al., ECAI-02). The paper provides an encoding of PSR in MBP's input language AR. The net2ar modeler program generates such encodings from a network description in randomnet format (See Software section)


• GPT, a planner based on real-time dynamic programming, is the first to have attacked both the partial observability and the cost optimisation aspects, in both the probabilistic and non-deterministic setting. It does not handle the numerical aspects. This is reported in (Bonet & Thiébaux, ICAPS-03). The paper provides an encoding of PSR in GPT's input language which is a PDDL variant. The net2gpt program generates problem descriptions in GPT's input language from a description in randomnet format.


• UMOP, a planner based on symbolic model-checking has experimented with a non-deterministic and totally observable version of the benchmark. This is reported in Rune Jensen's PhD thesis. (Jensen, PhD-03). The thesis provides an encoding of PSR in NADL, UMOP's input language. Rune has a tool to generate such encodings.


• FF, a planner based on heuristic search, has experimented with a deterministic version of PSR. This is reported in an extended version of (Thiébaux et. al., IJCAI-03). The paper provides a PDDL2.2 (ADL or ADL+derived predicates) encoding. Note that the domain used here is more complex than the domain used for International Planning Competition, as the planner must decide which lines should be resupplied. The net2pddlijcai program generates problem descriptions to go with these domain encodings.

• randomnet, a random PSR problem generator written by John Slaney. Its output format, designed by Piergiorgio Bertoli, is taken as input by translators into various planning languages. [download]



• net2pddl, a translator from randomnet output format to PDDL2.2 written by Piergiorgio Bertoli and Sylvie Thiébaux. It uses adl2strips written by Joerg Hoffmann. It generates a variety of encodings from plain STRIPS to ADL+derived predicates. This software was used to generate the IPC-04 problem suite. At present, it only supports the deterministic version of PSR. [download]



• net2jpeg, a translator from randomnet output format to jpeg, written by Matt Gray. Will be available for download soon.


• net2ar (also known as "Modeler"), a translator from randomnet output format to MBP's input format AR, written by Piergiorgio Bertoli. Supports the partially observable version of PSR.
  [download]


• SyDRe, a network simulator and supply restoration system written by Sylvie Thiébaux and Charles Gretton (see picture of the graphical interface above, and see See also Papers section). The network simulator can be used as a predictive model and a supply restoration component can serve as a reference basis for comparative tests against which planners can be compared. It supports all aspects of PSR. Will be available for download soon.


• net2SyDRe, a translator from randomnet output format to SyDRe input format, written by Matt Gray. Will be available for download soon

• Download IPC-04 PDDL2.2 domain encodings of the deterministic version of PSR (ADL or ADL+derived predicates). It is however better to download the net2pddl program which produces these encodings and many others, along with problem files (see Software section)



• Encodings used in (Thiebaux et. al, IJCAI-03), and (Bonet and Thiebaux, ICAPS-03) are available from the respective papers (see Papers section). If you REALLY need an electronic version, contact me.


• Download data in randomnet output format for the following problems used in the literature: elem, basic, small-rural, simple, ramdoms1f30, simplified-rural, rural.