Homework 6
Metric/Temporal Planning
Given [Apr 10, 2003]
Due [Apr 18, 2003]

Homework set by Minh B. Do. 
Please direct clarification questions to rao as well as
minh@enws209.eas.asu.edu 

The questions are on the Sapa and TP4 framework.
Assume that all techniques in Sapa and TP4 papers are used (except for
the mutexes in Sapa, which may be hard to do in this homework).

The domain specification is given at the bottom. It's a
variation of the logistics domain in which cars are allowed to drive
between any two locations while airplanes can only fly between
different airports.

The distances between locations, the speeds of different vehicle and
the (fixed) durations for load/unload actions are given in the sample
problem following the specification.  Initial/goal locations of
packages and vehicles are given in the problem file.

Questions:
1. Question 1 asks for the state-space search for temporal planning:
For the problem description in log_g1.pddl:

1.1 Show graphically the solution plans (a) P1 containing least number
of actions (b) P2 having the shortest makespan. (You use your head to
come up with these plans).

1.2 Trace Sapa's forward search to show how P1 can be found.  At each
time point, show how the search state S=(P,M,Pi,Q) changes. Also show
how goal satisfaction condition is checked.

Note: + You don't have to follow/discuss any search branch other than the one 
leading to the final plan.
      + For Sapa framework, to give a rough idea on how M is managed, assume
that all trucks and airplane have 10000 gallons of fuel at the beginning
and trucks consume fuel at the rate of 0.5 gallon/mile and airplane at the 
rate of 1 gallon/mile.

2. Question 2 asks for heuristics:

2.1. Build the temporal planning graph for the initial state. What is
the heuristic cost of the init state if the objective function is to:
   a. minimize makespan, 
   b. minimize cost, 
   c.  minimize summation of slack.

Assume that the cost for loading/unloading a package is 3. Cost for
driving is 0.5/mile and for flying is 1/mile. Also assume the goal
deadline is 10000 for both goals. Use zero-lookahead, sum-propagation
rule, cost to achieve goals is the summation of the costs to achieve
individual goals.

2.2. If we use infinite-lookahead, what is the heuristic cost using
the same approach as 2.1? 

2.3. Show how we extract the relaxed plan for minimizing cost objective
funtion for zero and infinite lookahead.  If the "max" heuristic is
used to propage the cost using infinite lookahead, what is the
estimated cost to achieve the first and second goals?


2.4. If we estimate the heuristic value for optimal makespan
objective function as follows:

- Extract the relaxed plan P that achieves the goals at earliest possible
time in the relaxed temporal planning graph.

- Adjust the makespan value by ordering actions in P so that least
number of causal links are violate. Thus, if there are two actions
that are mutex with each other, we try to order one before the
other. What is the makespan value of the final plan after mutex
adjustment? Is that value lower or higher than the perfect heuristic
value?


================log.pddl================================
(define (domain logistics)
  (:requirements :durative-actions :typing :fluents)
  (:types airport - location
          truck airplane - vehicle
          vehicle packet - thing
          thing location - object)

  (:predicates
    (at ?x - thing ?y - location)
    (in ?x - packet ?y - vehicle))

  (:functions
	(loading-time)
	(unloading-time) 
	(speed ?a - vehicle)
	(distance ?x - location ?y - location))

  (:durative-action load
    :parameters (?x - packet ?y - vehicle ?z - location)
    :duration (= ?duration (loading-time))
    :condition (and 
	(at start (at ?x ?z))
	(over all (at ?y ?z)))
    :effect (and 
	(at start (not (at ?x ?z)))
	(at end (in ?x ?y)))
  )

  (:durative-action unload
    :parameters (?x - packet ?y - vehicle ?z - location)
    :duration (= ?duration (unloading-time))
    :condition (and 
	(at start (in ?x ?y))
	(over all (at ?y ?z)))
    :effect (and 
	(at start (not (in ?x ?y)))
	(at end (at ?x ?z)))
  )

  (:durative-action drive
    :parameters (?x - truck ?y - location ?z - location)
    :duration (= ?duration (/ (distance ?y ?z) (speed ?x)))
    :condition (and
   	(at start (at ?x ?y)))
    :effect  (and 
	(at start (not (at ?x ?y)))
	(at end (at ?x ?z)))
  )

  (:durative-action fly
    :parameters (?x - airplane ?y - airport ?z - airport)
    :duration (= ?duration (/ (distance ?y ?z) (speed ?x)))
    :condition (and
	(at start (at ?x ?y)))
    :effect  (and 
	(at start (not (at ?x ?y)))
	(at end (at ?x ?z)))
  )
 )

===================================log_g1.pddl

(define (problem log_1)
 (:domain logistics)
 (:objects
	office1 office2 - location 
	airport1 airport2 - airport 
	truck1 truck2 - truck 
	airplane1 - airplane 
	packet1 packet2 - packet)

 (:init 
	(at truck1 office1) 
	(at truck2 airport2) 

	(at airplane1 airport1)
 
	(at packet1 office1) 
	(at packet2 airport1)

	(= (speed airplane1) 500)
	(= (speed truck1) 50)
	(= (speed truck2) 50)

	(= (loading-time) 0.3)
	(= (unloading-time) 0.6)

	(= (distance office1 office1) 0)
	(= (distance office1 airport1) 50)
	(= (distance office1 office2) 1350)
	(= (distance office1 airport2) 1500)

	(= (distance airport1 office1) 50)
	(= (distance airport1 airport1) 0)
	(= (distance airport1 office2) 1150)
	(= (distance airport1 airport2) 1100)

	(= (distance office2 office1) 1350)
	(= (distance office2 airport1) 1150)
	(= (distance office2 office2) 0)
	(= (distance office2 airport2) 100)

	(= (distance airport2 office1) 1500)
	(= (distance airport2 airport1) 1100)
	(= (distance airport2 office2) 100)
	(= (distance airport2 airport2) 0)
 )

 (:goal (and 
	(at packet1 office2) 
	(at packet2 office2)
	)
 )
)

============================================================