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 comprehensive 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 positioning allowing for exible formulation of arbitrary strategies. Based on the conditions of a speci c strategy, the eld is subdivided in regions by a Voronoi tessellation and each region is assigned a weight. Those weights in uence 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.
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 eld, 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 eld, 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 eld 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 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 eld is exploited for strategy description and weight calculation for each region.
The residual paper is divided into four main parts. The next section o ers 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
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 di erences are surely re ections of the characteristics exposed by the di erent 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 e ective
and robust to noisy data. An example for such positioning can be found in
[
Potential elds are another very popular tool for positioning. A potential eld
is a function which assigns a direction to each point on the eld and is usually
formulated as the negative gradient of a scalar eld. To navigate the robot can
simply follow the direction of the eld 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 elds are prone to local minima, which is a minor issue within dynamic
situations. They can adapt very smoothly in dynamic scenarios and can be
resistant 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
BHuman in [
In their work [
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 satis ed.
In their work Kyrylov, Razykov and Hou [
Voronoi diagram and its dual Delaunay triangulation state another popular
tool used for the player positioning. Hidehisa Akiyama and Itsuki Noda [
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 de ned as the area on the eld 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 [
Colin McMillen and Manuela Veloso present in [
The Situation Based Strategic Positioning (SBSP) described by Lu s Paulo
Reis, Nuno Lau and Eugenio Costa Oliveira adapts concepts of human team
strategies implemented in the simulated domain by FC Portugal [
Based on the analysis of the related work, the most common approach to de ne a team strategy is de ned by three layers: formations assigning each player a role; roles de ning the robots positioning on the eld 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 eld, 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 elds, alignment towards the Voronoi centroids. Few approaches discretize the eld in cells and try to determine the position in a more elaborated way, e.g., path planning, Paretooptimum. 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 exible tool for the formulation of the robot positioning and simplify the upper layers de ning 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 eld
like depicted in the Fig. 1. We de ne 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
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. Aguero et al. in [
The general idea is to separate the eld in weighted regions, which are then used to determine the target region as well as the path to this region. The conditions de ning 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 containing the desired position p0 is minimal and the regions containing obstacles are assigned high weights causing the path nder to avoid them.
There are numerous possibilities to separate the eld in regions. At this point
we decided to use Voronoi tessellation, which is a very powerful and exible tool.
The tessellation is de ned by a set of points, called Voronoi sites, distributed over
the eld. Based on those points we use the Fortune's algorithm [
The whole situation map is de ned by a Voronoi tessellation and positive weights assigned to each cell. Thus, the map consist of the spatial separation of the eld in regions and a graph structure over the de ning nodes. Basically, we can consider this map as a weighted undirected graph where the weights of the nodes are given directly by the de nition and the weights for the edges are determined as a combination of the metric distance between the de ning points and the weights of the nodes. From another point of view it can be seen as a discretized scalar eld. To solve the positioning task we employ the A* algorithm to nd the shortest path. Thereby the start node is the region containing the position of the robot and the target node de ned by the minimal weight.
More precisely, the Voronoi Based Situation Map (VBSM) is de ned 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 2 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
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-o between the accuracy and the speed, the eld is discretized in two steps. At rst 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 re ned 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 eld 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.
As already described in the introductory example, the target position for the supporter is determined as the center of the rectangle, which is de ned 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 eld sides due to noisy ball perception. To avoid this problem a hysteresis is used. We utilize scalar elds 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 eld. 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 eld. For each of the objects we introduce an id I := ftarget; striker; line; goalpost; g. We assume there is a distance function d : R2 ! R+ de ned for each of the objects 2 I. The distance function d assigns to each point x 2 R2 the distance between x and the object . Except for the target position, the objects should have a limited range of in uence. To formulate this we de ne the function Q : R+ ! [0; 1] by
Q ; (t) := e 0 t , if , else > t : 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 in uence and describes the steepness of the slope of Q ; . With this function we now can de ne scalar elds U for each of the objects in I: 3.3
The graph structure of VBSM makes an e cient application of A* search possible. To de ne 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 eld, where the robot tries to get to the lowest point. With this idea the cost function c can be de ned as the Euclidean distance in three dimensions:
Utarget(p) := 1 l dtarget(p) U (p) := Q ; (d (p)) W (p) :=
X U (p) 2I where l is the length of the eld 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 de ne the weight as a sum of the scalar elds at the Voronoi site p de ning the cell: c(p; q) := 0 qx qy W (q) 1 A (1) (2) (3) (4) (5) where p; q are two nodes of the Delaunay graph and the weight W de ned in the equation 4. The heuristic for a node p can be de ned as the direct cost to the target h(p) := c(p; p0). The factor 2 R+ is used to scale the in uence of the weight on the cost function and the heuristic. The heuristic function de ned this way is consistent which makes the A* search optimal. 4
In this section we investigate some of the basic properties of the presented approach in isolated experimental setups. The experiments are performed in the simulator SimSpark. To analyze the properties of the VBSM we utilize the knowledge 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 eld 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 di erent situations. At rst we consider the situation described in our introductory example from the section 3. To brie y 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 eld; 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 eld part as shown in Fig. 2 (right). Here, the supporter has to change the side to reach its position. In both experiments the in uence 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 nal path which actually emerges through the robot following the estimated path as illustrated in the Fig. 2. The de ning conditions are re ected much better as well.
The in uence of the parameter on the nal path can clearly be seen in both situations illustrated in the Fig. 2. Figuratively spoken, the height of the mountains de ned 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 de ned by the line between the ball and the goal. While the path is slightly adjusted in the st scenario, it is changed qualitatively in the second.
The estimated path can also be seen as a plan which roughly re ects the situation on the eld. The resolution of this plan is de ned by the resolution of the VBSM. Thus, the plan is re ned as the robot moves, which corresponds to the least commitment principle. However, the resolution has to be high enough to re ect 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
We presented a new method for strategic positioning in RoboCup based on a VBSM. Thereby the eld 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 Delaunay 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 positioning. Thereby, scalar elds have been used to calculate the weights. The tessellation consists of two parts: a rough static tessellation of the whole eld 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 re nement for the direct vicinity of the robot.
This approach utilizes some well studied techniques and yields a exible and powerful method for a description of positioning strategies. From our experiments 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 ongoing 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 re nement of the tessellation seems to be a crucial aspect. Local re nement 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 de ning points would mark the center of a region representing it better. In the current implementation the tessellation is recalculated 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.