Details

This Demonstration determines the path for a polygonal robot that can move inside a bounded workspace populated by polygonal obstacles. Motion planning requires determination if a given path would cause a collision with an obstacle. Planning in the workspace is challenging because collision checks apparently require sweeping the polygonal robot along the path and continuously checking for collision. A common trick in motion planning is to perform the planning in the configuration space for the robot. In the configuration space, the robot's configuration is represented by a point at its center . The polygonal obstacles map to polygonal obstacle regions in the configuration space. These obstacle regions are calculated using the Minkowski sum. The shortest path is then the line from the initial configuration to the destination configuration that does not intersect the obstacle regions in the configuration space. This same line represents the shortest path in both the configuration space and the workspace.

A valid path for a 2D robot in a 2D environment can be computed in four steps.

1. Check whether the robot's initial or final position collides with or enters any obstacle or is out of the workspace. If so, then there exists no possible path.

2. Compute the Minkowski sum of all the obstacles and the inverse Minkowski sum of the boundary. The Minkowski sum is the polygon generated from the robot and the obstacle such that the robot centroid can move along this polygon without colliding with or entering the obstacle. Computing the Minkowski sum requires that the robot and the obstacles be convex polygons.

3. Draw visible bitangent lines from the vertex of each Minkowski polygon and the centroids of the robot's initial and final positions. Bitangent lines are the lines whose ends are reflex vertices. Reflex vertices are the vertices of the polygons whose exterior angles are greater than (also called convex vertices). To obtain the visible bitangent lines, calculate the visibility graph and compute the intersection of the visibility graph and the bitangent lines. Form a graph of the visible bitangent lines and the Minkowski polygon lines.

4. Determine the shortest path from the generated graph using the A* search algorithm. References

[1] S. M. LaValle, Planning Algorithms, New York: Cambridge University Press, 2006.

[2] D.-T. Lee, "Proximity and Reachability in the Plane," Ph.D. dissertation, University of Illinois at Urbana-Champaign, Illinois, ProQuest Dissertations Publishing, 1978 7913526.

[3] Wikipedia. "Visibility Graph." (May 1, 2020) en.wikipedia.org/wiki/Visibility_graph.

[4] Wikipedia. "A* Search Algorithm." (May 1, 2020) en.wikipedia.org/wiki/A*_search_algorithm.