Artificial Intelligence

Programming Project #2

RobotWorld!

Due by 12:29:59 on Thursday, February 23, 2006.

Please email your solution deliverables to my departmental email account by the due date. Click here to email your solution. Turn in a hardcopy of your report on Thursday, February 23.

Be sure to follow the documentation standards for projects.


Introduction and Purpose

The goal of this programming assignment is to solve a robot navigation problem using a variety of search algorithms.  The domain of this problem is RobotWorld.  RobotWorld consists of a room, a robot, and a set of obstacles in the room.  The room will be specified as a 2D grid , and the obstacles will be specified as a set of (x, y) coordinates in the room.  The robot will have an initial state and a goal state.  The state representation will simply be the location of the robot.  No other objects in the room can move. The search problem is to find the shortest path from the robot to get from its initial state to the goal state.  The robot can move horizontally and vertically - it cannot move diagonally.

The program interface should work as follows:

robotsearch <robotworld_file>

The program must be written in Python. Consult the Python online tutorial and reference for details on how to read command line arguments. If multiple options are specified, they can be included on the command line in any order but all must precede the name of the input file, which should be the last argument. <robotworld_file> is the name of the text file containing the specification of the RobotWorld to be solved, described next.



Input File Specification

Your program will be tested on a variety of RobotWorlds.  Each RobotWorld will be specified by an input file of the following form:

BEGIN_WORLD
Max_Rows Max_Cols
Robot_State_Init
Robot_State_Goal
END_WORLD
BEGIN_OBSTACLES
Obstacle_State_1
...
END_OBSTACLES
BEGIN_SEARCH_ALGS
Search_Mnemonic_1 Option Option
...
END_SEARCH_ALGS

For example, below on the left is a sample RobotWorld input file.  A picture of the world it describes is shown on the right: * is empty, I is the robot's initial state, G is the robot's goal state, and O represents an obstacle.  The origin of the grid is always (0, 0) (the upper left corner).

BEGIN_WORLD
4 5             * * * * G
(3,1)           * * O O O
(0,4)           * O * * *
END_WORLD       * I * * *
BEGIN_OBSTACLES
(1,2)
(1,3)
(1,4)
(2,1)
END_OBSTACLES
BEGIN_SEARCH_ALGS
BFS
END_SEARCH_ALGS

Your program should prompt the user for an input file if not provided on the command line.  If necessary, you may assume that the maximum Max_Rows and Max_Cols will be 100.  Everything in the input file will be legal.  No input error checking is needed (e.g., all x,y coordinates will be in range, width/height will always be positive, etc.).  The minimum legal/acceptable input file would contain a complete world description, no obstacles, and one search algorithm.



Output Specifications

On every run, the program should output the number of nodes expanded in the state space, the length of the solution path, and the solution path (sequence of (x, y) coordinates) found. Reminder: a node is expanded when its successors are generated. Note that the same node may be expanded multiple times with some of the algorithms, in which case it should be counted multiple times. Each algorithm should terminate when it finds a solution path, so only the first solution that is found needs to be reported.

Below is an example of the output for each search algorithm (separate each output group using a blank line):

Robot World File: test.rwf
Room Size: 4 x 5
Number of Obstacles: 4
Robot Initial Location: (3,1)
Robot Goal Location: (0,4)

Search Method: Breadth First Search
Nodes Explored: 17
Solution Length: 9
Solution Path: (3,1) (3,0) (2,0) (1,0) (1,1) (0,1) (0,2) (0,3) (0,4)
Solution Time: 0.034


Search Algorithms

BFS - Breadth First Search - A simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on.

DFS - Depth First Search - Always expands the deepest node first in the current fringe of the search tree.  The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors.  As those nodes are expanded, they are dropped from the fringe, so the search "backs-up" to the next shallowest node that still has unexplored successors.

UCS - Uniform Cost Search - Similar to breadth first search except the nodes to expand next have the lowest path cost.  For UCS use the following cost function: Each move that continues along the same direction as the previous move should be assigned a cost of 1. Moves in the same axis but different direction are assigned a cost of 2.  Moves in a different direction are assigned a cost of 3.  This cost function will prefer long paths and paths with fewer turns.

GBFS - Greedy Best First Search - This search expands the node that is closest to the goal on the assumption that it will lead to a solution quickly.  The heuristic to be used in GBFS is the city block distance (sometimes called the Manhattan distance) from the current state to the goal state.  This strategy should always select the node that appears to the closest to the goal.  f(n) = h(n)

ASTAR - A Star Search - This search is similar to GBFS except it also considers the cost of reaching node n.  Use the same heuristic as in GBFS but consider the same city block distance from the current location to the initial node also.  f(n) = g(n) + h(n).

There are two options that can be also specified with the above search algorithms.

If the option NOBACK is specified, moves of the form n_i -> n_j -> n_i where n_i and n_j are states, are checked and discarded.  Such a circumstance occurs when the robot takes a step in one direction and then in the very next state it goes back to where it came from.

Duplicate nodes are identical configurations reached by different sequences of moves.  If duplicate nodes are found, the g(n) values should be compared and the node reopened if appropriate (e.g. if g(n) value is better than on a previous path, re-expand the node).  Duplicate nodes are always generated unless the NODUPS option is specified.

Helpful Hints

As is true in any programming task, it is wise to break your approach down into manageable steps. Below is one possible way to break this project down:

Decide how to represent the state. It is wise to implement a printing function for states, and to include the path leading up to the state as one of the state's fields.

Create instances of the initial and final states - these will be used to start the search and to determine when to end the search, respectively.

Write the operators and test them - simply define some state and apply the operators to them, making sure the output is correct.

Decide how to filter out operators that do not apply - for example, the robot cannot move left beyond the edge of the world. (HINT: A method that takes in a state and returns a list of operator names that apply is probably the most straightforward way to go.)

Decide how to filter out states that would cause a loop (when the DUPCHECK option is given), because they appeared earlier on the path leading up to this state.

Write a "generate successors" function that takes in a state and returns a list of states that can be reached with one operator rule application - your filtering method from the previous step will be used here.

Write a breadth-first search that takes in an initial state (or just uses the one you defined earlier) and returns the path from it to the final state, showing operator rule names and resulting states.

Implement best-first search. You will need to implement the heuristic function (h(n)) to estimate the cost-left-to-go. You will need to decide how to sort your queue.

Implement A* search. You will need to incorporate cost-so-far (g(n)) into the state.
One benefit of development in an object-oriented language is that it is easy to write methods and classes and test them one at a time. So, for example, when you've written your method to generate all successors, make up some state (feel free to sue the initial one, but you should make up others too), pass it to your method, and hand check the output to make sure it is correct. Using this strategy throughout your development of a solution is a good idea.
 

Sample Data Runs and Report

In addition to designing, developing, implementing, and testing your program, you will write a report discussing your project.  You are responsible for generating your own test data and arguing in your discussion that you have adequately tested the program.  You may wish to turn in output from testing runs to support the correctness of your program. If you do so, be selective in what you provide.

Several specific RobotWorld configurations will be posted on the web page approximately 24 hours before the due date for the assignment and you should turn in the results of your program when given these configurations.  The particular set of flags to use for each configuration will be given along with the configuration.

In your report, make sure you discuss the differences between the various search algorithms and heuristic functions. Are the heuristic functions admissible and/or consistent? What is the effect of turning on and off the two duplicate node checks?  Does your program perform as you expect it should given what you know about heuristic search?

The format of your report should include a title page, introduction and project description, a discussion on the algorithmic methods, a discussion on performance, and conclusions.  (Start each separate section on a new page).  Use graphs and charts to support your conclusions.  Be sure to answer and/or address the above questions.

Note the importance of the report in the overall grade and make sure you allocate adequate time for that in the assignment.

Deliverables

Please email your program source code, sample run files, and report file as attachments in an email to my departmental account. The report file should be in a file called prj2report.xxx where xxx is either txt, pdf, or doc.

You do not need to attach any data files, but you may if you think it will help explain how you proceeded.

All parts of this project must be turned in by 12:29:59 on Thursday, February 23. Turn in a hardcopy of your report.