Kshitij* -The Horizon: Team Description

Abhishek Sharma, Prabodh Mairh, Ravi Kumar, Ravi Shankar, Santosh Kumar Addanki, Kamalakar Karlapalem

International Institute of Information Technology, Hyderabad 500019, India

http://www.students.iiit.net/~robosoccer

Abstract RoboSoccer is an exciting and challenging contest which offers a standardized test bed for evaluating multiagent coordination, collaborative and adversal planning strategies and efficient implementation techniques. In our team Kshitij we tried to address the complexities in robotic soccer through the use of game plans, passive agent positioning, utility based decision making, an efficient passing scheme and prioritized marking policy. This paper briefly describes the above mentioned strategies of the team.

1. Introduction

RoboSoccer is a complex and realistic domain. It embraces as many real world complexities as possible – all motions are randomized, no communication is completely reliable, no sensory information is accurate [1, 2] and the stamina of the agent is limited. In a Multi-Agent domain such as RoboSoccer [3, 4, 5] where agents need to work as a team to achieve a common goal, coordination among the agents becomes indispensable. Since communication between agents in robotic soccer domain is highly unreliable; the need to come up with alternative means of coordination becomes highly essential. Our team addresses these issues through game plans and passive agent positioning. Our team Kshitij was developed using the publicly available Uva 2003 base code. Prime concentration was laid on coordination, planning and high level skills of the agent while concentrating on only few low level skills like dribble, interception and dodge.

Below we present a brief overview of the prominent work done towards the making of Kshitij:

• Implicit coordination using game plans
• Passive agent positioning
• Utility based decision making and a strategic looking mechanism
• An efficient passing scheme
• A prioritized marking strategy
• Low level skills: Dribble, Dodge, Interception
• Heterogeneous players

• Kshitij in Sanskrit means The Horizon. The Horizon symbolizes a continual state of growth, rebirth and regeneration

2. Description of major Strategies

(Section containing subsections)

2.1 Implicit coordination using game plans

In robotic soccer domain, where independent agents need to work as a team to achieve a common goal, coordination among agents becomes indispensable. Communication being an unreliable medium, we came up with alternative ways of achieving coordination; one of them is through the use of game plans.

It is observed that in the course of the game some positional patterns recur. The idea is to identify such patterns and associate predefined strategies/actions with them. Game Plans are predefined action strategies for a given positional situation of the game. In a particular situation of the game which has a Game Plan associated with it, all the agents of the team act along the lines of the common game plan which is a predefined preferred strategy and this results in an implicit coordination.

Identification of a Game Plan is done by dividing the region into numbered grids. Each Game Plan has a set of conditions associated with it, which must be satisfied in order to apply it. Current grid pattern is matched to the conditions of the available Game Plans, if there exists a Game Plan for which the current grid pattern satisfies all the conditions, the Game Plan is loaded and the agents behave accordingly.

Below we explain a typical case in which the usage of game plans was exploited

2.2 Passive agent positioning

Active agents react to situations, while Passive agents create situations. We used a simple scheme to position the passive agents based on positional utility. Passive agents try to free themselves and move to positions where they can receive passes. The position to which an agent moves is evaluated based on the freedom of the position and the possibility of receiving a pass by being in that position and the overall advantage the team gains by the agent being in that position. While the players try to position themselves, it is taken care that players do not simply move forward to gain positional advantage. The position to which the player moves is within the restrictions of the specific type of formation that the team is following.

2.2.1 Hierarchical Agent Positioning

We used a hierarchical positioning scheme in which the agents of a team position themselves with respect to the most probable teammate from which it can receive a pass rather than the active agent.

Suppose P1 is the active agent and P2 is the passive agent capable of being passed by P1. P2 moves to a position known to both P1 and P2, If P3 is another agent near to P2, then P3 would position itself such that it is capable of receiving pass from P2.One important constraint that has to be kept in mind is that the players do not move to offside positions. In this way an efficient positioning scheme is achieved which has an implicit look-ahead mechanism.

2.3 Utility based decision making

The overall agent behavior is divided in to three modules which define the Action strategy when

• Agent itself has the Ball (Active agent)
• Teammate has the ball (Passive agent)
• Opponent has the ball.

