Group Multi-Role Assignment W ith Conflicting Rolesand Agents

Haibin Zhu,

Abstract—Group role assignment (GRA) is originally a complex problem in role-based collaboration(RBC). The solution to GRA provides modelling techniques for more complex problems.GRA with constraints(GRA+) is categorized asa class of complex assignment problems. At present, there are few generally efficient solutions to this category of problems. Each special problem case requiresa specific solution.Group multi-role assignment(GMRA)and GRA w ith conflicting agents on roles(GRACAR)are two problem cases in GRA+. The contributions of this paper include:1)The formalization of a new problem of GRA+,called group multi-role assignment with conflicting roles and agents(GMAC), which is an extension to the combination of GMRA and GRACAR; 2) A practical solution based on an optim ization platform; 3) A sufficient condition,used in planning,for solving GMAC problems;and 4) A clear presentation of the benefits in avoiding conflicts when dealing with GMAC.The proposed methods are verified by experiments,simulations,proofs and analysis.

I.In t roduction

CONFLICTS are major reasons why collaborative efforts can become inefficient and ineffective.Such conflicts can result in verbal arguments,quarrels,emotional disappointment,and even physical confrontation[1]–[4].Resource sharing and personal interaction can be sources of conflict.This paper discusses a typical role assignment problem considering possible conflicts.The proposed method aims at carefully designed assignmentstrategies and policies to avoid potential conflicts.

Role-based collaboration(RBC)[5] has been investigated for almost two decades and verified as a prom ising way to deal w ith collaboration problems.The environments-classes,agents,roles,groups,and objects(E-CARGO)model is designed as the fundamental model of RBC,and has been proved possessing significant power of modelling.RBC and E-CARGO are confirmed to be applicable in dealing w ith real-world problems.

In supportof this claim, we have examined,formalized and solvedmany assignment cases thatextend general assignment problems[6].For example, we have formalized and solved the problemsas follows(Fig.1):

1)Group roleassignment (GRA)[7];

2)GRA w ith constraints(GRA+)including:

i)GRA w ith conflicting agents on roles(GRACAR)[8];

ii)Groupmulti-role assignment (GMRA)[9],10];

iii)GRA w ith conflict and cooperation factors[11];

iv)GRA w ith balance between preferencesand performance[12];and

v)Tree-structured task allocation [13];

3)GRA w ith multipleobjectives(GRA++)including:

i)GRA w ith budget constraints[14];

ii)Good at many and expert one[15];

iii)GRA w ith agents’busynessdegrees[16];

iv)GRA w ith agents’ preferences[17];and

v)Most economic redundant assignment [18].

Fig.1.The roadmap of thiswork.

These efforts provide solutions to real-world problems.They also broaden the scope of operational research[19]into the development of additional specific and efficient algorithms.It is important to note thatnotall GRA problems can be expressed by integer linear programming(ILP)[6],[19]–[24]due to the extended scope of assignment problems(Fig.2).From Fig.2,itcan be seen that a fundamental way to handle GRA,which includesGRA+and GRA++,is a transformation into ILPproblemsand then a solution through using an optimization platform.

Fig.2.Overlap of GRA w ith ILP.

This paper discusses a new type of GMRA problem.It introduces two key conflict types,i.e.,agent conflictsand role conflicts,and is called group multi-role assignment w ith conflicting roles and agents(GMAC).GMAC differs from the previous work[5],[7]–[18]in that the solutions to the previous GRA problems cannot be applied to this situation w ithout paying a significanteffort.The discovery route to the GMAC problem is illustrated in Fig.1.

Although the proposed problem is investigated from a theoretical and abstract way,it maps many industrial problems.Section II presents one case.Another common example is scheduling persons driving trucks,i.e.,agent(driver,truck),is scheduled for a city on a day,i.e.,role(city,day). Agent conflict happens because one person cannotdrive two different trucks at the same time,i.e.,agent(driver1,truck1)and agent(driver1,truck2)are in conflict.At the same time,role conflict occurs because a truck cannot go to different citieson the same day due to long distances,i.e.,role(city1,day1)and role(city2,day1)are in conflict.Therefore,the solution to the proposed problem issignificant.

This paper assumes that the human power is not enough to conduct GRA,which allows each person to take atmost one role.This assumption is acceptable when GRA has no solutions due to insufficient staff.W ith this consideration,there aremany variationswhen we conduct group multi-role assignment(GMRA).GMRA in fact opensa scope to manage a team to avoid future cooperation problems in many different aspects.If we compare general role assignment(GA),group role assignment(GRA),and GMRA,we may find that the introduction ofLandLa(Section III)can be used to model more complex team situations.Solutions to these problems make unique contributions to the literature definitely.

