人工智能原理人工智能原理 (46).pdf

Artificial IntelligencePlanning and SchedulingArtificial Intelligence2 8.3.1 Planning and Scheduling 8.3.2 Solving Scheduling ProblemsContentsArtificial Intelligence:Planning:Classic and Real-world Planning3 The previous chapter introduced the most basic concepts,representations,and algorithms for planning.上一章我们介绍了规划最基本的概念、表示、以及算法。The planning and scheduling in the real world are more complex,e.g.,现实世界中的规划和调度更为复杂，例如 spacecraft,factories,and military campaigns.航天器、工厂、以及军事行动。They should extend both 它们需要扩展 the representation language,and 表示语言，以及 the way the planner interacts with the environment.规划者与外部环境交互的方式。Planning and Scheduling 规划与调度8.3.Planning and SchedulingArtificial Intelligence:Planning:Classic and Real-world Planning4 Classical planning can represent:经典规划可以表示：what to do,做什么 in what order.按什么顺序 Classical planning cannot represent:经典规划无法表示：how long an action takes,动作持续多长时间 when it occurs.什么时候发生Classical Planning and Its Limitation 经典规划及其局限性8.3.Planning and SchedulingArtificial Intelligence:Planning:Classic and Real-world Planning5 Divide problem into planning phase and scheduling phase.将问题分为规划阶段和调度阶段 Planning phase 规划阶段 select actions with some ordering constraints,选择具有某种有序约束的动作，to meet the goals of the problem.去满足问题的目标。Scheduling phase 调度阶段 add temporal information to the plan,在规划中增加时间信息，to meet resource and deadline constraints.去满足资源和期限的约束。Plan First and Schedule Later 先规划后调度8.3.Planning and SchedulingArtificial Intelligence:Planning:Classic and Real-world Planning6 A scheduling problem,consists of a set of jobs,each of which consists a collection of actions with ordering constraints.调度问题包含一系列作业，每个作业包含一组具有顺序约束的动作。Each action has a duration and a set of resource constraints.每个动作有一段持续时间和一组资源约束。Each resource constraint specifies:type,number,consumable or reusable.每个资源约束指定：类型、数量、可消费或可重用。Actions can produce resources,including manufacturing,growing,and resupply.动作可以产生资源，包括制造、增产、以及供给动作。A solution must specify the start times for each action,and must satisfy all the temporal ordering constraints and resource constraints.解决方案需要对每个动作指定起始时间，并且要满足所有的时间顺序约束和资源约束。Representing Temporal and Resource Constraints 表征时间和资源约束8.3.Planning and SchedulingArtificial Intelligence:Planning:Classic and Real-world Planning7Example:A job-shop scheduling 车间作业调度8.3.Planning and SchedulingA B-action A must precede B动作A必须领先于BJobs(AddEngine1 AddWheels1 Inspect1,AddEngine2 AddWheels2 Inspect2)Resources(EngineHoists(1),WheelStations(1),Inspectors(2),LugNuts(500)Action(AddEngine1,DURATION:30,USE:EngineHoists(1)Action(AddEngine2,DURATION:60,USE:EngineHoists(1)Action(AddWheels1,DURATION:30,CONSUME:LugNuts(20),USE:WheelStations(1)Action(AddWheels2,DURATION:15,CONSUME:LugNuts(20),USE:WheelStations(1)Action(Inspecti,DURATION:10,USE:Inspectors(1)A job-shop scheduling for assembling two cars组装两辆汽车的车间作业调度Artificial Intelligence:Planning:Classic and Real-world Planning8 To minimize plan duration,must find the earliest start times for all the actions consistent with the ordering constraints.要使规划持续时间最短，必须找到与排序约束一致的所有动作的最早开始时间。To view these ordering constraints as a directed graph.将这些排序约束视为一个有向图。Solving Scheduling Problems 求解调度问题8.3.Planning and SchedulingA directed graph of temporal constraints for job-shop scheduling problem一个车间调度问题的时间约束有向图Artificial Intelligence:Planning:Classic and Real-world Planning9 Can apply the critical path method(CPM)to this graph to determine the possible start and end times of each action.可以将关键路径法(CPM)用于该图，来确定每个动作可能的开始与结束时间。A path through a graph representing a partial-order plan is a linearly ordered sequence of actions.一个表示偏序计划的图的路径是一个线性排序的动作序列。Solving Scheduling Problems 求解调度问题8.3.Planning and SchedulingA timeline of temporal constraints for job-shop scheduling problem一个车间作业调度问题的时间约束的时间表Artificial Intelligence:Planning:Classic and Real-world Planning10 If we introduce resource constraints,the resulting constraints on start and end times become more complicated.如果我们引入资源约束，所导致的开始和结束时间的约束变得更加复杂。Solving Scheduling Problems 求解调度问题8.3.Planning and SchedulingA timeline of resource constraints for job-shop scheduling problem一个车间作业调度问题的资源约束的时间表 The left-hand margin lists the three reusable resources,and actions are shown aligned horizontally with the resources they use.左边列出了三个可重用资源，并且，动作与它们所使用的资源水平对齐显示。