= Airport Pickup =

<<TableOfContents>>

== Problem Description ==

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

Imagine a city composed of locations and possible driveways between these locations. Two of these 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 (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, refuel/2}}}

== Input format ==
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.

== 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:

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. It is not possible for a vehicle V to be driven at the same time it is being refueled or
is picking or dropping a passenger. In other words, for a vehicle  x  it is not possible for  {{{drive(x,L,S)}}}  to appear with {{{pick(x,P,S)}}}, {{{drop(x,P,S)}}} or {{{refuel(x,S)}}} in the same step in the output sequence. 

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.

Time steps are given as integers starting from 0.


== Example(s) ==

=== Example #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).
}}}

'''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). 
}}}  

=== Example #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_2, 80). 
}}}

'''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). 
}}}

== Notes and Updates ==

 * Fixed typo on example 2 on 19/03/2011;
 * Training Instances: updated on date 03/02/2011;
 * Specification: updated on date 28/01/2011;

== Author(s) ==
 * Author: A. Ricardo Morales 
   * Affiliation: Texas Tech University, United States