Reasoning about soft constraints and conditional preferences Complexity results and approxi

Classroom Assignment using Constraint Logic ProgrammingSlim Abdennadher,Matthias Saft and Sebastian WillComputer Science Department,University of MunichOettingenstr.67,80538Munich,Germanyabdennad,saft,wills@informatik.uni-muenchen.deAbstractThe Classroom Assignment problem consists of scheduling a set of courses into afixed number of rooms,given afixed timetable.At the University of Munich,a classroom planhas to be created each semester after collecting timetables of all departments and wishesof teachers.This planning is very complex since a lot of constraints have to be met,e.g.room size and ing constraint-based programming,we developed a prototype,called RoomPlan,that supports automatic creation of classroom plans.With RoomPlan aschedule can be created interactively within some minutes instead of some days.RoomPlanwas presented at the Systems’99Computer exhibition in Munich.1IntroductionUniversity course timetabling problems are combinatorial problems which consist in scheduling a set of courses within a given number of rooms and time periods.In most universities,the university course timetabling problem is solved in two phases.In thefirst phase timetables have to be created,one for each department.Since departments can share rooms,the availability of rooms is not taken into account in thefirst phase.In the second phase,rooms have to be assigned to courses.The assignment of rooms is done centrally for the whole university.The classroom assignment problem is a difficult and time-consuming expert task since a lot of requirements have to be met.For example,courses must be assigned to rooms based on the number of students taking the courses and capacities of rooms.Furthermore,some courses may require special equipments such as beamer or internet access.While for thefirst phase of the university course timetabling several systems have been developed[4,12,7],to our knowledge mainly theoretical work has been done on the topic of the classroom assignment problem[6,5].Recently,Constraint Logic Programming[14,20,11,18](CLP)has become a promising approach for solving scheduling problems.CLP combines the advantages of logic programming and constraint solving techniques.The use of CLP has the advantage that the solving procedure can easily be adapted to changing scheduling characteristics.The classroom assignment prob-lem can be elegantly formalized as a partial constraint satisfaction problem and implemented by means of specialized constraint solving techniques that are available in CLP languages.In this paper,the generation of classroom plans for universities is tackled using the CLP framework.The system is called RoomPlan and is currently tested at the University of Munich.Our prototype brought down the time necessary for creating a classroom plan from a few days by hand to a few minutes on a computer.Usually not all specified requirements can be fulfilled.We distinguish two kinds of con-straints.Hard constraints are conditions that must be satisfied,soft constraints may be violated, but should be satisfied as far as possible.The classical approach to deal with these requirements is based on a variant of branch-and-bound search.This approach starts with a solution and re-quires the next solution to be better.Quality is measured by a suitable cost function.The cost function depends on the set of satisfied soft ually,the computation of the cost function is incorporated into the labeling process.In this paper,we propose another approach computing the cost function during the constraint solving process independent of the labeling procedure.This requires to modify the constraint solving part.In the beginning,constraint solving was“hard-wired”in a built-in constraint solver written in a low-level language,termed the“black-box”approach.Since this approach makes it hard to modify a solver or build a solver over a new domain,our aim was to implement a solver for our problem using the“glass-box”approach Constraint Handling Rules(CHR)[9,10].CHR is a powerful special-purpose declarative programming language for writing application-oriented constraint solvers.For our need,we extended an existingfinite domain solver written in CHR[11]in a way that the cost for a solution is computed during the propagation of soft constraints.CHR allows to express the calculation of the cost in a very declarative and straightforward manner.In this paper,we describe the main features of the constraint solver that was used to generate a classroom plan for the University of Munich.Section2introduces our classroom assignment problem and the constraints that a solution of the problem had to satisfy.Section3shows how the problem can be modelled as a partial constraint satisfaction problem.Section4gives an overview of the implementation.Section5describes the user interface.Finally,we conclude with a summary.2Problem DescriptionIn universities,where each department is responsible for its own timetable and where rooms can be shared by different departments,timetables are usually generated in two phases.In thefirst phase an assignment of courses within a given number of periods is done without taking into account the availability of rooms.This task has to be performed separately for each department.For the Computer Science Department at the University of Munich,thefirst phase is solved automatically by a system that generates a new timetable based on a timetable of the previous year[2,3].For other departments the generation of timetables is still done by hand.In the second phase an assignment of courses within a given number of rooms has to be performed.After collecting timetables of all departments and wishes of teachers a classroom plan is generated centrally.In the following,we want to investigate the classroom assignment problem of the University of Munich.Since timetables for departments change every semester,a new classroom plan has to be created each semester.The University of Munich dispose of different buildings.Thebiggest building consists of40rooms where about1000courses have to be held.The generation of a classroom plan is a difficult and time-consuming task since different kinds of constraints have to be taken into account:The no-occupation overlap constraint tells that occupation time of a room by courses must not overlap.The seat requirement constraint tells how many seats a course requires.The teacher’s wishes:We distinguish three kinds of wishes.–A room constraint binds a course date to a room.–A building constraint assigns a course date to a certain building.–An equipment constraint constrains a course date to be assigned to a room withcertain technical equipment,e.g.beamer or video.Usually not all specified requirements can be fulfilled since the number of(special)rooms is obviously limited.Therefore we distinguish two kinds of constraints.Hard constraints must always be satisfied,soft constraints may be violated.Roughly speaking,no-occupation overlap constraints and seat requirement constraints determine hard constraints,wishes may be hard or soft constraints.3A Constraint Model for Classroom AssignmentA constraint satisfaction problem(CSP)[16]is a pair,where isfinite set of variables, each associated with afinite domain,and is afinite set of constraints on these variables.A solution of a CSP maps each variable to a value of its domain such that all the constraints are satisfied.Since we have to address quality of a room plan and therefore,have to take into account wishes as well as exploitation of resources,CSP can not model our problem completely. Therefore,we use an extension of the CSP concept.A partial constraint satisfaction problem PCSP[8]is a triple,where is a CSP and is a total function, i.e.,maps constraints to weights.The weight of a constraint expresses its importance.Thus, one can describe hard constraints,which must be satisfied,as well as soft constraints,which should be satisfied.A hard constraint is given an infinite weight.Then,a solution of the PCSP is an assignment of the variables in to their domains,such that the total weight of all violated constraints is minimized.Now,the classroom assignment problem is modeled as a PCSP.Note,that it does not suffice to assign a room to each course,but instead we have to assign a room to each date,where a course is held.Therefore,we use one variable for each course date.For example,if a course consists of two lectures,the course is represented by two different course date variables.The initial domain of each course date variable is the set of all rooms in the university.Thus,the solution is an assignment of course dates to rooms.There are two constraints that occur only as hard constraints and thus have infinite weight: the no-occupation overlap constraint and the seat requirement constraint.Wishes may also be hard,i.e.have infinite weight.To ensure a good exploitation of resources by a solution,we evaluate assignments of a room to a course date.For this reason,we modify the weight for the constraint,that assigns a course date for a course to a room.This is done by adding a term to the user-defined evaluation,thus defining in the following way.seats requirement seatequipment(1) where seats is the number of seats in room,requirement seat is the number of seats required by course,equipment is a valuation of the technical equipment in and requirement equipment a value for the technical requirements of.and are negative constants weighting the exploitation of seats and equipment resources against each other and the violation of wishes. Since the equipment constraint can be soft,the value of the technical requirements can be greater than the value of the equipment.In this case,we have to avoid that the third term of the function is positive.4Solving the Problem using Constraint Handling RulesIn a PCSP,one has additionally to satisfying all hard constraints to take soft constraints into account.According to the PCSP model,we have to minimize the total weight of violated soft constraints.This is equivalent to maximize the total weight of satisfied constraints.We use a branch-and-bound approach to tackle this maximization problem.Branch-and-bound is a standard method to optimize a score that works by constraining the score during the search. Every time an assignment satisfying the hard constraints is found,the score is bound to be even better.Thus,the last assignment compatible to the hard constraints that is found will have an optimal score.Therefore,we incrementally compute a bound of the score,that an assignment compatible to the current hard constraints may have,during the enumeration.This way we prune the search tree every time the maximally achievable score is worse than the score of the previous solution.To prune the search tree efficiently in our branch-and-bound algorithm,we have to keep track of the upper bound of the score.The upper bound of the score may be affected each time the constraint store changes.This change may be done either by a constraint which is directly inserted by the labeling process or by constraint propagation.If only changes of thefirst kind could affect the upper bound,the calculation of the score could be easily incorporated into the labeling process.However,since we also have to take care of the second kind of constraint store changes,it is much more natural and intuitive to do this calculation concurrently to the labeling process and triggered by the alteration of the constraint store.Constraint Handling Rules(CHR) allows to express this in a very declarative and straightforward manner,where the calculation is formulated independently of the labeling.In the following,CHR is briefly introduced.Then,the core of the constraint solver,which performs hard and soft constraint propagation,is presented.Finally,a labeling strategy tofind good solutions is described.4.1Constraint Handling RulesCHR is a declarative high-level language extension especially designed for writing constraint solvers.With CHR,one can introduce user-defined constraints into a given host language.The main implementations of CHR are currently available in Prolog:Besides the library from1994, ECL PS 4.0now includes a new experimental prototype of CHR.An advanced optimizing CHR compiler was released for Sicstus3.7in1998[13].CHR has also been implemented in Common Lisp,OZ and Java.To implement the constraint solver for our classroom assignment problem we used the CHR library of Sicstus.Thus,code examples follow the syntax of CHR and Prolog.CHR is essentially a committed-choice language consisting of multi-headed guarded rules that rewrite constraints into simpler ones until they are solved.There are basically two kinds of CHR rules:Simplification rules replace constraints by simpler constraints while preserving log-ical equivalence.Propagation rules add new constraints which are logically redundant but may cause further simplification.Repeatedly applying the rules incrementally solves constraints. With multiple heads and propagation rules,CHR provides two features which are essential for non-trivial constraint handling.Due to space limitations,we cannot give a formal account of syntax and semantics of CHR in this paper.An overview on CHR can be found in[10].Detailed semantics results for CHR are available in[1].We introduce CHR by example.Let=<and=be built-in constraint symbols. We implement a user-defined constraint for max,where max(X,Y,Z)means that Z is the maximum of X and Y:max(X,Y,Z)<=>X=<YZ=X.max(X,Y,Z)==>X=<Z,Y=<Z.Thefirst rule states that max(X,Y,Z)is logically equivalent to Z=Y,provided it is the case that X=<Y.This test forms the guard of a rule,a precondition of the applicability of the rule. Hence,whenever we see the constraint max(X,Y,Z)in any goal where it holds that X=<Y we can simplify it to Z=Y.Analogously for the second rule.Thefirst and second rules are simplification rules.The third rule propagates constraints.It states that max(X,Y,Z)unconditionally implies X=<Z,Y=<Z.Operationally,we add these logical consequences as redundant constraints,the max constraint is kept.This kind of rule is called propagation rule.To the goal max(1,2,M)thefirst rule is applicable:max(1,2,M)will be simplified to M=2.Redundancy from the propagation rule is useful,as the goal max(A,3,3)shows:To this goal only the propagation rule is applicable,but then thefirst rule:max(A,3,3)cause thepropagation rule tofire and adds A=<3,3=3to the goal.Now,thefirst rule is applicable and simplifies the constraint max(A,3,3)to3=3.The constraint33is simplified to true by the built-in constraint solver.The constraint solver for max solved max(A,3,3)and produced the answer A=<3.4.2The Core of the Constraint Solver4.2.1Handling Hard ConstraintsRegarding just the hard constraints,our solver is essentially afinite domain solver,i.e.a course date variable is bound to a list of rooms and constraints may eliminate rooms from the domain list of the constrained variable.Constraint solving forfinite domains constraints is based on consistency techniques[17,15]. For example,the constraints X::[2,3,4]and X::[3,4,5]may be replaced by the new constraint X::[3,4](The constraint X::[2,3,4]means that X has to take a value from the list[2,3,4]).Implementing this technique with CHR is straightforward[11].Thefirst rule ensures that the domain for X is non-empty,the second rule intersects two domains for the same variable:X::[]<=>false.X::L1,X::L2<=>intersection(L1,L2,L),X::L.To solve our classroom assignment problem,the no-occupation overlap constraint can be expressed using the global constraint all distinct(Xs) tells that all variables in the list Xs must be bound to different values.The no-occupation overlap constraint is propagated to constraints allbuilding or equipment.CourseDate holds a course date identifier,the variable Wished further specifies the instance of the wish and Weight holds the weight of the wish.We use further the constraint assignment(CDate,CDateVar)which tells that CDateVar is the course date variable corresponding to the course date CDate.The constraint scoreWish(Up) tells that Up is the upper bound of the sub-score ScoreWish.In the following,we introduce simplification rules to update the sub-score ScoreWish, whenever a wish is satisfied or violated.In the following,we will discuss the rules for handling room constraints.The rules handling building and equipment constraints are analogous. assignment(CDate,CDateVar),CDateVar::Dom,wish(room,CDate,RoomWish,infinite)<=>assignment(CDate,CDateVar),CDateVar::Dom,CDateVar::[RoomWish].assignment(CDate,CDateVar),CDateVar::[RoomWish],wish(room,CDate,RoomWish,Weight)<=>Weight\==infinite|assignment(CDate,CDateVar),CDateVar::[RoomWish]. assignment(CDate,CDateVar),CDateVar::Dom,wish(room,CDate,RoomWish,Weight),scoreWish(Up)<=>Weight\==infinite,\+member(RoomWish,Dom)| assignment(CDate,CDateVar),CDateVar::Dom,scoreWish(Up-Weight).Thefirst rule propagates a hard wish,i.e.a wish with infinite weight,in such a way that an assignment of the course date variable to the wished room is performed.Therefore,the sim-plification rule tests whether constraints of the form assignment(CDate,CDateVar), CDateVar::Dom and wish(room,CDate,RoomWish,infinite)can be found in the constraint store.In this case,the rulefires and the constraint CDateVar::[RoomWish], that binds the room to the wished room,is added to the store.Furthermore,the wish constraint is removed from the constraint store.The application of this rule leads to the occurrence of two domains for the same variable.These constraints can be simplified by the intersection rule presented above.The second rule handles already satisfied soft constraints.If the constraints assign-ment(CDate,CDateVar),CDateVar::[RoomWish]and wish(room,CDate, RoomWish,Weight)are found in the constraint store,then the wish is obviously satisfied and the rule consequently removes the wish.The guard ensures that only soft constraints,i.e. wishes withfinite weight,are handled by this rule,since hard wish constraints are already han-dled by thefirst rule.Note that the upper bound of the score is unaffected if a wish is satisfied. In contrast,if a wish is violated,the upper bound of the score has to be decreased.The updating of the bound is done by the third rule.The guard ensures that only soft constraints which are violated lead to a change of the score.A room constraint is violatedif the wished room is not contained in the domain of the course date variable.If the rule fires,the upper bound is recomputed as Up-Weight and the constraint scoreWish(Up -Weight)replaces the constraint scoreWish(Up).The evaluation of resource exploitation is handled by a single rule.assignment(CDate,CDateVar),CDateVar::[RoomNr],scoreSeatsRes(UpS),scoreEquipmentRes(UpT)<=>assignment(CDate,CDateVar),CDateVar::[RoomNr],scoreSeatsRes_diff(CDate,RoomNr,SSD),scoreEquipmentRes_diff(CDate,RoomNr,TSD),scoreSeatsRes(UpS+SSD),scoreEquipmentRes(UpT+TSD).The rule updates the scores for seat resource and equipment resource exploitation,where the actual weight is calculated by the separate predicates scoreSeatsResdiff analogously to equation(1).The updating of the sub-scores is done by replacing the constraints scoreSeatsRes(UpS)and scoreEquipmentRes(UpT) by the recomputed constraints scoreSeatsRes(UpS+SSD)and scoreEquipmen-tRes(UpT+TSD)each time an assignment of a course date variable to a room was newly created,either by labeling or by constraint propagation.Each time a sub-score is recomputed,the total score has to be recalculated.This can be done by the following propagation rule.scoreWish(UpW),scoreSeatsRes(UpS),scoreEquipmentRes(UpT)==>score(UpC+UpS+UpT).The rulefires if a sub-score changes.Then,a constraint with the newly calculated upper bound of the total score is inserted.A further rule ensures that only the most restrictive score con-straint remains in the constraint store.score(A),score(B)<=>A=<B|score(A).This rule removes the larger of two upper bounds of the total score.Now,the upper bound can be used to prune the search tree,since we use a branch-and-bound algorithm.Every time an assignment of the course date variables that satisfies the hard constraints is found,we insert a constraint last4.3LabelingAfter stating the problem constraints,normally there are still many feasible solutions,so it is necessary to label the domain variables,i.e.assign them with values that remain on their domains.For the labeling one needs to apply a heuristic strategy that tends to enumerate high scoring solutions early in the search.In a branch-and-bound search this helps to prune the search tree.In practice also suboptimal solutions may be appropriate,which also emphasizes the use offinding good solutions early.We employed a leftmost variable,leftmost value strategy that selects for each assignment the leftmost course date variable and the leftmost value from the domain of the selected course date variable.Since we sort the list of variables as well as the values in the domains before the labeling as we describe below,this strategy prefers most constrained assignments.The sorting is done in the following way.We compute a weight for each course and a weight for each room with respect to a certain course,i.e.actually a weight for a certain assignment.The weights for courses respect seat and equipment requirements,such that courses with strong requirements get great weights.The weight of an assignment totals the weights of the soft constraints which are satisfied by the actual assignment.Then,the course date variables and the rooms in each domain are sorted in descending order by these weights.As a consequence the leftmost course date variables,which are selectedfirst by our strategy,belong to the courses with the strongest requirements.Further,the leftmost values in each domain lead to assignments,which satisfy the”best”soft constraints.5User InterfaceFor a classroom assignment system to be complete,aflexible user interface should be provided, so that the specific requirements of the problem can be stated easily.RoomPlan provides such an interface.The RoomPlan user interface was written in JAVA TM1.1using the Abstract Window Toolkit (AWT).It generates the data needed by the CHR solver in form of prolog facts and starts the CHR solver.Figure1shows the input form for the courses that have to be planned.The user has to type in the courses with title,first and last day and start-and endtime.Furthermore,the interface allows the user to define the system parameters as preferred.All parameters like the needed amount of seats and needed equipment,e.g.overhead projector are handled as soft constraints. In addition,the user can specify a wish for a special room.These wishes are given in four cat-egories:imperative,strong preferred,preferred and weakly preferred. Imperative wishes are hard constraints.If there is no wish for a special room,a building can be specified,which is considered by the classroom assignment.It may happen that there exists not even one classroom plan that complies with all the given hard constraints.Then the problem is called over-constrained.In case of a direct clash in form of two conflicting imperative room wishes,RoomPlan may detect this and then gives the user a variety of alternative rooms which satisfy the specified equipment wishes.Figure1:Classroom AssignmentFigure2shows a fragment of the generated classroom plan.In addition,the user can manu-ally alter a completely generated classroom plan and let it check by RoomPlan.An advantage of the interactive system is that the expert might assist the program to produce even better results.6ConclusionIn this paper,we have argued that Constraint Handling Rules(CHR)is a good vehicle for implementing a PCSP solver.We extended an existingfinite domain solver to deal with soft constraints.The idea was to compute the cost function during the propagation of constraints. This is much more natural and intuitive than the incorporation of the computation into the labeling process.Thus our approach is comparable in terms of declarativity to approaches embedding cost functions into a CLP(FD)system using reification.The solver is powerful enough to serve as the core of a classroom assignment system.Our system,RoomPlan,has been implemented using Sicstus Prolog.The CLP code is justabout700lines.RoomPlan assists a human planner in scheduling courses to rooms.Room-Plan was presented at the Systems’99Computer exhibition in Munich.It is currently tested at the University of Munich.Typically,for1000courses and40rooms,RoomPlan generates a satisfying schedule within a few minutes.Figure2:Fragment of a Classroom PlanRoomPlan has been designed to meet the specific requirements of the University of Munich. However,it can be applied to other universities,since the classroom assignment problem is already handled in a general way.However,if necessary,adaption can easily be done due to the the declarativity of constraint logic programming.In general problems a labeling strategy with previouslyfixed enumeration order is not suit-able,since a good order of variables or domain values often cannot befixed in advance.Only thespecial nature of our classroom assignment problem makes this strategy a suitable choice.Nev-ertheless,we are currently developing intelligent labeling strategies as quoted by Tsang[19]. AcknowledgementsWe would like to thank Thom Fr¨u hwirth and the anonymous referees for useful comments on a preliminary version of this paper.References[1]S.Abdennadher.Operational semantics and confluence of constraint propagation rules.InThird International Conference on Principles and Practice of Constraint Programming, CP’97,LNCS1330.Springer-Verlag,1997.[2]S.Abdennadher and M.Marte.University timetabling using constraint handling rules.InActes des Journ´e es Francophones de Programmation en Logique et Programmation par Contraintes,1998.[3]S.Abdennadher and M.Marte.University course timetabling using constraint handlingrules.Journal of Applied Artificial Intelligence,Special Issue on Constraint Handling Rules,to appear2000.[4]F.Azevedo and P.Barahona.Timetabling in constraint logic programming.In Proceedingsof2nd World Congress on Expert Systems,1994.[5]M.Carter and C.Tovey.When is the classroom assignment problem hard?OperationsResearch,40(1):28–39,1989.[6]J.Ferland and S.Roy.Timetabling problem for university as assignment of activity toputers and Operational Research,12(2):207–218,1985.[7]H.Frangouli,V.Harmandas,and P.Stamatopoulos.UTSE:Construction of optimumtimetables for university courses—A CLP based approach.In Proceedings of the Third International Conference on the Practical Applications of Prolog,pages225–243,1995.[8]E.C.Freuder and R.J.Wallace.Partial constraint satisfaction.Artificial Intelligence,58(1-3):21–70,December1992.[9]T.Fr¨u hwirth.Constraint handling rules.In A.Podelski,editor,Constraint Programming:Basics and Trends,LNCS910.Springer-Verlag,1995.[10]T.Fr¨u hwirth.Theory and practice of constraint handling rules,special issue on constraintlogic programming.Journal of Logic Programming,pages95–138,October1998.[11]T.Fr¨u hwirth and S.Abdennadher.Constraint-Programmierung:Grundlagen und Anwen-dungen.Springer-Verlag,September1997.[12]M.Henz and J.W¨u ing Oz for college time tabling.In Proceedings of the FirstInternational Conference on the Practice and Theory of Automated Timetabling,pages 283–296,1995.[13]C.Holzbaur and T.Fr¨u hwirth.A prolog constraint handling rules compiler and runtimesystem.Journal of Applied Artificial Intelligence,Special Issue on Constraint Handling Rules,to appear2000.[14]J.Jaffar and M.J.Maher.Constraint logic programming:A survey.Journal of LogicProgramming,20,1994.[15]V.Kumar.Algorithms for constraint-satisfaction problems:A survey.AI Magazine,13(1),1992.[16]A.K.Mackworth.Consistency in networks of relations.Artificial Intelligence,8:99–118,1977.[17]A.K.Mackworth.Constraint satisfaction.In S.C.Shapiro,editor,Encyclopedia ofArtificial Intelligence.Wiley,1992.V olume1,second edition.[18]K.Marriott and P.Stuckey.Programming with Constraints:An Introduction.The MITPress,1998.[19]E.Tsang.Foundations of Constraint Satisfaction.Academic Press,1993.[20]M.Wallace.Practical applications of constraint programming.Constraints Journal,1(1,2),September1996.。

