1. Introduction
Multi-agent system is an emerging cross-disciplinary, involving robotics, artificial intelligence, mechatronics, intelligent control and etc. To improve the collaboration capabilities in unpredictable environment is an important part of the development of robotics.
Robot soccer system is a typical and challenging multi-robot system. It is an emerging field of artificial intelligence research, combining the real-time vision system, robot control, wireless communications, multi-robot control, and many other areas of technology. Robot soccer provides an ideal platform for robot collaboration research in dynamic and unpredictable environment. Assigning the appropriate role for each robot in robot soccer under the fast-changing environment is a basis issue of the real time decision-making system and the key to victory.
Role assignment in robot soccer has a direct impact on the efficiency of the entire system, and influences the ability of each robot to finish their task. At present, role assignment in robot soccer is mainly based on behavior, fuzzy consistent relation, robot learning, and evolutionary algorithm, etc. Behavior-based approach is simple, but only has a local optimal solution and is poor of robot collaboration. Fuzzy consistent relation increases the flexibility of the team, but it is difficult to build the model. Machine learning and genetic algorithm adapt to the complex dynamic environment but need training process.
This chapter presents two new algorithms based on analytic hierarchy process and market mechanism.
Analytic Hierarchy Process (AHP), a method of decision theory in operational research, is used for the role assignment. Based on mathematics and psychology, Analytic Hierarchy Process was developed by Thomas L. Saaty in the 1970s and has been extensively studied and refined since then. The AHP provides a comprehensive and rational framework for structuring a decision problem, for representing and quantifying its elements, for relating those elements to overall goals, and for evaluating alternative solutions. It is used around the world in a wide variety of decision situations, in fields such as government, business, industry, healthcare, and education.
AHP can rank choices in the order of their effectiveness in meeting conflicting objectives. Logic errors can be avoided when policy makers facing complex structure and many programs. In this chapter, in order to select a suitable robot for a certain role, the hierarchy is built, the pairwise comparison matrices are constructed with the help of experts, the weight vector and the combination weight vector are calculated, and their consistencies are measured according AHP.
Market mechanism which is introduced into traditional behavior-based allocation is also used for role assignment. Firstly the task in the method is divided into two parts, combinatorial task and single task. The former is allocated to the specified robot group by using auction method while the latter is allocated to the single robot. Then the Bipartite Graph's weight and maximum match are adopted to solve the role collisions brought by dynamic assigning.
2. Behavior-based Role Assignment
The most fundamental and simplest role assignment method is fixing the role of each robot. Fixed role method is designating a role for each robot, when designing the decision-making system. And the role of each robot will not change in a strategy. Since the role of each robot is fixed before the game beginning, the movement of each robot is coherent. But this fixed role method has an obvious shortcoming: the robot could not always do the most suitable task, and it can not change its task according the fast-changing environment. This may cause the wastage of resources and the weak control ability of the decision-making system.
Every robot has a weight of each task, and the role of the robot is assigned by the weights in behaviour-based method. According to the different weights which are different for different task, different robot, and different status of the game, the decision-making system could choose the best finisher for each task.
Behavior-based role assignment algorithm is generally divided into three steps:
Step1: For a task j, calculate the weight of each robot according some algorithm which is designed in the decision-making system.
Step2: Find out the robot which has the greatest weight.
Step3: Assigned the task j to the robot which has the greatest weight, and do not assign another task to this robot in the follow-up distribution.
Step4: Go to step1 until every task finds a robot to achieve.
The method is characterized by the simpleness of the calculation process, and it is real-time and fault-tolerance. But this method sometimes leads to inconsistent of one robot’s role. That is the role of a robot may change fast. Behavior-based approach is simple, but it only has a local optimal solution and is poor of robot collaboration.
3. Role Assignment Based on Analytic Hierarchy Process
3.1. The Algorithm of AHP
Analytic Hierarchy Process (AHP) is one of Multi Criteria decision making method, and it allows some small inconsistency in judgment because human is not always consistent. The ratio scales are derived from the principal Eigen vectors and the consistency index is derived from the principal Eigen value. AHP has been widely used in economic planning and management, energy policy, military command, transportation, education, etc. The algorithm of AHP is as follows (more details are presented in Thomas L. Saaty‘s book: The Analytic Hierarchy Process):
1. Build the hierarchy.
Develop the hierarchy by breaking the problem down into its components. The three major levels of the hierarchy are the goal, objectives, and alternatives.
2. Construct the pairwise comparison matrices.
Begin with the second layer, use pairwise comparison and 1-9 scale to construct the comparison matrices. A comparison is the numerical representation of a relationship between two elements that share a common parent. Do until the last layer.
3. Calculate the weight vector and measure the consistency.
For each pairwise comparison matrix calculate the largest eigenvalue and the corresponding eigenvector. Calculate the CI (consistency index) and CR (consistency ratio) to text the consistency of the matrices. If CR < 0.1, the test passed, and the normalized eigenvectors can be seen as the weight vectors. If adopted, the pairwise comparison matrices would be restructured.
4. Calculate the combination weight vector and measure the consistency.
Calculate the combination weight vector and test the consistency. If the test passed, the decision can be made according the outcome expressed by the combination weight vectors. Otherwise, restructure the pairwise comparison matrices whose CR are larger. AHP tells us that the plan with the largest combination weight is the most suitable for the goal.
3.2. Role Assignment
We define four roles in this chapter: attacker, winger, assistant and defender, except the goalkeeper (fixed to be robot 0).
Different stadium situations mean different role assignment strategies. The position of the ball is used to describe the stadium situation, such as attack, defence and etc. And it will influence the values of pairwise comparison matrices. The stadium is divided into 7 regions (shown in Figure 1). Roles of robots need to be assigned in every region which is shown in Figure 1.
Now we take selecting the attacker when the ball is in region 4 for example to show how to assign the roles using AHP.
3.2.1. Build the Hierarchy
There are three levels of the hierarchy: goal, objectives, and alternatives.
1. Goal
The goal of role assignment is finding a suitable robot for a certain role. Selecting the attacker when the ball is in region 4 is for example in this section. So the goal is defined to be finding the attacker, shown in Figure 2.
2. Objectives
The factors which influence the assignment are as follows:
A: the distance between the ball and the robot.
B: the pose of the robot (here, we use the angle between the ball motion direction and the robot motion direction to describe it).
C: obstacles (we define the obstacle as this: robots in a particular fan region in the robot motion direction, and the bound is also an obstacle).
D: the position of the ball.
We do not take the position of the ball as an element of the objectives (shown in Figure 2). Because the role assignment and the importance of the factors are different when the ball is in different regions, so the pairwise comparison matrices may not be the same in each region. Now we only consider the situation when the ball is in region 4.
3. Complete the hierarchy
The goal and the objectives are described upper. And the alternatives are the four robots. The hierarchy with the goal, objectives, and the alternatives is shown in Figure 2.
3.2.2. Construct the Pairwise Comparison Matrices
When comparing the impact of two different factors for an upper layer factor, which relative measure scale is good? We use the 1-9 scale for the following reasons:
Conducting qualitative comparison, people usually have 5 clear hierarchies which can be easily expressed by 1-9 scale.
Psychologists believe, too many paired comparison factors will exceed peoples’ judge ability. Using 1-9 scale to describe the difference is appropriate.
Saaty have experiment total 27 kinds of comparison scale such as 1-3, 1-5, 1-9, 1-27, etc[9]. The result showed that not only in the simple measures 1-9 scale is the best, but also as good as the complicated scales.
Currently, most people use 1-9 scale (shown in Table 1.) in their applications of AHP.
Table 1.
The fundamental scale of absolute numbers(1-9 scales).
We first construct the pairwise comparison matrix of the second layer use the 1-9 scale. This work must be done by the experts, the opinion of each expert should be considered. We invited several experts in robot soccer to attend our work and the result is shown in Table 2. For example, B is moderate importance compared with A judged by the experts, so the value of matrix element a21 is 3 and the value of a12 is 1/3.
So the pairwise comparison matrix of the second layer is as follows:
When constructing the pairwise comparison matrices of the third layer, we need to compare the importance of the same factor among the four robots. But the values of the factors are not 1-9, this chapter establish a transformation using the idea of fuzzy mathematics to transform the factor value into 1-9 scale. The transformation method is shown in Table 3.
| Grade | A (distance) | C (difference of angles) | D (the number of the obstacles) |
| 1 | "/=90 | "/=100 | "/=6 |
| 2 | 80~90 | 90~100 | |
| 3 | 70~80 | 75~90 | 4~5 |
| 4 | 60~70 | 50~75 | |
| 5 | 50~60 | 40~50 | 2~3 |
| 6 | 40~50 | 30~40 | |
| 7 | 30~40 | 20~30 | 1 |
| 8 | 20~30 | 10~20 | |
| 9 | <=20 | 0~10 | 0 |
Table 3.
Measure transformation.
We use A(k), B(k), C(k) to express the grades of robot k according the factor A, B and C. Then we get the pairwise comparison matrices: B1, B2 and B3 as follows:
3.2.3. Calculate the Weight Vectors and Measure the Consistency
First we calculate the largest eiginvalue
Then CI (Consistency index) and CR (Consistency ratio) are calculated to test the consistency. And the RI (Random consistency index) is shown in Table 4.
Table 4. Random consistency.Consistency index of matrix A:
Consistency ratio of matrix A:
Because CR< 0.1, according the theory of AHP the consistency test is passed, and
Then we continue to calculate the third layer.
Consistency index of matrix Bk:
Consistency ratio of matrix Bk:
The results of the experiments show that almost every CR can pass the test, and if there is some CR > 0.1, it will not bring very bad influence to the final role assignment. We did some experiments which we intentionally make some CR > 0.1. And the final results of the role assignment are also good judging by the experts, if we do not restructure the pairwise comparison matrices.
3.2.4 Calculate the Combination Weight Vector and Complete the Role Assignment
After the eigenvectors
The theory of AHP tells us that the k-th plan which the corresponding W(k) is the largest is the most suitable for the goal. So robot k is the most suitable to be the attacker.
Using the AHP we find out the most suitable robot for being the attacker. The same method can be used to find out the most suitable robots for being the winger, assistant, and defender. If a robot is the most suitable for two more roles, for example attacker and assistant, we will choose it to be the attacker, in accordance with the principle of good offensive.
Above, we use AHP to solve the role assignment. The hierarchy is built, the pairwise comparison matrices are constructed with the help of experts, the weight vector and the combination weight vector are calculated, and their consistencies are measured according AHP. We followed the algorithm of AHP to assign roles when the ball is in region 4. The role assignment when the ball is in the other regions (shown in Figure 1) can be completed using the same algorithm.
3.3. Experiment
The simulation is done on Robot Soccer V1.5a (it can be downloaded on http://www.fira.net/soccer/simurosot/R_Soccer_v15a_030204.exe). In order to examine the role assignment method based on AHP, this chapter designs two strategies to compete with the own strategy of the platform for 50 matches. One use the role assignment method based on AHP, and the other use the role assignment method based on behavior. Figure 3 shows the goal difference when the two strategies compete with the platform’s own strategy separately. The average goal difference of the strategy using behaviour-based role assignment algorithm is 1.28, and the average goal difference of the strategy using AHP-based role assignment algorithm is 3.06.
The results of experiments on SimuroSot 5vs5 show that the method is feasible and effective. Though there is probable that the consistency test may not be passed. Our experiments show that if we do not restructure the pairwise comparison matrices, the final results of the role assignment are also good judging by the experts.
AHP can rank choices in the order of their effectiveness in meeting conflicting objectives. Logic errors can be avoided when policy makers facing complex structure and many programs. The success of the algorithm depends on the comparison matrices which are decided by the experts. Senior experts are the keys to this algorithm.
4. The Role Assignment Based on Market Mechanism
This section focuses on the role assignment based on market mechanism. Firstly define the tasks and dynamic task allocation in robot soccer using the concept of set theory. Then the basic idea and elements of the market mechanism, the solution process of the algorithm are presented. The problem of role conflict is solved using the maximum matching algorithm of bipartite graph. Experiments on the SimuroSot (5vs5) game platform show that the method is effective and convenient.
4.1. Robot Soccer Task and Task Allocation Dynamically
Now assume a set of R consists of n robots
According to the situation of the game, this role assignment method will abstract several tasks from the formation of the team such as shooting, guarding and so on. Then using some algorithm to get a reflection f from the robots set to the tasks set (f : R→T). In some statuses, it requires several robots to finish the task cooperatively.
In Figure 4 (The white is opponent, attack from left to right), it is obviously that the effect of only one robot shooting the gate is not good, and a better way is as follow: robot 1 move along the dotted line, pass the ball to robot 3, and robot 3 shoot the gate.
This chapter use the following definition: cooperative task M (
4.2. The Basics of Role Assignment Based on Market Mechanism
4.2.1. The Cost of Task, Reward and Income
1. Cost of the task
The cost of a robot achieving a task in robot soccer is the time. In this chapter, use cost(ri, tk) to mark the cost of robot ri achieving task tk. In robot soccer games, the cost will increase with the distance from the current position of the robot to the expected position, as well as the rotation angle and the difficulty of current status transforming to expected status. So the cost can be defined as follow:
d is the distance from the current position of the robot to the expected position,θ is the rotation angle,
2. Reward
Each robot will get reward if it finished its task. Robot ri will get reward after it finishing task tk : reward(ri, tk). For offensive one, it will get more rewards if it runs toward the middle of the enemy’s gate while the defensive one will get more rewards if it intercepts the ball run toward its gate. When one robot is at mid-ground, it will get rewards from attacking and defending. The reward(ri, tk) is defined as follows:
Attack indicates the ability of attacking after a robot finished its task and defend indicates the defending one. In a real match, they can be represented by the position of robot and the velocity of the ball and so on.
3. Income
The income of one robot after it finishing its task can be defined as followed:
4.2.2. Auction and Combinational Task Auction
Market mechanism is based on auction theory. Generally, there are four types of auction: English auction, Dutch auction, sealed first-price auction, sealed-bid second-price auction. All the above auctions have the same important steps: auction announcement, bidding, contract. First the auction announcement will inform the entire bidder that what is going to be auctioned and the bidder will bid it and only one bidder will get the contact. Then the auction comes to the end.
Now the combination task auction in this chapter has the following assumption:
Auction is done by cooperative task.
Robots could be united as one union to bid one combinational task, and one robot could be in different unions.
3. Auction is done as sealed first-price auction. The bidder which gives the highest price will be the winner in the auction.
One robot union should bid according to the above rules and distribute the tasks to the robot in the union. It is allowed that the robots make a bargain with the others.
4.3. The Algorithm of Role Assignment
4.3.1. Initial Task Allocation
At the start of one match, the system should allocate the initial task to each robot. The task is divided into two layers: the first layer consists of cooperative tasks and the second layer consists of single tasks. Firstly cooperative tasks are allocated to robot unions by auction and single tasks are allocated to individual robots by behavior-based. The specific description of steps is as follow:
Step1: Generate the task set T, and divide it into several cooperative tasks M1, M2,..., Mk and assign constraint to each cooperative task.
Step2: According to the number of robots (mark with x) in the cooperative task, choose x robots in the entire robots R, which has
Step3: For cooperative task Mi, back to step 1 if there is not suitable bidder, else select the union which gives the highest price.
Step4: The union allocate the task to each robot by behavior-base method, and if there is not any task-conflict and go to step6.
Step5: Solve task-conflict.
Step6: Output the result.
4.3.2. Task Re-allocation
To avoid that the roles of robots change too frequently, the system needs to adjust each robot’s task to get a consistent result. The following are the differences from initial task allocation:
1. The addressing of allocation
The task-allocation is executed forcedly by the decision-system at the start of the match, but each robot has to calculate the income from current task periodically. Robot requests task-allocation if the income is lower than its initial value. And the decision-making system will start task-allocation when receiving enough requests.
2. Whether receive new task or not
After one robot receiving a new task, firstly it will compare the status of the old one with the income of new one. It will not receive the new task if the old one is not done and the income of the old one is larger.
4.3.3. Removal of Role-conflict
Since one robot maybe belongs to different robot unions when bidding the cooperative tasks, it may get several tasks after allocation while some robots have no tasks, which is defined as task-conflict. In Figure 5, circles represent task, squares represent robots which having been allocated task, triangles represent robots which did not allocated yet and the line is the reflection of robot to task. If all the robots in the set X and tasks in the set T are complementary subsets of bipartite graph
Step 1:
In graph G, give a real number
For any
Get the flag
And get M which is a match of
Step2:
M is the solution if M has satisfied the point in subset X, and this algorithm comes to the end. Otherwise, select one non- saturated point
Step3:
Calculate the adjacent point set
Then calculate
Step4:
In4.4 Experiment and Analysis
50 matches using the strategy which contains the role assignment method based on market mechanism against the own strategy of the platform is shown in Figure 6.The results indicates that this algorithm improve the goal rate and increases the efficiency. The average goal difference of the strategy using Market-based role assignment algorithm is 2.84.
Dividing the tasks into cooperative tasks and atom tasks, using the auction theory to allocation in cooperative task layer, improve the cooperation between robots. This model can obviously increase the rate of successful and efficient of shooting.
5. Conclusions and Future Research
Figure 7 shows the goal differences using the strategies which contain AHP-based role assignment and Market-based role assignment. The success of the AHP-based method depends on the comparison matrices which are decided by the experts. And the modelling of the Market-based method also needs the experience of the experts. Senior experts are the keys to these two algorithms. One of the future researches is using self-learning to improve these algorithms.
Robot soccer is a dynamic, uncertain, and difficult predicting system. Multi-robot role assignment has become a hot spot in the current research. Much work has been done in role assignment, many new algorithms and theories are introduced into this area. But the study of robot role assignment is still in its early stage, there is still a long way to go.