The Use of Multiple Problem Decompositions in Time Constrained Planning Tasks

TIIF USF OF MULTIPLE PIWBLEM I>FCOMI'OSITIONS I~ TIMEt:ONSTRAINEU I'LANNING TASKS·

Stephen F. Smith The Robotics Institute Carncgic·Mellon Univcrsity Pittsburgh. PA 15213 USA

ABSTRACT

Problems requiring thc synthcsis of a collection of plans accomplishing distinct (but possibly related) goals has received incrcasing attention within Al. Such problcms arc typically formulated as multi·agcnt planning problems, cmphasizing a problern decomposition \\'herein individual agents assumc responsibility for the gencration of individual plans whilc taking ir.to account the goals and beliefs of other agents in the system. One conscqucnce of such a problern decomposition is a simplified view of resource allocation that assumcs avoidance of conflicts to be the sole concern. The validity of this assumplion comes into qucstion in time constrained problern domains rcquiring the allocation of multiple, shared resources. In job shop schcduling, for example, where sequences of manufacturing Operations must be detcrmined and scheduled for multiple orders, it is necessary to consider much more than availability to efficiently allocate resources over time. We argue that in such domains, an ability to reason from both resource·based and agent·based perspcctives is essential to appropriate consideration of all domain constraints.

I MULTI-AGENT PLANNING AND RESOURCE ALLOCA TION

Problems requiring the synthesis of a collection of plans accomplishing distinct (but possibly related) goals has received increasing attcmion within AI. Systems that address this problern have been called multi·agcnt planning systems [5], so termed because of the emphasis on a systcm of loosely·couplcd, cooperative planning agents, each responsible for the gencration of a single plan but cognizant of, and taking into accounl the·goals and bcliefs of other agents in the system. Work in this art:a··has focused primarily on the issue of goal protcnion. i.c. the planning of activities to achievc desircd goals despitc thc dynamic nature of the surrounding cnvironment. Thc issuc of allocating resources to such activities h<.ts typically bccn given sccundary importancc. thc assumption bcing that thc avoidancc of rcsource conflicts is the solc concern. The validity of this assumption comcs into qucstion in time constraincd domains rcquiring thc allocation of multiple, sha~cd resources. in job shop scheduling. for examplc. whcrc scquenccs of Operations must bc detcrmined and scheduled. for multiple orders. rcsource (e.g. machinc) assignmcnts to support thcsc Operationsare influenccd by much more than thc mcre availability of the resource during thc time pcriod in question. Other cnnstraints, such as capacity limitations, scquencing prefercnccs. and order spl itting prefercnccs. must also bc considcrcd. Efficient atlocation of rcsourccs under such constraints is difficult within the pmblcm decomposition ascribcd to multi·agent planning systcms at>ovc. givcn thc local and incomplctc view of rcsources hcld by each individual agent. Our cxpericnce with thc ISIS job shop scheduling system (4], which adopts Pcng Si Ow Gr<.td. School of lnd. Admin. Carncgic·Mellon Univcrsity Pittsburgh, PA 15213 USA

. This research was supponcd in pan by the Air Force Office of Scientific ReSearch under contract F49620·82·K·C.vl7, Wcstinghouse Elcctric Corpomtion. and the Robotics Institute.

such a problern decomposition. confinns this claim. What is needcd to directly exploit t.hese types of constraints is an ability to rcason from a resourcc bascd pcrspcctivc. suggesting thc use of multiple problern decompositions. This paper describes an initial approach to providing such a reasoning capability.

1l1e rcmainder of thc papcr is organizcd as follows. In Section II we briefly review thc approach takcn by ISIS in rcasoning with the large and conflicting set of constraints encountered in the job shop scheduling domain. This is followed in Scction III by a closer examination of the limitations of decomposing the problern solcly from a order (or agent) based pcrspcctive, and issues surrounding the integration of a rcsource based reasoning capability are explored. An initial system architecturc possessing an ability to reason from both perspectives is presented. Finally, in Section IV, some research directions are identified.

II CONSTRAINT·DIRECTED REASONING IN !SI$

The scheduling domain of ISIS is realistically complex, requiring the consideration of such diverse and conflicting factors as due date requirements, cost rcstrictions, production Ievels, machine capabilities, alternative production processes, order characteristics, resource charactcristics and resource availability. To addrcss this complexity, the ISIS design advocates two key ideas:

• an explicit formalization of the various scheduling influences as constraints in the system's knowledge base, and
• the formulation of schcdule construction as a constraint·directedheuristic search.

The first point above presumes a fairly broad view of constraints, and it is important to note that the ISIS Cllllstraint rcprcscntation encompasses scheduling objectivcs. goals, and prcferenccs as weil as thc rangc of necessary wnditions that dclineatc thc spacc of admissible schedules. Constraints of thc formcr variety providc a basis for optimization du ring thc cvaluation of alternative solutions. by assigning utilities indicati vc of thc degrce to which thcy have been satistied. Thc rcpresentation also captures nthcr knowlcdge nccessary to effcctively reason with the constraints, induding constraint importancc. constraint relevancc. and constraint intcrdcpendencics.

The gcner:nion of a shop schedule is a<::complished in an incremcnt:ll fashion. For cach ordcr to bc schcdulcd. thc system procecds through rnulli1; lc lcvels of an~lysi~;. principal of which is the heuristic scarch proccdure cmploycd to make detailed sclcctions of opcrations, rcsources, and time intervals for production of the order. Working from a set of allowable routings for the ordcr (i.c. a dirccted graph of operations capturing opcration prcccdencc constraints, alternative manufacturing pr~JCesses and resourcc substitutability), thc scarch procccds citl1cr forward trom thc ordcr\ rcquested start datc or backward from thc rcquestcd ship datc. Thc search space is composcd of sta tcs that rcprcsent alternative partial schcdulcs. and thc application of thc scarch opcrators scrves to generate ncw states that further spccify thc partial schcdulcs undcr dcvclopmcnt ( c.g. add anothcr opcration to a partial schedule for thc ordcr, bind a particular machine to an operation, allocate a particular time intcrval fvr thc order on a particular machinc). Using a bcam search, only thc best 11 scarch statcs are cxtcnded at cach itcration of thc scarch, and, as indicatcd above, the quality of a givcn state is cstimatcd on the basis of how weil it sarisfies thc objcctives, goals. and prefcrences that arc relevant to the scheduling decisions it embodics. The outcome of this search is a partieular routing tor the ordcr along with an assignment of time bounds to the rcsources required to produce it. Oncc refined into the order's final schcdule, thcse commitments scrve ro additionally constrain any subscqucnt schcduling that must bc pcrfonned:·

111 REi\SONING FROM MULTIPLE PERSPECTIVES

Thc ISIS hcuristic search paradigm outlined abovc attempts to pi"lWide a fra.mcwork for incorporating thc full rangc of constraints that typically influcncc human scheduler's decisions in the automatic construction ofjob shop sehedules. Unfortunatcly, its commitment to a particular decomposition of the schcduling problern places undue emphasis on the exploitation of a ccrtain class of constraints to the cffectivc exclusion of others. The "focus on onc order at a time" approach cmploycd. while uscful in rcducing thc ovcrall eomplexity of the problem, docs not provide an adequate basis for attending to inte''tm!rr constraints. i.e. Ci.·nstraints that influence thc allocation of rcsourccs ,,ver a number of nrders. Onc exampic of how this weakncss manilc~ts itsclf is in thc considcration of ordcr SCtiucncing prcfercnc~s. which <trisc duc to machine sctup costs ···. These ;:>rcfcrcnccs relatc to thc Intal sct of orders rcquiri ng a givcn resource in thc shop. Yct , within thc ISIS framcwork. t.hcy can bc considcred only in the context of the partiall y constructcd shop <;chcdule that cxists at thc time each ordcr is sclcctcd for schcduling. i\s such, tl1e extcnt of tl1cir influence is somcwhat coincidcntal.