The remainder of this paper is outlined as follows.Section II describes a real-world scenario.Section III specifies the elements used in formalization w ith E-CARGO and defines the proposed problem,i.e.,GMAC.Section IV illustrates experiments on the GMAC problem w ith the IBM ILOG CPLEX optimization package(CPLEX)and provides efficiency analysis.Section V presents a sufficient condition for GMAC to be feasible.Section VIillustrates the benefitsof avoiding the aforementioned conflicts in GMAC.Section VII outlines related work.Conclusions and suggestions for future research topics appear in Section VIII.A nomenclature is added in the Appendix to ease reading.

II.A Rea l-W or ld Scena r io

In company X,Adam, the chief executive officer(CEO),w ins a bid for a software development project.He seeks the assistance of Christine,the human resources(HR)officer by asking her to establish an appropriate team from among the company employees.Christine composes a task list(Table I)for the team and a list of candidates(the leftmost column in Table II). Next,she uses routine criteria to evaluate the qualification of each employee for specific project tasks(Table II).Table III informs thatmore than one task can be assigned to one employee due to staffing shortage but such numbers should be limited to guarantee quality.Past performance is used to set the task lim its for each team member.Based on Tables I–III,Christine can assign the tasks to candidates shown in Table II(numbers in the parentheses)by using the GMRA algorithm[10]to maxim ize the sum of all the assigned qualification values and satisfy all task requirementsgiven by Tables Iand III.

TABLE I Required Positions

Theassumption of Table IIisvalid and has its rationale.For example,if the roles are courses to take,C++,operating systems,data structure,and networking,and an agent(student)is evaluated by his performance on each course,we may acquire the numbers of 85%,78%,83%,and 91%,i.e.,0.85,0.78,0.83,and 0.91.Therefore,the sum of all the qualification valuesof an agent can be larger than 1.

Table III assumes the number of tasks for each person to take atmost.Therefore,they are supposed of integers.The setting of these numbers should be based on historical data and each person’s past performance.It is reasonable because different people have different energy,capacity,and personality;and some may deal w ith many tasks well but someothersmay not.

To guarantee overall project quality,Adam reminds Christine to address any conflicts from task assignments among team members.Conflicting tasks cannot be assigned to the same person.Conflicting persons cannot beassigned to the same task.On this basis,Christine creates Tables IV and V.

Faced w ith these new requirements,Christine encounters a new challenge that is more complex than GRMA[10]and GRACAR[8].She requests,and receives,additional time to establish an acceptable task assignment. Now,Christine has to deal w ith the GMAC problem before the extended deadline.

III.E-CARGO M odel and Rela ted Problems

TABLE II The Qua l if ica tions

TABLE III Al lowed Number of Assigned Tasks

TABLE IV Agent Con f l icts

where(4)means that each role should be assigned to one agent;and(3)indicates thateach agent is to be assigned only

TABLE V Role Con f l icts

where(6)means that oneagent isassigned,at most,one role.

Compared w ith GA,GRA raises the possibility of conflicting agents, because one role may be assigned to multiple agents.Compared w ith GA and GRA,GMRA raises the possibility of conflicting roles, because one agentmay be assigned to multiple roles.

We now need to introduce two new structures in order to formalizeGMAC.

By solving the GMAC problem, we obtain a new assignment scheme shown in Table II (bold numbers).Although thegroup performance is9.51 and lower than that of GMRA,i.e.,9.95, this scheme avoids conflicts.Based on GRMA assignment,underlined values in Table II indicate three pairs of conflicts:Bob and Ed,Chris and Doug on roleCoder,andCoderandTesterfor agent Ed.Considering the involved qualification values,0.9,0.64,0.33,0.70,and 0.78,which are 3.35 in total.If these conflicts cause a performance decrease of 15%,actual group performance for GMRA becomes 9.95– 3.35×15%=9.95– 0.5025= 9.4475,which is less than the new group performance value of 9.51.If the conflicts are not severe and lead to a performance decrease of only 10%, then GMRA performs better than GMAC.

To assist decision makers to well plan and organize a team before solving the GMAC problem,we need to state a necessary condition.

Theorem 1:A necessary condition for GMAC to have a feasible solution is that

Proof:Note that(9)is a necessary condition of the corresponding GMRA problem[10],which does not consider constraints(7)and (8), to havea feasible solution.Therefore,(9)isalso a necessary condition for GMAC.

IV.Exper imen ts

To verify the performance of the CPLEX solution to GMAC,we implement a Java program based on the CPLEX package [25].The platform is shown in Table VI.

The first experiment is conducted to establish the trend of consumed time vs.the increase of problem scales.In each step we test for 100 random cases.In each case,Q,L,La,Ac,andRcare random ly generated(uniform distributions) based onthedesignated conflict ratepca=pcr= 30%(see Definitions19 and 20),wheremvaries from 20 to 200 in increments of 20,andm=n.

TABLEVI Exper iment Plat form Con f igu ration

Unfortunately,we could not obtain the results after eight hours.From the experience,CPLEX uses much time in searching for problem solutionswhere noneexists.To address the matter, we apply the necessary condition for GMAC to havea feasible solution (Theorem 1).

In the next experiment,we added one step to check whether the problem case satisfies(9).If the necessary condition isnot satisfied,we do not start the CPLEX search.Fig.3 shows the experiment results,where we only show the maximum and average time, because the minimum time isalways0when not satisfying(9).The feasible rates for the random cases are shown in Table VII.

Fig.3.Time consumed by problems in different scales.

TABLE VII Feasible Ra tes for Dif ferent Sca les

In the third experiment,using the same settings from the second one, we conduct simulations(Fig.4)by guaranteeing that each case satisfies the necessary condition,i.e.,(9).We notice that the maximum consumed time is sim ilar to the second experiment but the average and minimum times increase due to the searching efforts of CPLEX.A side effect of applying the necessary condition is that all2000 caseshave feasible solutions.This experiment also indicates that the CPLEX based solutions are practical for solving problems w ith up to 200 agents,or up to 400 virtualagents,w ith respect to theLsetting.

Fig.4.Time consumed by p roblem s in different scales(necessary conditionsguaranteed).

V.Feasibil ity of GMAC

Fig.5 shows the time used by 100 different cases.In the figure,we put all the problems not satisfying(9)on the left and the others on the right.Itsuggests that CPLEX dealsw ith problems evenly and reports optimal solution results regardlessof feasibility.Such a situation wastesa lot of time.

Fig.5.Distribution of time consumed for not satisfying (9)cases(left half)and the other cases (right half).

VI.Benefits of Avoiding Con f l icts

TABLE VIII The Classificat ion of Con f l icts

As for losses,we mean that both the individual qualifications w ill be decreased if conflicts between two agents or roles happen.For example,in Table II,if Chris and Doug are in mild conflict, their actual qualification values on roleCodershould be decreased to 0.90×(1–20%)=0.72,and 0.64×(1–20%)=0.512,respectively.Similarly,ifCoderandTesterare in annoying conflict,then Ed’s qualifications for these two positions w ill be reduced to 0.33×(1–40%)=0.198 and 0.78×(1–40%)= 0.468.

Suppose that Ed and Doug are also in m ild conflict,which is not the case in Section II.The GMRA assignment results in two overlapping conflicts on Ed(agent conflict w ith Doug)andCoder(role conflictw ithTester),his qualification value onCoderreduces to 0.33×(1–20%)×(1–40%)= 0.1584.

In collaboration,we do not consider conflicts worse than extreme because such roles and agents should not be included in team building.As a rule of thumb,we assume that annoying conflicts(40%qualification penalty)should be avoided. Under such conditions, both parties in the conflicting pair lose 40%of their original qualification values.In summary, the loss of an agent’s qualification for a role is determ ined by the number of assigned conflicts.This requires a new structure for collecting the number of assignment conflicts.

To understand the different effects of the conflict rates,we setpcaandpcrfrom 10%to 50%,w ith a step of 10%.To make the data convincing,we create 100 groups for each conflict rate pair.Finally,we compute the averages of the 100 numbers for each of the 25 cases.Table IX shows the simulation results.

TABLE IX Simu lat ion Averages (m= 50,n= 40, pcl =0.4)

VII.Rela ted W ork

Conflictsare common phenomena in the real-world[1],[4],[27]–[41].Conflict-related research has been undertaken for decades[2],[4],[35],[37],[39]and is attracting increased attention from engineering researchers[1],[3],[27]–[31],[33]–[36],[38],[40],[41],especially so in the area of traffic management[31]–[33],[36].However,little research on role assignment conflict exists beyond the previous work.

