This assignment is due at 5pm on Tuesday, April 4th.
Warning: the displayer for this assignment requires tcl/tk and it's very hard to debug robot code without a displayer. So if you do this assignment off turing, you need to work on a system that has tcl/tk. The tcl/tk script is relatively simple, so it should not matter which version of tcl/tk you have.
For this assignment, you will complete a partially-built robot motion planner. This program plans paths for a polygonal robot which can translate but not rotate. It first computes the configuration space for the planning problem, i.e. enlarges the obstacles so that the robot can be shrunk to a point. It then divides free space into a set of vertical strips. Each strip is then divided into a set of free space cells. The cell structure is used plan a path through free space.
It's impossible to debug robot motion code without being able to display results graphically. Because our scheme code does not have built-in graphics, it writes files of graphics commands such as sample.dat. These command files can be displayed using the simple tcl/tk script display. Assuming that display lives in your current directory and that you have set its permissions so that it is executable, you would type:
prompt> ./display sample.dat&
The top line of the script contains the pathname of wish, the interactive shell for tcl/tk. If the script will not run and you are working somewhere other than turing, check that this pathname is correct for your tcl/tk installation.
The supporting code for this assignment contains code to write output files for key stages in the planning process. Therefore, you can do this assignment without understanding the displayer. However, if you wish to modify these display functions, that should be relatively easy.
The first line of the graphics command file must specify the size of the display window. Subsequent lines contain commands for drawing graphical object, such as lines, polygons, ovals, and text. You can probably deduce most of the command format by examining command files written by the existing display code. In fact, the commands are the same as those used in tcl/tk canvas objects, except that you don't have to specify the first two items (path=windowname and "create") required in a canvas command. The tcl/tk manual page (man canvas) contains a full set of commands and options you can give to them.
To run the planning code, you must load three files into your scheme:
The file robot-utils.scm must be loaded first. It contains geometric utility functions and definitions for all the record types required for the planner. You may modify the contents of this file, but you don't have to. If you do modify robot-utils.scm, remember that reloading this file redefines all the record types and makes previously-created objects out of date (unusable). Therefore, after you reload this file, you must reload the other two code files and rebuild any objects you have been manipulating.
The file robot-problems.scm contains three sample motion-planning problems.
The file robot-planner.scm contains partial code for the motion planning algorithm, to which you will be adding the final steps.
First, examine the sample planning problems and run the code for the first steps of the planner:
> (show-problem "foo.dat" *problem3*) > (define xxx (plan-path *problem3*)) > (show-c-space-problem "foo.dat" xxx) > (show-events "foo.dat" xxx)
The input problem consists of a set of walls defining the edges of the world. Outside the walls is solid rock, where the robot can't go. It also specifies the shape of the robot and the obstacles. The robot must be a convex polygon and each obstacle must be a convex polygon. The problem also specifies the starting and ending positions for the robot.
The code then enlarges each obstacle, moves the walls inwards, and shrinks the robot to a point. This is the configuration-space (c-space) version of the problem. A solution to the path planning problem is a path through c-space that does not touch any of the enlarged obstacles.
Each enlarged obstacle is still a convex polygon. However the enlarged obstacles may overlap one another. Moreover, parts of some obstacles may lie outside the walls. This shouldn't make a major difference to your code, if you write it correctly.
Finally, the code detects horizontal positions at which some interesting "event" happens in the obstacle structure. There are five types of events:
The displayer shows each event as a vertical line.
The first thing you must do for this assignment is to create a new robot planning problem of your own. This is really just an exercise in figuring out the problem format. Just be sure that your robot and each of your obstacles is convex.
Your second (and much larger) task is to complete the planner. There are four steps to fill in:
The hard work is in the first and second steps. The third and fourth steps are easy.
The existing planner code converts the input problem to a solution object. The solution object has a lot of fields, which are filled one by one as the planning process moves forwards. The solution object is then returned as the value of plan-path. This structure makes it easy to inspect intermediate states of the planning process.
The existing code has filled in some of the fields in the solution object. Your code should fill in the rest of the fields.
Before starting to write code, look through the geometric utility functions in robot-utils.scm. These functions do all the nasty equation solving and nasty algebraic tests required for your code. If you think you need to solve some nasty equations, re-check the list of utilities for something you can use to do the work for you.
Two adjacent events define a vertical strip. In this strip, the structure of free space is very simple. The strip is divided into pieces by the line segments which cross the strip. Each of these line segments is the side of a c-space obstacle.
An important constraint is that a line segment never starts or ends in the interior of a strip. Two line segments may touch one another at the boundary of the strip, but no line segments cross or touch in the middle of a strip.
The first step in your algorithm will convert the event list into a list of strip objects. Each strip object contains a list of divider objects, each of which is a line segment with some additional information. See robot-utils.scm for the details of the strip and divider data structures.
Your algorithm should scan through the problem from left to right. Since the event list is sorted by x-coordinate, you walk through the event list in order. At each point, the scan keeps a list of segments that cross the current x-position. At the start of the scan, you are off the lefthand side of the world and there are no segments in the list. As you encounter side-start and side-end events, you should add and remove segments from your segment list.
When the scan encounters an event, it should create a strip object containing the current list of active segments. This only applies, however, when the scan is between the left wall and the right wall delimiting the world. Outside the left and right walls, the scan should update the list of segments but not create any strip objects.
There may be several events at the same x-position. Your scan code must create only one strip boundary in such cases, i.e. not create zero-width strips. However, the start and end of a segment are always at different x-positions: prior code has removed vertical line segments from the event list.
When creating a new strip object, your code should convert the raw line segments into divider objects. This involves three computations
Finally, the list of dividers in each strip should be sorted by vertical position. (Use the scheme function sort-list.)
To decide whether a line segment is the top or the bottom of an obstacle, use the direction of the line segment. In the enlarged obstacles created by conversion to c-space, each obstacle boundary runs counter-clockwise around the outside of the obstacle.
The utility function y-intercept in robot-utils.scm is also useful for these clean-up operations.
There is no graphical display function for strips. However, you can tell if your strip structure is correct by inspecting the fields inside the scheme interpreter.
You now have a list of strips, each containing a list of dividers. This must be converted into a list of free-space cells (one common list containing cells from all strips).
To convert a strip into a set of cells, scan through the list of dividers. The list is ordered by vertical position. When you start the scan, you are outside the planning problem. That is, you are inside one obstacle: the solid rock outside the known world. As the scan encounters dividers, it should update how many obstacles it is in. The obstacle count goes up or down by one, depending on whether the divider is the top or bottom of an obstacle.
Since obstacles can overlap, it is possible to be in more than one obstacle at some scan positions. So the obstacle count may be larger than one. However, the obstacle count should never be negative.
When the obstacle count is zero, you have found the start of a piece of free space. The next divider should be the end of the same piece of free space. Create a cell object for this piece of free space, put it onto your output list, and continue the scan.
The cell structure can be displayed by calling show-cells on your solution object.
You now have a list of cells. To finish the cell representation, you must do two things:
The solution object contains a problem object. In this problem object are the start and end positions for the robot. You must look through the list of cells and find out which cells contain the start and end positions. This requires a function to determine whether a 2D point lies inside a cell.
Remember that a cell always has four sides. The left and right sides are always vertical. Use this to construct a simple algorithms for determining whether a point lies in a cell. Again, the utility function y-intercept is very useful.
To construct the neighbor list for each cell, you will need a function that takes two cells and reports whether they touch. It will be easier to build later parts of the planner if this function returns
Cells in the same strip are always separated by obstacles. Therefore, two cells that touch must touch along their left and right sides, which are vertical. Use this fact to design a simple algorithm to find the (vertical) shared line segment for two cells, assuming that they touch. Now adapt this algorithm to return #f if the cells don't touch.
You have now finished the hard work. To complete the planner, first build a simple breadth-first search loop to find a path from the start cell to the end cell. Each step in the path should move from a cell to one of its neighbors. This gives you the value for the cell-path field of the solution object. You can't display this path graphically, but you can tell if it's plausible by inspecting the cell values using the scheme interpreter.
Finally, convert the cell path to a list of vertices for a line-segment path. This is the value for the path field of the solution object. The function show-path can be used to display this path.
To understand why it's simple to create the line segment path, notice that each cell is convex. Therefore, if you connect any two points in the cell with a straight line, the line will lie entirely inside the cell. So a legal set of vertices for the line segment path are
You should submit:
This page is maintained by Margaret Fleck.