welcome: please sign in
location: Diff for "FinalProblemDescriptions/AirportPickup"
Differences between revisions 2 and 3
⇤ ← Revision 2 as of 2011-01-20 09:34:43 →
Size: 4563
Editor: CarmenSantoro
Comment:
← Revision 3 as of 2011-01-20 09:43:46 → ⇥
Size: 4612
Editor: CarmenSantoro
Comment:
Deletions are marked like this. Additions are marked like this.
Line 23: Line 23:
 * '''Input''': location/1, driveway/3, airport/1, gasstation/1, passenger/1, init_at/2, vehicle/2, init_at/2, init_gas/2  * '''Input''': {{{location/1, driveway/3, airport/1, gasstation/1, passenger/1, init_at/2, vehicle/2, init_at/2, init_gas/2}}}
Line 25: Line 25:
 * '''Output''': drive/3, pick/2, drop/2 and refuel/2  * '''Output''': {{{drive/3, pick/2, drop/2 and refuel/2}}}
Line 29: Line 29:
 A.  Atoms to describe the city:
 1) location(L) listing the names of locations.
 2) driveway(L1, L2, D) where L1 and L2 are locations, indicating that
    it is possible to drive from L1 to L2 ( and from L2 to L1 ) and that the
    gasoline cost from L1 to L2 is D. 0 < D <= 100.
 3) airport(L) indicating that location L is an airport.
    (there will be exactly 2 locations listed as airports)
 4) gasstation(L) indicating that location L is a gas station.

 B.  Atoms to describe the passengers:
 1) passenger(P) listing the names of passengers
 2) init_at(P,L) stating that passenger P is initially at location L, where L
    is an airport.


 C.  Atoms to describe the vehicles:
    1) vehicle(V, M) stating that V is a vehicle and its maximum gasoline capacity
       is M,   100 < M <= 500.
    2) init_at(V, L) stating that vehicle V is initially at location L.
    3) init_gas(V, G) indicating that initially, vehicle V has G units of gasoline.
       0<= G <= M. where M is the maximum gasoline capacity of the vehicle.		  A. Atoms to describe the city:
  1. {{{location(L)}}} listing the names of locations.
  2. {{{driveway(L1, L2, D)}}} where L1 and L2 are locations, indicating that it is possible to drive from L1 to L2 ( and from L2 to L1 ) and that the gasoline cost from L1 to L2 is D. 0 < D <= 100.
  3. {{{airport(L)}}} indicating that location L is an airport. (there will be exactly 2 locations listed as airports)
  4. {{{gasstation(L)}}} indicating that location L is a gas station.
 B. Atoms to describe the passengers:
  1. {{{passenger(P)}}} listing the names of passengers
  2. {{{init_at(P,L)}}} stating that passenger P is initially at location L, where L is an airport.
 C. Atoms to describe the vehicles:
  1. {{{vehicle(V, M)}}} stating that V is a vehicle and its maximum gasoline capacity is M, 100 < M <= 500.
  2. {{{init_at(V, L)}}} stating that vehicle V is initially at location L.
  3. {{{init_gas(V, G)}}} indicating that initially, vehicle V has G units of gasoline. 0<= G <= M. where M is the maximum gasoline capacity of the vehicle.
Line 56: Line 47:
 A) drive(V,L,S) indicates vehicle V drives to location L at step S of the
instruction sequence. This action is possible only if V is in a location adjacent
to L at step S. 		 A. {{{drive(V,L,S)}}} indicates vehicle V drives to location L at step S of the instruction sequence. This action is possible only if V is in a location adjacent to L at step S.
Line 60: Line 49:
 B) pick(V,P,S) indicates vehicle V picks passenger P at step S. This action is possible only if V and P are at the same location at step S.  B. {{{pick(V,P,S)}}} indicates vehicle V picks passenger P at step S. This action is possible only if V and P are at the same location at step S.
Line 62: Line 51:
 C) drop(V,P,S) indicates vehicle V drops passenger P at step S. This action is possible only if V is carrying P at step S.  C. {{{drop(V,P,S)}}} indicates vehicle V drops passenger P at step S. This action is possible only if V is carrying P at step S.
Line 64: Line 53:
 D) refuel(V,S) indicated vehicle V fills up its gas tank at step S of the sequence.  D. refuel(V,S) indicated vehicle V fills up its gas tank at step S of the sequence.
Line 69: Line 58:
{{{location(1). location(2). location(3). location(4). {{{
location(1). location(2). location(3). location(4).
Line 80: Line 70:
init_at(taxi_1, 2). init_gas(taxi_1, 50).}}} init_at(taxi_1, 2). init_gas(taxi_1, 50).
}}}
Line 84: Line 75:
{{{drive(taxi_1, 1, 0). {{{
drive(taxi_1, 1, 0).
Line 90: Line 82:
drop(taxi_1, a, 6). }}} drop(taxi_1, a, 6).
}}}
Line 94: Line 87:
{{{location(1). location(2). location(3). location(4). {{{
location(1). location(2). location(3). location(4).
Line 105: Line 99:
vehicle(taxi_2, 80). init_at(taxi_2, 4). init_gas(taxi_1, 80). }}} vehicle(taxi_2, 80). init_at(taxi_2, 4). init_gas(taxi_1, 80).
}}}
Line 109: Line 104:
{{{pick(taxi_1, a, 0). pick(taxi_2, b, 0) {{{
pick(taxi_1, a, 0). pick(taxi_2, b, 0)
Line 113: Line 109:
drop(taxi_1, a, 4). drop(taxi_2, b, 4). }}} drop(taxi_1, a, 4). drop(taxi_2, b, 4).
}}}

