welcome: please sign in
location: ProblemsDescription / HydraulicLeaking

Hydraulic Leaking

Problem Description

A simplified version of the hydraulic system on a space shuttle consists of a directed graph, G, such that:

Tanks can be full or empty. Valves can be open or closed. Some of the valves may be leaking. A state of G is specified by the set of full tanks, the set of open valves, and the set of leaking valves. A node of G is called pressurized in state S if it is a full tank or if there exists a path from some full tank of G to this node such that all the valves on the edges of this path are open.

We assume that in a state S a shuttle controller can open a valve V2 corresponding to a directed link <N1,N2> only if N1 is pressurized. (Note, a leaking valve can be opened.)

Problem: Given a graph G together with a initial state of G and a jet j, a shuttle controller needs to find a shortest plan among those using the least number of leaking valves. Write a program which automates this process.

Input format

The graph should be described by the collection of ground atoms:

The state description should use atoms:

The goal to achieve:

Output format

A sequence of atoms of the form

which means to open valve v at time step t. The switches should occur at consecutive time steps beginning from 0.


Comment: This problem took part in the Second ASP Competition and was proposed by Michael Gelfond, Ricardo Morales and Yuanlin Zhang.



ASP Competition 2011: ProblemsDescription/HydraulicLeaking (last edited 2011-01-14 10:31:16 by FrancescoCalimeri)