CGAL users discussion list

[Suryajith Chillara <>]

Problem Statement

Given a polygonal robot Q, which can translate (but not necessarily rotate) in a room cluttered with polygonal obstacles, maintain a data structure that can efficiently answer queries of the following form: Given a start position s of some reference point in Q and a goal position g, plan a collision-free motion of the robot from s to g.

The feed is done in two steps. First, the user uploads the geometric data that describes the work space. Then, the user uploads the queries in forms of pairs of start and goal positions - a pair at a time. For each pair the geometric description of the collision-free path is computed and offered to the user. The web page can illustrate the workspace, the queries, and the obtained solutions.

The user can choose values for several parameters, such as the quality of the path (e.g., short, high-clearance, shortest subject to prescribed clearance) and whether the robot can touch the obstacles.

 

Input:

1. The start position s and the goal position g with respect to a particular reference frame agreed upon earlier.
2. The dimensions of the polygonal robot.
3. A set of Obstacles S = { P₁, P₂, P₃ ... P_k}.
4. Clearance allowed.

Output:

1. The path in the form of list of edges.
2. An image describing the shortest collision free path.

Notation:

R(x,y) or simply R : The robot with its co-ordinates or stated otherwise.

C(R) : Configuration space ( the parameter space of the robot ).

C_forb(R,S) : Points in the configuration space corresponding to placements where the robot intersects one of the obstacles in S .

C_free(R,S) : Free space where the robot can move without obstacles.

Methodology:

The motion planning problem for a translating, convex, polygonal robot R to the case of a point robot by computing the free configuration space C_free . The reduction involves computing the Minkowski sum of −R, a reflected copy of R, with each of the obstacles, and taking the union of the resulting configuration-space obstacles. This gives us a set of disjoint polygons, whose union is the forbidden configuration space.

ComputeFreespace(S)
Input. A set S of disjoint polygons.
Output. A trapezoidal map of Cfree (R, S) for a point robot R.
1. Let E be the set of edges of the polygons in S.
2. Compute the trapezoidal map T(E) with algorithm TrapezoidalMap.
3. Remove the trapezoids that lie inside one of the polygons from T(E) and return the resulting subdivision.

One of the methods is by creating a trapezoidal map T(C_free ) of the free configuration space C_free . For a point robot, C_free is simply the empty space between the obstacles, so this is rather easy. The key idea is to replace the continuous work space, where there are infinitely many paths, by a discrete road map G_road , where there are only finitely many paths. The road map that can be used is a plane graph with nodes in the centers of the trapezoids of T(C_free ) and in the middle of the vertical extensions that separate adjacent trapezoids. The nodes in the center of each trapezoid are connected to the nodes on its boundary. After finding the trapezoids containing the start and goal position of the robot, a path is in the road map between the nodes in the centers of these trapezoids by breadth-first search.

Because breadth-first search is used, the path that is found uses a minimum number of arcs in G_road (a road map through the free space for the motion) . This is not necessarily a short path, because some arcs are between nodes that are far apart, whereas others are between nodes that are close to each other. An obvious improvement would be to give each arc a weight corresponding to the Euclidean length of the segment connecting its incident nodes, and to use a graph search algorithm that finds a shortest path in a weighted graph, such as Dijkstra’s algorithm. Although this may improve the path length, its still not the shortest path.

Any shortest path between pstart and pgoal among a set S of disjoint polygonal obstacles is a polygonal path whose inner vertices are vertices of S.

With this characterization of the shortest path, a road map can be constructed to find the shortest path. This road map is the visibility graph of S, which is denoted by G_vis (S). Its nodes are the vertices of S, and there is an arc between vertices v and w if they can see each other, that is, if the segment vw does not intersect the interior of any obstacle in S. Two vertices that can see each other are called (mutually) visible, and the segment connecting them is called a visibility edge.

NOTE: the endpoints of the same obstacle edge always see each other. Hence, the obstacle edges form a subset of the arcs of G_vis (S).

The segments on a shortest path are visibility edges, except for the first and last segment. To make them visibility edges as well, we add the start and goal position as vertices to S, that is, we consider the visibility graph of the set S^∗ := S ∪ {s , g }. By definition, the arcs of G_vis (S^∗ ) are between vertices which now include s, the start position and g, the goal position that can see each other.
The shortest path between pstart and pgoal among a set S of disjoint polygonal obstacles consists of arcs of the visibility graph G_vis (S^∗ ), where S^∗ := S ∪ {s,g}.