Wc ncxt adJrcss the problcm of how to cope with these inter-order constraints whilc prescrving the ability to adcquatcly cxploit intra-ordcr constraints. Spccitically, wc cxplorc the usc of a resource-based dccomptlSition in conjunction with an ordcr-bascd dccomposition to provid(~ this addcd ability.

Ä. l'artitioning thc Problem Solving Effort

The primary source of difticulty in constructing good job shop schcdules stems from thc conflicting nature ofthe domain's constraints. Constraints are said to bc in conflict whcn a scheduling dccision made with respect to satisfying any one affects the extent to which the others may be satisticd. The optimal resolution of a givcn confliet nccessarily requircs a problern decomposition in which all constraints involved in the wnflkt are grouped within the samc subproblcm. The ordcr-based dccomposition utilized by ISIS groups tagether thc constraints surrounding a panicular order and, conscqucntly, providcs an opportunity for cffcctivrly rcso1vmg order-centercd conflicts (e.g. conflicts involving preeedence constraints). A resource-based problern dccomposition, in contrast, produces a grouping of constraints that promotes thc resolution of a different sct of conflicts. Here thc strategy becomes one of scheduling on a resource by resouree basis, and the grouping ofconstraints containcd within a given subproblern includes a cross-section of the eonstraints associatcd with a number of orders. Conflicts orought to the foreground under this decomposition center araund thc resource allocation decisions that must bc made at a particular rcsourcc (c.g. conflicts involving varinus setup prcfcrcnces). It is obvious that thcre arc many conflicts that cann.ot be effcctively isolated within cithcr decomposition strategy, and, consequently, conflicts that cannot be optimally reso!l·ed from eilher problern solving perspcctivc. Nonethelcss, it is feit that a broadening of the range of constraints that can bc mcaningfully addrcssed through the use of multiple pcrspectivcs willlead to a more cquitable consideration ofthe domain's constraints.

.. The abovc dcscription is nec"""rily briefand omits sevcral impomnt issues that are not dircctly relevant to 01c discussion bciow. Thc reader is referrcd to [2, 3, 4, 7] (or more dciailcd accounts of this work. ... lt is somctimcs nece~<;ary 10 prepare or "'sct up·· a machinc before an operation C2D

be pcrfom1cd on it. lnis is Iypically c;,uscd by a change in the type of Operation to be pcrfonncd on thc rnachine and thc amount of ma<:hinc time consumcd for sctups is dcpcndcnt on thc type of cliange. A proper scquencing of orders on a machine can greaOy increase irs throughput

Givcn the dccision to employ multiple problern decompositions. the task bccomes onc of how tu best partition thc problcm solving cffort bctwccn distinct perspectives so as to maximizc the numbe1 of contlicts that can bc directly addrcssed. Since the formation of specitic Subproblems (c.g. schcdulc opcrations on the milling machine from a rcsourcc-based perspective. and schedule the othcr operations on an order by order basis) will determine which conflicts can be directly resolved, a partitioning that associates essential resource-bascd conflicts with the resourcc-based reasoning componcnt and. likewise. essential order-based conflicts with tl1c order-based rcasoning componcnt, is highly desirable. Fortunately, thc majority of rcsourcc-based conflicts can bc idcntified through tl1c dctection of bollleneck rcsourccs, so called because thcy arc scarce resources of thc shop. Accordingly, a division of cffort in which thc resourcc-based reasoning component is employed to make resource allocation dccisions at thc bouleneck resources and non-bouleneck resources are scheduled from an order­ bascd perspectivc is seen as most appropriate.

Dcspitc an ability to dcrive a fairly uscful problern dccomposition, interactions amongst Subproblems remain an important concern. Resourec allocation decisions made with respect to a particular bottlcneck, for example, might quite likcly Iimit the extent to which we can effectivcly rcsolve conflicts (or satisfy eonstraints) in subsequent order-bascd subproblcms. lt is feit that the hannful effects of thcse interactions can bc minimizcd somcwhat I.Jy a judicious ordering the Subproblems idcntified. Specifically, the relative importance of satisfying various constraints is scen as a useful criterion for coordinating the overall effort.

B. A Spccitic System Architecture

To gain a better understanding of thcse issues, a specific system architccture possessing both resource-based and order-based reasoning componcnts has been implcmentcd. Adopting the problern dccomposition strategy discussed in Scction J.A (i.e. that resource­ based reasoning is most eritical with rcspect to bottlencck rcsources), a simple scheme for eoordinating the overall effort has been imposed. Specitically, thc system first employs its resource-based reasoning component to establish resource reservations at the bottleneck resources. These resource allocation decisions, which arc guaranteed to be fcasible, thcn serve as "islands of certainty" [I) for subsequent exploitation by the order-based reasoning cumponcnt in developing the remainder of thc schedule. The rcsourec bascd rcasoning strategy currently employed is bascd on a partieular OR (Operations Research} heuristic developed in (6). The order-based reasoning component is a derivative ofthe strategy employed by ISIS that has bccn gencralized to operate on arbitrary ponions of the set of routings associatcd with a

particular order.

Tcsting of thc systcm is currcntly prncccding. and prcliminary rcsults usiug simulatcd plant Jata ···· appcar promising. Morcovcr, thc rcconfiguration of thc ISIS schcduling systcm to trcat prcviously imposcd rcsourcc rcscrvations as tixcd points or islands from which to cxpand thc scarch has aiso providcd an opflllrtunity to cmplny the user as thc rcsourcc-hascd rcasoning componcnt of thc systcm. In cxpcrimcm:; whcrc wc havc manually schcdulcd bottlcncck rcsources bcforc invoking the ordcr-bascd rcasoning component, thc bcnctits of providing an ability to rcason dircctly about thc critical rcsource allocation dccisions that havc to hc nwdc can bc immcdiatcly sccn, and give considerable credence to the approach we havc adoptcd.

IV DISCUSSION

ln this papcr we havc pointed up thc inadcquacy of the problern dccomposition typically embodied by mulli-agcnt planning systcms for ccnain classcs of problems involving thc synthesis of multiple plans. In panicular. wc arguc that problems rcquiring the cfficient allocation of a collection of sharcd rcsources ovcr time cannot bc effcctivcly addrcsscd by rclying solcly on thc incomplctc and local knowledge posscsscd by ir.dividual agcnts attending to thc construction of individual plans. The spccific focus of our work, thc gcneration of sehedulcs to govern production in a job shop. cxcmplifics this type of problern wherein efficient allocation of resourccs requires direct consideration of inter· order constraints. and, hence, an ability to rcason globally from a resourcc-based perspcctivc. Recognizing this, we havc proposcd a problern solving framework that cmploys both resource-bascd and ordcr-bascd decompositions of the schcduling problcm. Wc have suggestcd that thc division of cffort bctwccn thcsc distinct pcrspcctives can be uscfully guided by an attempt t.'1c rnaximizc the range of constraint conflicts that can be meaningfully resolved, and that the harmful cffects of the interactions amongst thc resulting Subproblems can be minimized by an appropriate prioritization of the domain's conmaints. 1\ initial system architecture was presented to demoostrate thc feasibility of this approach.

The work reported here has only bcgun to address thc !arger issues associated with the use of multiple problern dccompositions in balancing a !arge set of conflicting objectives. We havc made specific assumptions about the relative importance of satisfying various constraints which havc led to a static partitioning of thc problern solving effort (i.e. first schcdule bottlenecks from a resourcc based perspectivc and then schedulc non-bottlcnecks using an order-based dccomposition). While this, in gcneral, might constitute a rcasonable guidelinc for prioritizing the domain's constraints, there arc obviously Situations in which impnrtant constraints will nor be appropri:ttely attended to. Thc improvcmcnt of mauers rcquircs a more dynamic interplay bctwecn the rcasoning stratcgics associatcd with distinct problcm solving perspcctives in which dccisions madc whilc reasoning from a particular perspcctivc can be qucsrioncd and undonc in light of the constraints that bccomc relevant as different perspcctives are cmp](lycd. This is an issue that wc arc currcntly pursuing.

1\ sccond important issue concerns the lcvcl of sophistication of the resourcc-based reasoning strategy. ln adopting an OR heuristic as the snlc basis for decision nwking, wc have limited th~ systcm·s attention to thc constraint knowlcdge that is implicitly capturcd by thc hcuristic. While thc spcciftc hcuristic emplnycd does. in fact. attend to sevcral important intcr-ordcr constraints. it nonethekss opcratcs with a rcstriclivc model of thc schcduling cnvironmcnt. Ultimately, thc rca:;oning strategy must bc capablc of exploitmg any constraint found to be relevant to thc resourcc allocatiun decisions undcr consideration. This implics a stratcgy that rcasons with an cxplicit charactcrization of constraint knowledgc, analogous to thc hcuristic strategy currcntly employed by the systcm when reasoning from an order-based perspeclive. The dcvclopment of such a strategy is also currcntly under in vestigation.

···· The spccific job shop model cmployed is basr.d on the Westinghouse Turbine Components Plant locatcd in Winston-Salem, North Carolina. The readcr is referrcd to [4] for a discussion of the characteristia; and complcxities of tilis specific scheduling environment

1\CKNOWLEOGEMENTS

Thc ideas prescntcd in this paper have benetitcd greatly from many discussions with Mark Fox.