CMSC 722, AI Planning Planning and SchedulingSchedulingPlanning and SchedulingScheduling ProblemActionsReusable ResourcesConsumable ResourcesSlide 8ConstraintsCostsSlide 11Types of Scheduling ProblemsSingle-Stage Machine SchedulingMultiple-Stage SchedulingExampleNotationComplexitySolving Machine Scheduling ProblemsIP SolversPlanning as SchedulingLimitationsDiscussionIntegrating Planning and SchedulingTemporal AssertionsResource CapacitySlide 26Possibly Intersecting AssertionsConflict and ConsistencyPlanning ProblemsPIA GraphsSlide 31Finding Every Minimax Critical SetSlide 33Resolving Resource-Conflict FlawsContinuing the Previous Example …More about Over-Constraining ResolversSlide 37Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/1CMSC 722, AI PlanningPlanning and SchedulingDana S. NauUniversity of MarylandFall 2009Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/2SchedulingGiven:actions to performset of resources to usetime constraints»e.g., the ones computed by the algorithms in Chapter 14Objective:allocate times and resources to the actionsWhat is a resource?Something needed to carry out the actionUsually represented as a numeric quantityActions modify it in a relative waySeveral concurrent actions may use the same resourceDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/3Planning and SchedulingScheduling has usually been addressed separately from planningE.g., the temporal planning in Chapter 14 didn’t include schedulingThus, will give an overview of scheduling algorithmsIn some cases, cannot decompose planning and scheduling so cleanlyThus, will discuss how to integrate themDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/4Scheduling ProblemScheduling problemset of resources and their future availabilityactions and their resource requirementsconstraintscost functionScheduleallocations of resources and start times to actions»must meet the constraints and resource requirementsDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/5ActionsAction aresource requirements»which resources, what quantitiesusually, upper and lower bounds on start and end times»Start time s(a)  [smin(a),smax(a)]»End time e(a)  [emin(a),emax(a)]Non-preemptive action: cannot be interruptedDuration d(a) = e(a) – s(a)Preemptive action: can interrupt and resumeDuration d(a) =  i  I di(a) ≤ e(a) – s(a)can have constraints on the intervalsDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/6Reusable ResourcesA reusable resource is “borrowed” by an action, and released afterwarde.g., use a tool, return it when doneTotal capacity Qi for ri may be either discrete or continuousCurrent level zi(t)  [0,Qi] is »zi(t) = how much of ri is currently availableIf action requires quantity q of resource ri, Then decrease zi by q at time s(a)and increase zi by q at time e(a)Example: five cranes at location li:We might represent this as Qi = 5Two of them in use at time t: zi(t) = 5 – 2 = 3Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/7Consumable ResourcesA consumable resource is used up (or in some cases produced) by an actione.g., fuelLike before, we have total capacity Qi and current level zi(t) If action requires quantity q of riDecrease zi by q at time s(a)Don’t increase zi at time e(a)Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/8An action’s resource requirement is a conjunct of assertionsconsume(a,rj,qj) & …or a disjunct if there are alternativesconsume(a,rj,qj) v …zi is called the “resource profile” for riDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/9ConstraintsBounds on start and end points of an actionabsolute times »e.g., a deadline: e(a) ≤ u»release date: s(a) ≥ vrelative times»latency: u ≤ s(b)–e(a) ≤ v»total extent: u ≤ e(a)–s(a) ≤ vConstraints on availability of a resourcee.g., can only communicate with a satellite at certain timesDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/10Costsmay be fixedmay be a function of quantity and duratione.g., a set-up cost to begin some activity,plus a run-time cost that’s proportional to the amount of timee.g., suppose a follows bcost cr(a,b) for aduration dr (a,b), i.e., s(b) ≥ e(a) + dr (a,b)Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/11Objective: minimize some function of the various costs and/or end-timesDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/12Types of Scheduling ProblemsMachine schedulingmachine i: unit capacity (in use or not in use)job j: partially ordered set of actions aj1, …, ajkschedule:»a machine i for each action ajk»a time interval during which i processes ajk»no two actions can use the same machine at onceactions in different jobs are completely independentactions in the same job cannot overlap»e.g., actions to be performed on the same