Fall 2013
CS 582 – GEOMETRIC MODELING
October 22, 2013
Due Date:
Tuesday, November 26 at the start of class.
Submission Information:
Per instructions in the Programming Assignments information in the course web page. A short report in hard copy is required. The source and byte code files should be submitted using
submit –user cs582 –tag 582_5 A5.java otherSourceFiles classFiles
Goals and Approach:
The goals of this exercise are to introduce you to path planning with scenes defined by solid models. This is an important topic not just in robotics but also in other applications such as virtual environments. A secondary goal is to give you some experience in digging through a research paper. We will use a fairly simple algorithm called the Probabilistic Roadmap Planner, described in the paper
“Probabilistic roadmaps for path planning in high-dimensional configuration spaces”, L. E. Kavraki, P. Svestka, J.-C. Latombe and M. H. Overmars, IEEE Transactions on Robotics and Automation, Vol. 12, No. 4, pp. 566-580, August 1996.
This approach is especially good for robots with many degrees of freedom, but it actually works surprisingly well in many low-dimensional problems.
The paper is on line at http://ieeexplore.ieee.org .
Note that you need to be at a USC machine to be able to get to the pdf full text, unless you are an IEEE member with on-line privileges.
Description:
We will define a scene containing obstacles by using a modified version of the facilities we developed in Assignment 4. We will define primitive blocks, combine them by (regularized) Boolean operations, and move objects via transformations. Any named object defined in this manner can be used as a scene. We will replace the menu item Group with three others: Union, Difference and Intersection, which corrrespond to the regularized Boolean operations of CSG.
A Boolean operation menu asks for the names of two old and one new object and has semantics NewObject = OldObject1 + OldObject2. (Here + stands for one of the Boolean operators.) Note that Object arguments for both Transforms and the set operators may be primitives, moved objects, or composite objects, obtained from previous motions or set operations.
To make things simpler, we assume the robot is a point, and therefore its motion is translational. We only consider piecewise linear trajectories (composed of one or more line segments) and require that all motions be parallel to the principal axis, x, y, z.
The GUI is a simple extension of that of Assignment 4. We add a new menu, Plan, with two submenus Scene and Endpoints. Scene asks for an object name; the given object defines the current scene. As you will see, a scene determines the pre-processing or learning phase in the planning algorithm. Endpoints asks for two points in 3-D, which are the initial and final points of the trajectory.
The program is to compute a collision-free trajectory between the two points and display it. The initial and final points should also be displayed, e.g., as small boxes or small spheres. A new set of Endpoints erases the old trajectory and computes a new one for the same scene. A new Scene starts the process from scratch, erasing everything, running the learning phase, etc.
We add also to the Display menu a new submenu, Roadmap. This is an on-off switch. When on, we also display the roadmap constructed in the planning phase. This is especially useful for debugging.
Notes on the Algorithm:
The algorithm has a learning phase, and a query phase. Learning needs to be done only once per scene, and then many queries can be answered. Roughly, learning amounts to getting an approximation for the free space (i.e., the set of robot positions for which there are no collisions). We throw at the scene a bunch of random, uniformly distributed points and keep those that are not colliding with the obstacles. (This requires a point membership classifier to decide if a point robot is colliding with the scene’s obstacles – point classification will be covered in class soon.)
Then we use a fast local planner to connect these points (nodes) into a graph called a roadmap. An edge between two nodes of the roadmap means that there is a collision-free path between the points. The simplest local planner for our case is an algorithm that passes a line segment between the points and checks if the segment intersects the obstacles. (This requires a simplified line classifier, also covered in class.) However, this will generally not produce motions aligned with the axes, and some modifications are in order. You will need to figure out what to do for orthogonal paths. The roadmap can be extended, as described in the paper, but we may not need to do that for our problem.
The query phase connects the two given points to the same connected component of the graph, and then follows edges of the graph to get a complete path.
This was a very cursory description of the algorithm, which is not enough to understand the process completely. Read the paper. Note, however, that much of the later part of the paper is not relevant to our problem.
Also note that you can (and should) start working on the assignment immediately, before knowing how to implement point and line classifiers. There is a lot to do, such as managing roadmap graphs, etc.
