PowerPoint Presentation
Reasoning with Preferences and Temporal Constraints: OPTIC
Copyright By PowCoder代写 加微信 powcoder
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 <= 35
But 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 Constraints
A 0/1 integer variable per preference p1 , p2
A 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 <= 35
In 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 Combinations
Now 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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com