CSE 415 Winter 2006: A* Search
Due: Wednesday Feb. 1st at 11:59pm; email to Tyler
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 real 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.
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
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. Therefore,
you will need to code a utility function that determines if a
given line segment intersects a given rectangle. The heuristic function h should use the
straight line distance from the current vertex to the goal vertex, which can never
overestimate the true distance.
Hints: For some suggests regarding how to implement the collision detection, click here.
Testing
Your program should read the input data from a file. The format of the file
is as follows.
- The first line contains 2 (real) numbers separated by spaces. These
are the X and Y coordinates of the start state.
- The second line contains 2 (real) 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.
Two samples 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
plus at least one test data set that you design. You may share your
dataset with the class if it is an interesting one.
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.
Turn-in
- Please turn in your program/data/output electronically to Tyler at trobison@cs.washington.edu. Use a subject like 'CSE415 hw2 submission'.
- You can submit your assignment late for a 10% penalty (as described in the course policy), but only up to 1 week late for this assignment; it
must be submitted on or before feb 8th to receive any credit.
- Include all files
needed to compile your program. Also include any additional data (files) you
tested your program on. Please zip or tar them together.
- Include, perhaps in a text file, instructions on running the program; for java, it might be
"type 'javac *.java' to compile, and 'java RobotSearch data1' to run on data1", for instance. It doesn't
need to be lengthy or elaborate; it just needs to tell me how to run it. I should be able to run the
program on different data sets without having to read through code and recompile the program; please have a command-line interface,
or the equivalent, that allows a user to supply a data file.
- Please comment each method separately, describing its arguments, return value (if any), and,
most importantly, its purpose. Also comment any important regions of code within a method;
important loops or calculations that require explanation.
- As with the first assignment,
you may program in Java, C++, Lisp or a Lisp variant.
