CS365: Artificial Intelligence

Consider a planar robot with N thin (stick-like) links. The end-effector configuration in the plane can be specified in 3 parameters (x,y,theta).

This robot has to operate in an environment with a bunch of line obstacles.(The lines can be strung up to become polygons).

Given a start and goal configuration, you need to find a path from start to goal that avoids obstacles on the way.

With a little care you should be able to test your code for upto N=15 or so for simple environments. Your results must work for 5 links (what is the minimum that is "redundant"?).

You should take two files as input: "robot.dat" which defines the robot AND the obstacles, and "goals.dat" which defines a series of configurations which are to be reached by the robot.

7 // Num of DOFs in robot
12 10 10 8 8 6 5 // numDOFs link lengths. Li > 1

4 // Num of line obstacles numObst
-12 5 // vertex[i].x, y coords
15 5

// line obstacle 2
15 10
-12 10

// line obstacle 3
20 5
40 5

// line obstacle 4
40 10
20 10

// the hard part here is to figure out the angles which will result in interesting poses of the robot.
// EACH ROW CONTAINS numDOFs angles, ie a configuration.
// The robot moves from one configuration to the next to the next etc.
// At the very least, a single START and GOAL should be there.

0 0 90 0 0 0 0 // numDOFs link lengths
90 0 0 90 0 0 0 // numDOFs link lengths
0 90 0 90 90 -90 0 // numDOFs link lengths

As a web page titled hw3/index.html with images showing path traces from your GUI.

The START and GOAL(s) configuration can be in BLUE and RED, say, and the path can be grayscale. You should show the trace for some poses in the path.

You are free to use standard routines (e.g. dijkstra's) - but Please CITE any source code / library you have used.

Code with strikingly similar performance (esp if erroneous) will be stringently evaluated for plagiarism.

A. The first thing you should do is design a Graphical interface that can show the robot and the obstacles. You can use python, java, tcl/tk or whatever. Develop this FIRST; Without it you cannot test anything.

B. We would recommend the Probabilistic Roadmap algorithm as covered in class, but you can also try other algorithms given in ch. 25 of R&N - e.g. cell decomposition or octrees. But those methods would be much more difficult to implement.