RoboCup represents an International testbed for advancing research in AI and robotics, focusing on a definite goal: developing a robot team that can win against the human world soccer champion team by the year 2050. To achieve this goal, autonomous humanoid robots' coordination is crucial. This paper explores novel solutions within the RoboCup Standard Platform League (SPL), where a reduction in WiFi communication is imperative, leading to the development of new coordination paradigms. The SPL has experienced a substantial decrease in network packet rate, compelling the need for advanced coordination architectures to maintain optimal team functionality in dynamic environments. Inspired by market-based task assignment, we introduce a novel distributed coordination system to orchestrate autonomous robots' actions eficiently in low communication scenarios. This approach has been tested with NAO robots during oficial RoboCup competitions and in the SimRobot simulator, demonstrating a notable reduction in task overlaps in limited communication settings.
CEUR ceur-ws.org
Robocup is the world’s largest robotics competition which aims to push the boundaries of research covering a wide range of topics. Managing the coordination among a team of fully autonomous humanoid robots is a key aspect of dealing with the RoboCup 2050’s challenge, consisting of creating a team of fully autonomous humanoid robot soccer players able to win a soccer game complying with the rules of FIFA against the winner of the World Cup.
In the RoboCup Standard Platform League (SPL), the current trend is to rely less on WiFi
communication, in order to push the boundaries of the robot’s capabilities in managing the
distributed task assignment problem in challenging conditions. Novel approaches, like
gesturebased [
In particular, in the last few years, the network packet rate has been reduced from the original
5 packets per second per robot to a 1.200 total amount of packets per team per match. According
to the rulebooks, from RoboCup 2019 to RoboCup 2022 the number of allowed packets per
team has been reduced by 84% [
The main contribution of this work is the definition of a new distributed coordination
system, derived from the market-based task assignment for orchestrating the actions of multiple
autonomous robots, ensuring their eficient performance even in setups with low communication
rates. Our approach has been tested on real robots during competitions and in the SimRobot
simulator[
Coordinating a team of humanoid robots is a challenging task, especially in a very dynamic
environment with hard constraints in the communication modalities. The RoboCup competition
is one of the best testbeds for developing novel approaches, where a team of robots must
cooperate efectively to compete in soccer matches. Within this competition, diferent leagues
address the multi-agent coordination problem in distributed and centralized setups and using
fully observable and partially observable environments, depending on the league[
An early approach for task allocation modeled as an asynchronous distributed system has
been presented in [
In the 3D Simulation League, an advancement in robot coordination is introduced in[
Additionally, other solutions to the challenge of coordinating heterogeneous robots are
discussed in [
To take advantage of the auction based-mechanism [
To improve the placements of the robots on the field, some approaches rely on the Voronoi
schema [
The proposed method creates a fully distributed market-based coordination system, inspired
by the one proposed in [
Our main contribution is the proposal of a market-based, distributed approach for multi-agent coordination, when there is a lack of information for an extended period. This specific topic has been overlooked in previous works and research which mainly focus on a standard situation in which it is always possible to share information among the agents. However, in a real-world application, it may happen that robot communication is not always possible or is delayed, especially when the communication medium is the network. Our methodology focuses on addressing this particular situation, leveraging the prediction models to compensate for the limited information exchange among agents.
In order to represent the operative scenario, we consider tasks, denoted as = { 1, … , }, and robots, denoted as = { 1, … , }, where in general > . Furthermore, we assume that we possess knowledge of an optimal robot placement configuration depending on the world state. In our study, a central theme that underscores the eficiency and efectiveness of our approach is the execution of both task assignment and world modeling in a distributed manner, without exchanging further information. In the context of the RoboCup domain, we N E T − 1 Ψ
ctx provider
UEM − 1 m tasks
Γ n tasks Φ <, >
An essential prerequisite for an efective distributed task assignment algorithm is to have an accurate representation of the world. The local model of the world ( ) contains several components to represent the surrounding environment. The essential elements that contribute to world modeling include the obstacle model which incorporates the estimated poses of all robots and other rigid obstacles; a ball model, utilized for the estimation of the ball state (position and velocity); and a lines detector, employed to identify soccer lines within the field. Each component is derived from sensor data and is refined through the application of filtering techniques to mitigate perception errors. The inputs that afect the models are the robot’s perceptions referred to as and the events sent from other robots through a common network.
We distinguish events that reflect the main situations in soccer matches. For example, an event is triggered when a robot detects a whistle from the referee. Another example of event triggering is when none of the team members have seen the ball for a while. In such a case, if a robot finds the ball, the context changes, and an event is triggered to notify the other agents. It is important to notice that these events are in general not triggered at a specific rate, but they occur at irregular intervals, mirroring the dynamic nature of the real-world environment. Consequently, there exists the possibility of extended temporal gaps during which no event is sent through the network.
To address this limitation, we employ a function denoted as to update the of other robots, referred to as for robot j. Specifically, this function merges the of the previous step with any received event, when available. In the absence of a received event, it uses a predictive model to compute a probabilistic model of the world. This allows us to avoid sending the whole
through the network obtaining a good estimation using only the available information.
received from the sensors into the previous local model. by incorporating input data (1) (2) (3) Both the local model update functions and involve predictive models which compensate for the absence of information, in case no network event is received. For example, a Gaussian Mixture Model (GMM) is employed to model the obstacles, a Kalman Filter for the ball preceptor, and odometry data for updating field elements and lines. Having an updated version of the Local
World Model ( 1, , … , −1, ,
}, it is possible to reconstruct the Distributed ) with a merging function which fuses the set of local models. = ( 1, , … , −1, ,
) , = (
,−1 , ) = Ψ( −1 , )
In our study, our primary objective is to enhance team coordination and strategic decisionmaking by adapting to the evolving configurations of the world. To achieve this, we introduce the contexts to represent various scenarios. Specifically, we rely on a module, the Context Provider, which uses the information within the DWM to dynamically select the most appropriate context (CTX ) from a predefined set. The context selection relies on a priority queue. Each context is linked to specific conditions. These contexts represent distinct situations in which a strategic adjustment becomes necessary.
At the same time, the information condensed in the DWM is used as input to function to generate a set of desirable positions representing the optimal robot configuration at that moment. Notice that the configuration generated is role-independent, and each point within it does not represent an assignment to a specific robot but rather signifies a collection of potential waypoints. The points generated from have two purposes: filter out of tasks and further refine the Utility Estimation Matrix (
).
The Utility Estimation Matrix represents the main data structure used to take into account the information from teammates and simulate task auctions locally. It is composed of N rows for robots and M columns for tasks, where the entry (, ) contains a non-negative number representing the utility. The utility is computed by considering several components that measure the efectiveness of a given DWM with respect to a robot and a role , so it quantifies how well robot can perform the task . The final goal is to maximize the sum of all the assignments. The computation of is also influenced by the context selected by the context provider, allowing for adaptive role assignments based on the chosen strategy. The columns of the matrix are ifltered using a module that compares the target of the roles with the waypoints derived from . This filtering process transforms the matrix into an × square matrix, with an equal number of roles and agents. Finally, a function Φ provides the pairs < , > from the filtered : Φ( , ) →−< , > ∀, (4)
The roles in the matrix are ordered by importance, meaning that a role in position has more priority than a role in position if < . The assignment process starts with the role in position 0 and assigns it to the robot associated with the row that maximizes its utility. Subsequently, we proceed to the next role in order of priority while considering the unassigned robots. This process allows each robot to simulate the potential assignments of other robots. As the is probabilistically identical for all agents, each robot will reach an identical set of assignments.
The function is a domain-specific optimal function that we assumed a priori, and which is used in the selection of the best N tasks and for the refinement of the UEM. The selection of the function is based on some precise aspects that are desired to maximize or minimize, according to the environment. In a RoboCup soccer field, where the coexistence of many robots in a limited space can create some issues in the evolution of the game, we are interested in maximizing the distances with adversarial robots. For this purpose, the function we chose is the Voronoi diagram (Fig.3), which guarantees some advantages in the spatial disposition of the agents.
Given a set of points in the plane (called sites), the Voronoi diagram is the partition of the plane in polygons based on the distance to them. In particular, it ensures every point inside the same region is closer to its associated site than to the others. Formally, defined a metric distance , we call = { | = 1, ..., } the set of sites and = { | = 1, ..., } the set of Voronoi regions, each one associated to the site . Thus, taken a point of the plane: ∈
⟺ (, ) ≤ (, ) ∀ ≠ Every point such that ∈ ∧ ∈ compose the Voronoi edge between the polygons and . So, the edge is constituted by all the points that have the same distances with the sites and , i.e.:
= {|(, ) = (, )} with ∈ ∧ ∈ Every point that belongs to at least three diferent Voronoi regions is called Voronoi node: = ∩ ∩ ∩ ... ∩ In our case study, among all possible methods to build the graph, we decided to consider and construct it as the dual graph of the Delaunay triangulation, where the set of starting points (5) (6) (7) is composed of all positions of opponent robots. The final Voronoi nodes and edges represent respectively the furthest points from the opponents and the optimal path to follow between two adjacent nodes. In other words, Voronoi nodes constitute the optimal positions for the team disposal. The filtering process for the N out of M tasks is done through the proximity of the tasks to the nodes. In this way, we can ensure to pick the most suitable tasks for the environment evolution. The refinement of the UEM is performed by applying ofsets to the tasks in their nearest node directions, displacing the task positions to the local optimal solution.
The system has been tested qualitatively during the last oficial RoboCup competition 1, and quantitatively in the SimRobot environment, simulating multiple matches.
To assess the performance of our approach, we employ the metric of multiple role periods. Specifically, we have computed for each role, in each match, the total duration during which two or more robots assumed the same role simultaneously. Since the striker represents the most dynamic role with the highest priority, it best reflects coordination performance.
We performed three sets of experiments, comparing the following approaches: 1. multi-agent fixed-rate coordination that does not utilize events and Voronoi. 2. multi-agent event-based coordination without Voronoi schema correction. 3. multi-agent event-based coordination with Voronoi schema: the presented approach that includes the events and the novel Voronoi correction in the task assignment mechanism.
The results, displayed in Figure 4, show the cumulative role overlap duration. The x-axis represents the roles, while the y-axis represents the cumulative time. The total simulation duration is 60 minutes. The adoption of an event-based communication model allows for a more adaptive approach to environment changes compared to a fixed-interval rate, enabling the robots to communicate only when necessary. This is further improved using the Voronoi schema which obtained the best results in terms of overlapping time between roles (orange-green bars comparison). In fact, the Voronoi schema improves the coordination reducing role overlaps, by distributing the tasks of each role far from the tasks of the other roles, preserving efectiveness.
In this study, we tacked the challenge of coordinating a team of fully autonomous humanoid robots participating in the RoboCup competition, in a low communication setup. The recent changes in SPL’s rules, such as reduced network packet rates and an increased number of playing robots, prompted us to develop an innovative distributed coordination system based on market-based task assignments.
Our system allows robots to model the world locally, propagate world predictions when network data is limited, and consequently eficiently assign tasks to team members. We adopted a market-based approach in which every robot simulates an auction locally assigning the available tasks to maximize the expected reward. We employed a Voronoi Graph to filter out additional roles to match the number of tasks with the number of available robots. Additionally, the Voronoi diagram has been also used for calculating a portion of the reward, contributing to the diferentiation of the total reward. To address limited communication, we utilized prediction models to compensate for missing information from other agents, sending messages only when specific events occur. Finally, we conducted extensive experiments, both in the real RoboCup environment and the SimRobot simulator, to assess our approach’s performance.
The results clearly indicate that our approach efectively reduces task overlaps in lowcommunication scenarios, a critical factor in RoboCup matches. This research contributes significantly to the robotics field and RoboCup competition, ofering a practical solution to the challenges posed by reduced communication rates in SPL.