ShortestPath(S, s, g)
Input. A set S of disjoint polygonal obstacles, and two points s, the start position and goal position in the free space.
Output. The shortest collision-free path connecting start and goal positions .
1. G_vis ← VISIBILITY_GRAPH(S ∪ {s,g})
2. Assign each arc (v, w) in G_vis a weight, which is the Euclidean length of the segment vw.
3. Use Dijkstra’s algorithm to compute a shortest path between the start and final points in G_vis .

Let S be a set of disjoint polygonal obstacles in the plane with n edges in total. (Algorithm ShortestPath needs to compute the visibility graph of the set S^∗ , which includes the start and goal position. The presence of these ‘isolated vertices’ does not cause any problems) To compute the visibility graph of S, we have to find the pairs of vertices that can see each other. This means that for every pair we have to test whether the line segment connecting them intersects any obstacle.

VisibilityGraph(S)
Input. A set S of disjoint polygonal obstacles.
Output. The visibility graph G_vis (S).
1. Initialize a graph G = (V, E) where V is the set of all vertices of the polygons in S and E = 0.
2. for all vertices v ∈ V
3.     do W ← VisibleVertices(v, S)
4.          For every vertex w ∈ W , add the arc (v, w) to E.
5. return G

A vertex w is visible from p if the segment pw does not intersect the interior of any obstacle. Consider the half-line ρ starting at p and passing through w. If w is not visible, then ρ must hit an obstacle edge before it reaches w. To check this we perform a binary search with the vertex w on the obstacle edges intersected by ρ. This way we can find out whether w lies behind any of these edges, as seen from p. (If p itself is also an obstacle vertex, then there is another case where w is not visible, namely when p and w are vertices of the same obstacle and pw is contained in the interior of that obstacle. This case can be checked by looking at the edges incident to w, to see whether ρ is in the interior of the obstacle before it reaches w.)

While treating the vertices in cyclic order around p we therefore maintain the obstacle edges intersected by ρ in a balanced search tree T. (Edges that are contained in ρ need not be stored in T.) The leaves of T store the intersected edges in order: the leftmost leaf stores the first segment intersected by ρ, the next leaf stores the segment that is intersected next, and so on. The interior nodes, which guide the search in T, also store edges. More precisely, an interior node ν stores the rightmost edge in its left subtree, so that all edges in its right subtree are greater (with respect to the order along ρ) than this segment eν , and all segments in its left subtree are smaller than or equal to eν (with respect to the order along ρ).

Treating the vertices in cyclic order effectively means that we rotate the half-line ρ around p. The status of the rotational plane sweep is the ordered sequence of obstacle edges intersected by ρ. It is maintained in T. The events in the sweep are the vertices of S. To deal with a vertex w we have to decide whether w is visible from p by searching in the status structure T, and we have to update T by
inserting and/or deleting the obstacle edges incident to w.

Algorithm VisibleVertices summarizes the rotational plane sweep. The sweep is started with the half-line ρ pointing into the positive x-direction and proceeds in clockwise direction. So the algorithm first sorts the vertices by the clockwise angle that the segment from p to each vertex makes with the positive x-axis. To be able to decide on the visibility of a vertex w, we need to know whether pw intersects the interior of any obstacle. Hence, the obvious choice is to treat any vertices that may lie in the interior of pw before we treat w. In other words, vertices for which the angle is the same are treated in order of increasing distance to p.

VisibleVertices(p, S)
Input. A set S of polygonal obstacles and a point p that does not lie in the interior of any obstacle.
Output. The set of all obstacle vertices visible from p.

1. Sort the obstacle vertices according to the clockwise angle that the half line from p to each vertex makes with the positive x-axis. In case of ties, vertices closer to p should come before vertices farther from p. Let w₁ , . . . , w_n be the sorted list.
2. Let ρ be the half-line parallel to the positive x-axis starting at p. Find the obstacle edges that are properly intersected by ρ, and store them in a balanced search tree T in the order in which they are intersected by ρ.
3. W ← {}
4. for i ← 1 to n
5.     do if Visible(w_i ) then Add w_i to W.
6.         Insert into T the obstacle edges incident to wi that lie on the clockwise side of the half-line from p to w_i .
7.         Delete from T the obstacle edges incident to wi that lie on the counterclockwise side of the half-line from p to w_i.
8. return W

