CSC/ECE 517 Fall 2014/final E1475 nrnn

E1475. Intelligent assignment of teams

This page discusses the requirements and design specifications of final project E1475. Intelligent Assignment of teams. It starts out by giving an introduction and discussing previous implementations and related work. It then details out the workflow of the proposed implementation and shows the algorithm, workflow, use case diagrams and sequence diagrams associated with it. Finally the page mentions discusses the class design and database design that would go with the implementation of the project.

Problem Statement

According to the existing code workflow, the assignment of topics to teams are based on FCFS (first come first serve) basis, where a team which first signs up for a topic gets the topic while other teams are waitlisted on the same topic. Since ‘sign up time’ is the only factor considered for topic assignment this method causes problems such as:

1. The assignment of topics are FCFS, hence not completely fair.
2. Non-uniform distribution of topics among the teams in a class.
3. The current system fails to resolve the problem when many teams bid for handful of topics(among many topics) causing unnecessary additions to the waitlist.
4. The assignment of topics is more focused on individual selection and ‘sign up time’. Factors such as team size are not considered which are important while assigning a topic to the team and potentially can reduce many issues faced by the current system.

To address the above mentioned issues, we have designed an ‘intelligent assignment of topics’ system which tries to address the issues faced by the current system.

Introduction

Introduction to Expertiza

Expertiza<ref>Expertiza</ref> is a project developed using Ruby on Rails<ref>Ruby on Rails </ref> platform. It provides features like peer review, team assignments and submission of projects. This can be achieved by submitting code base, URL of hosted code on remote server and Wiki submissions. It is an open source application and the code can be cloned from github<ref>github</ref>. This application provides an efficient way to manage assignments, grades and reviews. This makes the process easier and faster when the class strength is large.

Expertiza is supported by National Science Foundation under Grant No. 0536558. Additional funding from the NCSU Learning in a Technology-Rich Environment (LITRE)<ref>Learning in a Technology-Rich Environment (LITRE)</ref> program, the NCSU Faculty Center for Teaching and Learning, the NCSU STEM Initiative, and the Center for Advanced Computing and Communication.

Existing sign up process

The sign up process for group projects is observed by most students to be a troublesome task in expertiza. The current sign up process for topics is based on FCFS<ref>FCFS</ref> basis, where a student who signs up for a topic of his/her choice first, gets it. We have discovered some pitfalls with the current ‘topic assignment’ system in Expertiza which arises due to the below mentioned factors. Due to these reasons, we now try to propose an intelligent system which can addresses many issues faced with the current Expertiza system.

Pitfalls with the current system

1. One student can sign up only for a single topic. In cases where many topics are available, a student is forced to choose a single topic among many available topics which can be a difficult task. To select a single topic which best fits his/her choice among many available topics requires a pre-study of all topics prior to the sign up process. Such a pre-requirement is not fulfilled by most students, which results in a student signing up for a topic which he/she has randomly selected OR because it was among the only available topics.
2. If a student is not able to sign up for a topic of his choice, he can waitlist himself for all the remaining topics, which causes unnecessary traffic in the waitlist queue of a topic.
3. If all the teams choose a handful of topics among many topics, it would also result in unnecessary additions in the waitlist queue for those few topics resulting in a situation where all the topics are not uniformly distributed among all the teams
4. Before, signing up, if more than one student forms a team and if each student belonging to the same team tries to sign up for different topics, than those topics are allotted to individual students resulting in a situation where a team can hold more than one topic. Thus other teams are forced to choose from remaining topics which eventually results in longer waitlists.

After observing the above problems with the existing method of ‘topic assignment’ in expertiza, we have proposed and implemented an ‘intelligent assignment of topics’ method to overcome all the shortcomings of the existing system in expertiza.

Previous work

