Zeno Travel

Our last domain is Zeno Travel, based on a domain used in IPC-3. Problem instances of this domain involve using airplanes to move people between cities. An airplane requires fuel to fly. It can be flown at two different speeds—the higher speed requiring more fuel. Our problem instance used one aircraft, two people, three cities and seven fuel levels. The actions of the domain are “start-boarding”, “complete-boarding”, “start-debarking”, “complete-debarking”, “start-refueling”, “complete-refueling”, “start-flying”, “complete-flying”, “start-zooming”, and “complete-zooming”. The initial configuration specifies the location of the plane, the initial fuel level of the plane and the location of all people (as well as some initializations to allow for arithmetic type operations on the fuel-level objects). The goal configuration specifies a destination for the plane and destinations for all people. The noise in this domain comes from the family of “complete-X” actions. Each time a “complete-X” action is executed it will have the desired effect with probability 1/k for some positive integer k (note that k is a function of the action executed, specifically k = 20 for “complete-boarding” and k = 30 for “complete-debarking”). If the desired effect is not achieved then there is no effect, and this occurs with probability 1 − (1/k). This structure is meant to represent actions with random duration. Each “durative” action X is represented by two primitive actions “start-X” and “complete-X”, giving X a duration that is geometrically distributed.

Ultimately, this problem presented no real challenge because we neglected to include action costs. Since actions have either standard desired effect or none at all, a planner can simple continue to execute an action until its effect is achieved, without incurring any cost.

Håkan L. S. Younes
2005-12-06