Pacman AI, Part IV

Introduction

This is the fourth part of the Pacman AI project. In this part of the project, the Pac-Man agents are designed to use sensors to locate and eat invisible ghosts. Task difficulty changes from tracking single, stationary ghosts to hunting packs of multiple moving ghosts with ruthless efficiency.

Exact Inference

First, update the observe method, so that the agent can correctly update its belief distribution over ghost positions. After doing this, the agent can accurately locate a ghost by circling it. By implementing the online belief update for observing new evidence. In the beginning, the Pac-Man agent believes the ghost could be anywhere, which is a uniform prior. Whenever a new reading is received, the ‘observe’ function is called, then the belief at every position is updated.

Screen Shot 2017-11-17 at 11.46.33 AM.png

Now that we can locate stationary ghosts. However, in real games, all ghosts are running around. Then we can update the ‘elapseTime’ method, which allows the agent to use the ghost’s move distribution to update your agent’s beliefs when time elapses.

Screen Shot 2017-11-17 at 11.51.17 AM

We assume that ghosts move independently, so I first implemented all code for just 1 ghost at a time, then added multiple ghosts. Now that we can locate moving ghost by updating beliefs. Our final goal is to hunt those ghosts down, so we should also implement a greedy buster agent to hunt down ghosts.

Screen Shot 2017-11-17 at 12.00.15 PM

Now we have an agent that can hunt the closest ghost based on their beliefs of the ghosts’ location.

 

Approximate Inference

For this part of the project, I implemented a particle filtering algorithm for tracking a single ghost. A particle is a ghost position in this inference problem. The methods for the ParticleFilter class are implemented as follows:

Screen Shot 2017-11-17 at 4.47.24 PMScreen Shot 2017-11-17 at 4.49.05 PMScreen Shot 2017-11-17 at 4.49.56 PM

After this implementation, the agent can track ghosts as effectively as with exact inference. As can be seen from the video below, the belief cloud generated by the particle filter looks noisy compared to the one for exact inference.

 

All above implementations are based on one assumption: ‘All ghosts behave randomly independently.’ Now that we want to make the case more complicated. The ghosts don’t want to be caught so they try to keep away from each other in order to increase the efforts needed to find and capture them all. Since the transition models are no longer independent, all ghosts must be tracked jointly in a dynamic Bayes net.

The joint particle filter is implemented as follows:

Screen Shot 2017-11-17 at 5.07.00 PMScreen Shot 2017-11-17 at 5.07.33 PMScreen Shot 2017-11-17 at 5.07.53 PM

The correct implementation handles two special cases: (1) when all particles receive zero weight based on the evidence, all particles are resampled from the prior to recover; (2) when a ghost is eaten, all particles to the place that ghost in its prison cell are updated. The below video shows how dispersing ghosts are tracked effectively.

 

Conclusion

This is the end of Pacman AI, Part IV. After 4 projects, the agent was improved significantly. In the beginning, all it can do is to search for something in the map, and now the agent is a ghostbuster that can hunt down ghosts without seeing the exact location.

Readers of the post should not copy any of my code for their own course assignment, but feel free to be inspired and come up with your own ones. I do not want to upload code file to GitHub because that makes my code handy to copy and paste. Also, code screenshots are made unclear on purpose, because technically I should not upload solutions.

 

AI

Arthur Zhang View All →

A current master student in WUSTL, department of Electrical and System Engineering.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: