CSE 415: Introduction to Artificial Intelligence

Spring 2014

HW Assignment 2 (Program): 25 pts
Turn In Here
Download the skeleton code here:
A* Skeleton is removed Due Friday, May 2 at 11:59pm, late date Sunday, May 4 at 11:59pm

Problem Description

The above picture shows the Trilobot Mobile Robot from Arrick Robotics, advertised to be intended for AI research and education, so we chose him to represent this assignment. He can move around his environment and pick up things, and he uses informed search, as opposed to a blind search.

This homework assignment is to program an A* heuristic search to allow an agent to compute the shortest path from a start point to a goal point that goes around obstacles. The scenario of this problem is that the agent is located at point A and he needs to get to point C. He can move to any of a finite set of points in his environment. However, there are also a set of obstacles, so he cannot move directly from A to C, but must instead avoid the obstacles. The points in the space have integer coordinates (x,y) and are just the vertices of the obstacles. To make the problem a little computationally simpler, we will limit the obstacles to be rectangles.

The agent wants to plan a path from A to C that does not cut across any of the obstacles. A move must be from some vertex I to another vertex J (the robot will never be at a point other than a vertex, unless it is moving from one vertext to another). I and J may be on the same rectangle or on two different ones. He is allowed to move along an edge of an obstacle, just not through it.

Implementation Tips

For the A* algorithm, you will need an Open list and a Closed list. The Open list contains states that have been generated and not yet expanded. The Closed list contains states that have already been expanded. Each state contains at least the following:

the coordinates of a point
the g-value cost of the path from the initial state to this state
the h-value that estimates the cost from this state to the goal
the f-value that is the sum of these two
a list of the successors of this state (will be empty till the state is expanded)
the parent state

Things to remember during the implementation:

The possible operators at each state are just the moves to any of the other states. Many of them will be illegal, because the line from the current state to the other state intersects a rectangle. We have provided a function (check find_valid_move in the skeleton code) that determines if a given line segment intersects a given rectangle. Use this function to determine if the next state is valid from the current state or not. Call the function once for each state and generate a list of all valid next states.
The heuristic function should use the straight line distance from the current vertex to the goal vertex, which can never overestimate the true distance.
Optional: As discussed in the class, you have to retrieve the lowest f-value node from the Open list and expand it. We have provided a heap implementation (here) which can perform the retrieval in O(1) time. However, using this code is completely optional. You can always use a for loop and find the lowest f-value iteratively in O(n) time.

Testing

Your program should read the input data from a file. The format of the file is as follows.

The first line contains 2 (integer) numbers separated by spaces. These are the X and Y coordinates of the start state.
The second line contains 2 (integer) numbers separated by spaces. This is the goal state.
The third line contains 1 (integer) number. This is the number of obstacles.
Each of the remaining lines gives the position of an obstacle. The line contains 8 numbers, representing the X and Y coordinates of each corner of the obstacle (which is rectangular) in clockwise order.

The provided skeleton program includes code for reading input file and generating different useful python lists. Check that carefully and try to understand all the list structures before you start writing your own code.

Two sample input files are provided - A simple dataset (annotated with comments, picture), and a more difficult one (annotated with comments, picture). First try the very simple one and then the more difficult one. You may test on your own data sets, too, if you desire.

Results

Your solution will be the minimal path from the start state to the goal state that does not intersect the obstacles. You should output both the path and its cost. The path can be found by following the parent pointers backward from the goal state. Note that because of possible floating point differences, the costs you get may vary according to what machine and language you use. One sample output format for the simple dataset is provided here. Try to follow this format as closely as possible.

Turn-in

You should turn in the following:

your well-commented code
the solutions your program finds in the above given format.

Evaluation

25 points total, 15 for a working program, 2 for solution to the simple data set, 5 for solution to the difficult data set, 3 for code and comments.