Visible(w_i )
1. if pw_i intersects the interior of the obstacle of which wi is a vertex, locally at w_i
2.     then return false
3.     else if i = 1 or w_i−1 is not on the segment pw_i
4.         then Search in T for the edge e in the leftmost leaf.
5.             if e exists and pwi intersects e
6.                 then return false
7.                 else return true
8.     else if w_i−1 is not visible
9.         then return false
10.       else Search in T for an edge e that intersects w_i−1 w_i .
11.           if e exists
12.               then return false
13.               else return true

Implementation:

Step 1: Computing Minkowski sums (16th May to 24rth May)

This can be done using the existing minkowski_sum_2  using the Polygon_2<Kernel,Container> class-template.

Step 2: Computing the free configuration space(C_free) (24rth May to 4rth June)

Computing the free space using already existing trapezoidal decomposition algorithms using the algorithm explained above. Here clearance should be taken into consideration.

Step 3: Visibility graph generation (5th June to 25th June)

Using the Boost Graph Libraries, the graphs can be handled using the algorithms as explained above.

Step 4: Shortest collision free path generation (25th June to 3rd July)

Given the graph and the initial and final nodes, dijkstra's shortest path algorithm(which is a part of BGL) can be applied.

Step 5: Creation of a plone module (4rth July to 12th July)

I at the moment am not very familiar with the plone module generation but do have a decent idea of plone management. Since I already am familiar with Python, the creation of the module shouldn't be difficult. Plone as far I understand and used, uses Python for most of it module dev and not PHP. I shall look into this issue.

Step 6: Rendering the configuration space (12th July to 17th July)

One of the best ways to give the user the solution is in a graphic format. For this already existing opengl libs can be used to render the image at the server end and then send the image via the web.

Step 7: Import of the shortest path data and the image (17th July to 21st July)

Completion of the module by importing the the shortest path data which was in the form of an edge list and an image.

Step 8: Testing, debugging and documentation (21st July to 9th Aug)

Problems that might arise:

The width of the robot may be width of the path at a certain point, Then the clearance of the maximal robot's width has to be taken into consideration. I am still trying to come up with an algorithm to tackle that based on edge intersections with the graph.

Statement of commitment:

If selected to work on this problem as a part of GSoC 2010, I shall work full time on this problem until it gets finished.

Personal data:

I am Suryajith Chillara, a Final year undergraduate at Indian Institute of Technology, Kanpur.

Email:

Address:

125, Tungabhadra, National Games Village, Koramangala, Bangalore-560045

A list of relevent courses :
1.Introduction to programming
2.Linear Algebra
3.Real and complex analysis
4.Introduction to algorithms and Data structures
5.Discrete Mathematics
6.Computer Aided Engineerng Design
7.Computational Geometry

I have completed almost all of these courses with a good performance.

List of the most important software projects contributed and success.
None. Most of my coding has been done for the research problems that I have encountered.

Which are your best skills in terms of programming and scientific computing?

Most of my research work has been coded in C/C++ which made me very much familiar with these languages. I have also used Python extensively with SciPy and NumPy packages for fast prototyping of some functions or algorithms which would later be written in C/C++ to be included in the main code base.

In general what is your taste in terms of programming? language, methodology, team work, etc.
I taught myself C/C++ programming 5 years ago where the first few years I have coded C++ in a C style as I was not very familiar with the OOP and the generic programming paradigms. Later as I slowly started realizing the true potential of C++ when I started learning the use of STL and the auxiliary boost libs.

I have also used Python a lot recently for fast prototyping and testing of some of the numerical algorithms. I have used the SciPy and NumPy packages a lot. I have been working on. I also started learning LISP for  its rich exact arithmetic features, an early view of OOP paradigm etc.

Is there anything that prevents you from working full time on the project during the program period?
None.

How do you see your involvement after the program ends? Do you see yourself pushing the project further, or do you see yourself contributing to other CGAL projects?

As I wish to do my grad studies in the field of Computational Geometry and Geometric modeling, it would provide me a great opportunity to contribute for a very long extended period of time.

Are you more interested in the theory/scientific aspect of CGAL, or do you feel more like a hacker?
In actuality I like both the systems. I love hacking through the code and adding some more theorized features of scientific importance.

What are your long-term wishes in terms of job ?
As I did not get through grad school admissions this year ( I have only applied to IISc, Bangalore), I wish to get some job for an year to sustain myself and then apply for the grad studies next year.