[SOLVED] CS代考 ICAPS 2010

PowerPoint Presentation

Reasoning with Preferences and Temporal Constraints: OPTIC

Copyright By PowCoder代写加微信 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 You’re Solving a MIP that could be NP Hard…Again we tested it empirically, it’s 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]