Previously in 2012, to address this issue of expertiza, a team proposed a possible solution of ‘lottery based topic assignment’<ref>Lottery based topic assignment</ref> algorithm. The algorithm works by considering every team as strength of 1, representing the student in the team. After sign up the topic would be allotted to the team based on a lottery system where a team is randomly selected for every topic. However this method failed to address the following issues:

1. It did not consider the case where a team could be of more than one member, hence it allowed every team member to bid for different topics resulting in the same problem as mentioned in point (4) of Pitfalls with the current system.
2. The topics were awarded randomly through an algorithm which assigns topics to teams randomly (Lottery System) and does not consider any other criteria which caused the existing system of topic assignment to be a game of luck factor rather than on individual’s choice.

Developer Note The name lottery has been retained for most of the files. This is because Intelligent Assignment could be confused with actual assignments. Intelligent Assignment and the subsequent discussion refers to the latest approach used in LotteryController for assigning topics to teams.

Requirements

1. The instructor should be able to create assignments which can utilize intelligent assignment of teams. (It is an optional feature)
2. The instructor should be able to set the maximum number of bids a team can make. Defaulted to 3.
3. The teams should be able place bids on different topics limited to the number set by the instructor for these assignments
4. The teams should be able to prioritize their bids.
5. The instructor should be able to kick off [what does that mean?] the intelligent assignment of teams.

Design Workflow

To address the issues faced by both, the current system and lottery based system, we propose a solution based on "intelligent team assignment" approach. This approach is based on two important factors:

1. Team strength
2. Priority order of the topics submitted by the team.

An added advantage of this approach is that, unlike the previous system, the intelligent team assignment system allows each team to bid for multiple topics which increases the chance of every team getting at least one topic that they placed their bid on. Each team can place their bids in priority order, the priority of the bids are also considered while assigning topics to the teams.

For example: If TeamA is up to its maximum strength and bids for Topic1,Topic2,Topic3 where Topic1 has the maximum priority then TeamA has larger chance of being assigned Topic1, but if Topic1 is already assigned (to a different team which had equal probability of getting the same topic based on team strength and bid priority) then Topic2 would be considered for assignment followed by Topic3. Thus the priority mentioned by each team is also an important factor for assigning topics to teams.

To give an example of how the system works, let's consider the following phases of topic assignment.

I. Before the sign up process:

1. Initially, every student is a team of 1 member. Before the sign up process takes place, students can merge their teams to form a larger team. The person to whom they have merged becomes the team owner/captain.
2. It is preferred that the number of members in the team should be as close as maximum strength allowed for each team to increase the chance of winning a topic

II. During the sign up process

1. Every team is allowed x bids that they can use during the sign up process to select the topics of their choice. The number of bids allowed for each team is decided by the instructor which is entered into the system during assignment creation/updation. [The value of x is decided by the instructor using class strength, number of topics created for an assignment and maximum team strength allowed for that assignment.]
2. During the sign up process, the team can place x bids on x topics of their choice in a priority order.

III. Before running "intelligent team assignment" algorithm

1. After the signup process, each team would have placed their bids on x topics.
2. Smaller teams can still merge with other smaller teams to increase their chance of winning a topic.
3. However, if TeamA merges with TeamB after the sign up process, than the topics selected by TeamB is retained and the topics of TeamA are lost after successful merge. Thus the topics of the team to which it has merged are retained while its own topics are lost due to the merge process which takes place after sign up.

IV. Running the "intelligent team assignment" algorithm

The instructor logs in to expertiza using his credentials and runs the intelligent assignment algorithm for that assignment.

V. After running the "intelligent team assignment" algorithm

1. Most of the teams would be assigned topics based on the priority submitted. If in case there are some teams which are not assigned any topic, it is probably because the strength of the team is very less as compared to maximum allowed team strength thus reducing the importance of their bids. Also, smaller team would be merged to teams which have topics allocated if the maximum team size constraint is not violated.
2. This team can then check the sign up sheet for un-allotted topics(by looking at number of available slots) and sign up for the unallotted topics.

