next up previous
Next: Multiagent Strategy Control Up: Real-Time Perception for Multiple Previous: Data Association

Tracking and Prediction

In the setting of a robot soccer game, the ability to detect merely the locations of objects on the field is often not enough. Like for real soccer players, it is often essential for robots to predict future locations of the ball (or even of the other players). We have used an Extended Kalman filter (EKF) for such a purpose[5]. The Kalman filter is very suitable for such a purpose since the detection of the ball's location is noisy.

The EKF is a recursive estimator for a possibly non-linear system. The goal of the filter is to estimate the state of a system. The state is usually denoted as an n-dimensional vector x. A set of equations is used to describe the behavior of the system, predicting the state of the system as:


where tex2html_wrap_inline628 is a non-linear function which represents the behavior of the non-linear system, tex2html_wrap_inline630 is the external input to the system and tex2html_wrap_inline632 is a zero-mean, Gaussian random variable with covariance matrix tex2html_wrap_inline634 . tex2html_wrap_inline636 captures the noise in the system and any possible discrepancies between the physical system and the model. The subscript k denotes the value of a variable at time step k.

The system being modeled is being observed (measured). The observations can also be non-linear:


where tex2html_wrap_inline642 is the vector of observations and tex2html_wrap_inline644 is the non-linear measurement function, and tex2html_wrap_inline646 is another zero-mean, Gaussian random variable with covariance matrix tex2html_wrap_inline648 . It captures any noise in the measurement process.

The EKF involves a two-step iterative process, namely update and propagate. The current best estimate of the system's state tex2html_wrap_inline650 and its error covariance is computed on each iteration. During the update step, the current observations are used to refine the current estimate and recompute the covariance. During the propagate step, the state and covariance of the system at the next time step are calculated using the system's equations. The process then iteratively repeats, alternating between the update and the propagate steps.

Through a careful adjustment of the filter parameters modelling the system, we were able to achieve successful tracking and, in particular prediction of the ball trajectory, even when sharp bounces occur.

Our vision processing approach worked perfectly during the RoboCup-97 games. We were able to detect and track 11 objects (5 teammates, 5 opponents and a ball). The prediction provided by the EKF allowed the goalkeeper to look ahead in time and predict the best defending position. During the game, no goals were suffered due to miscalculation of the predicted ball position.

next up previous
Next: Multiagent Strategy Control Up: Real-Time Perception for Multiple Previous: Data Association

Peter Stone
Tue Sep 30 19:12:38 EDT 1997