Thesis Work: Online UAV Exploration for UGV Route Planning
Project Description
The focus of my research is how to effectively explore an unknown region with a UAV planning for a ground vehicle. In the system, the UAV has a custom stereo system which generates a height map for planning. The ground vehicle has no sensors. Thus when the UGV needs to go somewhere in the unknown environment the UAV needs to find a safe path for a ground vehicle. My work is the online exploration for the UAV and maintaining the tempo of the operation by allowing the UGV to follow behind the UAV in an efficient manner.
System Details
- Hexacopter with custom 600mm baseline stereo camera, RTK gps, and Nvidia TX2
- Clearpath Jacakal with RTK Gps
- Ubiquiti Networks Mesh Wifi Radio with ~600mbps of bandwidth
Generation One Exploration Algorithm
The first generation of the exploration algorithm I developed leverages the knowledge of the boundaries between known space and unknown space also known as frontiers. Using the path planner built into the ROS package move_base (Dijkstra) an optimal plan is generated from the UGV to the goal allowing it to go through unknown space. With this plan, I identify where the plan crosses a frontier and use that as the exploration point for the UAV. This cycle repeats until a plan for the UGV can be made without going through unknown space.
Simulation Demonstration
The video below shows the algorithm working in a simulated environment. You can see the method works but you can also see some of the inefficiencies of this method when it goes back forth exploring some areas that are far apart. This video is sped up 10X.
Hardware Demonstration
The video below shows the algorithm working on hardware out in the field. The UAV is exploring around the side of a building. This video is sped up 3X. The green path is the plan generated for the UGV. The pink sphere is the frontier the UAV is going to explore.
Generation Two Exploration Algorithm
After seeing the strengths and weaknesses of the first generation exploration algorithm I decided that there was a better approach to use that would minimize how far the UAV travels compared to the first method. The main issue identified with the first method is its inability to see suboptimal paths. For example, when exploring around the side of a building we can easily see that you can go to the left and the right side of the building but Dijkstra's algorithm only sees the one path through the graph with minimum cost and we cannot identify the other way. Thus the aircraft might oscillate exploring both side of the building. Thus the main improvement for the second generation exploration must be the ability to identify suboptimal paths.
The method selected to handle this is the Rapidly-exploring random tree (RRT). Since this is a random sampling method of path planning we can identify suboptimal paths and find where they intersect the frontiers. My method is a modified version of the Bidirectional RRT. There are two trees exploring from the start and the goal respectively. The start tree is confined to the explored space and the goal tree is confined to unexplored space. Thus when we look for connections between the two trees we will find paths that intersect the frontiers. Thus we can generate multiple possible frontiers to explore and use a cost system to weight the best frontier to look at. The parameters analyzed for cost is how close the frontier is to the UAV and how close the frontier is to the goal.
The image to the right shows an example of the frontier identification. The orange tree is the tree going from the goal (bottom of image) and is constrained to unknown space (black). The blue tree is the tree exploring from the start and is constrained to explored space (green). The red is area identified as obstacles. The yellow lines are the connections between the two trees and the pink points are the frontiers identified.
Simulation Demonstration
The video below shows the new algorithm working in a simulated environment. You can see that the oscillation seen in the first method is gone but it is slightly less optimal in the frontiers it selects since it is a random sampling method. Overall I think this method works better from my qualitative observations so far. This will be evaluated quantitatively in the future. This video is sped up 10X.