This is the overall flow of the 'intelligent team assignment' approach

Features

1. As each team can place their bids on the available topics based on topic priority. Hence every team gets to choose more than one topic of their choice.
2. The teams are assigned topics based on modified Stable marriage problem<ref>Stable marriage problem</ref> algorithm which considers factors such as team size and priority ensuring that the topics are no longer assigned based on FCFS basis. This approach addresses the most important issue where a topic is not assigned to the team just because the team was late to sign up for the topic as compared to the other teams.

Modified version of Stable Matching Algorithm

This flow chart illustrates the "modified stable matching" algorithm used to assign topics to teams based on the strength of the teams(bidder) and the priority in which they bid for the topic.

Modified version of Stable Matching

After the above mentioned "modified stable matching" algorithm is run, there might be a case where few teams (for simplicity consider TeamA) might not get any topic due to reason that the topics that TeamA placed their bids on, had other competing team TeamB which were up to their maximum team strength (or greater than TeamA strength) and had higher priority for the same topics. Thus TeamB got the topic but TeamA didn't get it. In order to handle this edge case we, implemented the ‘auto team merge’ algorithm which is run immediately after the ‘modified stable matching’ algorithm to handle such edge cases.

This algorithm takes two parameters as input:

1. A list of teams which are un-assigned any topic
2. A hash of team and topics which were assigned

Algorithm:

1. Sort the list of teams in descending order of team size

2. For each team

a.Get the team_size and topics that the team placed their bid on

b.Arrange the topics according to the priority order mentioned by the team

i. For each of the topic, check which team is assigned this topic and store its team strength in assigned_team_size

ii. If the team which is assigned this topic is not up to maximum strength and if the (team_size + assigned_team_size<= max_strength allowed for each team) then assign this team the topic. Otherwise go to i. and repeat the process for next priority topic.

end

end

Sequence Diagram

Fig 1. Sequence Diagram

Fig 1. shows the sequence diagram for this feature. The diagram shows the sequences exclusive to this feature. Therefore, this assumes that the assignment/exercise has already been created. Once the assignment is created, the instructor can enable the 'intelligent assignment of teams' feature for the particular assignment. Enabling this feature would give the students(or teams) a view to place bids on the topics they like. They can associate each bid with a priority. Once the deadline has passed, the instructor can kickoff the process which performs the automatic assignment. This would in turn start assigning teams with topics based on their bid preferences.

Use Cases

Fig. Use Case Diagram

Use Case	Enable Intelligent Assignment
Primary Actor	Instructor
Preconditions	Instructor is logged into the Expertiza system. Instructor has created an Assignment and allotted the Assignment Topics
Postconditions	Intelligent Assignment option is enabled for the assignment. Students can place their bids for the assignment topics on commencement of the selection process
Basic Flow	The instructor selects the assignment for which the topic selection process has not yet started. The instructor checks the “Enable Intelligent Assignment” option and presses Save. The system saves the instructors choice for the assignment.

Use Case	Add bids
Primary Actor	Student (Team Leader)
Preconditions	Student is logged into expertiza system . SignUp sheet with the list of topics is available for the assignment.
Trigger	Student selects the assignment in the topic selection phase
Basic Flow	The student selects the topic of interest from the list of topics in the SignUp sheet. The student chooses the priority of the topic. The system saves the bid for the topic and the corresponding priority. The system presents the updated view with the chosen topic.
Alternate Flow	The student has already exceeded the maximum bid limit but still selects a topic. The system throws an error saying “Bid limit exceeded”

Use Case	Delete bids
Primary Actor	Student (Team Leader)
Preconditions	Student is logged into expertiza system . Student has already selected few topics for bidding.
Trigger	Student selects the assignment in the topic selection phase
Basic Flow	The student selects the topic for which the bid existed. The student clicks “Delete bid”. The system removes the bid for the topic. The system presents the updated view reflecting the changes.

