|
Size: 2440
Comment:
|
Size: 2446
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| == Problem description == |
== Problem Description == |
| Line 14: | Line 13: |
| Tanks can be full or empty. Valves can be opens 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. | 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. |
| Line 21: | Line 20: |
| == Input Format == | == Input format == |
| Line 41: | Line 40: |
== Output Format == |
== Output format == |
| Line 50: | Line 48: |
| == Example== | |
| Line 54: | Line 51: |
| This problem took part in the Second ASP Competition and was proposed by Michael Gelfond, Ricardo Morales and Yuanlin Zhang. | Comment: This problem took part in the Second ASP Competition and was proposed by Michael Gelfond, Ricardo Morales and Yuanlin Zhang. |
| Line 56: | Line 53: |
| == Example == |
Hydraulic Leaking
Problem Description
A simplified version of the hydraulic system on a space shuttle consists of a directed graph, G, such that:
- Nodes of this graph are labeled as tanks,jets, or junctions.
- Every link between two nodes is labeled by a valve.
- There are no paths in G between any two tanks.
- For every jet there always is a path in G from a tank to this jet.
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:
- tank(t): t is a tank
- jet(j): j is a jet
- junction(p): p is a junction
- valve(v): v is a valve
- link(n1, n2, v): v is the valve on the pipe connecting node n1 and n2.
- numValves(n): n is the total number of valves in the graph
The state description should use atoms:
- full(t) iff tank t is full. A tank is empty if it is not mentioned to be full in the input.
- leaking(v) iff valve v is leaking. A valve is not leaking if it is not mentioned to be leaking in the input.
The goal to achieve:
- goal(j): jet j needs to be pressurized
Output format
A sequence of atoms of the form
- switchon(v, t).
which means to open valve v at time step t. The switches should occur at onsecutive time steps beginning from 0.
Comment
Comment: This problem took part in the Second ASP Competition and was proposed by Michael Gelfond, Ricardo Morales and Yuanlin Zhang.
Example
Author(s)
- Francesco Calimeri
- University of Calabria, Italy
- Maria Carmela Santoro
- University of Calabria, Italy