Voronoi Based Strategic Positioning for Robot Soccer S. Kaden, H. Mellmann, M. Scheunemann, and H.-D. Burkhard Department of Computer Science, Cognitive Robotics Group Humboldt-Universität zu Berlin, Germany {kaden,mellmann,scheunem,hdb}@informatik.hu-berlin.de Abstract. Strategic positioning is a decisive part of the team play within a soccer game. In most solutions the positioning techniques are treated as a constituent of a complete team play strategy. In a com- prehensive overview we discuss the team play and positioning methods used within RoboCup and extract the essential requirements for player positioning. In this work, we propose an approach for strategic position- ing allowing for flexible formulation of arbitrary strategies. Based on the conditions of a specific strategy, the field is subdivided in regions by a Voronoi tessellation and each region is assigned a weight. Those weights influence the calculation of the optimal robot position as well as the path. A team play strategy can be expressed by the choice of the tessellation as well as the choice of the weights. This provides a powerful abstraction layer simplifying the design of the actual play strategy. We also present an implementation of an example strategy based on this approach and analyze the performance of our approach in simulation. 1 Introduction With the advancement of RoboCup, team play turns into a key feature of success. While in simulation leagues a strong team play is a decisive aspect since the very beginning, in hardware leagues more basic aspects like motion, perception and modeling usually yield more overall improvement. A central part of team play is the strategic positioning of players on the field, i.e., the placement of robots not in possession of the ball. Hereby, two core issues have to be addressed: where does the player have to go to and how does he get there. The answer, depends among others on numerous factors, involving player positions on the field, ball position, distribution of team-mates and opponent players and so on. In this paper we present an approach which allows to formulate all the aspects necessary for the positioning and mechanisms to derive the target position and the path to it. To achieve that, the whole field is separated into weighted regions. To obtain a practical separation, Voronoi tessellation is employed due to its convex structure and embedded neighboring relation. Each region is evaluated according to some criteria. The weights encode a variety of aspects, e.g. obstacles, free space, the probability that the ball is contained or the dominant regions of players. Based 272 S. Kaden, H. Mellmann, M. Scheunemann, and H.-D. Burkhard on those weights, an optimal region can be determined, as well as a feasible path to this region. For illustration and testing purposes we utilize a supporter example strategy to prove the functionality of our approach. Beside a simple heuristic strategy for positioning, a scalar field is exploited for strategy description and weight calculation for each region. The residual paper is divided into four main parts. The next section offers a comprehensive overview of strategic positioning approaches proposed within the RoboCup. The description of the VBSM algorithm is given in section 3. In section 4 we discuss the experiments and their results. At the end we present a conclusion and provide an outlook for future work. 2 Related Work The problem of the strategic positioning within the RoboCup context has been widely investigated in the past years. The ideas vary a lot and there seems to be no standard approach. Some major differences are surely reflections of the characteristics exposed by the different leagues. In general, the solutions within the simulation leagues are more elaborated, assume a much more rich and reliable world model and are more computationally complex in comparison to the solutions of the hardware leagues. In most cases the positioning issue is not solved separately, it is mostly part of an entire team play solution. In the following overview our main focus is rather on the positioning ideas than on the high-level parts necessary to organize a team like role assignment. One of the most direct ways to position a robot is to calculate its target position as a geometric relation to its world model, which results in a reactive behavior. Although very simple, those techniques proved to be quite effective and robust to noisy data. An example for such positioning can be found in [1] by Carlos E. Agüero et al. which targeted the issue of role switching and role positions within the Four Legged League (4LL). Here the defender should occupy a point on the line between the goal and the ball to prevent the opponent attacker most effectively from scoring a goal. A supporter chooses the center of the rectangle stretched by the ball and the most distant opponent corner. Another example from 4LL is given by Phillips and Veloso, in [15]. They present reactive supporter strategies. Here the field is subdivided in rough fixed regions, such like offensive, defensive etc., which allows to choose different strategies depending on which region the ball is in. For instance, when the ball is in the offense region, the supporter covers a point left or right in a fixed distance beside the ball. Is the ball situated in the defense region, it is followed by the supporter in one axis which stays in the offense region. In addition, the supporter chooses a corner of the opponent penalty area if the ball is close to the opponent goal to catch the ball if it rebounds. In the Humanoid League (HL), K. Petersen, G. Stoll and O. von Stryk [14] developed another reactive behavior for a supporter. Similar to the previous approach, the supporter chooses a position relative to the ball. Thereby the relation may be adjusted depending on the game situation. Voronoi Strategic Positioning 273 Potential fields are another very popular tool for positioning. A potential field is a function which assigns a direction to each point on the field and is usually formulated as the negative gradient of a scalar field. To navigate the robot can simply follow the direction of the field at its current position. This approach may represent the world state, e.g., obstacles are represented as maxima (repeller ), as well as strategy, e.g., the target position is formulated as a minimum (attractor ). Potential fields are prone to local minima, which is a minor issue within dynamic situations. They can adapt very smoothly in dynamic scenarios and can be re- sistant to noise. These properties make them a very tempting tool for dynamic planning scenarios with noisy data. A good example is presented by the team B- Human in [17](SPL). Here, the team play is organized in three fixed formations which are activated based on the state of the game, e.g., goal score. A formation defines a role for each player. A specific role defines the actual player position on the field, e.g., the target supporter position is calculated based on the position of the ball and the striker. This target position as well as the current game sit- uation is formulated by a potential field, which is used for navigation. Thereby, the target position is formulated as an attractor whereas the other players, the own penalty area as well as the line between the ball and the opponent goal are formulated as repellers. This way the robot avoids obstacles and forbidden areas on its way to the target position. A very similar approach is presented by Work, Chown, Hermans, Butterfield and McGranaghan in [18](4LL). The formations are additionally organized in strategies and each role splits in a number of sub roles. A sub role is activated depending on the ball position on the field and defines the target position of the player. The positioning itself is also based on the potential fields and is formulated in a similar way to the Team B-Human approach. In their work [13] (SPL) Nieuwenhuisen, Steffens, and Behnke consider the positioning of a robot as a path planning problem. Hereby, the task of approach- ing the ball while avoiding obstacles is directly addressed. A multi resolution occupancy grid in egocentric Cartesian and Log-Polar coordinates is used to model the obstacles. The resolution of the grid is higher in the proximity of the robot and the path is determined by the A* search. B-Human use in [17](SPL) an extended bidirectional Rapidly-Exploring Random Tree to estimate the path to the ball, which doesn’t require discretization of the space. Another way is to formulate the positioning task as an optimization problem where the world state and the strategy are encoded as conditions to be satisfied. In their work Kyrylov, Razykov and Hou [7,8](S2D) subdivide the field in a grid. Each cell is then rated according to certain criteria. For instance, the player should be open for a direct pass, the distance to opponent players should be maximized and the distance to the reference position defined by the strategy should be minimal. These criteria, e.g., the reference position, are defined by the formation and the roles of the players. The target position is then determined as a Pareto-Optimum based on those criteria. Both publications deal with different scenarios (offensive, defensive) and discuss different criteria for the optimization. 274 S. Kaden, H. Mellmann, M. Scheunemann, and H.-D. Burkhard Voronoi diagram and its dual Delaunay triangulation state another popular tool used for the player positioning. Hidehisa Akiyama and Itsuki Noda [2](S2D) use in their work a Delaunay triangulation of the field to encode the positioning of the robots depending on the ball position. To construct such triangulation, a representative set of possible ball positions and the corresponding positions of the players are predefined. Those ball positions define the nodes of the tri- angulation. During the game the actual positions of the players are determined as an interpolation between the positions provided by the nodes of the triangle in which the ball is located. Another way to use Voronoi diagrams for position- ing is presented by Hesam Addin Dashti et al. in [4](S2D). Thereby, the actual positions of the robots define the Voronoi cells, i.e., are the Voronoi sites. The repulsing and attracting properties of the objects on the playing field, e.g., ball, opponents, goal, etc., are modeled as forces which affect the agent and are rep- resented by vectors. The vector to the center of gravity of the agent’s Voronoi cell provides an additional alignment vector. Thus the player try to relax the Voronoi diagram and to keep as much distance between each other as possible, which results in a good field coverage. In [3](S2D) the technique is extended by including the opponent players as additional cells into the diagram. Considering the time which is needed to reach a point instead of the Euclidean distance to it provides another kind of regions which are called dominant regions (DR). Figuratively speaking, a DR is defined as the area on the field which can be reached by a particular player before the others. In general, calculation of dominant regions requires a good motion model of the players which may be especially a problem for opponent robots. In [12](SSL) Nakanishi, Murakami and Naruse introduce the notion of a dominant polygon which essentially is an approximation of the area which can be reached by the robot within a fixed given time limit. Thereby a quadratic motion model for the players is used. Those polygons are used on one hand to estimate the dominant regions for all the player on the field and on the other hand to determine a good position for a pass. To achieve a good passing position the robot essentially tries to leave the dominant polygons of the opponents which may interfere. Another example is presented in [11](SSL) by Nakanishi, Bruce, Murakami, Naruse and Veloso where the dominant regions are used to plan pass combination. E.g., if a pass would lead through an opponent region, a third player is moved in between to close the gap and the pass is performed indirectly (1-2-3 shoot). The border between the dominant regions of a pair of robots is calculated analytically assuming a simple quadratic motion model . Calculating those borders pairwise for all the players on the field leads to a full DR-diagram. Colin McMillen and Manuela Veloso present in [10] (4LL) a different approach based on plans. A Play is a plan which assigns roles for each of the players. A role consists of a predefined responsibility region and a behavior strategy for each of the three cases: the ball is outside or inside of the region, or the ball is not seen. A particular play is applied when the game situation satisfies some predefined requirements. When several plays are applicable, the one with the higher weight is selected. The corresponding requirements are based on the game state like Voronoi Strategic Positioning 275 remaining game time, count of players and the actual score. Another scenario based approach is Scenario-Based Team working (SBT) [16] (S2D) by Ali Ajdari Rad, Navid Qaragozlou and Maryam Zaheri. A scenario contains a sequence of sub-plans consisting of actions for each robot. Furthermore, it is equipped with a goal, e.g., shooting a goal or conquer the ball, triggering conditions, expected costs etc.. During the execution each agent tries to satisfy its iterative sub-plan, which defines the agent’s actions. To position the players the field is subdivided in regions. The scenarios are structured in a directed graph, where the nodes are particular scenarios and edges are weighted with a probability for the next scenario to be executed. This graph is created before the game by connecting the scenarios depending on their goals and triggers. The weights of the edges are adjusted during the game depending on the success of a scenario. The Situation Based Strategic Positioning (SBSP) described by Luı́s Paulo Reis, Nuno Lau and Eugénio Costa Oliveira adapts concepts of human team strategies implemented in the simulated domain by FC Portugal [6] and partly used by the team CAMBADA within the Middle Size League (MSL) [9]. The team strategy in SBSP consists mainly of a set of tactics, tactic activation rules and roles. A tactic itself consists of predefined plans and team formations. The formations describe the positioning of a player inside a formation. The position- ing consists of a reference position, a predefined fixed region, as well as behavior for the cases when the ball is inside or outside of this region. To position the robot the reference position is adjusted with respect to the ball. 3 Voronoi Based Situation Map Based on the analysis of the related work, the most common approach to define a team strategy is defined by three layers: formations assigning each player a role; roles defining the robots positioning on the field and its behavior; and at last the positioning method which determines the actual movements of the robot. In most cases, the positioning itself (the lowest layer) is implemented directly as a kind of a geometric relation to dynamic and static objects on the field, e.g., relative to the ball, a free position based on DR etc; or is formulated as forces applied to alter the position, e.g., potential fields, alignment towards the Voronoi centroids. Few approaches discretize the field in cells and try to determine the position in a more elaborated way, e.g., path planning, Pareto- optimum. In general, a simple positioning layer leads to more complexity in the higher layers to generate sophisticated behavior. The following approach strives to provide a generalized and flexible tool for the formulation of the robot positioning and simplify the upper layers defining the overall strategy. To make our idea more clear we introduce a simple example. Imagine a situation with two robots and the ball placed in the opponent part of the field like depicted in the Fig. 1. We define the one closer to the ball to be the striker and the other one the supporter. Note, the robots will never change their roles in our examples as we are focusing only on the positioning problem itself. In this example neither the striker nor the ball moves. The only acting part is the 276 S. Kaden, H. Mellmann, M. Scheunemann, and H.-D. Burkhard Fig. 1. An example situation: (left) initial positions of the supporter (center) and the attacker (closer to the ball); the center (black diamond) of the red dashed rectangle illustrates the target position for the supporter; the scalar field encoding the strategy is depicted by the intensity of the yellow glow (the global minimum is at the diamond); (right) the Voronoi tessellation with the weights of the regions depicted by the intensity of the yellow color; path calculated by the A*. supporter. We consider the situation from the point of view of the supporter. Its only task is to move to a position where it could receive a pass or take over the ball in case the striker loses it. For that we assume a simple heuristic strategy for the supporter which is inspired by Carlos E. Agüero et al. in [1]: thereby the supporter’s desired position p0 is defined as the center of the rectangle spanned by the ball and the opposite opponent corner of the field as depicted in the Fig. 1. Now the task is to formulate the problem of the supporter getting to the point p0 while avoiding collisions with other objects like the striker or the goal posts. Of course one could immediately imagine a simple positioning solution for this case. But the aim of the presented approach is to provide a general solution for a wide range of positioning problems. This example is just fine to illustrate the concept and to explore its basic principles. 3.1 General Idea The general idea is to separate the field in weighted regions, which are then used to determine the target region as well as the path to this region. The conditions defining the desired position and the path can be formulated in terms of the separation in regions and the choice of weights. With this approach our example strategy could be formulated in a way where the weight of the region Voronoi Strategic Positioning 277 containing the desired position p0 is minimal and the regions containing obstacles are assigned high weights causing the path finder to avoid them. There are numerous possibilities to separate the field in regions. At this point we decided to use Voronoi tessellation, which is a very powerful and flexible tool. The tessellation is defined by a set of points, called Voronoi sites, distributed over the field. Based on those points we use the Fortune’s algorithm [5] to calculate the tessellation. Apart from a set of regions we also get a graph, called Delaunay graph, which is defined by the cells as nodes and the neighborhood as edges. This graph gives us a possibility for efficient search within the tessellation. With this we can easily construct very complex tessellations based on the conditions given by our strategy. The whole situation map is defined by a Voronoi tessellation and positive weights assigned to each cell. Thus, the map consist of the spatial separation of the field in regions and a graph structure over the defining nodes. Basically, we can consider this map as a weighted undirected graph where the weights of the nodes are given directly by the definition and the weights for the edges are determined as a combination of the metric distance between the defining points and the weights of the nodes. From another point of view it can be seen as a discretized scalar field. To solve the positioning task we employ the A* algorithm to find the shortest path. Thereby the start node is the region containing the position of the robot and the target node defined by the minimal weight. More precisely, the Voronoi Based Situation Map (VBSM) is defined by (G, W ) where G := (V, E) is the Delaunay graph of the Voronoi sites V ⊂ R2 . The function W : V → R assigns a weight w ∈ R+ to each node of the graph G. Note, each node represents a Voronoi cell and therefore the weights are assigned to each of the Voronoi cells. 3.2 Tessellation of the Field To achieve a desired tessellation we have to choose the points (the Voronoi sites) appropriately. The resolution of the tessellation, i.e., number of points, has a major impact on the computational cost of the tessellation, the weights as well as the search. To resolve the trade-off between the accuracy and the speed, the field is discretized in two steps. At first points are chosen in a way that their Voronoi cells result in hexagons. These points are used to get a rough base resolution. In the second step the tessellation is refined around the position of the player, e.g., supporter. For that the position itself is added as a Voronoi site as well as 16 Voronoi sites around it, which are equidistant distributed on a circle. As the result, the scalar field will have a higher resolution around the player’s position. Thus, the determined path will be more precise in the proximity of the player. Note that the geometry of the tessellation changes over time depending on the position of the player. The path calculated in one frame gives only a rough direction for the movement. The resulting path which emerges through the robot following the given directions will be much smoother as the higher resolution around the robot moves with it. The Fig. 1 (right) illustrates the resulting tessellation. 278 S. Kaden, H. Mellmann, M. Scheunemann, and H.-D. Burkhard 3.3 Positioning Strategy As already described in the introductory example, the target position for the supporter is determined as the center of the rectangle, which is defined by the ball’s position and the outer opponent corner (from ball’s point of view). If the ball is close to the longitudinal axis of symmetry the determined position of the supporter might change the field sides due to noisy ball perception. To avoid this problem a hysteresis is used. We utilize scalar fields to formulate this strategy and to express it in terms of weights of the VBSM. Thereby, the target position is modeled as global minima of a scalar field. The striker, goal posts as well as the line between ball and opponent goal should be avoided and therefore are modeled as maxima of the scalar field. For each of the objects we introduce an id I := {target, striker, line, goalpost, · · · }. We assume there is a distance function dι : R2 → R+ defined for each of the objects ι ∈ I. The distance function dι assigns to each point x ∈ R2 the distance between x and the object ι. Except for the target position, the objects should have a limited range of influence. To formulate this we define the function Q : R+ → [0, 1] by  α− α e β β−t , if β > t Qα,β (t) := . (1) 0 , else The function Qα,β has a compact support which is bounded by the parameter β and has its maximum equal 1 in t = 0. The parameter β describes the radius of the influence and α describes the steepness of the slope of Qα,β . With this function we now can define scalar fields Uι for each of the objects in I: 1 Utarget (p) := · dtarget (p) (2) l Uι (p) := Qαι ,βι (dι (p)) (3) where l is the length of the field diagonal. To model the striker and the line between the ball and the opponent goal we have used in our experiments the values αstriker := αline := 800, βline := βstriker := 1000 and for the goalposts we have used αgoalpost := 800, βgoalpost := 500. For each Voronoi cell we define the weight as a sum of the scalar fields at the Voronoi site p defining the cell: X W (p) := Uι (p) (4) ι∈I 3.4 Path Finding with A* The graph structure of VBSM makes an efficient application of A* search pos- sible. To define the cost function and the heuristic for the search, the weights of the nodes can be seen as height information. Figuratively, they shape a kind of mountains over the field, where the robot tries to get to the lowest point. With this idea the cost function c can be defined as the Euclidean distance in three dimensions:     px qx c(p, q) :=  py  −  qy  (5) α · W (p) α · W (q) 2 Voronoi Strategic Positioning 279 where p, q are two nodes of the Delaunay graph and the weight W defined in the equation 4. The heuristic for a node p can be defined as the direct cost to the target h(p) := c(p, p0 ). The factor α ∈ R+ is used to scale the influence of the weight on the cost function and the heuristic. The heuristic function defined this way is consistent which makes the A* search optimal. 4 Experimental Analysis In this section we investigate some of the basic properties of the presented ap- proach in isolated experimental setups. The experiments are performed in the simulator SimSpark. To analyze the properties of the VBSM we utilize the knowl- edge of the precise positions of the objects within the simulation. Thus, we can assume there is no sensory noise. In particular this allows to observe the actual path or the robot movement. The trajectory of the center of mass is projected onto the playing field as walked path. The following experiments illustrate the VBSM in an example scenario of supporter positioning. It means, the situation is visualized from its point of view. In particular we consider two different situations. At first we consider the situation described in our introductory example from the section 3. To briefly recall: the ball is placed in the opponent half; a robot (striker ) is placed next to the ball, while the supporter is placed in the center of the field; the only active party is the supporter: its task is to get to its strategic target position as depicted in Fig. 2. In the second situation the striker and the ball are located in the upper opponent field part as shown in Fig. 2 (right). Here, the supporter has to change the side to reach its position. In both experiments the influence of the cell weights on the search costs is varied by changing the parameter α in the cost- and heuristic function 5. Due to the rough overall resolution of the tessellation, the estimated path calculated in one frame approximates the ideal path only roughly. However, as already mentioned, the geometry of the tessellation changes over time depending on the position of the player, which leads to a smooth final path which actually emerges through the robot following the estimated path as illustrated in the Fig. 2. The defining conditions are reflected much better as well. The influence of the parameter α on the final path can clearly be seen in both situations illustrated in the Fig. 2. Figuratively spoken, the height of the mountains defined by the cell weights is scaled by α, which changes the relation between the cost of the actual distance and the costs produced by the weights. Thus, with a small α the way around an obstacle seems to be longer than the way through it and vice versa in the case of a large α. In the Fig. 2 (left) the path is closer to the obstacle for a smaller and farther for a larger α. In the Fig. 2 (right) a too small α causes the robot to ignore the virtual obstacle defined by the line between the ball and the goal. While the path is slightly adjusted in the fist scenario, it is changed qualitatively in the second. The estimated path can also be seen as a plan which roughly reflects the situation on the field. The resolution of this plan is defined by the resolution of 280 S. Kaden, H. Mellmann, M. Scheunemann, and H.-D. Burkhard Fig. 2. Walk path of the robot in two different scenarios with different influence α of the cell weights in the search cost: from thin to thick the paths correspond to α = 600, 1000, 3000; (left) the supporter walks to its position; (right) the supporter changes the side with parameters α = 600 and α = 3100; the VBSM. Thus, the plan is refined as the robot moves, which corresponds to the least commitment principle. However, the resolution has to be high enough to reflect crucial qualitative aspects of the situation. For instance, in the case of too rough resolution some maxima might disappear between the cells in analogy to the Nyquist–Shannon sampling theorem. 5 Conclusion and Future Work We presented a new method for strategic positioning in RoboCup based on a VBSM. Thereby the field is subdivided in regions by a Voronoi tessellation and each region is assigned a weight. The region with a minimal weight is chosen as the target region. The path to the target is estimated with A* on the De- launay graph which is dual to the tessellation. Whereby, the distance between the nodes as well as the assigned weights are represented by a cost function and heuristics. A positioning strategy can be expressed in VBSM by the choice of the tessellation, i.e., the Voronoi points, and the weights of the regions. An example implementation was illustrated in a scenario of supporter po- sitioning. Thereby, scalar fields have been used to calculate the weights. The tessellation consists of two parts: a rough static tessellation of the whole field and higher resolution around the robots position. This implementation has been tested in simulation. It has been shown to produce a smooth resulting path in static situations despite a rough discretization, which is mainly due to the dynamic tessellation refinement for the direct vicinity of the robot. Voronoi Strategic Positioning 281 This approach utilizes some well studied techniques and yields a flexible and powerful method for a description of positioning strategies. From our ex- periments the VBSM reveals a lot of capabilities and seems to be a promising approach for further development. So far only static scenarios have been considered. The main focus of the ongo- ing research, is on investigating how more complex strategies can be formulated with VBSM as well as its behavior in dynamic situations. Further studies also need to investigate the choice of the tessellation as well as the way to assign the weights. In particular, the refinement of the tessellation seems to be a crucial aspect. Local refinement depending on the weights or along the estimated path could lead to better representation of conditions encoded in the weights. Also relaxing to a centroidal Voronoi tessellation could lead to a higher expressive power of the weights as the defining points would mark the center of a region representing it better. In the current implementation the tessellation is recalcu- lated in every step, adaptive algorithms could reduce the computational costs by adjusting the old tessellation rather than calculating a new one. Similar to the tessellation, the weights could be propagated between the frames. This would provide a possibility for modeling some time dependent properties directly in the VBSM. For instance, the dominant regions could be estimated by propagation of the weights representing an opponent between the cells based on its motion model. Another idea is to lower the weights along the estimated path, which would result in a kind of memory for the path and prevent oscillations. References 1. Agüero, C.E., Matellán, V., Caˆnas, J.M., Gómez, V.M., Carlos, J.: Switch! dy- namic roles exchange among cooperative robots. In: in Proceedings of the 2nd In- ternational Workshop on Multi-Agent Robotic Systems - MARS 2006. INSTICC. pp. 99–105. Press (2006) 2. Akiyama, H., Noda, I.: Multi-agent positioning mechanism in the dynamic envi- ronment. In: Visser, U., Ribeiro, F., Ohashi, T., Dellaert, F. (eds.) RoboCup 2007: Robot Soccer World Cup XI, Lecture Notes in Computer Science, vol. 5001, pp. 377–384. Springer Berlin / Heidelberg (2008) 3. Dashti, H.T., Kamali, S., Aghaeepour, N.: Positioning in robots soccer. In: Lima, P. (ed.) Robotic Soccer, pp. 29–44. I-Tech Education and Publishing (2007) 4. Dashti, H., Aghaeepour, N., Asadi, S., Bastani, M., Delafkar, Z., Disfani, F., Ghaderi, S., Kamali, S., Pashami, S., Siahpirani, A.: Dynamic positioning based on voronoi cells (dpvc). In: Bredenfeld, A., Jacoff, A., Noda, I., Takahashi, Y. (eds.) RoboCup 2005: Robot Soccer World Cup IX, Lecture Notes in Computer Science, vol. 4020, pp. 219–229. Springer Berlin / Heidelberg (2006) 5. Fortune, S.: A sweepline algorithm for voronoi diagrams. Algorithmica 2, 153–174 (1987) 6. Hannebauer, M., Wendler, J., Pagello, E., Reis, L., Lau, N., Oliveira, E.: Situation based strategic positioning for coordinating a team of homogeneous agents. In: Balancing Reactivity and Social Deliberation in Multi-Agent Systems, Lecture Notes in Computer Science, vol. 2103, pp. 175–197. Springer Berlin / Heidelberg (2001) 282 S. Kaden, H. Mellmann, M. Scheunemann, and H.-D. Burkhard 7. Kyrylov, V., Hou, E.: Pareto-optimal collaborative defensive player positioning in simulated soccer. In: Baltes, J., Lagoudakis, M., Naruse, T., Ghidary, S. (eds.) RoboCup 2009: Robot Soccer World Cup XIII, Lecture Notes in Computer Science, vol. 5949, pp. 179–191. Springer Berlin / Heidelberg (2010) 8. Kyrylov, V., Razykov, S.: Pareto-optimal offensive player positioning in simulated soccer. In: Visser, U., Ribeiro, F., Ohashi, T., Dellaert, F. (eds.) RoboCup 2007: Robot Soccer World Cup XI, Lecture Notes in Computer Science, vol. 5001, pp. 228–237. Springer Berlin / Heidelberg (2008) 9. Lau, N., Seabra Lopes, L., Filipe, N., Corrente, G.: Roles, positionings and set plays to coordinate a robocup msl team. In: Lopes, L., Lau, N., Mariano, P., Rocha, L. (eds.) Progress in Artificial Intelligence, Lecture Notes in Computer Science, vol. 5816, pp. 323–337. Springer Berlin / Heidelberg (2009) 10. McMillen, C., Veloso, M.: Distributed, play-based coordination for robot teams in dynamic environments. In: Lakemeyer, G., Sklar, E., Sorrenti, D., Takahashi, T. (eds.) RoboCup 2006: Robot Soccer World Cup X, Lecture Notes in Computer Science, vol. 4434, pp. 483–490. Springer Berlin / Heidelberg (2007) 11. Nakanishi, R., Bruce, J., Murakami, K., Naruse, T., Veloso, M.: Cooperative 3- robot passing and shooting in the robocup small size league. In: Lakemeyer, G., Sklar, E., Sorrenti, D., Takahashi, T. (eds.) RoboCup 2006: Robot Soccer World Cup X, Lecture Notes in Computer Science, vol. 4434, pp. 418–425. Springer Berlin / Heidelberg (2007) 12. Nakanishi, R., Murakami, K., Naruse, T.: Dynamic positioning method based on dominant region diagram to realize successful cooperative play. In: Visser, U., Ribeiro, F., Ohashi, T., Dellaert, F. (eds.) RoboCup 2007: Robot Soccer World Cup XI, Lecture Notes in Computer Science, vol. 5001, pp. 488–495. Springer Berlin / Heidelberg (2008) 13. Nieuwenhuisen, M., Steffens, R., Behnke, S.: Local multiresolution path planning in soccer games based on projected intentions. In: Röfer, T., Mayer, N., Savage, J., Saranlı, U. (eds.) RoboCup 2011: Robot Soccer World Cup XV, Lecture Notes in Computer Science, vol. 7416, pp. 495–506. Springer Berlin Heidelberg (2012) 14. Petersen, K., Stoll, G., von Stryk, O.: A supporter behavior for soccer playing humanoid robots. In: Ruiz-del Solar, J., Chown, E., Plöger, P. (eds.) RoboCup 2010: Robot Soccer World Cup XIV, Lecture Notes in Computer Science, vol. 6556, pp. 386–396. Springer Berlin / Heidelberg (2011) 15. Phillips, M., Veloso, M.: Robust supporting role in coordinated two-robot soccer attack. In: Iocchi, L., Matsubara, H., Weitzenfeld, A., Zhou, C. (eds.) RoboCup 2008: Robot Soccer World Cup XII, Lecture Notes in Computer Science, vol. 5399, pp. 235–246. Springer Berlin / Heidelberg (2009) 16. Rad, A., Qaragozlou, N., Zaheri, M.: Scenario-based teamworking, how to learn, create, and teach complex plans? In: Polani, D., Browning, B., Bonarini, A., Yoshida, K. (eds.) RoboCup 2003: Robot Soccer World Cup VII, Lecture Notes in Computer Science, vol. 3020, pp. 137–144. Springer Berlin / Heidelberg (2004) 17. Röfer, T., Laue, T., Müller, J., Fabisch, A., Feldpausch, F., Gillmann, K., Graf, C., de Haas, T.J., Härtl, A., Humann, A., Honsel, D., Kastner, P., Kastner, T., Könemann, C., Markowsky, B., Riemann, O.J.L., Wenk, F.: B-human team report and code release 2011. Tech. rep. (2011) 18. Work, H., Chown, E., Hermans, T., Butterfield, J., McGranaghan, M.: Player po- sitioning in the four-legged league. In: Iocchi, L., Matsubara, H., Weitzenfeld, A., Zhou, C. (eds.) RoboCup 2008: Robot Soccer World Cup XII, Lecture Notes in Computer Science, vol. 5399, pp. 391–402. Springer Berlin / Heidelberg (2009)