CSE574 notes for 4/8/03
Dan Bryce


Multiobjective Search
---------------------
 - Time: can be in terms of makespan or slack.  Level is similar to makespan.
 - Cost: can be Cumulative action cost or resource cost.
 - Need an objective function that specifies the user's preferences

Example Multiobjective Problem -> Travel domain
-----------------------------------------------
 - Plans differ in makespan and cost
 - Longer plans have lower cost

Cost/Benefit of using goal deadlines
------------------------------------
 - There is a phase transition in the difficulty of generating plans with 
   deadlines.
 - Few deadlines may make the problem easier because there is less branching
   on valid start times of actions.
 - Many deadlines may make the problem harder because there will be fewer valid
   plans, making the planner backtrack more often.
 - User specified criteria on (lower makespan) deadlines are softer than actual 
   goal deadlines.

Determining what is an optimal solution to a multiobjective problem
-------------------------------------------------------------------
 1. Pareto Sets - allows planner to give the user options of non-dominated solutions
                - the set of non-dominated solutions contains elements where each
                  solution is best in at least one criterion
                - for solutions with the same criterion values for all values, one
                  is kept in the pareto set arbitrarily.
                - User preferences can help rank the set of solutions.
 2. Combination - Convert all objective values into one measure (eg. time is money)
                - The search is no longer multiobjective and can no longer keep sets
                  of solutions
                - User's can specify a weighted linear function or a non-linear one.
                - A more robust (and costly) way to combine measures is to use neural
                  nets.  But this require a human to train it for plans they like.
               ** In heuristic computation, we still need to reason about the criterion
                  independently, then combine the values instead of directly estimating
                  the combined value.

Estimations for MT planning heuristics
--------------------------------------
 - Makespan can be estimated by the temporal planning graph's levels
 - Cost
   + We need to know the cost of each subgoal 
   + Cost is a monotonic decreasing function of time, consequently the lowest cost for
     reaching a goal is not always at the first level it can be acheieved.
   + In general, its hard to get effective, admissible cost heuristics (see TP4)
   + For each literal at a level in the temporal plan graph we need to keep the min
     cost with which its acheived as well as the min-cost action.
   + Tracking literal cost this way requires only step functions because cost is 
     evaluated only at interesting discrete time points.
   + Problem -> how do we know when to stop construction of a planning graph to get 
                good (enough) estimates on cost?
     Solutions -> 1. Wait for an empty Q
                  2. Wait till all action costs have stabalized.
                  3. k-lookahead beyond reaching goals.
   
Cost Propagation
----------------
 - Literals: cost is the cost of the min cost supporting action
 - Actions: Aggreagate the cost of preconditions by sum, max, or combo.
            - could be improved by taking the cost of the set of preconditions

Heuristics using cost functions
-------------------------------
 - h(time, cost) = h_val, (e.g. 100*time + 1*cost) of literals 
 - Use relaxed plans cost and makespan as estimates
   + The greedy relaxed plan can be biased towards lower objective functions
   + RP can be adjusted to account for mutex actions by increasing the makespan