Particle Filter

Pacman AI

Approximating the position of the enemy agent using the particle filter

Particle Filter is one of the important concepts being used in the program. It predicts the approximate position of an enemy agent which is currently not in sight, along with a probability score of that point. The results are being used by the offensive agent to avoid enemies not in sight and by the defensive agent to predict approaching enemies.

Pseudocode

function find_approx_pos<Agent A>:
    noisyDistance<A> = getNoisyDistance
    if A's exact position is known then,
	S<A> = list of points representing particles(all at exact location): with equal probability value
    else:
	S<A> = getPosUsingParticleFilter<S<A>, A, noisyDistance>

function getPosUsingParticleFilter<S<A>, A, noisyDistance>:
    A_t = list<>, A_r = list<> lists which store updated probabilities and approx location

    for each particle in S<A> :
	if particle not in A_t:
	    add to A
	else
	    sum particle probability to A_t's particle probability

    for each particle in A_t:
	union particle with A_r, with same probability values
	if the agent A may have moved in the previous step:
	    union all neighboring point of the particle to A_r, with same probability values

    if length of A_t<numParticles:
	if the particle may of moved:
	    pick random point from S and add its neighbor
	else:
	    pick random particles from S<A> and add it:

    for each particle in A_t:
	update particle probability as = old_probability * getDistanceProbability(particle) // using gameState.getDistanceProb
	n = n+updated_probability

    normalize probability scores using n


   return A_t

Design and Implementation:

The entire maze was converted into a graph dictionary, and which was then used to process and retrieve information from the particle filter algorithm. The initial condition is set using start points of each agent provided at the time of initialization and then the exact position is updated every time an agent is detected. The structure of the createTeam function and offensive and defensive agent initialization was modified to make the two agents on the same team share the particle information. This makes the approximation more accurate.

Analysis:

The algorithm performed as intended. However, the accuracy would deteriorate over time if the agent was not actually detected. Hence, the probability scores were used as weights when using approximate positions in value iteration rewards matrix.