Bristowet al.[1] propose an agent-based framework for modeling behavior under possible agent conflicts.They suppose that agents’actions can be in conflict.By allow ing agents to view their individual situation from a system’s perspective,their framework provides rules to improve the quality of decision making.

Tessieret al.[4]review multi-agent systemsw ith probable conflicting agents.They define conflict based on propositional attributes.They also describe the categorization of human conflict handling methods.Finally,they propose a conflicthandling action model.In fact,our proposed solution is one way of conflictavoidance in theirmodel or can be considered as one instance of the“flight” method in human conflict handling.

Caietal.[27] present ameasurement for conflicts in order to implement a belief assignment.They generalize the classical pignistic probability transform as a pignistic belief transform.They also propose a betting distance of two pignistic belief transforms to evaluate the conflict degree of basic probability assignment.Their work can be used to evaluate the benefits of conflict avoidance related to this work.

Canbazet al.[28]intend to resolve design conflicts in distributed design, because a complex design requires various designers to work together at the same time but in different places.They believe that the inconsistencies of design objectivesand working proceduresare reasons to cause design conflicts, whichmay lead to imprecisemanagement.They put forward a conflictmanagementmodel and use the constraint satisfaction problem solution to detect and rectify design conflicts.

Honget al.[31]design a framework for conflict resolution in air traffic control by using air traffic complexity,which ensures conflict avoidance among airplanes.These conflicts relate to disasters thatmay lead to fatalities,an unacceptable situation.Their work providesa typicalscenario for our future work on conflict avoidance based on group role assignment.We believe that the proposed modellingmethod in this paper,i.e.,GMAC,can simplify the modeling of the problem discussed in[31], which presents over 30 constraint expressions. After the conflictmatrices are determ ined,our proposed modelling makes practitioners concentrate on more important issues.Applying GMAC to air traffic control is interesting future research work.

Jiangetal.[32]analyze the differences in conflict situation between driving cultures,and field traffic data have been collected by video recording and image processing at urban midblock crosswalks both in Beijing,China,and Munich,Germany.W ith observation,conflict analysis,and time-tocollision (TTC)calculation,they createa trajectory-based data matrix to understand the entire conflict process.They also provide an intercultural comparison of TTC distribution and relationships between TTC and other parameters.Their work can be applied to conflict analysis in sim ilar real-world scenarios.

Katrakazaset al.[33] propose a method for conflict prediction through the use of highly disaggregated vehiclebased traffic data from a traffic micro-simulation and the corresponding traffic conflicts data generated by the surrogate safety assessmentmodel.Their results show the viability of using trafficm icro-simulation along w ith the surrogate safety assessment model for real-time conflict prediction and the superiority of random forestsw ith 5-m in temporalaggregation in the classification results.

Kinsaraetal.[34]discuss systemsmethodologies tomodel third-party intervention in international conflicts w ithin the framework of the graph model for conflict resolution.They introduce an inverse graph model to utilize the graph model for conflict resolution as a negotiation tool by altering the procedure.This inversion helps decision makers understand the conflict situation,undertake certain actions w ithin the conflict,and specify preferences for a particular resolution.Such conflictsbelong to disturbing and serious categories.

Lvet al.[36]investigate vehicle-pedestrian conflicts and their relationship to traffic safety.They present amethod to generate high-resolution traffic trajectories from sensor data,then identify vehicle-pedestrian conflicts from the trajectories using a rule-basedmethod.Such conflictsmay lead to loss of life and require thorough resolution.

Nyanchama and Osborn[37]describe a role-graph model for role-based access control.In discussing the model,they clarify roles in conflict.They use thegraph model to providea taxonomy for conflict types.They solve the complex problem of role assignmentw ith potential conflicts by partitioning the role graph into role collections thatare not in conflict and can be assigned to an agent all together.

Rajanet al.[3]study the verbal conflict of humaninteraction behavior.They believe that the detection of such conflicts would enablemonitoring and feedback in a variety of applications.To address the lim itationsof traditional verbal conflict detection methods,they propose an end-to-end convolutional-recurrent neural network architecture that learns conflict-specific features directly from raw speech waveforms,w ithout using explicit domain know ledge or metadata.The conflictsmentioned in theirwork are annoying and theirwork is beneficial to some applications but their goal and research methodsare completely different from this work.

