|
Size: 4615
Comment:
|
Size: 4611
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 25: | Line 25: |
| * '''Output''': {{{drive/3, pick/2, drop/2 and refuel/2}}} | * '''Output''': {{{drive/3, pick/2, drop/2, refuel/2}}} |
| Line 28: | Line 28: |
| 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 44: | Line 44: |
| 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. |
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. |
| Line 47: | Line 47: |
| 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 49: | Line 49: |
| 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 51: | Line 51: |
| 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. |
Airport Pickup
Contents
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, refuel/2
Input format
A. Atoms to describe the city:
location(L) listing the names of locations.
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.
airport(L) indicating that location L is an airport. (there will be exactly 2 locations listed as airports)
gasstation(L) indicating that location L is a gas station.
B. Atoms to describe the passengers:
passenger(P) listing the names of passengers
init_at(P,L) stating that passenger P is initially at location L, where L is an airport.
C. Atoms to describe the vehicles:
vehicle(V, M) stating that V is a vehicle and its maximum gasoline capacity is M, 100 < M <= 500.
init_at(V, L) stating that vehicle V is initially at location L.
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.
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