Use Case	Reorder Priorities
Primary Actor	Student (Team Leader)
Preconditions	Student is logged into expertiza system . Student has already selected few topics for bidding.
Trigger	Student selects the assignment in the topic selection phase
Basic Flow	The student selects the topic for which the bid existed. The student changes the priority of the topic. The system updates the bid for the topic with corresponding priority. The system presents the updated view with reordered topics.

Use Case	Run Intelligent Assignment
Primary Actor	Instructor
Preconditions	Instructor is logged into the Expertiza system. Instructor has created an Assignment and enabled the intelligent assignment option. The due date for the topic selection has passed.
Postconditions	The topics are intelligently assigned to the teams
Basic Flow	The instructor selects the assignment for which topic selection process has completed. The instructor selects the run intelligent assignment option. The system performs intelligent assignment of topics and allots topics to teams.

Database Design

In order to meet other solution requirement, the initial plan was to add new tables. The following diagram represents the new tables in Crow Foot's Notation<ref>Crow Foot's Notation</ref>. The user table mentioned is not new and is present only to explain the field - ownerId.

Earlier, all the information in AssignmentTopic and AssignmentTopicMetadata tables were in a single table called sign_up_topics. There was lot of data redundancy observed and we also required to add an extra field in the table sign_up_topics. Therefore, we decided to store the topics related to an assignment according to the diagram. One caveat to this design is that all the topics for an assignment are considered equal in terms of category, maximum bids allowed and maximum bids in waiting list.

The table bid is supposed to store all the bids on the topics with their priority. The owner of the bid will be recorded too. Current requirement is to have only one bid per topic by an owner. Therefore, we could have (ownerId, topicId) pair as the primary key. However, in order to support multiple bids in a future scenario, we have used a field id as the primary key.

Implementation Changes: However, because of the way the current database dependencies were strongly coupled, we decided to go ahead by adding a column "Max_Team_Bids" to the Assignments table and a "priority" column to the Bids table. The above approach can be used as a reference for future developers.

Database Design

UML Design

The intelligent assignment controller is dependent on the AssignmentTopicController and other models like - Assignment, AssignmentTopic and Team. When the instructor starts the intelligent assignment of topics to teams, IntelligentAssignmentController triggers the assignment algorithm.

The students interact with AssignmentTopicView which lists down all the topics for the assignment and allows students to bid for topics with priority. AssignmentTopicController is responsible for recording all the bids and priorities correctly.

Following is the UML diagram of the O-O design focusing only on the component related to intelligent assignment of topics to teams.

Implementation Changes We have avoided separating out AssignmentTopicMetadata from Assignment as this would have caused a lot of dependency conflicts.

UML Design

Design Patterns

The following principles and patterns are used:

1. DRY: Using DRY coding practices. The earlier code had a lot of redundant functions such as getTeamsFromId which was violating the DRY principle. We have used the methods provided by the ActiveRecord class making the code structure and easy to understand.
2. MVC Use of the Model View Controller for maintaining the Intelligent Assignment flow.
3. Separation of concerns: The IntelligentAssignmentTopicController is separated from AssignmentTopicController as the former's functionality is specific and hence should not be part of the general AssignmentTopic Controller.

Troubleshooting

During our development process, we stumbled upon certain bugs in certain areas which slowed down our process. This is brief summary of those issues and their corresponding fixes. These changes are not the right resolution, however, we have listed it here so that future developers could benefit from these.

• Error thrown while adding assignments/teams/teamusers

The model nodes has a method acts_as_nested_sets which causes this issue.

• Error thrown while loading the sign_up_sheet_controller

Comment this line "require 'graph/graphviz_dot'"

• Missing rgt or lft column in nodes table

Probably because the db migration AddCategories has not been run. The code in that is commented. Uncomment that and run the migration.

References

<references/>