Andrew Curtis and Dr. Randal Beard, Electrical and Computer Engineering

Unmanned Air Vehicles (UAVs) have become an important research topic in recent years. Military and civilian groups desire to use UAVs for several purposes, including surveillance, search and rescue, communications relays, and warfare. In the MAGICC Lab at BYU, we are researching low-cost methods of using miniature UAVs (wingspan of less than 2 meters) for these applications. We have developed a small autopilot to fly these UAVs and are able to give them commands by wireless communication from a laptop that is used as a ground station. With this research platform, we are able to easily test our methods and algorithms, and we have achieved much success in this endeavor.

One important research problem for miniature UAVs is path planning. Larger air vehicles typically fly at altitudes far above the surrounding terrain; therefore, planning paths between two points can be done with a single straight line path between the points. However, for miniature UAVs on missions that require being near the ground, we cannot ignore the terrain. Planning paths becomes especially difficult when planning in congested urban terrain. In such terrains, the UAVs have very little room to maneuver, and must restrict their flight paths to the area above roads and shorter buildings, but must avoid tall buildings. The path planning problem we are addressing is to develop an algorithm to quickly find paths through an arbitrary urban terrain. Path planning has been addressed in the research literature for decades. Much of this research has focused on path planning for robots that can stop at any time and change direction. A UAV, though, cannot stop in midair and has a limited turn radius. If these motion constraints are not considered in path planning, resulting paths might not be flyable.

We have found success with an algorithm developed by LaValle1, referred to as Rapidly exploring Random Trees (RRTs). This algorithm involves building a search tree of possible paths through the planning region. An important feature of RRTs is that they can take into account more motion constraints than other algorithms, so we have incorporated the constraints on UAV motion into the algorithm. The process is to pick a random point in the search space, choose the closest point already in the graph, then try to add a segment from this point toward the randomly chosen point. We test for collisions along the path and also perform extra collision testing at the turn, to make sure there will not be an unexpected crash. If the tests are successful, the segment is added to the graph, and the search continues until the graph reaches the goal position. This method has been successful, and we have published the results of this research2.

For this project, my goal was to improve upon this path planning process. The RRT algorithm has a few drawbacks. First, the RRT algorithm quickly finds a solution, but then does not have a good mechanism for modifying and improving upon that solution. Second, planning with straight line segments is fast, but we must perform extra collision testing because the UAV cannot perfectly track this path due to its flight constraints. It would be useful to be able to represent the exact path the UAV will take, so we can plan paths in more narrow areas. Finally, the planner is fast, but is currently not able to run in real time onboard the UAV. This feature would be useful in order to quickly re-plan a path during a mission.

The first problem was addressed by Frazzoli3 and we have adapted some of his work. He suggested that once the RRT algorithm finds a complete path, future tests should focus on only improving the path. Nodes that cannot possibly improve the current path are deleted, and exploration is focused on the best prospects. Using this technique gives us slightly better results.

The next problem is that straight line paths are problematic for collision testing. I researched the possibility of using Dubins curves4 to represent these paths. Dubins curves are combinations of minimum radius circles and straight lines that have been proved to be the minimum length path of constrained radius between two points with specified directions. Since UAVs have a minimum turn radius, Dubins curves can approximately model the path a UAV can fly. An example of a path using Dubins curves is shown on the right. I discovered that computing the length of these paths is much more intensive than computing the length of a straight line. Recently, I found some research into speeding up this computation5. Some of the published techniques were able to speed up the process by a factor of 10. However, additional techniques that were intended to be even faster turned out to have some flaws. So far, the advantages of the Dubins curves in collision detection are not worth the extra time it takes to compute them. If these additional techniques of computing the lengths of Dubins curves were investigated and the flaws removed, they could become a more useful tool in path planning.

My final goal was to implement this path planner in real time onboard a UAV. I was not able to achieve any significant increase in the speed of the path planner. Considering that the microprocessor onboard the UAV is much slower than the desktop computer where I ran the tests, we cannot currently expect the algorithm to be feasible on a UAV. An additional problem is that in order to plan paths through a terrain, the planner must have access to a terrain map; unfortunately, the autopilot lacks sufficient memory to hold such a map. A faster processor and a larger memory space on the autopilot would be necessary to complete this task. We will continue to do our path planning on the ground station and send the resulting path to the UAV. With some continued work, the methods I have studied could become useful in the future.

References

1. S. M. LaValle and J. J. Kuffner. Randomized Kinodynamic Planning. International Journal of Robotics Research, 20(5):378-400, May 2001.
2. J. B. Saunders, B. Call, A.Curtis, R. W. Beard, T. W. McLain. Static and Dynamic Obstacle Avoidance in Miniature Air Vehicles. In Proc. of “Infotech” Aerospace Conf., September 2005.
3. E. Frazzoli, M. A. Dahleh, and E. Feron. Real-time motion planning for agile autonomous vehicles. Journal of Guidance, Control, and Dynamics, 25(1):116-129, January-February 2002.
4. L. E. Dubins. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 79:497-516, 1957.
5. A. M. Shekl and V. J. Lumelsky. Classification of the Dubins set. Robotics and Autonomous Systems, 34(4):179-202, 2001.