The decision making in each of the above cases about the action to be performed is done by evaluating the usefulness of the particular action to the team as a whole. The utility of the action is calculated by using several parameters like positional gain, freedom gain, control over the ball, confidence of the world model. Below we specify the actions that were evaluated for each of the three situations.

Agent itself has the ball

Dribble: Dribble utility is calculated based on the position of ball after the dribble, and the options that the agent may have after reaching that position.

Direct pass: The utility of a Direct Pass is evaluated based on the probability of the teammate receiving the ball and other factors like the options the teammate has after receiving the pass

Forward pass: Its utility is based on the teammate's ability to reach the ball ahead of all other opponents and the advantage the team gains by the pass being successful especially in the opponent half.

Through pass: Through Pass is primarily done in the opponent penalty area and as such its utility is calculated based on the probability of teammate scoring a goal after receiving the pass.

Shooting at goal: It is evaluated based on the possibility that the goal keeper or other opponents would not intercept the ball

Dodge and Hold Ball: Utility of Hold Ball and Dodge are calculated based on the possibility of the opponent being outplayed when these actions are performed and the probability that control could be maintained over the ball.

Teammate has the Ball

Passive Agent positioning: If teammate has the ball, the passive agents close to the agent position themselves in such a way that they are able to receive a pass. The positioning takes care that they do not move very far from their strategic position nor commit any offside while trying to position themselves. While positioning themselves they follow a hierarchical positioning scheme where in they position themselves with respect to the player from whom they have higher probability of being passed

World model update: A good and accurate world model is highly essential for an agent to react properly. Also the region of interest to a particular teammate is limited and depends extensively on the type of the player and his present position in the game. We use an efficient strategic looking mechanism that defines an optimal looking direction. The optimal looking direction is calculated based on the confidence of the teammates, opponents and the ball which have a direct impact on the actions to be performed by the agent.

Opponent has the ball

Interception: Based on the position of the game the agent decides whether or not to intercept the ball. Especially while defending the goal the players do not try to intercept the ball unless they are the fastest to the ball in the entire player set, as they might get dodged.

Marking the opponent: Agents mark the opponents so that they are not able to receive a direct pass or a forward pass. Also if it is felt that the opponent player has a fair chance of scoring the goal then we try to mark the goal so as to prevent him from shooting in to the goal. Also all the opponents are not equally dangerous and as such care should be taken to mark the most dangerous ones. It is done based on the priority of the opponent. The priority of an opponent agent is calculated based on his position, distance from the ball and the goal and his freedom. Also care is taken that two players do not go and mark the same opponent while leaving another opponent unmarked.

Blocking: Some times it is not advisable to intercept the ball even when one is the fastest teammate to the ball especially while defending because the chances of getting dodged are very high .So we try to Block the movement of the opponent so as to reduce his options.

2.4 An efficient passing scheme

The agent considers three modes of passing to a teammate: Direct Pass, Forward Pass and Through Pass. The decision of the type of pass to consider is made on the basis of the utility of each of these passing schemes. The individual utilities of each of these schemes are evaluated and the one with the maximal utility is chosen.

Direct Pass: In direct pass all the agents within a threshold distance of the active agent are considered for passing. Also while giving a pass in the forward direction the farther teammates are preferred while the nearer teammates are preferred for passing in the backward direction. The Utility of passing for each of the teammates within a specified threshold is calculated based on the Positional Points of the teammate, its freedom points, the probability of the pass being successful, confidence of the player, and the options available for the teammate after receiving the pass. Pass is given to a teammate with the maximum utility.

Forward Pass: In Forward Pass the communication model is exploited and the player kicks the ball to a position in front of the teammate and the point to which the ball would be kicked is communicated to the receiver. The point to which the ball would be kicked is calculated in such a way that the receiver would be able to intercept the ball while maintaining his speed and as such increase the overall aggressiveness of the team.

Through Pass: Through Pass becomes a handy skill especially in the opponent penalty area where the ball is kicked to a point such that the receiver is the fastest to intercept the ball at that point. Here the ball is kicked in such a way that the end velocity of the ball becomes zero unlike in forward pass and hence the teammate has the option of giving an even wider pass. Also the communication between the agents is exploited to give the receiver an edge of few cycles over the opponents.

