[SOLVED] CS ICAPS 2010

PowerPoint Presentation

Reasoning with Preferences and Temporal Constraints: OPTIC

Copyright By Assignmentchef assignmentchef

Relationships Between Planners
CRIKEY = FF + STN;
Colin = CRIKEY s/STN/LP/;
POPF = COLIN + Fewer ordering constraints;
OPTIC = POPF + Preferences.

Partial Order Planning Forwards: POPF
Forward-Chaining Partial-Order Planning. A. J. Coles, A. I. Coles, M. Fox, and D. Long. ICAPS 2010
Have I Been Here Before? State Memoisation in Temporal Planning A. J. Coles and A. I. Coles. ICAPS 2016.

Move Train BED SAC
Move Train SAC LON
Bus Route 2 CITY
Bus Route 1 SAC

Optimising Preferences: OPTIC

Searching for Good Solutions in Goal-Dense Search Spaces. A. J. Coles and A. I. Coles. ICAPS (2013)
Temporal Planning with Preferences and Time-Dependent Continuous Costs. J. Benton, A. J. Coles and A. I. Coles. ICAPS (2012)
LPRPG-P: Relaxed Plan Heuristics for Planning with Preferences. A. J. Coles and A. I. Coles. ICAPS (2011)

The train and the bus are at the station simultaneously: (sometime (and (at train SAC) (at bus SAC)))
The bus arrives in the city at 9am or earlier: (within 35 (at bus CITY)))

How Can we Encode this in the LP?
Train arrives before bus departs:
BDSAC TASAC >= 0.01
Bus arrives before train departs:
TDSAC BASAC >= 0.01
Bus arrives at CTY by 9am (time 35):
BACTY <= 35But these are not hard constraints, if we put them in as such then the LP could become unsolvable and the plan can be reported as invalid when it is not.Need to use a MIP and allow the option to veto the constraints.Big M ConstraintsA 0/1 integer variable per preference p1 , p2A very large constant M.Train arrives before bus departs:BDSAC – TASAC + Mp1 >= 0.01
Bus arrives before train departs:
TDSAC BASAC + Mp1 >= 0.01
Bus arrives at CTY by 9am (time 35):
BACTY Mp2 <= 35In the objective function:Minimise: whatever + 5 p1 + 2 p2 Now the MIP solver can choose either to make p1 = 0 (p2 = 0) and satisfy the constraints or make p1 = 1 (p2 = 1) and violate the constraint paying the objective cost.Synergy: Planner and Optimisation Solver 47 CombinationsNow Youre Solving a MIP that could be NP HardAgain we tested it empirically, its not generally that time consuming, in fact surprisingly building the MIP takes longer than solving it:/docProps/thumbnail.jpeg CS: assignmentchef QQ: 1823890830 Email: [email protected]