Open World Model for Simulated Soccer
SECTIONS:-
In agent based RoboSoccer Simulation an agent must be able to evaluate its position with respect to its teammates and opponents, and then decide whether to wait for the pass, run for the ball, cover an opponent's attack or go to help a teammate. This role that an agent plays is influenced by it's perception of the surrounding environment.
In this project
we intend to build a probabilistic model or a
memory client capable of localizing mobile
robots in the field and similar to other robosoccer clients like those
for passing and kicking the ball. The basic function of the memory client
would be to provide an estimate to the position and velocities of other
players and the ball to the sensing player. Immediately the question arises,
why do we need to keep such a record of positions and velocities when the
player can every time turn around and see. Shown below are few of the myriad
critical situations which a player may face during the game.
In the above cases
1. The opponent players, very close to the ball but not in the field of view, are ready to take over the ball.
2. The player with the ball can't get the help of his teammates not in his field of view when surrounded by opponent players.
Thus to tackle such
situations the player needs to have information about the field even outside
his field of view. Moreover in such close situations it may not be possible
to turn around and see.
The memory client
will maintain a Belief
over the position and velocity of the other players and ball based on previous
observations. The Belief maintained would be dynamic in nature. Dynamism
of the Belief implies a change as the game goes on. As the time for which
a particular object(players or the ball) has not been seen increases, the
uncertainty over it's position increases or in other words the Belief goes
weaker. When the same player is seen again it's previous Belief is modified
according to it's new position.
The results expected are the probabilistic positions and velocities which are closest to the actual unknown position and velocities. The graph below shows the expected deviation from actual parameters. The maximum deviation depends on the mobility of the sensing player. The two maxima on the curve represents the instants when no new data is being received by the player. The sharp fall denotes the improvement over the confidence value on observing the new data
Approximation of Belief Functions
Belief Functions is a class of functions which is very widely used to model uncertainty, impreciseness or the provability of a state with incomplete information. More is the Belief more is the certainty of the state. Belief functions can be Probabilistic or Non Probabilistic. Non Probabilistic Belief Functions are in the form of Inequalities and therefore restrict the plausibility of the existence of state. They are discrete in nature and incomplete for modeling noisy systems. By discrete we mean if state is estimated to lie in a pre-determined range, it's belief is assigned One else Zero. But for memory modeling these functions are not suitable as the state space is very large and variation in Beliefs is required to differentiate between many objects. Secondly, these functions are more complicated to work with. Therefore, for our purpose we use a class of probabilistic belief functions known as Kalman Filters. We define the Belief in our case as:
where,
denotes the position vector of the nth player at time t and
denotes the data collected upto time t,
denotes the Belief over the position of nth player posterior to data collected
till time t
The purpose of Kalman Filters is to estimate the state of the system from measurements which contain random errors. They are somewhat similar to Radial Basis Functions as they have strong resemblance to distance weighted belief values. The advantages of Kalman filters is that they are very easy to modify recursively. The second advantage is that they are able to produce good estimates even when precise nature of noise added is unknown. They are centered at mean and symmetric about it. The simplest of this class is the Exponential Function. But this function does not provide enough modifiable parameters that may suit our purpose. We, therefore move to the next family Gaussian Functions. The advantages of the Gaussian Functions are as follows:
It
captures noise in the system very efficiently. Also since the real time
systems have Gaussian Noise, these functions are most suited for real time
systems.
They
are computationally efficient since every moment can be simply expressed
in terms of Mean and Variance.
The
function definition includes the first two moments Mean and Variance. We
can by varying them with time and distance obtain the required recursion.
It is the procedure by which the Belief Functions are modified with time and with the new coming information. Belief Conditioning can be done in two ways:
It involves the estimation of the new Belief of the objects position based on the new coming data. Application of the Baye's Theorem to the definition of the Belief Function gives the following:
where,
denotes
the latest data value obtained from the server.
denotes
the normalizing constant.
The last equation suggests the Incremental update equation:
The conditional probability The following graphs
demonstrate the Bayesian Conditioning of Single dimensional Gaussian Belief
by another Gaussian distribution(received data). The second graph below
shows the new Belief with mean at different position. Earlier the confidence
of belief was about 0.6, now it has become 2.4.
is called the Environment Perception Model. When the actual position is
unknown we can approximate it to be the one given by our previous Belief.
Then this environment perception is the probability of new data given the
estimated position. Since the new data is not as well noise free we take
it's Probability Distribution Function to be Gaussian again. The prior
Belief is Gaussian and the product of two Gaussian functions is also a
Gaussian , this ensures the validity of the Incremental Update Equation.
When no data is being received about a player during consecutive time cycles Belief cannot be modified Bayesian. We'll have to use the physics of the system to obtain the new position and velocity estimate. Moreover, the confidence over them must decrease as the time of no data increases. The Belief is centered about mean and it's spread can be estimated by variance. Therefore the following update equations are used:
Following points can be noted from these equations :
1. The confidence over the position or the velocity is given by the reciprocal of inverse i.e., the value of the Belief function at it's centre.
2. The Belief function is centered about the estimated position of the object.
3. As the time of no data(k) increases velocity decreases and therefore the object slows down.
4. Also as k increases variance increases and the function spreads out. Hence the confidence decreases.
The following graph shows the recursive conditioning of a unidimensional Gaussian Belief. When no new data for a particular player is being observed in consecutive time cycles the Belief over both position and velocity decays.
Quantification refers
to extracting out meaningful information from the Belief Function. The
value of Belief Function above a threshold value is chosen for the estimation
of position and velocity. If the Belief function has value less then the
threshold at all positions then that Belief is discarded and a uniform
distribution is assumed. This helps in saving time which would otherwise
be wasted over a decayed belief Function. For our purpose we just select
the best estimate which always turns out to be the mean or the centre of
the Belief Function.
SoccerServer and Data Received
Soccerserver is the system that enables various types of programming languages to play a match of soccer against each other. A match is carried out in server-client style: A server,soccerserver,provides a visual field and simulate all movements of a ball and players. Each client is part of the brain of player controlling a particular action of the player. Communication between a server and each client is done viaUDP/IP sockets. Therefore users can use any kind of programming systems that have udp/ip facilities.
Visual information arrives in the following basic format:
Objects can be ball, player, flag, line and goal. The direction is the angle w.r.t to the face direction of the sensing player. Dischng and Dirchng are the velocities of the observed player in the polar coordinates.
Below given is an example
of the received data.
recv 2789 : (see 760 ((goal l) 66.7 -33) ((flag c t) 4.3 -44 0 0) ((flag l t) 55 .7 -3) ((flag p l t) 42.5 -23) ((flag p l c) 53.5 -43) ((ball) 60.3 -34) ((player r Poland) 44.7 -42) ((player India) 49.4 -35))
recv 2789 : (hear 761 referee foul_r)
recv 2789 : (hear 762 referee free_kick_l)
recv 2789 : (see 763 ((goal l) 66.7 -33) ((flag c t) 4.3 -44 0 0) ((flag l t) 55 .7 -3) ((flag p l t) 42.5 -23) ((flag p l c) 53.5 -43) ((ball) 60.3 -34) ((playe r Poland) 44.7 -42) ((player India) 49.4 -35)) ~
Algorithm
1. In the first step the data received is parsed, classified according to the various objects and data stored in a buffer.
2.Triangulation: From the relative distance between nearest stationery objects the approximate coordinates of the sensing player are calculated. Once these are known the coordinates of other moving objects are calculated.
3. Bayesian modification is done to those players whose data has been received.
4. Rest are Recursively modified.
5. When the game starts, we initialise the Beliefs by a Uniform Distribution. Also when the Belief has decayed below a threshold again it is taken as Uniform to save calculations.
6. For Quantification
the whole field has been divided into 68x100 grids. The position for which
the Belief function has the maximum value(mean) is the new position. It
then is quantised to one of the grids.
The data which is coming is of three types
1.
@Article{ Han/Veloso :1998,
author= { Han,Kwun and Veleso,Manuela
},
year= { 1998
},
keywords= { Kalman Filters,Extended Kalman Filters,Kalman Gain Matrix,Recursive
Propagation,Multi-Object Tracking,Mahalanobis Distance},
institution= { CMU-CS}
title=
{ Physical Model Based Multi-objects Tracking and Prediction in Robosoccer}
,
journal= { },
month= { },
volume= { },
pages= { },
e-mail= { (kwunh+mmv) @cs.cmu.edu },
www= { http://www.ri.cmu.edu/~kwunh/
},
annote= {
Robosoccer is a multiagent framework in which multiple agent collaborate
in an adversarial environment.But still robots cannot incorporate on-board
full autonomous capabilities. In particular, vision processing is off-board,
centralized to the individual clients that control the robots. The vision
system needs to overview the complete field and to compute in real time
positioning information for the moving ball and the players. This paper
describes the ongoing work on developing a multi-object tracking and prediction
in this challenging set-up. This paper presents a preliminary work applying
an extend Kalman filter to follow the trajectory of multiple moving colored
objects.
The paper is a good reference for basic knowledge about Bayesian methods
of learning .
-Tarun Gupta,Manu Saxena,2/2000
}
2.
@Article{Fox/Burgard_et_al:
1999,
author= { Fox, Dieter and Burgard,
Wolfram and Kruppa, Hannes and
Thrun, Sebastian},
year= { 1999
},
keywords= { Mobile Robots, Localization, Robotic
Vision,Multi-Robot Cooperation,Monte-Carlo methods},
institution= { CMU-CS}
title=
{ A Monte Carlo Algorithm For Multi-Robot Localization},
journal= { },
month= { March},
volume= { },
pages= { },
e-mail= {
www= {
annote= {
This paper
presents a statistical algorithm for collaborative mobile robot localization
in Robot Soccer. The authors have tried to develop a probabilistic model
for keeping the track of the position of each player. Bayesian Learning
Techniques have been used to develop the distribution function and refine
the distribution with the new data as it comes. The distribution function
has been approximated using Re-sampling .
The algorithm
developed here can be used in various domains like RoboSoccer and in tasks
requiring agent collaboration.
-Tarun Gupta,Manu Saxena,2/2000
}
3.
@Article{Stone/Veloso
et_al :1999,
author= { Stone,Peter and Veloso,Manuela
and Riley,Patrick},
year= { 1998
},
keywords= { Agent Architecture,World Model,Localisation},
institution= { CMU-CS}
title= { The CMUnited-98 Simulator
Team},
journal= { },
month= { March},
volume= { },
pages= { },
e-mail= {(pstone,veloso)@cs.cmu.edu/priley@andrew.cmu.edu/~priley},
www= {http://www.cs.cmu.edu/{~pstone,~mmv},http://www.andrew.cmu.edu/~priley},
annote= {
The CMUnited
Champs article describes the complete CMUnited software, emphasizing the
new improvements. The basic ideas to build the agents and things to keep
in mind while designing an agent have been discussed. Though no algorithm
as such has been discussed, the paper is nicely written and easy to understand.
The algorithm
developed here can be used in various domains like RoboSoccer and in tasks
requiring agent collaboration.
-Tarun Gupta,Manu Saxena,2/2000
}
[ COURSE WEB
PAGE ] [ COURSE
PROJECTS 2000 (local CC users) ]