2.5 A prioritized marking strategy

In soccer, while defending against any team all the opponents are not equally dangerous. The most dangerous opponents should be marked while the rest may be ignored. In our team the opponents are prioritized based on how useful they can be to their team. The priority is given based on the distance of the opponent from the goal, freedom, its chances of receiving a pass, type of attacker and the position from which he is attacking. The opponents are marked in the decreasing order of priority, while keeping in mind that one opponent is marked by only one teammate, and the distance covered by each of the teammates is minimal.

2.6 Heterogeneous players

Our team extensively uses the concept of heterogeneous players. Wing attackers are made to have high stamina and speed. But since speed comes at the cost of stamina regain rate an efficient trade of between the two is chosen. Central attackers are made to have high dash rate, large kickable margin and very low error in kick. Midfielders are made to have high stamina and speed so here also an efficient trade off is chosen.

2.8 Low Level Skills

Apart from these we also developed some low level skills like dribble, interception and Dodge ball.

Dribble: We dynamically calculate the direction to dribble and also the length to which the ball is kicked by considering the opponents within a specific angle range (to be specified by the human expert) and distance range within which opponents are to be considered.

Interception: Initially the first point at which the ball could be intercepted is calculated .Then we check at every subsequent cycles if we are still the fastest to the ball in the whole player set. Of this whole set of points we find out a point having a maximal utility and use it as the point of interception.

Dodge ball: This skill is used to dodge an opponent by keeping the ball away from it but close to our body. The ball is kept at one side to attract the opponent and when the opponent comes close to tackle, the ball is moved to the other side and the agents proceed further.

3. Conclusion

The challenges in Robosoccer that we attempted to overcome were implicit coordination without explicit use of communication, passive agent positioning to create favorable situations, a strategic looking mechanism to have a reliable world model and the handling of heterogeneous players. Though direct communication between the agents is possible, it is highly unreliable and as such the agents cannot totally rely on interagent communication to achieve coordination and have to use other strategies for achieving the same .Though these strategies may be effective, most of them are computationally inclined. Game Plans offer an elegant and cost effective solution to achieve coordination between the agents. These are described in detail in [6].

Passive agents are rendered useless to the team by being marked. In our team Kshitij we tried to overcome such marking by positioning themselves so as to receive better passes.

A good and accurate world model is highly essential for an agent to react properly. As the view angle and quality are limited, it is not possible for the agent to have an accurate and complete view of the entire world. To overcome this problem, we developed an efficient looking mechanism that defines an optimal looking direction based on the position of the ball, position of teammates, and opponents.

We experimented the above strategies against some of the good teams participating in the robocup and the performance was reasonably good.

4. Acknowledgements

We are thankful to Mr. Ravindranath from CDE of IIIT for initially motivating us and taking all the pains to explain about the project and giving valuable advices whenever we approached him. We are extremely thankful to the University of Amsterdam Tri-Learn team members for making publicly available an excellent and well documented base code without which we could not have made the team in such a short period.

References

1. Peter Stone. Layered Learning in Multi-Agent Systems. PhD Thesis, School of Computer Science, Carnegie Mellon University, 1998
2. Peter Stone and Manuela Veloso. Task Decomposition, Dynamic Role Assignment, and Low Bandwidth Communication for RealTime Strategic Teamwork. Artificial Intelligence, 110 (2), pp.241-273, June, 1999.
3. Emiel Corten et al. Soccerserver Manual, Version 5 rev 00 beta, at URL http://www.dsv.su.se/~johank/ Robocup/ manual, July, 1999
4. Itsuki Noda. Soccer Server: A Simulator of Robocup. In Proceedings of AIsymposium '95 Japanese Society for Artificial Intelligence, pp. 2934, 1995
5. Itsuki Noda, Hitoshi Matsubara, Kazuo Hiraki, and Ian Frank. Soccer server: A Tool for Research on Multiagent Systems. Applied Artificial Intelligence, Vol.12, pp.233-250, 1998
6. Abhishek Sharma, Prabodh Mairh, Santosh Kumar Addanki, Kamalakar Karlapalem. Exploiting Game Plans for recurring positional patterns and Passive Agent positioning for Implicit Coordination (Submitted to Robocup symposium to be held at lisboa 2004)