[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Fwd: On the Sapa homework
Date: Mon, 21 Apr 2003 19:30:50
+0700
From: Nguyen Hong Hanh <nguyenhhanh@hn.vnn.vn>
Subject: On the Sapa homework
To: rao@asu.edu
X-Mailer: Microsoft Outlook, Build 10.0.2616
Importance: Normal
X-Spam-Status: No, hits=0.2 required=5.0
tests=IN_REP_TO,ORIGINAL_MESSAGE
version=2.53
X-Spam-Level:
X-Spam-Checker-Version: SpamAssassin 2.53
(1.174.2.15-2003-03-30-exp)
To Rao and class,
Having to write down the answer for the homework myself, I realized
that
the second part is kind of time-consuming (I never learned from my
past
experience of having to actually draw a planning graph in Rao's
class).
Anyway, I want to add some clarifications to the second part,
hopefully
it comes not too late to save some people's time.
When drawing the relaxed temporal planning graph in Questions 2.1,
2.2,
and 2.3, you don't need to put all junk (unnecessary) actions that
do
not contribute to the heuristic values into the graph. For
examples:
fly(Plane,Airport2,Airport1), or drive(Truck2,Airport2,Office1). I
realized that if we attempt to build the full relaxed temporal
planning
graph with all the actions in, then it becomes pretty big as we go
forward. You only need to show how "useful" actions that
contribute to
the different objective functions (asked in Question 2.1) are lined
up
in the RTPG and how they affect the cost functions over time.
However,
don't just draw the RTPG with solely actions that appear in the
solutions, put some other actions in to show that the RTPG is a
superset
of the solutions.
In question 2.2, you also only need to draw actions around the line
of
actions that contribute to the minimum cost. The more important point
is
to show how the cost functions change precisely according to time
and
which actions "give" those value at those time points. Storing
those
actions will help in solving part of Question 2.3.
For the last question in 2.3, you don't need to extract the relaxed
planning graph. Only show on the graph in 2.2 how the costs are
propagated and what the final values are.
Minh
PS: If you already built the full planning graph, then well, you
learnt
how complicate the thing is even for a simple problem. Welcome to
the
real-world.
PSS: To Rao: The solution is coming in the next mail in the form of
5
scanned hand-written pages.
-----Original Message-----
From: Subbarao Kambhampati
[mailto:rao@parichaalak.eas.asu.edu]
Sent: Thursday, April 10, 2003 10:50 PM
To: minh@parichaalak.eas.asu.edu
Subject: I plan to use this (small) subset of your homework
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?
================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)
)
)
)
============================================================