ISocRob 2011 Team Description Paper
João Messias, Aamir Ahmad, João Reis, João Sousa, Pedro Lima
Institute for Systems and Robotics, Instituto Superior Técnico, Av. Rovisco Pais 1049-001 Lisboa, Portugal
Abstract This paper describes the status of the ISocRob MSL robotic soccer team as required by the RoboCup 2011 qualification procedures. The most relevant technical and scientifical developments carried out by the team, since its last participation in the RoboCup MSL competitions, are here detailed. These include cooperative localization, cooperative object tracking, planning under uncertainty, obstacle detection and improvements to self-localization.
1 Introduction
The SocRob (Society of Robots) project, which focuses on cooperative robotics and multi-agent systems, has been active since 1997 at the Institute for Systems and Robotics at Instituto Superior Tecnico (ISR/IST), Technical University of Lisbon. The ISocRob team is the project's case study on soccer robots, and has regularly participated in RoboCup Middle-Size League since 1998, in the RoboCup Soccer Simulation League in 2003 and 2004, and in the RoboCup Four-Legged League in 2007, in a joint effort with the Italian team SPQR.
This paper describes the main novelties at the technical/ scientific level which have been developed by the team since 2009, when it last participated in RoboCup MSL. When appropriate, we cite the team publications on the described topics.
2 Scientific and Technical Challenges
Cooperative Localization Using Visually Shared Objects
We introduce a modification to Monte-Carlo Localization (MCL) that changes the particle injection step (used when a robot detects it is lost), using information provided by other robot(s) of the team on the location of an object commonly observed by the lost robot. This modification speeds up the recovery of the lost robot and is robust to perceptual aliases, namely when environments have symmetries, due to the extra information provided by the teammates. The introduced method enables cooperative localization in a multi-robot team, using visually shared objects, taking advantage of the specific features of particle filter algorithms. Each robot is assumed to run MCL for its selflocalization, and to be able to detect when the uncertainty about its localization drops below some threshold. An observation model that enables determining the level of confidence on the ball position estimate is also assumed to be available at each robot of the team.
Let us consider a team of N robots, $r_1, \ldots, r_n$. Robot $r_i$ has pose (position + orientation) coordinates $\mathbf{l}{r_i} = (x{r_i}, y_{r_i}, \theta_{r_i})$ in a global world frame, and estimates them using a MCL algorithm.
Each robot can determine the position of an object o in its local frame, therefore being able to determine its distance and bearing to that object as well. Robots can also determine if they are lost or kidnapped, i.e., if their confidence in the pose estimate drops below some threshold. If a robot is not lost, it can also determine the object position in the global world frame using the transformation between its local frame and the global world frame that results from the knowledge of its pose. The estimate of the object position in any frame is determined based on a probabilistic measurement model that includes the uncertainty about the actual object position. When the global world frame is used, additional uncertainty is caused by the uncertain pose of the observing robot.
The position of the object as determined by robot $r_i$ in the global world frame is denoted by $\mathbf{p}_o^i = (x_o^i, y_o^i)$, while the distance and bearing of the object with respect to the robot, as measured by the robot, are given by $d_o^i$ and $\psi_o^i$, respectively. Details of this algorithm is presented in our work [2]. A graphical explanation of the algorithm is represented in Figure 1.
Cooperative Object Tracking
This work builds mainly upon [8] and [7], carried out in the direction of object tracking and sensor fusion among teammates respectively. In [8], a PF based tracker is presented with a unique and novel 3-D observation model based on color histogram matching. Each robot has an individual tracker and its most notable feature is that the tracking could be performed in 3-D space without the object color information, but at the cost of computational expense. In [7] a sensor fusion technique for cooperative object localization using particle filters is presented. Parameters of a GMM approximating a teammate's tracker's particles are communicated to the other robots. Particles at a robot's tracker are then sampled using own belief and the received GMM.
We introduce an approach to cooperative object tracking where we implement a Particle Filter based tracker. This algorithm is represented in Figure 2. For each observing robot, we determine confidence factors associated to the tracked target from two origins: i) the confidence on the observation itself and ii) the confidence on the self-localization estimate of the observing robot. The observation model of each mobile sensor is a parametrized probability density function (e.g., a Gaussian centered on the observation). The probability density functions associated to the observations of the team robots are shared by all of them in a pool. Each robot selects the best function, i.e., the one with higher confidence factors, from the pool, and uses it to assign weights to the particles in the traditional PF update step. The parametrization of the observation models intends to reduce significantly the amount of data communicated to teammates, since the probability density function can be univocally represented by its communicated parameters. The method handles, within a single unified framework, inconsistencies (disagreements) between sensors due to observation errors and/or self-localization uncertainty. In order to achieve near real-time tracking, we track the object in 2-D space only and use the object color information. These will be relaxed in the future work, as they depend mostly on the available computing power.
3D Object to 2D Image Bijection Principle
In our soccer robot platform the vision system is dioptric which involves one fish-eye lens camera facing down towards the field. One of the target object to track is the ball. In order to do so in 3-D using a single camera, we show that for each set of image points of the ball's periphery in an image as seen by a single camera, there exists a unique 3D position of the ball.
$$d = f\Theta, \tag{1}$$
We propose 3D spherical object to 2D image bijection principle which states that the periphery of a spherical object of known radius when observed through a fish-eye lens which follows the equidistant projection model (1), always projects into a unique curve in the image frame for each possible 3D position of that object. Conversely, each curve in the image which satisfies the condition of being projected from the periphery of a known spherical object back projects into a unique 3D position of that object. Fig. 3 shows the position of an object $(S_o)$ and the image $(C_i)$. We obtain the equation of $C_i$ as follows:
$$C_i \equiv r_o^2 - r_o \sqrt{r_o^2 - R_o^2} \left( \sin\left(\frac{d}{f}\right) \sin\Theta_o \cos(\Phi - \Phi_o) + \cos\left(\frac{d}{f}\right) \cos\Theta_o \right) - R_o^2 = 0, (2)$$
It is evident from (2) that for every 3D position (ro, Θo, Φo) of the sphere of radius Ro, there exists a unique curve Ci, conversely for every given image curve Ci there exists a unique sphere position in 3D hence the spherical object to image transformation under equidistant projection model is bijective. This leads us to conclude that it is possible to uniquely identify the position of a known dimension spherical object in 3D using a single equidistant projected image.
Obstacle Detection
The ability to reliably detect obstacles is essential for any robotic soccer team, since it provides a basis for safe motion control. In MSL, this is typically accomplished through image processing. In ISocRob this algorithm has been based, since its inception, on a simple color blob detection mechanism, which segmented out the darkest areas of an image and classified them as obstacles if their pixel area was sufficiently large. This, however, led to sporadic measurements and was too sensitive to light conditions, which in turn caused the robots to have unreliable motion control at times. For these reasons, the team developed a new, more robust, obstacle detection algorithm. This method is able to track multiple obstacles in real time by creating and maintaining independent Kalman Filters for each detected obstacle.
Its principle of operation is as follows: a histogram is first computed for the green channel of each received image. In this channel, obstacles are more easily discernible, exploiting the fact that, in the MSL environment, obstacles are black on a green background. Based on this histogram, a threshold is then calculated which best separates obstacles from other components in the background. The segmented components are then labeled into connected regions in the image.
Given that the dimensions of the expected obstacles are known a priori, since robots from all teams have roughly the same size, this allows us to create a prior which can be used to improve classification. Based on real data, this prior constitutes the expected pixel area of an obstacle in the image, given its perceived distance. If a labeled area then matches the expected area whithin certain bounds, it is then classified as an obstacle.
To account for sensor noise and possible erroneous classifications, each detected obstacle is then associated with a Kalman Filter, which realistically models the dynamics of that obstacle's motion in the image. Given the velocity of the robot running this algorithm, an estimate of the obstacle's velocity can then be naturally obtained as a byproduct of the operation of these filters. Evidently, this implies the existence of a data association step, each time an image is received. The way though which these associations, between obstacles and active Kalman Filters, is accomplished, is similar to common mechanisms for data association with unknown correspondences, typically present in multiple-target tracking algorithms. If the Mahalanobis distance of the innovation of any active filter, by using a detected obstacle as measurement, is whithin a given range, then the most likely obstacle is associated with that filter. If no existing filter verifies this condition, then a new filter is created to track that obstacle.
In its current state, and still finishing development, the filter can track multiple obstacles with up to 87% correctness.
Task Performance Analysis
The ability to easily define task plans as Petri Nets has long been a hallmark of the ISocRob team. However, due to the increased (mostly visual) complexity of these models when scaling up these tasks plans to multiple agents, these representations usually carry a risk of performing unexpectedly is expert care is not taken. It can occur, for example, that unreachable states are unknowingly included in the model, or that some subset of it is susceptible to deadlocks (or livelocks). For these reasons, it is important to formally analyze the models before they are guaranteed to be safe to use in practice. In [3,6], extensive testing and analysis has been performed, both at a qualitative and quantitative level, of all the Petri Net models used by the team, using as theoretical basis the work presented in [1]. Using as a main tool a realistic simulation environment (Webots, see Fig. 4), an analysis of the firing rate of the model's transitions was performed, from which it is possible to estimate the probability of success of a given plan, against variable conditions such as adversarial capabilities. These most useful results not only allow us to identify which behaviors are best suited against a particular opponent team, but they also allow us to identify the primitive actions which most affect the probability of a successful outcome for a given behavior. Based on this information, we then focus on improving these actions to maximize the performance of the team.
Formation Control for Cooperative Perception
The SocRob project has been recently acting as a case study for a joint project between ISR and research teams at ISEP and FEUP, the PCMMC (Perception-Driven Coordinated Multi-Robot Motion Control) project (funded by Fundação para a Ciência e Tecnologia (FCT), reference: PTDC/EEA-CRO/100692/2008). The focus of this work is on developing a framework for formation control of a team of robots with the goal of enhancing the perception of a given object. Various challenging problems are dealt with to this end, such as developing innovative formation state estimation methods, dynamic control, decentralized data fusion and cooperative target tracking techniques.
POMDP-Based Task Planning
In recent research, the team has begun to explore the possibility of performing task representation based on the Partially Observable Markov Decision Process (POMDP) framework [5]. This framework's powerful modeling capabilities can account for stochasticity in a robot's actions and observations, typically resulting in behaviors which can value information gathering as well as reward acquisition (typically for achieving a goal). By specifying a task as a POMDP, the behavior of the robot no longer has to be specified as a manually-constructed conditional sequence of actions, since the solution of the POMDP model naturally results in a policy which returns the best possible action given the robot's information, taking into account all possible contingencies present in the model. Preliminary results show that simple tasks (such as a 2-robot attack plan) can in fact be efficiently solved by casting the problem as a POMDP. This is one of the team's active and challenging research topics.
Monte Carlo Localization with Selective Resampling
Since 2008, the ISocRob team has been using a custom Monte Carlo Localization algorithm to provide stable self-localization to the team's robots [4]. Since then, the algorithm has been greatly improved, progressively addressing its limitations based on its performance during game situations.
Since various concurrently active algorithms, such as cooperative localization and tracking, rely on having a reliable measure of the probability of a robot being correctly localized, the team's MCL algorithm is now able to estimate this measure based on a priori information collected by the robots, based on the weight and variance of the filter's particle set. Using this information, the stability of the algorithm can be improved by selectively performing resample only when a robot's localization certainty drops. This reduces the chance of losing good localization due to sporadic measurements. Furthermore, the algorithm is now able to dynamically select the best resampling scheme to maximize this localization certainty measure.
References
- H.COSTELHA. Robotic Tasks Modelling and Analysis Based on Discrete Event Systems. PhD thesis, Instituto Superior Tecnico, 2010. ´
- LIMA, P., SANTOS, P., OLIVEIRA, R., AHMAD, A., AND SANTOS, J. Cooperative localization based on visually shared objects. In Proc. of RoboCup2010 Symposium (Singapore, 2010).
- MARTINS, C. Goalkeeper robot behavior design and coordination in soccer robotics. Master's thesis, Instituto Superior Tecnico, 2010. ´
- MESSIAS, J., SANTOS, J., ESTILITA, J., AND LIMA, P. Monte carlo localization based on gyrodometry and line-detection. In Proc. of ROBOTICA2008 - 8th Conference on Mobile ´ Robots and Competitions (Aveiro, Portugal, 2008), pp. 39–50.
- MESSIAS, J., SPAAN, M., AND LIMA, P. Multi-robot planning under uncertainty with communication: a case study. In AAMAS 2010 Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (Toronto, Canada, 2010).
- RODRIGUES, N. Individual and cooperative behaviors representation based on petri nets. Master's thesis, Instituto Superior Tecnico, 2010. ´
- SANTOS, J., AND LIMA, P. Multi-robot cooperative object localization decentralized bayesian approach. In Proc. of RoboCup 2009 Symposium (Graz, Austria, 2009).
- TAIANA, M., SANTOS, J., GASPAR, J., NASCIMENTO, J., BERNARDINO, A., AND LIMA, P. Tracking objects with generic calibrated sensors: an algorithm based on color and 3D shape features. Robotics and Autonomous Systems (2010).