Hydraulic System Planning

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 can be stuck in the close position. A state of G is specified by the set of full tanks, the set of open valves, and the set of valves stuck in the closed position.

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 and not stuck.

Problem: Given a graph G together with an initial state and a number of jets j1 ... jn, a shuttle controller needs to find a shortest sequential plan to pressurize j1,...jn. Write a program which automates this process. All valves are assumed to be closed in their initial state.

Predicates

• Input: tank/1, jet/1, junction/1, valve/1, link/3, numValves/1, full/1, stuck/1, goal/1 

• Output: switchon/2

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 uses atoms:

• full(t) iff tank t is full. A tank is empty if it is not mentioned to be full in the input.

• stuck(v): valve v is stuck

The goal(s) to achieve:

• goal(j): jet j needs to be pressurized

Output format

A sequence of atoms of the form

• switchon(v, t).

means an action to open valve v at time step t, where t is an integer. The switches should occur at consecutive time steps beginning from 0. (Note that, in contrast to the original description, the order of atoms in the output does not matter.)

Example(s)

INPUT

tank(t311). tank(t312). tank(t313). tank(t314).
jet(j1). jet(j2).
junction(p1). junction(p2). junction(p3). junction(p4). junction(p5). junction(p6). junction(p7). junction(p8). junction(p9). junction(p10).

valve(v1).  valve(v2).  valve(v3).  valve(v4).  valve(v5).
valve(v6).  valve(v7).  valve(v8).  valve(v9).  valve(v10).
valve(v11). valve(v12). valve(v13). valve(v14). valve(v15).
valve(v16). valve(v17). valve(v18). valve(v19). valve(v20).

numValves(20).

link(t311, p1, v1).  link(p1, p2, v2).  link(p3, p4, v4).  link(t313, p4, v5). link(p2, p3, v3).  link(p2, j1, v6).  link(p3, j1, v7). link(p5, p1, v8).  link(p4, p6, v9). link(p5, p6, v10). link(p6, p5, v11). link(p7, p5, v12). link(p6, p10, v13). link(t312, p7, v14). link(p8, p7, v15).  link(p10, p9, v17). link(t314, p10, v18). link(p9, p8, v16). link(p8, j2, v19). link(p9, j2, v20).

full(t311). full(t312). full(t313). full(t314). stuck(11).

goal(j2).

Output:  switchon(v20,2). switchon(v17,1). switchon(v18,0). 

Notes and Updates

With respect to the version of this problem as of the 2nd ASP Competition, there can be more than one goal per instance. All valves are assumed to be closed in their initial state.

It is important to point out that the Competition's instance family is such that each individual goal subgraph is disjoint (a tank can reach at most one goal).

Author(s)

• Author: Francesco Calimeri
  • Affiliation: University of Calabria, Italy
• Author: Maria Carmela Santoro
  • Affiliation: University of Calabria, Italy