Planning with Resources Philippe Laborie [email protected] ILOG Foreword Applications of AI Planning Aerospace Space - Satellite, Launcher manufacturing - Launch site operations - Spacecraft operations - Space users - Autonomous space exploration Aviation - Manufacturers and suppliers - Airlines, Airports - Maintenance and repair organizations - Air Traffic Control 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Foreword Applications of AI Planning Defense Military logistic applications Rescue and Military operations planning Non-combatant Evacuation Operations Emergency Assistance Air Campaign Planning Army Unit Operations Coalition Operations 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Foreword Applications of AI Planning New information technology Planning & Scheduling for the Web Workflow, Business Process Management Systems Management Aids Help Desks and Assistants Personal Assistants Data analysis tasks, Database query Virtual reality or other simulated environments Computer games (bridge) 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Foreword Applications of AI Planning Industry Process planning Factory automation - Production line scheduling - Assembly planning - Maintenance planning Electronic design and manufacturing Logistics Project planning Construction planning Engineering Tasks Management Tasks 5 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Foreword Applications of AI Planning Civil Security and Environment Crisis Management Evacuation Planning Search & Rescue Coordination Oil Spill Response Medical Applications Bioinformatics Personal Active Medical Assistant 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Foreword Applications of AI Planning What most of these applications have in common ? Manufacturing: A grinding operation requires a grinding machine. The grinding machine can perform only one operation at a time. Only one grinding machine is available in the shop. Project Management: In a web site development project, the task of testing browsers compatibility requires an effort of 6 person-months of a quality engineer. 5 quality engineers are available. Satellite: When the satellite is not within range of a receiving station, it can store images on an onboard solid-state memory that provides a capacity of 90 Gbits (550 images). Crisis Management: An aircraft B737-200 has a capacity to evacuate at most 120 people. Maximum cargo loading is 3,400kg for a volume of 14.3 m3. Maximal range of the aircraft is 2480km. … they need the ability to reason about resources 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Overview Planning with Resources Part I. State of the Art Overview Definition of a Resource Problem Modeling Problem Solving Part II. Focus on Constraint-Based Approaches Constraint-Programming Problem Modeling Problem Solving Constraint Propagation Search 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Planning with Resources Part I: State of the Art Overview State of the Art Definition of a Resource A resource is any substance or (set of) object(s) whose cost or available quantity induce some constraint on the operations that use it Manufacturing: A grinding operation requires a grinding machine. The grinding machine can perform only one operation at a time. Only one grinding machine is available in the shop. The1 grinding machine is a resource. It constrains the grinding operations to execute sequentially on the machine. 0 Grinding-op1 10 Grinding-op3 Grinding-op2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece time State of the Art Definition of a Resource A resource is any substance or (set of) object(s) whose cost or available quantity induce some constraint on the operations that use it Project Management: In a web site development project, the task of testing browsers compatibility requires an effort of 6 person-months of a quality engineer. 5 quality engineers are available. 5 The team of quality engineers is a resource. It constrains the number of tasks that can be executed in parallel and the 0 duration of these tasks. 3 months 2 engineers Web-site-dev1 Test-software1 11 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece time State of the Art Definition of a Resource A resource is any substance or (set of) object(s) whose cost or available quantity induce some constraint on the operations that use it Satellite: When the satellite is not within range of a receiving station, it can store images on an onboard solid-state memory that provides a capacity of 90 Gbits (550 images). 550 The solid-state memory is a resource. It constrains the number of images that can be taken between two periods of visibility of the receiving station. 0 time Pic1 12 Pic2 Pic5 Pic3 Pic4 Send-data PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Definition of a Resource A resource is any substance or (set of) object(s) whose cost or available quantity induce some constraint on the operations that use it Crisis Management: An aircraft B737-200 has a capacity to evacuate at most 120 people. Maximum cargo loading is 3,400kg for a volume of 14.3 m3. Maximal range of the aircraft is 2480km. 3400 The seat capacity of the B737-20 is a resource. It constrains the number of people the plane can evacuate in a single flight. The cargo capacity of the B737-20 is another resource. It constrains the weight the aircraft can transport in a single flight. Etc... 0 time Load-truck 13 Load-car Unload-car Unload-truck PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Definition of a Resource Resources Typology 14 Unary resource: Resource of capacity 1. Two activities requiring the same unary resource cannot overlap Discrete resource: Resource of capacity Q. Activities requiring the same discrete resource can overlap provided the resource capacity Q is not exceeded Reservoir: Resource of capacity Q and initial level L; Activities may consume or produce the reservoir. The level of the reservoir over time must be kept in the interval [0,Q] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Definition of a Resource unary resource availability 1 0 Op1 15 Op2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece time State of the Art Definition of a Resource discrete resource availability Q 0 time Op1 Op2 16 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Definition of a Resource In theory, a discrete resource of maximal capacity Q can be represented as Q unary resources Op1 {R1,…,Ri,…,Rj,…,RQ} Opi Opj OpQ OpQ+1 17 {R1,…,Ri,…,Rj,…,RQ} {R1,…,Ri,…,Rj,…,RQ} No solution after trying Q! allocations {R1,…,Ri,…,Rj,…,RQ} {R1,…,Ri,…,Rj,…,RQ} PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Definition of a Resource reservoir level Q 0 Op1 Op3 Op2 18 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece time State of the Art Definition of a Resource Resources are tightly linked with the notions of time & concurrency For unary and discrete resources, activities use the resource over some time interval Handling parallel execution of activities is necessary to take advantage of non-unitary capacities There may exist complex relations linking the duration of an activity with the amount of resource it uses, consumes and/or produces 19 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Definition of a Resource Resources may impose other constraints than just capacity State constraints : two activities requiring the resource to be in incompatible states cannot overlap Minimal transition time between two consecutive activities using the same unary resource Batching: two overlapping activities using the same resource must start and end at the same time These additional constraints can generally be expressed by classical planning predicates 20 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Definition of a Resource So … the hard point for planning with resources is mainly the management of Numerical time and Numerical capacity/availability 21 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling: STRIPS How hard is it to model time and capacities in STRIPS ? Exercise. Build a STRIPS model for the following domain A task to test a web-site lasts for 3 months and requires 2 quality engineers (out of 5 available). As a result of the task, the web-site is tested. Other tasks also have duration and compete for the same resource. The model must correctly handle task parallelism. 22 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Difficulty #1: Numerical quantities No integer arithmetic is available in STRIPS. We need to provide one. In domain description (:predicates (plus ?i ?j ?k)) In problem definition (:objects _0 _1 _2 _3 _4 _5 _6 _7 _8 … ) (:init (plus _0 _1 _1)(plus _1 _1 _2)(plus _2 _1 _3) … (plus _0 _2 _2)(plus _1 _2 _3)(plus _2 _2 _4) … ) 23 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Difficulty #1: Numerical quantities No integer arithmetic is available in STRIPS. We need to provide one. Example of action that increase a quantity (:action IncreaseQuantity :parameters (?i ?d ?j) :precondition (and (quantity ?i) (plus ?i ?d ?j)) :effect (and (not (quantity ?i)) (quantity ?j))) 24 ; ?j == ?i + ?d PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Difficulty #2: Discrete Resource The task is a time interval over which the resource is used. Two actions to represent the task (:action TestWebSite-Start :parameters (?q2 ?q0) :precondition (and (free-engineers ?q2) (plus ?q0 _2 ?q2)) :effect (and (not (free-engineers ?q2)) (free-engineers ?q0))) 25 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Difficulty #2: Discrete Resource The task is a time interval over which the resource is used. Two actions to represent the task (:action TestWebSite-End :parameters (?q0 ?q2) :precondition (and (free-engineers ?q0) (plus ?q0 _2 ?q2)) :effect (and (not (free-engineers ?q0)) (free-engineers ?q2) (web-site-tested))) 26 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Difficulty #2: Discrete Resource The task is a time interval over which the resource is used. Initially, the amount of resource is 5: (:init (free-engineers _5) … ) 27 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Difficulty #3: Task Duration Use a predicate startedAtTask to record when the task was started and a global clock clock to measure time (:predicates (clock ?t) (testwebsite_started_at ?t) … ) (:action TestWebSite-Start :parameters (?t0 … ) :precondition (and (clock ?t0) … ) :effect (and (testwebsite_started_at ?t0) … )) 28 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Difficulty #3: Task Duration (:action TestWebSite-End :parameters (?t3 ?t0 … ) :precondition (and (testwebsite_started_at ?t0) (clock ?t3) (plus ?t0 _3 ?t3) … ) :effect (and (not (testwebsite_started_at ?t0) … ))) 29 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Difficulty #3: Task Duration Now we only need an action to increase time when necessary: (:action Tick :parameters (?t0 ?t1) :precondition (and (clock ?t0) (plus ?t0 _1 t1)) :effect (and (not (clock ?t0)) (clock ?t1))) We start at time 0: (:init (clock I0) … ) 30 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Conclusion It is possible to represent time and resources in STRIPS BUT … the model is not completely intuitive No built-in arithmetic A relative change on a resource (free-engineers -= 2) is represented by two absolute changes: (DEL (free-engineers ?x)) (ADD (free-engineers ?x+2)) Representation of time is not natural (action TICK) 31 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Conclusion A relative change on a resource is represented by two absolute changes (PRECOND (free-engineers ?x1)(plus ?x1 _1 ?x2)) (DEL (free-engineers ?x1)) (ADD (free-engineers ?x2)) MUTEX (PRECOND (free-engineers ?y1)(plus ?y1 _1 ?y2)) (DEL (free-engineers ?y1)) (ADD (free-engineers ?y2)) 32 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : STRIPS Conclusion AND what about the performances ? engineers Test Software Training TestWebSite TestWebSite Test Software Training 26s 150s 580s 33 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling Beyond STRIPS Standalone languages PDDL2.1 BTPL Planning systems (language) parcPLAN O-Plan IXTET ASPEN RAX-PS 34 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : PDDL 2.1 PDDL 2.1 was developed for the AIPS-2002 Planning Competition [Fox&Long 2002] Extension of PDDL [McDermott&al 1998] for domains involving time and other numeric-valued resources PDDL 2.1 35 Level 1: “Classical” propositional planning Level 2: Numeric Variables Level 3: Durative actions, No continuous effects Level 4: Durative actions, continuous effects PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : PDDL 2.1 Numeric variables (:functions (free-engineers) ) (:action Hire :parameters ( ?n ) :precondition ( … ) :effect (and (increase (free-engineers) ?n) … )) 36 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : PDDL 2.1 Numeric variables Conditions: (= (f ?x) ?q) (< (f ?x) ?q) (> (f ?x) ?q) (<= (f ?x) ?q) (>= (f ?x) ?q) Effects: (increase (decrease (scale-up (scale-down (assign 37 (f (f (f (f (f ?x) ?x) ?x) ?x) ?x) ?q) ?q) ?q) ?q) ?q) ; f(?x) += ?q ; f(?x) -= ?q ; f(?x) *= ?q ; f(?x) /= ?q ; f(?x) = ?q PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : PDDL 2.1 Durative actions Action duration Start Conditions at start End Effects at start Conditions at end Invariant 38 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Effects at end State of the Art Problem Modeling : PDDL 2.1 Durative actions (:functions (free-engineers) ) (:action TestWebSite :parameters ( ) :duration (= ?duration 3) :condition (and (at start (>= (free-engineers) 2))) :effect (and (at start (decrease (free-engineers) 2)) (at end (increase (free-engineers) 2)) (at end (website_tested)))) 39 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : BTPL Basic Temporal Planning Language [Brenner 2001] 40 Extension of PDDL. Focus on time and concurrency. Whereas PDDL2.1 represents an action with two events (start and end), BTPL allows for more complex actions involving several events No relative changes on numerical attributes (increase/decrease) as in PDDL2.1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : BTPL A BTPL ground action is a tuple a=(pre, eff) where pre are preconditions (set of literals) eff = {ue1,..,uen} is a set of unit events of the form ue=(c,e,d) describing the (conditional) effects of A d: delay (rational number) c: condition of ue: set of literals to be satisfied at t+d e: effect of ue: add/delete list occurring at t+d pre A c1 d1 d2 41 ue1 e1 c2 ue2 e2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : BTPL Example: ATM cash dispenser (card_in ?y) DialCode(?x) (code_ok ?x ?y) 5 (cash-out) (ticket) 7 not (cash-out) not(card_in ?y) 10 (cash-out) InsertCard(?y) TakeCash() (card_in ?y) 1 42 1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece not(cash-out) (have_cash) State of the Art Problem Modeling : BTPL BTPL extension Allow expressing action preconditions (pre) and event conditions (c) that hold over time intervals [t1,t2) before the action or event time-point. pre: (p,d1,d2) t-d1 t-d2 t A c: (q,d3,d4) t’-d3 t’-d4 ue e d 43 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece t’=t+d State of the Art Problem Modeling : parcPLAN parcPLAN [Lever&Richards 1994, ElKholy&Richards 1996] Rich temporal expressivity based on time-intervals whose extremities are time-point variables E.g.: position(robot,r1)@(t1,t2) Expression of minimal/maximal delays between time points E.g.: t1+5 t2 44 Handle unary and discrete resources, no reservoir PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : parcPLAN Web-site project example action develop(?website)@(start,end) { conditions: designed(?website)@(t1,t2), implemented(?website)@(t3,t4), tested(?website)@(end,t); effects: developped(?website)@(end,t); constraints: designates(?website, WEBSITE), start <= t1 <= t2 <= t3 <= t4 <= end <= t, end <= start + 18; } 45 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : parcPLAN Web-site project example action test_in_company(?website)@(start,end){ effects: tested(?website)@(end,t); resources: requires(engineers(),2)@(start,end); constraints: designates(?website, WEBSITE), end <= t, end = start + 3; } action test_outsource(?website)@(start,end){ effects: tested(?website)@(end,t); constraints: designates(?website, WEBSITE), end <= t, end = start + 4; } 46 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : IXTET IXTET [Ghallab&Laruelle 1994, Laborie&Ghallab 1995] is a temporal and resource planner 47 From IndeXed TimE Table State of the world is represented by a set of valued attributes (state variables) Relies on time-points as elementary temporal primitives Allow representation of unary, discrete and reservoir resources PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : IXTET State of the world is represented by a set of valued attributes (state variables) E.g.: color(car):red position(robot):r1 Conditions are expressed over time intervals E.g.: hold(position(robot):r1,(t1,t2)) Change is represented via the notion of event associated with a time-point E.g.: event(position(robot):(r1,r2), t) 48 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : IXTET Minimal/Maximal delays can be expressed between time-points E.g.: t in [0, 12] t2-t1 in [3, 5] Unary and discrete resources can be used over timeintervals E.g.: use(engineers():2, (t1,t2)) Reservoir can be produced/consumed at time-points E.g.: consumes(money():100,t) 49 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : IXTET Web-site project example IXTET operators are called task task develop(?website)(t) { ?website in WEBSITES; timepoint t1, t2; hold(status(?website):designed, (t1,t2)); hold(status(?website):implemented, (t2,t)); hold(status(?website):tested, (t,end)); start <= t1 <= t2 <= t <= end; (end - start) in [0,18]; } 50 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : IXTET Web-site project example task test_in_company(?website)(start, end){ ?website in WEBSITES; event(status(?website):(?, tested), end); uses (engineers():2, (start,end)); (end - start) in [3,3]; } task test_outsource(?website)(start, end){ ?website in WEBSITES; event(status(?website):(?, tested), end); consumes (money():100, start); (end - start) in [4,4]; } 51 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : IXTET Web-site project example The problem is modeled in the same way as a task resource money() { capacity = 200; } resource engineers { capacity = 5; } task init()() { timepoint t; explained event(status(website1):(?, init), start); explained event(status(website2):(?, init), start); explained event(status(website3):(?, init), start); develop(website1)(t); develop(website2)(t); develop(website3)(t); start <= t <= end; t - start in [0,16]; } 52 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : IXTET Web-site project example resource money() { capacity = 200; } resource engineers { capacity = 5; } task init()() { timepoint t, u; explained event(status(website1):(?, init), start); explained event(status(website2):(?, init), start); explained event(status(website3):(?, init), start); develop(website1)(t); develop(website2)(t); develop(website3)(t); start <= t <= end; t - start in [0,16]; uses(engineers():1, (u,end)); // One quality engineer only u-start in [7,7]; // available first week } 53 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : O-Plan O-Plan 54 [Currie&Tate 1991, Drabble&Tate 1994] Open PLANning architecture Hierarchical planning system The language (Task Formalism) allows a rich representation of time and resources PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : O-Plan Web-site project example Actions have conditions and effects and can be refined into sub-actions thanks to schemas schema develop_website; vars ?website = ?{type websites}; expands {develop ?website}; nodes 1 action {design ?website}, 2 action {implement ?website}, 3 action {test ?website}; orderings 1 -> 2, 2 -> 3; time_windows duration self = 0 .. 18 months; end_schema; 55 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : O-Plan Web-site project example schema test_website_in_company; vars ?website = ?{type websites}; expands {test ?website}; conditions only_use_if {free_engineers} = true; effects {free_engineers} = false at begin_of self, {free_engineers} = true at end_of self; time_windows duration self = 3 months; end_schema; schema test_website_outsource; vars ?website = ?{type websites}; expands {test ?website}; resources consumes {resource money} = 100 kE; time_windows duration self = 4 months; end_schema; 56 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : O-Plan Web-site project example The problem is modeled in the same way as a goal schema task todo; nodes 1 start, 3 action {develop site1}, 4 action {develop site2}, 5 action {develop site3}, 2 finish; orderings 1 -> 3, 1 -> 4, 1 -> 5, 3 -> 2, 4 -> 2, 5 -> 2; resources consumes {resource money} = 0 .. 200 kE overall; time_windows 0 at begin_of 1, 16 at end_of 2; end_task; 57 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : O-Plan Time Precedence between actions Minimal/maximal action duration Time windows for events Minimal/maximal delays between events Action dmin dmax Schema 58 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : O-Plan O-Plan Resource Typology Unary Resource Consumable 59 Strictly Producible By-Agent By and Outwith Agent Discrete Reusable Non-Sharable Outwith Agent Reservoir Sharable Independently PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Synchronously State of the Art Problem Modeling : O-Plan Resource usage Consumable/Producible resource schema <SCHEMA>; resources consumes {resource <R>}= <q..Q> [at<EVT>]; resources produces {resource <R>}= <q..Q> [at<EVT>]; Reusable resources schema <SCHEMA>; resources allocates {resource <R>}= <q..Q> [at<EVT>]; resources desallocates {resource <R>}= <q..Q> [at<EVT>]; 60 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : ASPEN ASPEN 61 [Chien&al 2000] Automated Scheduling and Planning ENvironment The main ingredient of the model is the notion of (hierarchical) activity types. Numerical time State variables Numerical resources (unary, discrete, reservoir). PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : ASPEN ASPEN Example inspired from [McCarthy&Pollack 2002] State variables: described as a set of possible transitions State_variable Position { states = (“patio”,”dining”,…); transitions = ( “patio”<->”dining”, “dining”<->”kit”, “dining”->”living”, …); default_state = “living”; } 62 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : ASPEN ASPEN 3 reasons for an activity to be inserted in the plan Activity Eat(breakfast) Reservations: State Variable: Position must_be kitchen 63 An activity requires a given state for a state variable PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : ASPEN ASPEN 3 reasons for an activity to be inserted in the plan Activity Eat(breakfast) [0,60] Constraints: ends_before start of Take(medicine) by [0,60] Activity: Take(medicine) 64 An activity express temporal constraint with another activity of a given type PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : ASPEN ASPEN 3 reasons for an activity to be inserted in the plan Activity DailyExercise() Decompositions: Exercise1() 65 Exercise2() Exercise3() An activity can be decomposed into sub-activities PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : ASPEN Web-site project example State_variable status { states = { “init”, “designed”, “implemented”, “tested” }; transitions = { “init” -> “designed”, “designed” -> “implemented”, “implemented” -> “tested” }; default_state = “init”; } Activity develop { Website w; duration = [0,18]; decomposition = { design with (w -> w) a1, implement with (w -> w) a2, test with (w -> w) a3, where a1 ends_before start of a2, a2 ends_before start of a3 }; } 66 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : ASPEN Web-site project example Activity test { Website w; decomposition = { test_in_company with (w -> w) or test_outsource with (w -> w) }; reservations = { status(w) must_be “implemented”, status(w) change_to “tested” at end; } } Activity test_in_company { Website w; duration = 3; reservations = { engineers use 2; } } 67 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : ASPEN Web-site project example Activity test { Website w; decomposition = { test_in_company with (w -> w) or test_outsource with (w -> w) }; constraints = { starts_after end of implement with (w -> w) } } Activity test_in_company { Website w; duration = 3; reservations = { engineers use 2; } } 68 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : RAX-PS RAX-PS 69 [Jonsson&al 2000] Interval based planner No distinction between propositions holding over intervals and actions taking place over intervals Valued state-variables (same as IXTET or ASPEN) Main ingredient is the notion of token: a given value for a state variable holding over some time-interval PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : RAX-PS RAX-PS Notion of time-line for a state variable v Engine Attitude Idle Turn(A,B) Thrust(B) Point(B) Idle Turn(B,C) time Token tuple < v, P(xP), s, < Attitude, Turn(A,B), 10, 70 e > 20 > PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : RAX-PS Each token T is associated a configuration constraint GT called compatibility. This constraint determines which other tokens must be present in a valid plan if the plan contains T and how these tokens are constrained with respect to T. Usually, GT is a disjunction of basic configurations 71 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Modeling : RAX-PS Example (Define_Compatibility (ProjectStatus(?w) tested) :compatibility_spec (OR (met-by (ProjectStatus(?w) test_incompany)) (met-by (ProjectStatus(?w) test_outsource))) (Define_Compatibility (ProjectStatus(?w) test_incompany) :constraints (?duration <- 3) :compatibility_spec (AND (equals (Engineers (+2 Used))))) (Define_Compatibility (ProjectStatus(?w) test_outsource) :constraints (?duration <- 4)) 72 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving Planning Languages Planners Planning Techniques: - Planning Graph - SAT Planners and other encodings - Heuristic Planning - Local Search & Repair - Partial Order Causal Link (POCL) - Hierarchical Task Networks (HTN) Basic Tools: - Linear Programming (LP) - Mixed Integer Linear Programming (ILP or MIP) - Satisfiability (SAT) - Constraint Satisfaction Problems (CSP) 73 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Linear Programming (LP) Input: a set of variables, a system of linear inequations and a linear objective to minimize ai, j , b j , ci , xi R maximize c i xi i subject to a i, j xi b j i, j 74 Output: a value for each variable that maximizes the objective function PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Linear Programming (LP) Example maximize ( x y 50 ) subject to 50 x 24 y 2400 , 30 x 33 y 2100 , x 45 , y 5 75 Optimal solution: x=45, y=6.25 (objective = 1.25) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Linear Programming (LP) 76 Efficient algorithms available using the Simplex method Except for some pathological cases, the method exhibits a polynomial complexity Practical problems involving several hundred thousands of variables can be solved Many software and libraries available (freeware or commercial e.g. ILOG CPLEX) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Mixed Integer Linear Programming (ILP/MIP) Input: same as LP but some variable are constrained to be integer ai, j , b j , ci , x k R , maximize c i xl Z xi i subject to a i, j xi b j i, j 77 Output: a value for each variable that maximizes the objective function PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Mixed Integer Linear Programming (ILP/MIP) Example maximize ( x y 50 ) subject to 50 x 24 y 2400 , 30 x 33 y 2100 , x 45 , y 5 , y is integer 78 Optimal solution: x=45.12, y=6 (objective = 1.12) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Mixed Integer Linear Programming (ILP/MIP) 79 Problem is NP-hard ... But fairly efficient approaches exist based the cooperation of LP and a tree search. Basic idea: relax the problem as a LP, solve it, if some integer variable xl has non integer value vl, branch on xl=[vl] xl=[vl]+1 Survey paper: [Bixby&al 2000] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Satisfiability (SAT) Boolean variables Literal Clause Theory P,Q,R,… P,Q,… (PQ),… C1C2,… true,false (un)negated variable disjunction of literals conjunction of clauses Satisfiability problem: is a given theory valid ? That is, does it exist an assignment of all the boolean variables in {true, false} such that the theory is true. 80 MAX-SAT: what is the maximum number of clauses that can be satisfied. PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Satisfiability (SAT) Example: (P Q) (Q R) (R P) A solution: P=Q=true, R=false (P Q) (Q R) (R P) 81 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Satisfiability (SAT) Satisfiability is NP-complete … but efficient methods exist Complete methods (Davis-Putnam procedure and its improvements) Approximation methods (randomization and local search) 82 Can solve problems with thousands of variables Survey paper: [Gent&Walsh 1999] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Constraint Satisfaction Problems (CSP) Problem. Given: A set of variables X={x1,…,xn} A finite domain Di for each variable xi A set of constraints Ci(xi1,…,xik) on some subset of variables described in extension (subset of the cartesian product Di1 …Dik satisfying the constraint) or in intension (e.g. xi=min(xj,xk) ) Find an assignment of all variables in X that satisfies all the constraints 83 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Constraint Satisfaction Problems (CSP) Example: Variables: c {blue, red} x {1,2,3,4}, y {1,2,3,4} Constraints: (xy) (x.y 10) (c=blue) (x>y) 84 A solution: (x=1),(y=2),(c=red) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Basic Tools Constraint Satisfaction Problems (CSP) 85 Problem is NP-complete (SAT can easily be reduced to a CSP on boolean variables) Efficient resolution techniques using constraint propagation and tree search Survey papers: [Kumar 1992, Smith 1995] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving Planning Graph SAT Planners Heuristic Planning GraphPlan IPP STAN R-IPP SAT-PLAN [Rintanen&Jungholt 1999] LPSAT [Kautz&Walser 1999] HSP GRT FF GRT-R Metric-FF Sapa TP4 LPG Excalibur ASPEN Local Search & Repair POCL HTN 86 SNLP UCPOP parcPLAN IxTeT RAX UMCP SHOP Sipe-2 O-PLAN PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Graph Planning Graph [Blum&Furst 1997] Planning Graph expansion 0 i-1 i propositions i+1 propositions actions 87 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Graph Planning Graph Mutex relations Inconsistent Effects 88 Interference Competing Needs PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Inconsistent Support State of the Art Problem Solving: Planning Graph Planning Graph 89 Solution extraction PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Graph Planning Graph Solution extraction Ad-hoc algorithm (GraphPlan) SAT encoding CSP encoding 90 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Graph Planning Graph Some Planning Graph Planners GraphPlan [Blum&Furst 1997] IPP [Koehler&al 1997] STAN [Long&Fox 1999] SAT encoding SatPlan 91 [Kautz&Selman 1999] CSP encoding CPLAN [vanBeek&Chen 1999] GP-CSP [Do&Kambhampati 2000] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: R-IPP R-IPP IPP extension to resource constrained plans 92 [Koehler 1998] GraphPlan based algorithm The planning graph is annotated with possible interval boundaries for resource level PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: R-IPP Resource r with possible level in [Qmin(r),Qmax(r)] 0 i-1 i L(i-1,r)[Lmin(i-1,r), Lmax(i-1,r)] 93 i+1 L(i+1,r) ? PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: R-IPP Resource r with possible level in [Qmin(r),Qmax(r)] L max ( i 1, r ) max( L max ( i 1, r ), No action affecting r is applied i-1 94 i i+1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: R-IPP Resource r with possible level in [Qmin(r),Qmax(r)] L max ( i 1, r ) max( L max ( i 1, r ), { l ( a ) / a action at level i setting amount of r to be l ( a ) } L(r):=l(a) i-1 i i+1 An action a can set the amount of resource to l(a) 95 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: R-IPP Resource r with possible level in [Qmin(r),Qmax(r)] L max ( i 1, r ) max( L max ( i 1, r ), { l ( a ) / a action at level i setting amount of r to be l ( a ) } { L max ( i 1, r ) p ( a ) / S non exclusive set of producers of level i } ) a S i-1 i i+1 A non-exclusive set of action produces r L(r)+=p(a) 96 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: R-IPP Similar calculations for Lmin(i+1,r) The classical notion of mutex is extended. Two actions are mutex also if: 97 They are of different type w.r.t. a resource (consumer, provider, producer) They are provider of the same resource Their combined effect is impossible They have contradictory resource requirements PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: R-IPP Resource boundaries are used to 98 Restrict the number of applicable actions in a given level Allow detection of additional mutexes Prune the search when solving the planning graph PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving Planning with Resources based on SAT and/or LP/MIP encodings 99 [Rintanen&Jungholt 1999] LPSAT [Wolfmann&Weld 1999] [Kautz&Walser 1999] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving [Rintanen&Jungholt 1999] propose an approach similar to R-IPP based on a SAT-encoding 10 0 Producers and Consumers can be executed in parallel The search is not restricted to backward-chaining as in the GraphPlan framework. PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving LPSAT Based on a SAT-encoding of the planning graph [Ernst&al 1997] i-1 i i+1 Explanatory Frame Axioms: At(P1,B,i-1) At(P1,B,i+1) SlowFlight(A,B,i) FastFlight(A,B,i) Actions effects and conditions: SlowFlight(A,B,i) 10 1 At(Plane,A,i-1) At(Plane,B,i+1) At(P1,A,i-1) At(P1,B,i+1) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving LPSAT SAT extended by LCNF representation and solver: propositional variables may trigger some linear constraints [Wolfmann&Weld 1999] (P Q) (Q R) (R P) P (50x+24y2400) Q (30x+33y2100) R (x45) 10 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving LPSAT LCNF allows expression of resource requirements i-1 i i+1 Resource requirements: SlowFlight(A,B,i) Refuel(i) 10 3 (Level(i-1) - Level(i+1)= 15) (Level(i+1)= 240) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving [Kautz&Walser 1999] propose an ILP encoding 10 4 Actions a that consumes/produce a resource One action that reset the resource to its maximal capacity (refuel) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving [Kautz&Walser 1999] propose an ILP encoding ri 1 ri k i q a ai a Cons q a ai ri 1 ri k i a ai a Cons a Prod q a ai a Prod s i a i a Prod Cons s i a i 1 a Prod Cons s i ( ri 1 Q MAX ) ri 1 s i Q MAX 0 si ( k i 0 ) s i M k i 0 , M such that k i M Q MIN ri q a ai Q MIN ri Q MAX ri q a Prod q a ai a Cons a Cons 10 5 q a ai Q MAX ri q a Prod PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece a ai State of the Art Problem Solving: Heuristic Planning Heuristic Planning Forward or backward state planning Use of an efficient heuristic h(s) Heuristic cost: h(s’) s’ Initial state Cost of current plan: g(s) 10 6 Goal s Candidate actions PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Heuristic Planning Heuristic Planning In HSP, the heuristics h(s) is computed by solving a relaxed problem where all the delete lists of actions are ignored. s: state, p: proposition, cs(p) estimation of the cost for achieving p from state s cs ( p ) { if ps min op O ( p ) 1 c s ( Prec ( op )) otherwise 0 HSP heuristics (non-admissible): h ( s ) c p Goal 10 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece s ( p) State of the Art Problem Solving: Heuristic Planning Some heuristics planners 10 8 HSP [Bonet&Geffner 1999,2001] GRT [Refanidis&Vlahavas 1999] FF [Hoffman&Nebel 2001] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Heuristic Planning Heuristic Planning with Resources 10 9 GRT-R [Refanidis&Vlahavas 2000] Metric-FF [Hoffman 2002] Sapa [Do&Kambhampati 2001] TP4 [Haslum&Geffner 2001] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: GRT-R GRT-R: Heuristic planner handling consumable resources in the heuristics Heuristic cost: h(s’) <N=2, R1=5, R2=1>, <N=3, R1=2, R2=3> Q1=10, Q2=10 s’ Initial state s <N=1, R1=6, R2=2> Cost of current plan: <N=2,R1=5,R2=4> 11 0 Candidate actions PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Goal State of the Art Problem Solving: GRT-R The heuristic with resource allows guiding and pruning the search The heuristics h(s) is computed by regression from the goal state toward state s Issues: complexity in time and memory for computing the sets of cost vectors 111 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Metric-FF Metric-FF. Extension to FF [Hoffmann&Nebel 2001] Reminder: FF is a forward search heuristic planner. At a given state s, the heuristics h(s) is estimated by solving a relaxed problem that ignores the delete lists of operators. This is done in GraphPlan style. Heuristic cost: h(s’) Initial state s Cost of current plan: g(s) 11 2 Solve relaxed problem s’ Candidate actions PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Goal State of the Art Problem Solving: Metric-FF Metric-FF restricted formalism Conditions: q>C, qC Effects: q+=C (production), q-=C(consumption) Metric-FF idea: on a resource, something similar to ignoring the delete list is to ignore consumption and only consider production events (monotonicity). Monotonicity: each proposition true at level i in the planning graph remains true at any level j i 11 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Metric-FF As for FF Finding a solution to the relaxed problem is polynomial (because of the monotonicity) Finding the shortest solution to the relaxed problem is NP-complete. A (good) solution to the relaxed problem is computed using similar techniques as in R-IPP The value of the heuristic is the number of operators in this solution 11 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Metric-FF The notion of monotonicity is very generic Extended Metric-FF formalism Conditions: linear expressions {<.,=,,>} linear expression Effects: {:=, +=, -=} linear expression Transformed into a simpler Linear Normal Form language where a monotonic relaxation is applied 11 5 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Sapa Sapa. Heuristic Metric Temporal Planner Focus on durative actions: action A, duration D(A) Notion of time stamped state cj Predicates true at t ti tj Persistent conditions to be protected pi Scheduled events: - Ends of persistent condition Resource levels at t - Change truth value of a predicate - Change a resource Past t Future 11 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Sapa Notion of applicable action Result of applying an action to a state A cj Predicates true at t ti tj Persistent conditions to be protected pi Scheduled events: - Ends of persistent condition Resource levels at t - Change truth value of a predicate - Change a resource Past t Future 11 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Sapa Heuristic planning Heuristic cost: h(s’) s’ Initial state Goal s Cost of current plan: g(s) Candidate actions The heuristics relies on solving a relaxed problem where delete lists and resources are ignored using GraphPlan like techniques 11 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Sapa In the relaxed problem Delete lists and Resource usage are ignored Partial Plan Relaxed planning graph Approximation of the distance from the goal FastFlight(A,B) Deplane(P1,B) Deplane(P1,A) Board(P2,B) Deplane(P2,C) Board(P1,A) SlowFlight(A,B) Deplane(P1,C) FastFlight(B,C) SlowFlight(B,C) sinit 11 9 s Lower bound on the date P1 can be at C (useful to prune the search) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Sapa In the relaxed problem, resources are used to adjust the heuristics For a resource R, pre-computation of the action AR that can increase maximally the level of R (of a level R) Init(R): initial level of R at state s from which the relaxed plan was computed. Con(R) and Pro(R) are the total consumption and production of R in the solution of the relaxed plan. If Con(R)>Init(R)+Pro(R), we know that at least Con ( R ) ( Init ( R ) Pro ( R )) R additional actions to produce R will be necessary 12 0 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: TP4 Similar approach used in TP4 But the planner is a regression planner, starting from the goal 12 1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Planning with Resources Part II: Focus on Constraint-Based Approaches Overview Planning with Resources Part II. Focus on Constraint-Based Approaches Reminder: POCL and HTN Planning Constraint-Programming Problem Modeling Problem Solving Constraint Propagation Search 12 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Partial-Order Causal-Link Planning (POCL) Search in a space of partially-ordered plans Iteratively selects some flaw of the current partial plan and attempt to fix them until there are no more flaw (solution plan) Flaws: - unachieved preconditions - threads on causal links 12 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Partial-Order Causal-Link Planning (POCL) Unachieved preconditions Insert a new action and a causal-link OR w p p Initial q state q s s q q r v r 12 5 u u Goal v p PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Partial-Order Causal-Link Planning (POCL) Unachieved preconditions Insert a causal-link with an existing action p Initial q state q s s q q r v r 12 6 u p PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece u Goal v State of the Art Problem Solving: Planning Techniques Partial-Order Causal-Link Planning (POCL) Threads on causal-links p p Initial q state q s s u p p r v r u Goal v p Fixes: action promotion OR demotion 12 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Partial-Order Causal-Link Planning (POCL) Threads on causal-links p p Initial q state q s s u p p r v r u Goal v p Fixes: action promotion OR demotion 12 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Partial-Order Causal-Link Planning (POCL) Threads on causal-links p p Initial q state q s s u p p r v r u Goal v p Fixes: action promotion OR demotion 12 9 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Partial-Order Causal-Link Planning (POCL) 13 0 Some POCL planners SNLP [McAllester&Rosenblitt 1991] UCPOP [Penberthy&Weld 1992] IXTET [Ghallab&Laruelle 1994] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Hierarchical Task Networks (HTN) Hierarchical Operators (see O-PLAN) Task T(x1,…xn) Method 1 precondition: p q Method 2 precondition: v q s r 13 1 s r PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Hierarchical Task Networks (HTN) HTN Planners work by iteratively - expanding tasks (choose a method) and - resolving conflicts until a conflict-free plan can be found which consists only of primitive tasks Most of industrial applications of AI Planning use the HTN approach Provides a strong structuration of the domain to efficiently guide the search 13 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece State of the Art Problem Solving: Planning Techniques Hierarchical Task Networks (HTN) Some Partial-Order HTN Planners SIPE-2 [Wilkins 1988] O-Plan [Currie&Tate 1991] UMCP [Erol&al 1995] Often based on constraint propagation [see later] Some Forward-Chaining HTN Planners SHOP 13 3 [Nau&al 1999] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving: Planning Techniques Partial-order approaches to planning (POCL, HTN) are recognized to be the most flexible for handling time and resources [Smith&al 2000] Partial order planning is receiving more and more attention [Nguyen&Kambhampati 2001,Geffner 2001] 13 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving: Planning Techniques In partial order planning, from the point of view of resources, a partial plan is a temporal network of activities that require/produce/consume some resources. It’s essentially the same as in constraint-based scheduling 13 5 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming Constraint-Based Scheduling = Scheduling + Constraint Programming Scheduling problems arise in situations where a set of activities has to be processed by a limited number of resources in a limited amount of time 13 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming Paradigm to solve combinatorial optimization problems One states the problem in terms of variables and constraints after which, a search procedure is used to find a solution 13 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming Each variable has an initial domain of possible values ( x [0,…,4] ) Constraints propagate to reduce domains “x < 3” x [0,…,2] 13 8 Each constraint has its own propagation algorithm (reusable) As propagation isn’t sufficient, a search tree is build PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming decision making new constraints backtracking Dec. vars: x in [1..3] y in [1..3] z inDefinition [1..3] Problem Constraints: x - y = 1 y<z Search y=2 [1..3] Dec. Dec. vars: vars: xx in = 3[2..3] [1..3] yy in = 2[1..2] zz in [1..3] [2..3] Variables, = 3Domains, Constraints: =1 and Constraints Constraints: xx -- y y= 1 y < z y<z y=2 initial variables, constraints, and domains reduce domains, deduce constraints, contradictions 13 9 Constraint x y- y<Propagation =z 1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece problem specification partial solution Constraint-Based Approaches Constraint-Based Scheduling [Baptiste&al 2001] Problem Definition Modeling Objects: Activities, Resources, Temporal Constraints, Resource Demands 14 0 Search Scheduling Strategies Problem Specification / Partial solution Constraint Propagation Resource Demands, Temporal Constraints PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming : Properties Besides the separation of problem definition, constraint propagation, and search, the Locality Principle [Steele 1980] is important: each constraint must propagate as locally as possible, independent of the existence or non-existence of other constraints. [Stallman&Sussman 1977] separation between deductive methods (constraint propagation) and search [Kowalski 1979] distinction between logical representation of constraints and the control of their use: Algorithm = Logic + Control 14 1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming Global Constraints One of the strong points of CP tools are the so called global constraints (Opposed to constraints like x < y.) Example is the “all-different” constraint where you have n variables which all should take a different value: i , j [1,..., n ] / i j , ( x i x j ) 14 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming V11 V12 V10 V2 V9 V3 V8 V4 V7 14 3 O(n2) binary constraints Weak constraint propagation V1 V6 V5 One global constraint (Easier modeling) Strong constraint propagation [Regin 1994] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming : Search Search Heuristics Variable and value selection heuristics. Choose variable to assign a value to and then choose a value for this variable (instantiate the variable). Typical strategy Choose most constrained variable, i.e., a variable that is difficult to instantiate; start with the difficult parts (this before they get even more difficult). Choose least constraining value, i.e., a value that leaves as many values as possible for the remaining uninstantiated variables. 14 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming : Search Variable selection heuristics choose variable with smallest remaining domain choose variable with maximal degree in constraint graph (most constraints defined on it) 14 5 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming : Search Value selection heuristics choose value that participates in highest estimated number of solutions. Number of solutions are estimated by counting the solutions to a tree-like relaxation or the original constraint graph. choose minimal value Recall: In general decisions correspond to additional constraints. 14 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming : Search Search Tree Exploration Depth First Search (DFS). The traditional search strategy of CP. Best First Search (BFS). Choose the node with the best minimum cost. Limited Discrepancy Search (LDS). Divides the search tree into strips, trying to stick close to the heuristic. … and several others like Depth-Bounded Discrepancy Search, Interleaved Depth-First Search. 14 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Constraint Programming : Search Optimization In case an objective function is present, one tries to find the best solution. Such optimization can be done in several ways When a solution with cost c is found, restart search to find a solution with cost c-1. Do dichotomization. Besides upper bounds coming from solutions, when being complete one can also calculate lower bounds. When a solution with cost c is found, stay in this solution node, add a “cut” that says the cost needs to be at most c-1, and continue search. 14 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling Scheduling is the “problem of allocating scarce resources to activities over time” [Baker 1974] Typology of 14 9 Activities Temporal constraints Resources PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Activities Non-preemptive activities Activity A t Start time: s(A) End time: e(A) Processing time: p(A) == e(A)-s(A) 1 Activity 3 numerical Variables 15 0 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Activities Notations on current domain of activity time window Activity A smax(A) smin(A) 15 1 emax(A) t emin(A) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Activities Preemptive activities p1 Start time: s(A) Activity A ... pi t End time: e(A) Processing time: p(A) = pi e(A)-s(A) 15 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Activities Preemptive activities Preemption at fixed dates (break calendar) p1 Activity A ... pi t M T W T F S S M T W T F S S M T W T F S S M T W T F S S M T W T Processing time: p(A) = pi = e(A)-s(A) - breaks(A) 1 Activity 3 numerical Variables 15 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Activities Preemptive activities Preemption by other activities p1 Activity A ... pi Activity B t Activity C 1 Activity 1 Variable Set of dates 15 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling: Temporal constraints Generally expressed as ti - tj [dmin, dmax] where ti, tj : start or end time point of some activities dmin, dmax: minimal and maximal delay Generic enough to model 15 5 release dates: start(A) [r,+) deadlines: end(A) (-,d] precedence: start(B)-end(A) [0,+) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling: Temporal constraints Simple Temporal Problem (STP) [Dechter&al 1991] Distance Graph representation dmax tj ti -dmin 15 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling: Temporal constraints Arc consistency ( Single Source Shortest Paths) ensures a backtrack-free search n=#time-points, p=#temporal constraints Memory: O(p) Time: O(n.p) (with negative cycle detection) Path consistency ( All Pairs Shortest Paths) 15 7 Memory: O(n2) Time: O(n2) Provides all pairs distances (useful for heuristics) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Resource Usage Resource quantities q(U) are decision variables The same activity may use several resources U1: A requires Machine1 A U2: A requires(q2) Workers U3: A consumes(q3) Memory 15 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Resource Usage Resource usage follow the “constraint protocol” In particular, they can be used in meta-constraints [A requires Machine1] [A consumes(q2) Memory] [B requires(q3) Workers] 15 9 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Decision Variables Start, end and processing time of activities: s(A), e(A),p(A) Required quantities of resources: q(U) From the standpoint of constraint-programming, the limited capacity of resources imposes some global constraint on the decision variables of the problem 16 0 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Objective functions Often the objective is to minimize a function f(e(A1),…,e(An)) Makespan: f = max(e(Ai)) Total weighted flow time: f = wi.e(Ai) Maximum tardiness: f = max(Ti); Ti=max(0,e(Ai)-di) Total weighted tardiness: f = wi.Ti Total weighted number of late jobs: f = wi.Ui Earliness/Tardiness costs 16 1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Objective functions Other common objective functions 16 2 Minimum transition costs Minimum peak resource usage Schedule maximum weighted # of activities Schedule on a minimum weighted # of resources PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Modeling : Scheduling Problem Given: A set of resources A set of activities A set of temporal constraints on/between activities A set of resource usage An objective function f Find an instantiation of the decision variables that 16 3 satisfies all the constraints and minimizes f PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving A.I. Planning and Scheduling techniques start to converge into a “POPS” (Partial Order Planning and Scheduling) concept 16 4 Partial Order Planning is “Reviving” “Partial Order Scheduling” is most of what ConstraintBased Scheduling is about PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving POP and POS work on the same type of structure: a temporal network of operators/activities POP focus on operator/activity generation constraints POS focus on time and resource constraints The fundamental idea is that in both case, a solution plan or a solution schedule can be characterized by a set of local properties These local properties can be enforced by constraint propagation and/or by branching in the search tree 16 5 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving Example of such a local property in POP: The Necessary Truth Criterion [Chapman,87] Clobberer: -free(A) Establisher: +free(A) White knight: +free(A) Pre: free(A) ? 16 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving In what follow, we identify the local properties that are used in Constraint-Based Scheduling to characterize solution schedules and describe 1. the propagation and 2. the branching schemes based on these local properties 16 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving : Global Constraints What’s happening inside ? Key principle is that a resource knows the set of activities that requires it (start, end, processing time) For instance a unary resource takes care of the n ( n 1) 2 disjunctive constraints of the form e ( A ) s ( A ' ), or e( A' ) s( A) 16 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving : Global Constraints What’s happening inside ? 16 9 When adding an activity requiring a resource, the resource automatically takes care of the relations with all other activities requiring the same resource Remark: One can add activities during search Note however that sometimes you need to know that all the activities that will require the resource are known to do any propagation PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving : Global Constraints What’s happening inside ? We have several types of constraints that all make sure the capacity of the resource is not exceeded at any point. These constraints differ in the strength of the propagation they induce: timetables precedence energy disjunctive constraint balance constraint edge-finding 17 0 In general: more propagation = more effort These constraints are global constraints, they “globally” consider the set of activities on a resource PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving : Global Constraints Different algorithms available to propagate resource capacity (timetable, disjunctive, edgefinder, balance, etc.) Several algorithms may be used in cooperation on the same resource A resource knows the set of activities that uses it As soon as something changes on the resource (change of activity start/end/processing time, change of resource demand, new resource usage added), propagation algorithms are triggered 17 1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving : Global Constraints A resource is said to be closed if no additional resource usage will be inserted into the current schedule lower in the search tree When a resource is closed, stronger propagation can be inferred LINIT=0 17 2 +q -q PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Problem Solving : Global Constraints In mixed A.I. Planning & Scheduling, a resource can be considered closed if for example : No operator use this resource; or In hierarchical planning, it corresponds to an already processed abstraction level; or The decision has been taken to close the resource on the current sub-tree : close R insert an operator using R Forbid insertion of any operator using R. Stronger pruning. 17 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Time-tabling [LePape 1994] Interesting activities A are those for which emin(A) > smax(A). s max s min 17 4 e max e min Between smax(A) and emin(A) we know A will be executed. PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows s max s min Q e max e min q Aggregated necessary demand QMAX t 17 5 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows e max s max s min Q s min e min e min Aggregated necessary demand QMAX t 17 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Time-tabling 17 7 C() E() Time Bounds Precedence Level Energy Time Bounds Precedence Not First/Last PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Time-tabling 17 8 Used for large problems Worst case O(n) algorithm Incremental Smart about when to propagate and when not, group propagation, etc. In practice a very fast algorithm PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Disjunctive constraint Considers pairs (A, B) of activities If two activities can not overlap because of the capacity they require, and one, say A, can not be scheduled before the other, then New time bounds are deduced A new precedence constraint is deduced 17 9 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Disjunctive constraint on unary resource [Erschler 1976] A s max e max s max A e min s min B e max s max e min s min e max e max s max B s min e min s max ( A ) e min ( B ) s min e max ( A ) s max ( B ) e min ( A ) s min ( B ) 18 0 e min PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Disjunctive constraint 18 1 C() E() Time Bounds Precedence Level Energy Time Bounds Precedence Not First/Last PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Disjunctive constraint 18 2 Works on unary, discrete, and state resources More propagation than timetable constraint on unary resources Low memory cost Needs fake activities to cope with resources not available at certain times Algorithm : O(n2) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Edge-Finding [Carlier&Pinson [Nuijten 1990] 1994] [Baptiste&LePape 1995] Detecting First Among n Activities on Unary Resource , A , [ e max ( { A }) s min ( ) p ( ) p ( A )] [ A ] 18 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Edge-Finding B p=4 B p=4 C p=5 18 4 7 A A 4 p=2 C p=5 15 7 16 6 16 6 16 4 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece 15 Constraint-Based Approaches Algorithms based on time windows Similar reasoning for detecting Last, Not First, Not Last with respect to a set Edge-Finding can be extended to discrete resources [Nuijten 1994, Baptiste&LePape 1996] 18 5 C() E() Time Bounds Precedence Level Energy Time Bounds Precedence Not First/Last PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows Energetic Reasoning [Erschler&al 1991] Discrete resource: {A,B} Acts, [Q MAX .( s min ( B ) e max ( A )) W ( A ) W ( B ) W C { A ,B } [ s ( A ) e ( B )] 18 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece [ s min( B ), e max( A )) (C ) ] Constraint-Based Approaches Algorithms based on time windows Energetic Reasoning 6 C1 p=1 1 2 C2 6 16 C2 p=3 5 15 A 4 p=4 4 6 18 7 p=3 15 A 12 4 p=4 B B p=4 16 5 16 4 C1 p=1 16 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece p=4 16 Constraint-Based Approaches Algorithms based on time windows Energetic Reasoning 18 8 C() E() Time Bounds Precedence Level Energy Time Bounds Precedence Not First/Last PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on time windows More Propagation based on time windows 18 9 Preemptive resource constraints: mixed edge-finding [LePape&Baptiste 1998] Activity cannot be nth [Nuijten&LePape 1998] Energetic reasoning [Baptiste&al 1999] Multi-machine propagation [Sourd&Nuijten 2000] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Algorithms based on analyzing time bounds of activities propagate few (or even nothing) when the problem is not tight Example: On discrete resources, for the time-table constraint, if for all activity of the schedule: emax - smin 2.pmin, the time-table constraint propagates nothing smax smin 19 0 emin PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece emax t Constraint-Based Approaches Algorithms based on relative positions These propagation algorithms do not directly take into account precedence relations (but only through their effect on time bounds) In PO Planning Time bounds of operators are loose Extensive usage of precedence relations between operators in the partial plan Traditional resource propagation algorithms do not prune the search space enough 19 1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Example: Blocks world. Limited number of hands (2) modeled as a reservoir of capacity 2 and initial level 2 -1 +1 -1 -1 +1 19 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece +1 Constraint-Based Approaches Algorithms based on relative positions Analyze precedence relations on the left side of the propagation rule (C()) Based on a Precedence Graph that collects and maintains precedence relations between activities: Initial statement of the problem Precedence constraints inside a planning operator Search decisions (e.g.: causal link, threat, ordering decision on resources) Discovered by propagation algorithms (disjunctive constraint, edge-finding, energetic reasoning, emaxsmin). 19 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Precedence Graph Events x=(tx,qx) where the availability of a resource changes Arcs : Two kind of arcs: tx<ty and tx ty +2 +2 -2 +2 [-10,-5] -1 Activity { Arc { Event Production Consumption < Transitive closure is incrementally maintained 19 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Partition for an event x in a precedence graph U(x) B(x) BE(x) BS(x) 19 5 x E(x) A(x) AE(x) AS(x) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Energy Precedence Propagation [Laborie 2001] Does not assume the resource to be closed For any solution: X U , B ( X ), s ( X ) min ( s (Y )) ( q (Y ). p (Y )) / Q MAX Y 19 6 Y In a partial schedule, we can decline this property to perform constraint propagation PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Energy Precedence Propagation [Unary,Discrete] Discrete resource: X U, [ B ( X )] [ s min ( X ) min ( s min (Y )) ( q min (Y ). p min (Y )) / Q MAX ] Y Y QMAX=2 B p=4, q=2 B p=4, q=2 9 X C p=4, q=1 E E D 0 19 7 p=2 q=1 X C p=4, q=1 D p=2 q=2 0 p=2 q=1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece p=2 q=2 Constraint-Based Approaches Algorithms based on relative positions Energy Precedence Propagation C() E() Time Bounds Precedence Level Energy Time Bounds Precedence Not First/Last Worst-case complexity: O(n2) 19 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Balance Constraint [Cesta&Stella 1997,Laborie 2001] Assumption: when applied to a reservoir, all producers of the reservoir are known in the current schedule Local property: for a given event x in a solution schedule, we can compute the level of the reservoir just before x at date t(x)-e as: ( x ) L INIT q(y ) y BS ( x ) A schedule is a solution on the reservoir iff x U , 0 ( x ) Q MAX 19 9 In a partial schedule, we can decline this property to perform constraint propagation PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Reservoir Balance Propagation Given an event x, using the graph, we can compute ( x ) an upper bound on the reservoir level at date t(x)-e assuming: All the production events y that may be executed strictly before x are executed strictly before x and produce their maximal quantity q(y); All the consumption events y that need to be executed strictly before x are executed strictly before x and consume their minimal quantity q(y); All the consumption events that may be executed simultaneously or after x are executed simultaneously or after x 20 0 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches U(x) AE(x) BE(x) x BS(x) 20 1 E(x) (x) L INIT p max ( y ) y B ( x ) U ( x ) AS(x) c min ( y ) y BS ( x ) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Reservoir Balance Propagation Similar bounds can be computed: Lower bound on the reservoir level at date t(x)-e Lower/Upper bound on the reservoir level at date t(x)+e For symmetry reason, we focus on Given (x) (x) , the reservoir balance algorithm discovers: Failures New bounds for required quantities of resources q(x) New bounds for time variables t(x) New precedence relations 20 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Reservoir Balance Propagation 20 3 Discovering failures: As soon as: x , ( x ) 0 , no solution exist that satisfy the precedence relations Property: the rule [ x , ( x ) 0 ] [ fail ] is sufficient to ensure the soundness of the search on a reservoir w.r.t. the reservoir underflow. A symmetrical property exists for reservoir overflow based on ( x ) . PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches LINIT=0 U(x) [+1,+2] [-1,-1] [-2,-1] [+1,+1] E(x) [+0,+10] [+1,+3] [-5,-5] [-5,-5] [-5,-4] BS(x) [+1,+1] BE(x) -(x)= 0 + (2+1+10+1) - (1+5+5+4) = -1 < 0 !!! 20 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Reservoir Balance Propagation Safe event: An event x is said to be safe if and only if ( x ) Q MAX , ( x ) Q MAX ( x ) 0, ( x ) 0 20 5 Property: If all the events are safe, then any instantiation of the time variable that satisfies the precedence constraints also satisfies the reservoir constraint. In other words, the current partial order is safe and the reservoir is “solved”. PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Reservoir Balance Propagation Reservoir balance equation: ( x ) L INIT y BS ( x ) y BE ( x ) U ( x ) q max ( y ) 0 y BS ( x ) It means that some events in BE ( x ) U ( x ) will have to be executed strictly before x in order to produce at least: ( x ) L INIT 20 6 p max ( y ) In case the first part of the equation is such that: L INIT q max ( y ) q max ( y ) y BS ( x ) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Reservoir Balance Propagation events z BE ( x ) U ( x ) will have to be executed strictly before x in order to produce at least ( x ) Some Let ( z1 ,..., z i ,..., z n ) BE ( x ) U ( x ) the set of production events in sorted by increasing minimal time k Let k be the smallest index such that: p max ( z i ) ( x ) i 1 20 7 Then: t ( zk ) t ( x ) PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches LINIT=0 U(x) [-2,-1] [+1,+2] [-2,-2] [+2,+2] [+1,+2] [+0,+10] [-5,-5] [+1,+3] [-5,-5] [-5,-4] BS(x) [+1,+2] BE(x) (x)= 0 - (2+10) + (2+5+5+4) = 4 20 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece E(x) Constraint-Based Approaches Algorithms based on relative positions Reservoir Balance Propagation In AI Planning applications, if some producers of the reservoir may still be inserted in the partial plan: transform the balance algorithm into a real truth criterion: Some events z BE ( x ) U ( x ) will have to be executed strictly before x in order to produce at least ( x ) OR Some operator containing a producing event z will have to be inserted such that t(z) < t(x) 20 9 Such a “truth criterion” is described in [Laborie 2003] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Algorithms based on relative positions Reservoir Balance Propagation C() E() Time Bounds Precedence Level Energy Time Bounds Precedence Not First/Last Worst-case complexity: O(n2) O(n3) 21 0 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Level-Based O(n2) O(n3) Reservoir Discrete Timetabling Unary O(n) Balance O(n2) EdgeFinding Disjunctive O(n log n) O(n2) O(n log n) O(n2) Time-Bounds analysis 21 1 Energy-Based EnergePreced. tic Energy Reason. O(n3) Precedence analysis PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece O(n2) Constraint-Based Approaches Search Techniques Branching Schemes Search Heuristics Beyond the Basic Search Scheme 21 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Branching Schemes Example of Branching Schemes : 21 3 Event Pair Ordering Setting Times PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Branching Schemes Property : In a solution for a unary resource, all the pairs of resource usage are ordered. Activity Pair Ordering (Unary Resource) : Select a not-ordered pair of resource usages : (u,v) U Branch on : [e(u) s(v)] [e(v) s(u)] Needs a precedence graph to maintain the sets of notordered pairs of resource usage 21 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Branching Schemes Property : On a capacity resource, a partial schedule where all the events are safe is a solution. Event Pair Ordering (Discrete, Reservoir, etc.) : 21 5 Select a critical pair of events (x,y) on a resource R (event = start or end time-point of an activity using R) Critical Pair of events : not-ordered pair of event : (x,y) such that neither x nor y is safe (in the sense of the balance constraint) Branch on : [t(x) < t(y)] [t(x) t(y)] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Branching Schemes Property: in a solution on a discrete resource, there is no Minimal Critical Sets. Minimal Critical Set Ordering [Laborie&Ghallab 1995, Cesta&Oddi 2002] Select an MCS on a resource : e1 s1 s2 s3 21 6 e2 e3 q1+q2+q3 > Q q1+q2 Q q1+q3 Q q2+q3 Q Branch on the resolvers of this MCS : [t(e1) t(s3)] [t(e3) t(s1)] [t(e3) t(s2)] PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Branching Schemes All previous branching schemes are complete Setting Times (All resources) : Select an activity a in the schedule Branch on : [s(a) = smin(a)] [s(a) > smin(a)] Dominance rule relying on constraint propagation : instead of posting [s(a) > smin(a)], activity a is marked as non-selectable until its start time has been updated by propagation. 21 7 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Search Heuristics Slack-Based Heuristics [Smith&Cheng 1993] Choose a resource where the slack of any subset of potentially conflicting activities on that resource is minimal. Slack of a subset S is maxA S (emax(A)) – minA S (smin(A)) – sumA S p(A) Sequence that resource / Take a sequencing decision on that resource. Choose pair of unsequenced activities with minimal maximal slack. Maximal slack of A and B is max(emax(A) – smin(B), emax(B) – smin(A)) – p(A) – p(B). Choose sequencing that leaves maximal slack. 21 8 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Search Heuristics Texture-based Heuristics [Beck&al 1997] 21 9 Texture measurement: dynamic analysis of a search state to reveal problem structure Heuristic: based on the revealed structure, find “most critical” part of the search state and take a decision to reduce criticality The texture measurement and the heuristic to take decisions are separate. Note: for efficiency reasons one might want to make more than one decision before recomputing texture measurements PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Search Heuristics Example of Texture-based Heuristics: SumHeight Heuristic 22 0 Texture measurement: a probabilistic estimate of the extent to which activities are competing for each resource and time point (“contention”) Find the most critical (highest contention) resource and time point Take a decision to reduce contention PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Search Heuristics The SumHeight Texture Measurement: Individual Demand time smin 22 1 emin smax emax PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Search Heuristics R2 R2 22 2 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece R2 time Constraint-Based Approaches Search Heuristics The SumHeight Decision Find the resource, R*, and time point, t*, with highest contention Find the 2 activities not sequenced with each other with the highest individual demand for R* at t* Post a precedence constraint between them Complexity: R = # resources, n = # activities per resource O(R.n.log(n)) for texture calculation O(n2) for finding decision after texture calculation 22 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Beyond the Basic Search Scheme Shaving [Torres&Lopez 2000] Perform some kind or forward checking that exploit the interactions between resources Use some global propagation algorithms to determine if there exist a schedule that verify a property p E.g. Try posting A B on a unary resource ... If no solution schedule verify p then p must be verified in any solution. Thus it can be inferred. … if global propagation algorithms fail, then infer the opposite constraint B A 22 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Beyond the Basic Search Scheme Shaving. Example of application: Time-Bound Shaving Activity A, Select such that emin(A) emax(A) If propagating e(A) < leads to a dead-end: infer e(A) If propagating e(A) > leads to a dead-end: infer e(A) Perform a dichotomic search on [emin(A), emax(A)] to compute the best adjustments Other shavings: Precedence, Ranked First/Last activities 22 5 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Beyond the Basic Search Scheme Shaving. Example (Tested on ILOG Scheduler): Famous Job-Shop problem mt10 (1010) Strong constraint propagation (disjunctive, edge-finder, precedence energy) Strong Shaving (time-bounds, precedence, rank first/last). Shave until a fix point is reached. Optimality proof requires: 2 choice points !!!! About 2mn CPU time 22 6 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Beyond the Basic Search Scheme Probing Main idea: At each node of the search, solve a relaxed version of the current schedule and use this solution to guide the search Relaxed problem: for example only keep temporal constraints [ElSakkout&Wallace 2000] or cost relevant activities [Beck&Refalo 2001] If the solution to the relaxed problem cannot be extended to a solution, identify the discrepancies and branch on the different alternatives to solve these discrepancies. 22 7 If the relaxed problem can be solved to optimality, it provides a lower bound on the objective function PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Beyond the Basic Search Scheme Probing 22 8 [ElSakkout&Wallace 2000, Beck&Refalo 2001] Example: Job-shop with Earliness/Tardiness Costs of last activity PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Beyond the Basic Search Scheme Probing During the search, maintain at each node the optimal solution of a linear relaxation of the problem (no resource constraints) Minimize yi subject to: i Cost: Time windows: Precedence: 22 9 y i tc i x i ,m pt i ,m dd i y i ec i dd i x i ,m pt i . m s min a i , j x i , j s max a i , j x i , j pt i , j x i , j 1 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Constraint-Based Approaches Beyond the Basic Search Scheme Using the relaxed optimal start time (from LP), build textures Identify a peak (where the texture > capacity) Select a pair of activities, A and B, at the peak Branch: (A B) (B A) New precedence constraints (as well as precedence discovered by constraint propagation) are used to update the LP relaxation 23 0 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Conclusion Constraint-Based Scheduling Properties that contributed to the industrial success of Constraint-Based Scheduling 23 1 The paradigm clearly separates the constraints (semantics, propagation algorithms) from the search space exploration (branching schemes, heuristics) Constraint propagation allows dramatically pruning the search before everything gets instantiated Each constraint is an autonomous algorithm, the paradigm is extensible: new application-dependent constraints can easily be implemented PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Conclusion Constraint-Based Scheduling Properties that contributed to the industrial success of Constraint-Based Scheduling 23 2 Constraint propagation algorithms often rely on some bounds that can be seen as the optimal solution to a relaxed (sub)problem In optimization problems, the search tree is pruned by computing some lower bound on the objective function, usually it corresponds to the optimal objective function of a relaxed problem Powerful heuristics also often rely on analyzing a good solution to a relaxed problem PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Conclusion Constraint-Based Scheduling Relaxed (sub)problems Optimal solution Good solution bounds bounds Propagation heuristics Search Real problem 23 3 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece Conclusion Constraint-Based AI Planning Relaxed (sub)problems Optimal solution Good solution bounds bounds Part I heuristics Part II Propagation Search Real problem 23 4 PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece

Descargar
# Planning with Resources