Airport Pickup

Contents

  1. Airport Pickup
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Sample #1 input
    6. Sample #1 output
    7. Sample #2 input
    8. Author(s)

Problem Description

A planning problem than that involves moving objects around a weighted graph.

Imagine a city composed of locations and possible driveways between these locations. Two of this locations are Airports and some are Gas Stations. A set of passengers are waiting in Airport #1 and Airport #2. Passengers from Airport #1 need to reach Airport #2 and vice-versa.

A set of vehicles are located around the city. Each of these vehicles can pick and transport one passenger at a time.

Driving a vehicle between two city locations costs the vehicle certain amount of gasoline. Initially all vehicles have certain amount of gasoline already in them. If a Vehicle runs out of gasoline, it cannot be driven anymore. Vehicles can re-fill gasoline at a Gas Station.

Find a plan to drive the vehicles and move all the passengers to their respective destinations.

A problem instance consists of a description of a city's (a weighted undirected graph), information about which locations in the city are Airports and Gas Stations, and statements about the location and status of vehicles and passengers.

Predicates

  • Input: location/1, driveway/3, airport/1, gasstation/1, passenger/1, init_at/2, vehicle/2, init_at/2, init_gas/2

  • Output: drive/3,  pick/2,  drop/2 and refuel/2

Input format

  1. Atoms to describe the city:

    1. location(L) listing the names of locations.

    2. driveway(L1, L2, D) where L1 and L2 are locations, indicating that it is possible to drive from L1 to L2 ( and from L2 to L1 ) and that the gasoline cost from L1 to L2 is D. 0 < D <= 100.

    3. airport(L) indicating that location L is an airport. (there will be exactly 2 locations listed as airports)

    4. gasstation(L) indicating that location L is a gas station.

    B. Atoms to describe the passengers:

    1. passenger(P) listing the names of passengers

    2. init_at(P,L) stating that passenger P is initially at location L, where L is an airport.

    C. Atoms to describe the vehicles:

    1. vehicle(V, M) stating that V is a vehicle and its maximum gasoline capacity is M, 100 < M <= 500.

    2. init_at(V, L) stating that vehicle V is initially at location L.

    3. init_gas(V, G) indicating that initially, vehicle V has G units of gasoline. 0<= G <= M. where M is the maximum gasoline capacity of the vehicle.

Output format

The output format is a sequence of instructions to drive the cars and move the passengers. This sequence is formed with the atoms drive(V,L,S), pick(V,P), drop(V,P) and refuel(V,S) where:

  1. drive(V,L,S) indicates vehicle V drives to location L at step S of the instruction sequence. This action is possible only if V is in a location adjacent to L at step S.

    B. pick(V,P,S) indicates vehicle V picks passenger P at step S. This action is possible only if V and P are at the same location at step S.

    C. drop(V,P,S) indicates vehicle V drops passenger P at step S. This action is possible only if V is carrying P at step S. D. refuel(V,S) indicated vehicle V fills up its gas tank at step S of the sequence.

This action is only possible if V is at a gas station.

Sample #1 input

location(1). location(2). location(3). location(4).
airport(1). airport(4).
gasstation(3).
driveway(1,2,10).
driveway(2,3,20).
driveway(3,4,15). 

passenger(a).
init_at(a,1).

vehicle(taxi_1, 100).
init_at(taxi_1, 2).  init_gas(taxi_1, 50).

Sample #1 output

drive(taxi_1, 1, 0).   
pick(taxi_1, a, 1). 
drive(taxi_1, 2, 2).   
drive(taxi_1, 3, 3).   
refuel(taxi_1, 4)      
drive(taxi_1, 4, 5).   
drop(taxi_1, a, 6).

Sample #2 input

location(1). location(2). location(3). location(4).
airport(1). airport(4).
gasstation(3).
driveway(1,2,10).
driveway(2,3,20).
driveway(3,4,15). 

passenger(a).  init_at(a,1).
passenger(b).  init_at(b,4).

vehicle(taxi_1, 100). init_at(taxi_1, 1).  init_gas(taxi_1, 50).
vehicle(taxi_2, 80).  init_at(taxi_2, 4).  init_gas(taxi_1, 80).

== Sample #2 output == 

pick(taxi_1, a, 0).    pick(taxi_2, b, 0) 
drive(taxi_1, 2, 1).   drive(taxi_2, 3, 1).   
drive(taxi_1, 3, 2).   drive(taxi_2, 2, 2).         
drive(taxi_1, 4, 3).   drive(taxi_2, 1, 3).   
drop(taxi_1, a, 4).    drop(taxi_2, b, 4).

Author(s)

Author: A. Ricardo Morales
Affiliation: Texas Tech University, United States

ASP Competition 2011: FinalProblemDescriptions/AirportPickup (last edited 2011-03-19 18:02:38 by GiovambattistaIanni)