Hydraulic Planning

<<TableOfContents: execution failed [list index out of range] (see also the log)>>

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 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 jet j, a shuttle controller needs to find a shortest sequential plan to pressurize j. Write a program which automates this process.

Input Format

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

The state description uses atoms:

The goal to achieve:

Output Format

A sequence of atoms of the form

which 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

Comment

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

Author(s)