Such and Criado[38] propose a way to merge multiple users’ privacy preferencesby considering preference conflicts.Such conflicts belong to the annoying category and must be resolved when conductingmulti-party privacy management in Social Media. After such conflicts are resolved,users ofSocial Media may reach an agreement in merging privacy preferences.

TABLE X The Compar ison Among Role Assignment Problems

Yanget al.[40]discuss the onboard locally centralized conflict resolution problem of heterogeneous unmanned aerial vehicles(UAVs)w ith variable headings.Such conflictsmay damage agents(UAVs),cause loss of expensive equipment,and are considered extreme.They map the nonlinear safe separation constraint to the sine value space,and make a linear constraint of safe separation for pairw ise conflicting UAVs.Then,a mixed integer linear programm ing model is built to cope w ith the conflict resolution problem of heterogeneous UAVs to minimize the overall costs.The modeled problem is finally solved by CPLEX.

Zhanget al.[41]formalize the multi-robot task allocation w ith definite path-conflict-free handling problem based on grid maps.In their model,two subtasks of each cooperative taskmust be executed by two robots.Therefore, path conflict becomes an obstacle.They design a task allocation algorithm,which m inim izes the completion time and realizes conflictfree path planning.In the proposed method,they deal w ith both the common path conflictsand the path conflictsbetween robots when they exchange positions.

The aforementioned research indicates a strong need to fundamentally investigate GRA+including the problem discussed in thispaper.

Liuet al.[12]study a problem of GRA,called GRA w ith Balance between preferences and performance(Table X),and propose a way to balance decision-maker preferences w ith agentqualifications.Liuet al.[13]also investigate a different case of GMRA,a tree-structured task allocation problem(Table X),and propose formalizations and practical solutions based on CPLEX.They speed up the CPLEX solution and provide better planning techniques aimed at solution feasibility by introducing necessary conditions and sufficient conditions.

Dam iano-Teixeira[25]discusses the requirement of managing role conflicts for female faculties.Thomas[42]concerns role conflicts in managing different styles of educations.The contributions related role or role relation network also present an important application scope for the proposed problem and solution[43],[44].Deadlock avoidance[45],[46]in automated guided vehicle systems can also bean application of the proposed modeling.

The previous work[5],[7]–[18]established a solid foundation for conducting the investigationsof this paper.The related problems can be compared w ith each other as listed in Table X,which providesmore details about the related role assignment problems mentioned in Fig.2,wherePis anmvector to express the decision-makers’preference degrees for agents,is a promotion role matrix andis a peer role matrix.

VIII.Conc lusions

In this paper, we continue the effort to provide more accurate and efficient assignment schemes as a part of research in RBC and E-CARGO.The problem of GMAC is formalized,a solution based on CPLEX is implemented then tested and analyzed w ith regard to efficiency, planning,and benefits.Thework of this paper again confirms the discovery power of RBC,E-CARGO and GRA.

It ismeaningful to further investigate the follow ing issues:

1)Conflict expression as real numbers in a structure that conveys relative degreesof conflict damage.This can improve the assignment process.

2)Evaluation of conflicts to form more exactnumbers that reflect their degreeof severity.

3)More formalexpression of the relationships among roles and agentswhen conducting GRA.

4)Application of E-CARGO and GRA to more complicated scenarios[29],[39],[46]–[49] by introducing more formalized factors and constraints.

5)Effective algorithms for classification[50]used to solve similar problems to GMAC.

Acknow ledgment

Any opinionsand conclusions in this work are strictly those of the author(s)and do not reflect the views, positions,or policies of – and are not endorsed by – IDEaS,DND,or the Government of Canada.Thanks go to M ike Brewes of Nipissing University for his assistance in proofreading this article.

Appendix

TABLEXI Nomenc la ture

A lgorithm 1Obtain T from T′Input:(|=m),(|= n),images/BZ_46_779_2694_825_2736.png(|= m′), (|=n′),L, La, L′, La′,and T′Output:T begin T = {0};for (0≤ j

a′ = images/BZ_46_1535_260_1580_302.png[i];if (T′[i, j]== 1)if ((a′)&&(r' ))i" =a′[0];//Split the agent j" =r′[0];//Split the role T[i", j"]= 1;T′[i, j]=0; La[i"]= La[i"]–1;if (La[i"]== 0)a′–{i"};endif L[j"]= L[j"]–1;if (L[j"]==0)r′–{ j"};endif endif endif i = i+1;endwhile end for endimages/BZ_46_1606_363_1664_405.pngimages/BZ_46_1792_363_1851_405.png

?