Bounded optimization of resource allocation among multipleagents using an organizational decision modelQiang Wei a,*,Tetsuo Sawaragi a ,Yajie Tian a,baPrecision Engineering Department,Graduate School of Engineering,Kyoto University,Sakyo-ku,Kyoto,606-8501,JapanbAdvanced Telecommunications Research Institute International,Kansai Science City ‘Keihanna’,JapanAbstractMulti-agent System (MAS)can be used to dispose bounded optimization problems with dynamically changing resources because its autonomous distributed management model aspect is fitted to dealing with such external disturbances.One of the problems in multi-agent optimizations is that it is difficult to rigorously define the optimization criteria with respect to the global optimization in advance.Rather,it may depend much on more situated factors such as temporal availability of resources and coexistence of current conflicts,conflicts among what has been already scheduled and what is to be scheduled.In this paper,an organizational model called Garbage Can Model (GCM)is introduced.In GCM,through its three decision-making strategies and the fluidities of problems and resources,solutions made by an individual agent are concerned with several agents that are co-existing in the environment.The problems allocated to each agent are solved not only by an agent’s own efforts,but also by the change of problem solving status of other agents.Our simulation experiment shows that GCM is a preferred framework for multi-agent optimization problems in dealing with the above difficulties.q 2005Elsevier Ltd.All rights reserved.Keywords:Garbage can model (GCM);Multi-agent system (MAS);Conflict;Bounded optimization;Decision mode1.IntroductionAn optimization problem is a computational problem in which the objective is to find the best of all possible solutions for some problems with the given resources.Such kind of optimization is called as ‘bounded optimization/optimality’([1]).Bounded optimization configuration is an equilibrium point of the forces that tend to maximize the quality of decisions,minimize the time to make those decisions,and maximize the speed of adaptation to the environment ([2]).To accommodate these forces,we should incorporate a variety of representations of functions,ranging from a fully declarative,decision-theoretic model to fully complied condition-action rules and procedures with finite calculation.In some problems with bounded resources and multiple optimal goals,the best solution cannot be foundeasily.It much depends on the temporal available resources and the relationships of goals.In recent years,many researchers argue that multi-agent optimization is one of the approaches of dealing with such difficulty ([3,4,14]).Most of MASs is decentralized systems composed of autonomous agents.The autonomous distributed organiz-ational model makes that MAS is suitable for some bounded optimization problems with dynamically bounded resources and multiple goals,in which the optimization is carried out under the resource allowance (i.e.bounded rationality),and global optimization criteria are divided into several local objectives that will be achieved by each unit (i.e.agent ).The global criteria are achieved through agents’individual optimizations and the negotiations among them.Generally,there are three kinds of crucial problems when applying MAS to such a multi-goals optimization problem:the un-predicted temporal available resources in each optimization stage;the competitions among agents and the re-allocations of problems and resources for the changing of the environment.In this paper,we adopt an organizational model named Garbage Can Model (GCM)[12]to multi-agent1474-0346/$-see front matter q 2005Elsevier Ltd.All rights reserved.doi:10.1016/j.aei.2005.01.001Advanced Engineering Informatics 19(2005)67–78/locate/aei*Corresponding author.Address:Panasonic R&D Center of China,Panasonic Beijing Laboratory,Precision Engineering Department,18th Floor,Zhongguancun Tower,No.27,Zhongguancun Street,Beijing,China.Tel.:C 861082856173;fax:C 861082856428.E-mail address:weiqiang@ (Q.Wei).optimization.In GCM,the problems and resources to be optimized are thrown into several garbage cans(i.e.choice opportunities)in a time series.When the problems and resources in a garbage can satisfy some pre-defined criteria (e.g.the garbage can is full-filled),the can will be dumped (i.e.be thrown away of the current environment).The optimization systems are composed of un-dumped garbage cans,among which the problems and resources are able to be re-allocated(i.e.shifted from one can to another) according to some decision-making strategies(aniz-ational norm).This model allocates temporal resources dynamically and efficiently,not only because it provides many opportunities when problems and resources are being thrown into the system,but also because it provides lots of fluidities for the problems and resources which have been allocated to garbage cans.Furthermore,agents’compe-titions for the bounded resources are relaxed through the decision-making strategies in GCM.This paper focuses on how to deal with the optimizations among autonomous agents in resource-bounded environ-ment.It is organized as follows:in Section2we discuss the decision problems in MAS multi-agent system.Then one of organizational models—GCM is introduced in Section3. Through an example we explain how to apply GCM to a multi-agent optimization system in Section4.After that,by comparing the result of this new system to original MAS optimization system,we show the advantage when GCM is applied to a multi-agent scheduling problem.In the Section 6,we summarize the whole paper and talk about our future work.2.Multi-agent optimization problemA multi-agent system is a dynamic system composed of autonomous agents.It is a decentralized management system in which there is no any super-agent or system controller.The system functions rely on each agent’s functions.Multi-agent optimization is an optimal method-ology in which the global optimization criteria are divided into several local optimization goals.Each agent in the MAS is only concerned about a local optimization goal.The global optimization is achieved through a combination of these local optimizations.This kind of methodology is suitable for those complicate problems in which there are too many constraints or goals to define a global optimiz-ation criterion clearly and exhaustively in advance.In multi-agent optimization,an agent is an independent optimizing unit and it achieves its local goal individually.It communicates with other agents only when its optimization process cannot be carried on without others’collaborations. In such a loosely coupled optimization system[13],there are some crucial problems to be considered.First,to predict temporal available resources in every stage of bounded optimization is one of the eargest difficulties in multi-agent optimization.MAS is not a closed system,but is an open system that continuously interacts with its outside world.The participants,resources as well as problems of a MAS are changed from time to time.For a MAS designer,it is difficult to predict the withdrawal/ appearance of agents,the occurrence and production of problems/resources in advance.In addition,each agent in a MAS takes actions and consumes resources independently and dispersedly.The resources available in the system in a certain situation are difficult to predict in advance because agent’s resource-consuming activities are idiopathic and irregular.Second,agents sometimes interfere and conflict with each other in a MAS.Most of such conflicts belong to resource competitions,which are usually caused by agents’various implementations seeking for an identical goal.In a MAS without coordination and collaborations,agents are usually concerned about how to achieve their local goals in their own implementations even if they have an identical global goal.When two agents want to make use of an identical resource simultaneously,a conflict will occur.Another difficulty in multi-agent optimization is that solutions cannot be generated before all the problems and resources are available to the optimization system.In a traditional multi-agent optimization system,solutions are generated only when all the problems and resources are known to the optimization system.In such system,the optimization is carried on among all the problems/resources and tries tofind the best solution for these problems and resources.Such strategy has some the disadvantage not only because it is difficult tofind the best solution for all the problems/resources in some optimization problems(e.g. NP-hard problem),but also because it cannot be used in real time bounded optimization problems,in which the problems and resources are delivered and allocated into the optimization system in a time series.In the latter case,it is impossible to know all the information about the problems and resources before all of them have entered into the system.Therefore,there is no solution generated before all the problems and resources are known.But on the other hand,real world problems do need an anytime algorithm—a bounded optimization algorithm that gener-ates some solutions under partial available problems and resources in order to satisfy real time requirements.3.Garbage can model3.1.Overview of original GCMGCM was originally introduced in afield of organization theory for explaining organized anarchies It is a kind of descriptive model that is most appropriate for modeling the tasks in organizations descriptively where the technologies are not clear,the involvement of participantsfluctuates in the given amount of time and effort,and choices are sometimes inconsistent and not well defined([5,6]).Q.Wei et al./Advanced Engineering Informatics19(2005)67–78 68According to Cohen’s model,there are four elements in GCM:†Problems:The concern of people inside and outside the organization.†Choice opportunities:Occasions when an organization is expected to produce behavior that can be called a decision.†Energy from participants:The resources of the organiz-ation consumed for decision-making.†Solutions:Decision’s product.In GCM,a choice opportunity can be viewed as a garbage can into which various kinds of problems and energies are dumped by participants.Each of these four elements mentioned above is a time-serial stream andflows into the system.When some criteria are satisfied,a decision is made on a garbage can and it is removed from the current environment.The energy and problems in garbage cans are managed by participants.Participants are the elements that provide energy for problem-solving in garbage cans.In GCM,all participants work as a group,and sometimes also decide the accessible properties(i.e.matching properties)between energy and problems.Different participants may provide different energy(e.g.different energy both in quantity and in category)to garbage cans(Fig.1).There are three key behavioral assumptions in GCM:†Energy additivity assumption:As soon as the total effective energy that has been expended on a choice equals or exceeds the requirements of problems at a particular point in time,a decision is made.†Energy allocation assumption:The energy of each participant is allocated to no more than one choice during each time period.†Problem allocation assumption:Each problem is attached to no more than one choice in each time period, choosing from among those accessible by calculating the apparent energy deficits at the end of the previous time period and selecting the choice closest to the decision.Thefirst two assumptions guarantee the validities of the resources and problems in a garbage can;the last one defines the rule when allocating problems into a garbage can.A new problem will be allocated to a garbage can if a decision will be made on this can by this allocation(i.e.a garbage can is full-filled and should be dumped).In other words,when allocating a new problem,wefirstly consider about the garbage cans in which the resource-problem combinations are closest to the assigned criteria.Decisions in GCM are made in three different ways:†By resolution.Problems are resolved after some periods of working on them.†By oversight.Energy and problem are allocated to an arbitrary choice opportunity if a decision can be made on it.†Byflight.Decisions are made through shifting problems from one choice opportunity to another.3.2.Merits and demerits of original GCMThe most important character of GCM is that problems and energies in GCM are allowed to move to another garbage can anytime whenever some criteria aresatisfied anizational mode in Garbage Can Model.Q.Wei et al./Advanced Engineering Informatics19(2005)67–7869(i.e.problems may disappear from a choice opportunity and participants may come and go)([7]).In this way,problems in each garbage can are solved not only by a participant’s own efforts,but also by the change of problem solving status in other garbage cans as well as by the external environment from which the problems are thrown into the cans.In other word,problem solving in GCM may not only depend on the problem solver’s own optimizing efforts,but also depend on the problem solving activity and/or status performed so far. The problems that are under-determined in the early stage will become easy to solve with the changes of problem solving status and the environment.Furthermore,GCM carries out a continuous partial optimization on the dynamic problems and energy.In GCM, problems and energyflow into/out of the system continu-ously.In such a dynamic environment,it is difficult to carry out an offline optimization on all the problems and energy because all the problems/energy are not available.In GCM, a partial optimization is carried out when a problemflows into the system.It depends on the current available problems and energy(i.e.allocating the problem according to current available problems and energy).This partial optimization is not the eventual decision for this problem because with the entering of following problems/energy and theflights of problems/energy this problem may be re-allocated tofind a better solution.Such optimizations are carried out until the problemflows out of the system.This strategy is highly suitable for optimizations with real-time inputs and dynamic environments.The demerit of the original GCM is that the evaluations/ criteria to all garbage cans are unified and simplified.The allocation of problems and energy are managed by a unified organizational strategy.Moreover,this organizational strat-egy also decides the decisions made on garbage cans.Each garbage can itself has no opportunity to exhibit and realize its individual interests and preference in allocating problems and energy.This demerit makes the original GCM only suitable for the bounded optimization problems of single goal and non-bounded resource.In order to apply GCM to deal with the problems with multi-goals and bounded resources, we extended GCM to a new one in which the concept of multi-agent and GCM are combined together.3.3.An extended GCM—multi-agent garbage can modelIn our extended GCM,we introduced the agent concept into the original GCM.The garbage can in original GCM is managed by an agent,which is responsible forfinding an optimal resource-problem combination for its garbage can. These agents have different evaluation and criteria in managing the optimization of their own garbage can.The organizational optimization is a combination of these agents’optimization.Through placing extra emphasis on the combination of these criteria,the multi-goals and bounded resources constraints can be satisfied simul-taneously.From this view,GCM is also viewed as a MAS in which the optimization of energy and problems are achieved by autonomous agents.Furthermore,in order to adapt to the changes of problem solving status and the environment,the optimizations of agents in GCM are carried on at the time until decisions are made on agents.Since multi-agent optimizations are dynamic and distributed optimizations,the optimal sol-utions of agents achieved in the early stage may become inefficient with the environment changed.The weakness of some traditional multi-agent optimization algorithms is that these inefficient solutions do not allow to be changed anymore.On the contrary,through theflight of GCM, incomplete or partial solutions that are derived but not appropriate asfinal solutions can be efficiently utilized without make them invalid.When allocating a new problem,instead of wasting too much effort infinding a local optimal solution for this problem,GCM provides a shared andfluid environment for agents’negotiation and group decisions.The system established in GCM can be viewed as a buffer between inputs(i.e.problems and resources)and outputs(i.e.solutions).The group optimiz-ations among garbage cans are carried on not only when the problems and resourcesflow into the system,but also when the solutionsflow out from the system.Moreover,such optimization is not only achieved through an individual’s efforts,but also through the change of other agents’status, through theflight of the problems and resources among agents.Thefluidity endows GCM with much more self-organized optimization capabilities than the simple sum-mation of agent’s individual efforts.Throughflight,the optimization to an individual problem is not only carried out once,but also carried out again and again in the life cycle of this problem.Agents are different from the participants in original GCM because all participants work as a group to provide energy for problem solving in garbage cans.Different participants may provide different energy(e.g.different energy both in quantity and in category)to garbage cans. There is no such one-to-one corresponding relationship between participants and garbage can.On the contrary,each agent is responsible for the optimization of a certain garbage can.Agents in our extended GCM do not provide energy for problem solving,but manage the allocations of proble-ms/resources in a certain garbage can and communicate with other agents to achieve a collaborating optimization.4.Extended GCM in multi-agent optimizationIn this section,through an example we illustrate how to apply GCM to multi-agent optimization.4.1.Example descriptionThe example shown in this section is called Loading, Allocating and Scheduling Problem(LASP),which isQ.Wei et al./Advanced Engineering Informatics19(2005)67–78 70concerned about the algorithm of placing some products (i.e.blocks with different length,width,height and weight)into a given space.This problem is from the requirements of low costs to current industrial transporting systems.In this paper,it is supposed that all products have similar bottom areas but difference heights and weights.These products flow into the optimization system in an irregular and unexpected way.The goal is to put these products into the space efficiently with satisfying some constraints,such as one of the results shown in Fig.2.The details of this real world problem has been discussed in our former papers ([8–10]).LASP is a difficult bounded optimization problem because of the multiplicity of input products and the multiple constraints in real world transporting conditions.This problem is also an optimization problem with multi-goals (e.g.efficiency and constraints)and bounded resources (e.g.bounded available space and bounded optimizing time).Usually,LASP is solved in two processes.The first process is to generate a series of modules ,each of which is composed of several products and the second process is to allocate the modules into containers.In this paper,we focus our attention on the first process.The real world version of our example has many constraints to satisfy simultaneously.According to our investigation to the real-life environment,it is found that these constraints are usually divided into two categories:Hard Constraints and Soft Constraints .Hard constraints are strong requirements from users,which must be satisfied absolutely in any condition;soft constraints are domain-specific preferences,which should be satisfied as much as possible.Soft constraints can be relaxed sometimes in order to make a trade-off between constraints and efficiency.The introductions of hard and soft constraints increase the flexibility in optimization and conform with a human’s judgment (i.e.decision making strategy)in the real-life environment.In our definitions of constraints shown below,pl i ,pw i ,ph i ,pg i denote the length,width,height and weight of products p i ;ml k ,mw k ,mh k ,mg g denote the length,width,height and weight of module m k ,where ml k Z max f pl k i g ,mw k Z max f pw k i g ,mh k Z P ph k i and mg k Z P pg k i ,p ki 2m k .WG and H are the maximum weight and the maximum height of a module,respectively.The hard and soft constraints are described as follows:Hard constraints:mg k %WG ;ðk Z 1;2;/;n Þ(1)mh k %H ;ðk Z 1;2;/;n Þ(2)These two constraints assign the maximum weight and height of a module.They define strict constraints for problem’s allocations that should be satisfied in any situation.Soft constraints:Soft constraints are concerned about the relationships of products in a module,which include the difference of weight and the difference of bottom areas between two neighboring products.†Weight difference constraint pg i C 1K pg i %3wg ;max ð3wg Þ%N wg(3)†Bottom area difference constraint pl i C 1K pl i %3l ;max ð3l Þ%min ðpl i Þ=5(4)pw i C 1K pw i %3w ;max ð3w Þ%min ðpw i Þ=5(5)N wg is constraint criteria given by user.In our simulation,N wg Z 30.3wg ,3l and 3w are the parameters for relaxing the soft constraints of weight,of length and of width,respectively.The initial values of them are set to 0,and they will be increased step by step to their toplimit.With the increase of 3wg ,3l and 3w ,the weight and bottom area constraints between two neighboring products in a module are relaxed gradually.The soft constraints come from the stability and safety requirements in real world transporting processes.They are not defined as strictly as hard constraints.When there is an urgent space efficiency requirement,these soft constraints can be relaxed to some extent.In real world transporting system,these soft constraints may depend on the requirements and the preferences of the users.The difficulties of this bounded optimization problem includes the uncertainty of real-time input products and the constraints that can be relaxed.Products flow into the system continuously when the optimization is going on.The system must take two kinds of optimization into consider-ation in each episode:one is to allocate the new coming product to a certain module and the other is to re-allocate those products which have flown into the system to find a new optimal solution for the change of the environment.Another difficulty in such optimization problem is that the soft constraints given by a user are usually uncertain and adjustable,as defined in the above equations.Moreover,to satisfy these constraints usually lead to a worse loading efficiency.Therefore,the conflict between the allocation and re-allocation of products,and the conflictsbetweenFig.2.A simulation result of our example.Q.Wei et al./Advanced Engineering Informatics 19(2005)67–7871loading efficiency and constraints are two difficulties we confronted in such real-life problem.4.2.Modeling LASP by extended GCMIn this section,we simulate the process of generating the modules mentioned above using GCM.The four elements in GCM are mapped as follows:†Problems—Products to be placed into modules†Choice opportunities—Empty modules with height limitations and loading limitations(i.e.weight limitations)†Energies from participants—Space assigned in module †Solutions—The modules satisfied the criterion defined in Eq.(6)As we mentioned,GCM was originally designed for organizational decision,in which the loading factor of energy in each garbage can was not considered carefully when a decision is made.In our example,in order to enhance the efficiency of GCM we introduce a decision factor R k,which is expressed as the following equation:R k Z Pph k iH!R%1;i Z1;2;/;n(6)where ph k i is the height of the i th product,n is the products’count and H is the maximum height in module i.R k is a parameter to indicate the efficiency of a module.A decision on a module is made if R k O R,which means a decision can be made if the total height of products in the module exceeds a constant R assigned by users,and otherwise it remains under determined.Therefore,R is the criterion to judge whether a module should be dumped or not.Fig.3shows the process of applying GCM to LASP. Empty modules and productsflow into the system in time series.After an empty moduleflows into the system,it is managed by an agent.An agent has the capabilities of receiving,rejecting and throwing a product into/from its module according to its local criterion and goal.The energy is considered as the space(i.e.carrying capacity)in each module,which is consumed by the products allocated to this module.Products are allocated to modules by agents after theyflow into the system.The product’s allocation of agents should satisfy the hard and soft constraints described in Section 4.1.Through the negotiations among agents, products are able to shift from one module to another(the strategy of negotiation will be explained in the following). The negotiations of agents are conducted by the organiz-ational rules in GCM.When the space and products in a module satisfy the criteria defined above,this module is viewed as a full garbage can and will be dumped out of the system.The position it occupied will be left for another empty module.In our experiment,the maximum number of the available positions is set to six.4.3.Agents’autonomy and organizational normsAll modules in the example are divided into three states: inactive modules,active modules and dumped modules. Inactive modules are the choice opportunities that stay in the queue and wait to be thrown into the system;active modules are the choice opportunities that have been thrown into the system.Dumped modules are the modules that the total height of the products satisfies Eq.(6).They will be dumped and the products in them cannot be moved to other modules anymore.All the agents in extended GCM are independent entities and have the autonomy of achieving their local goals. An agent manages an active module through receiving/ rejecting products and shifting the products in its module to other modules.The agent’s local judgment andcriterionFig.3.GCM mapping of our example.Q.Wei et al./Advanced Engineering Informatics19(2005)67–7872(i.e.to make good use of the space in it module and to satisfy the hard and soft constraints as good as possible)guide the management to its module.The optimization of the whole system is just composed by these agents’individual optimizations.On the other hand,agents allocate a new coming product should obey the following organizational norms: Step1.Allocated by oversight.If the product can be allocated to a module by the module’s agent,and this module becomes full and is going to be dumped out of the system after this allocation,then the agent allocates the product to its module without considering other(better) solutions(i.e.other agent’s allocation statuses);otherwise go to Step2.Step2.Allocated byflight.If this product can be allocated to a module(e.g.module1)through an agent shifting one of its product(e.g.product A of module1)to another module(e.g.module2),and this kind of shift results in a module(either module1or module2)that becomes full and is going to be dumped out of the system,then the agent shifts product A from module1to module2(shown in Fig.4) and allocates the arriving product into module1;otherwise go to Step3;Step3.Allocated by resolution.If the arriving product can be allocated into modules,allocate it to the module that has the maximum height(i.e.the module that is most near to a decision-making);otherwise go to Step4;Step4.Create a new module and allocate the product in it.If the maximum number of active modules are reached(in our case it is six),a special decision-making process is started and dump the module with the maximum height out of the system.In this model,although products are allocated to modules when theyflow into the system,they still havefluidity to shift to another module in order to get a better solution.The finalized allocations of products and spaces are not made until they are going toflow out of the system(i.e.dumping a garbage can).The co-existence of many products and spaces in active modules provides lots of chance for re-allocation and re-optimization.The algorithm mentioned in the above provides a real time andflexible strategy for multi-agent optimization. Oversight is a fast decision-making strategy between deliberation/optimization and solution costs.An arriving product will be allocated into a module as soon as possible if this module is full after allocating this product.We do not try to deliberately search which module has the maximum loading ratio after allocating this product.This aspect seems to be irrational,but a human expert is actually adopting such a strategy.This strategy can be regarded as bounded-rational if we consider the tradeoffs between the easiness of getting satisfactory and the cost needed by deliberate optimization.In our problem,such strategy rapidly decreases the number of active modules co-existence in the system and keeps the system in a compact optimizing scope.It decreases the computational complex-ities consumed in searching the most optimal module at the cost of a little loading quality.Oversight does not affect the total loading ratio too much,because although the module we found may be not the most optimal one,it is an nearly optimal one which has a loading ratio more than R (e.g.R Z0.9).Flight provides many re-allocation and optimization opportunities forfinding better solutions.In GCM,we named the exchange of products among modules asflight.If the new coming product cannot be allocated by oversight,it will be allocated through reallocating one of the products in an active module to another active module.In suchflight,an optimal solution is not only contributed by the status of an individual module,but also by the status of all the co-existing active modules.That is,although the product can only be allocated into a module(e.g.module1),other module’s(e.g.module2)status/situations do affect the capabilities of module1to hold the product.It should be stressed that in order to avoid the repetitive flight of a product,theflight should be controlledunder Fig.4.Shift product A from module1to module2if a decisions can be made on module2’.Q.Wei et al./Advanced Engineering Informatics19(2005)67–7873。