CSE 537 Project 3: Log-PacMan
(100 points, Due Thu Oct 31st 11:59PM)


In this project, indeed you will re-implement the first project by using XSB-Prolog.

Files to edit:
search.py Where all of your search algorithms will reside.
searchAgents.py Where all of your search-based agents will reside.


What to submit: Besides submitting prolog files (which contain implementation of A*, BFS and DFS search strategies in prolog), you just need to edit search.py and searchAgents.py files and submit these two files in order to complete this project. You can access these python files from your First project. So, you are expected to submit following files (and a document):

Document (10 points) You also need to submit a document which inside, you must explan how you implement different search strategies in prolog.

Basic steps in order to complete this project:

Step #1

Since you need to model your test maze as prolog facts, you need to edit class PositionSearchProblem (in searchAgents.py), in a way that by considering the place of walls, finish cell (goal cell) and start cell, you make corresponding facts in a prolog file, say maze.P, during the EXECUTION OF YOUR PROGRAM. For example, if you have following maze, your program will generate corresponding maze.P file:


Please consider that this way of modeling the maze is just a simple example and of course you are welcome to model the maze in any way you feel the most comfortable.

Also, modification (adding code to model the test maze) to PositionSearchProblem can be done in its constructor after initializing self.walls, self.startState and self.goal.

Step #2

Create following prolog files (during your project DEVELOPMENT phase):

Step #3

So by now you will have three prolog files which implement three different search strategies in addition to a program which will parse the maze and create maze.P file. Now, it is time to use these files in your search.py file! In this file, complete the functions "breadthFirstSearch", "depthFirstSearch" and "aStarSearch" with the help of prolog files you have created by now.

But, how to complete this step? There should be a way to connect Python to XSB-prolog. There are many ways to call XSB from Python program. The easiest way to do so is to use interface pyxf.py from SPADE (Smart Python multi-Agent Development Environment) library! SPADE is a Multi-agent and Organizations Platform based on the XMPP/Jabber technology and written in the Python programming language. pyxf.py is multipurpose python interface to XSB-prolog, SWI-prolog, ECLiPSe Prolog and Flora2. In order to use this interface, you need to install SPADE which can be done with easy_install (easy_install SPADE) or pip (pip install SPADE).

Here, a very simple example is explained to help you move forward faster. Lets assume that we have two programs:

Now, from python, we want to query q(X) and get X = a, X = b and X = c as a result of the query. Following program (after installing SPADE library), explains the way you can connect to XSB to get query q(X) answered:


Now, the result of executing this program is:


So, as you see the result of the query is a list. Each element of this list is a dictionary which binds variable X to the possible solutions (here 'a', 'b' and 'c').

Please consider that, as you know, the result of functions written in search.py must be a list of actions such as [s,s,w,s,w,e,w,n,s,w]. So, after getting result of query from XSB, you may need to convert your intermediate solution to this form to make the whole log-pacman project works.

For further examples, please click on the XSBKB link to get more familiar with this interface.

So, simply by using this interface, you can complete this step, therefore, complete your project.