Project Report
Student Name : Pranalee Jadhav
Student ID : 801030690
Title : Robot Path Planning Using Trapezoidal Cell Decomposition
Problem Statement :
Given an environment having convex and non-convex polygonal obstacles, the robot has to reach the goal state using a continuous, collision free and shortest path between start and goal state.
Model of robot used:
2D, single point, holonomic robot.
Programming language: Matlab
Objective:
1. Implement trapezoidal cell decomposition using the line sweep algorithm to decompose the environment into set of trapezoids/ cells (some of the trapezoids can have a side length as zero making them triangle)
2. Find Connectivity graph between the generated trapezoids/ cells.
3. Identify cells comprising start point and goal point respectively.
3. Find shortest path using the connectivity graph from start cell to goal cell.
4. Show the path from the start point to goal point.
Assumptions:
- Environment is a bounded rectangle.
- Obstacles are not overlapping and are without holes.
- Start and goal points are not outside of the obstacles and within the environment.
- Any side of the obstacle is not parallel to y-axis.
- Number of obstacles in the environment are finite.
Explanation:
Trapezoidal cell decomposition
It is useful to find obstacle-free path for robots.
To find obstacle-free path in a complex and non-convex environment, we can decompose the environment into set of convex polygons like triangles or trapezoids .
In this project, I am implementing trapezoidal cell decomposition as trapezoids consists of at least a pair of parallel sides which makes it easier to calculate path between neighbouring trapezoids as compared to triangles.
I am using sweep line algorithm for trapezoidal cell decomposition which is given below. In step 2 of below algorithm, we are finding type of vertex. There are total 6 types.
Type | Endpoints | Convex/Concave |
1 | One left and one right (in,out) | convex |
2 | One left and one right (in,out) | concave |
3 | Both right (out) | convex |
4 | Both left (in) | convex |
5 | Both right (out) | concave |
6 | Both left (in) | concave |
figure 1.1
Algorithm:
Input: Set of polygon, start and goal point
Steps:
- Create vertex, edges array from the set of polygons.
- Find the type of vertices.(refer figure 1.1)
- Sort vertices depending on x-coordinate value from left to right.
- Initialize segments array and trapezoids array.
- Iterate through set of vertices
- Sweep line upward and downward from current vertex until an obstacle or boundary is intersected.
- Identify set of intersection points.
- Update segments array by either deleting or adding obstacle segments depending on vertex type.(if vertex type is ‘out’, add corresponding segments in array. if vertex type is ‘in’, remove corresponding segments from array )
- Add trapezoids to trapezoids array, if any, generated.
- Generate connectivity graph by finding connections between trapezoids.
- Find midpoint of each vertical sweeping line segment.
- Iterate through trapezoids
- Find center of trapezoids.
- Connect trapezoid center to the midpoints of common edges between neighbouring cell.
- Identify start cell containing start point and goal cell containing goal point.
- Find shortest distance path between start and goal cell.
- For creating path, join start point to center of trapezoid of start cell and similarly join center of trapezoid of goal cell to goal point. Other points are already created in step 8b. Highlight the path with shortest distance.
Steps to run the code:
Open matlab->Run file main_draggablepolygon.m
In the figure window, select type of polygon (number of sides)
Click on ‘add a polygon’
Drag the polygon vertices to change polygon interface as per wish.
Drag start and goal points to required location
Click on ‘decompose environment’
After this step, you will see the shortest path from start to goal point.
External Libraries used:
Draggable library to create interactive environment that allows draggable polygons in user interface.
Challenges faced:
- Finding sweep line algorithm. Many Textbooks and online resources only explains theoretical concept of trapezoidal cell decomposition and sweep line algorithm but not the steps of implementation.
- Motion path planning libraries like Klampt were not compatible with my Mac OS.
- Learning Matlab.
Scope of the project:
As mentioned in list of assumptions, it will not work for obstacles with holes and if any side of the obstacle is parallel to y-axis.
Future Scope:
Efficiency of the algorithm can be improved by merging neighbouring trapezoids if possible. These new cells are called ‘Boustrophedon Cell’. As number of cells decreases, path finding becomes easier and faster.
Summary:
Thus, I have successfully implemented Trapezoidal cell decomposition and satisfied the objective as submitted in the project proposal. I successfully tested with varied set of obstacles. I referred technical papers, textbooks to understand the concepts of algorithm which helped me in implementing the algorithm. I understood the drawbacks of the algorithm, like, for obstacles with side parallel to y-axis, it is better to use other algorithms like approximate cell decomposition, voronoi diagram.
Apart from this, I enjoyed programming in Matlab which was new to me.
References:
- Robotic Planning and Kinematics by Francesco Bullo and Stephen L. Smith Version v0.91(e) (11 Apr 2016).
- http://user.ceng.metu.edu.tr/~akifakkus/courses/ceng786/hw3.html
Screenshots:
Webpage Link:
or
https://lee0392.blogspot.com/2018/04/robot-motion-planning-project.html