Tech News: An Introduction to Automatic Path Planning

Screenshot of a of a flight route planned automatically in the Germandrones Ground Station

Example of an automatically generated flight route.

Illustration of the algorithm’s path finding procedure

Illustration of the algorithm’s path finding procedure.

Germandrones is preparing a ground-station plug-in to generate routes considering any geofences and terrain features automatically. How does it work? And what are the benefits?

Creating a flight route is a complex process. In addition to connecting points in a two-dimensional map, aspects such as efficiency, maximum allowed altitude, minimum ground clearance, climb- or descent gradients and turn radii come into play when operating a fixed-wing drone.

Germandrones is developing a supplement to its ground control station that can find a safe flight path between specified start and end points. The new software is currently being tested in various projects and prepared for practical use.

The user will simply place two markers in the map and select a few parameters to determine how these will be connected (i.e., minimum, and maximum allowed altitudes etc.). Considering that the path planning process can take 10 – 15 minutes when done by a human operator while assembling the Songbird drone is done in two and a half minutes, this is a valuable addition to any time-critical use case such as emergency response. The tool considers all information such as geofences, the elevation profile of the terrain and the capabilities of the drone.

As a result, a series of waypoints with the appropriate coordinates and altitude values is generated. The path finding procedure of this tool is separated into a generation and a checking process, making it ready for future extensions.

At the core of the software, a path finding method is needed. Classical approaches such as Dijkstra's algorithm are not suitable as they require a discretized set of nodes to work with. In the present case, a sampling-based planning algorithm, more specifically, the Rapidly Exploring Random Tree Star Smart (RRT*-SMART) has been used which is suitable for nonconvex, multidimensional search spaces. It creates nodes first by randomly building a space-filling tree. In further steps this can be refined selectively, and multiple steps optimize the resulting path.

The RRT algorithm can reliably generate solutions, even if it is not always optimal depending on the amount of computing time. The main benefit of the RRT* version is an improved optimalization of the final path while still being able to ensure a fast convergence towards this solution. With the choice of RRT*-SMART, our software aims to generate optimal obstacle free paths in reduced execution time, compared to other RRT versions. It can easily be used over short or long distances with complicated configurations and additional hardware requirements.

Avoiding circular or polygonal geofences is guaranteed for both waypoints and the space between them. In other words, we make sure that no waypoint is within a geofence, but that the connecting path between two waypoints does not violate a geofence. This happens in every step of the algorithm without increasing its complexity at the same time.

Furthermore, during the path finding process the software makes sure that the altitude changes are feasible for our Songbird models. This concerns the capabilities of the drone in terms of how fast it can climb to a higher altitude or dive to lower altitudes. It is a highly important characteristic to design realistic and safe mission paths.

In addition to the above characteristic, our path planning tool takes into account lower and upper altitude boundaries, e.g., in case of a limited airspace approval.

This feature can be proved an important time saver in designing mission tasks in complex terrains where strict altitude constraints are applied.

Nevertheless, the last two safety mechanisms have been proved significantly restrictive for the algorithm in some cases. A combination of demanding terrain with a constricted altitude profile makes it difficult to determine safe areas for the drone to perform altitude changes. To deal with that as well as the extended execution time of the algorithm in those cases, special approaches have been adopted. The most important ones were an intelligent waypoint-sampling in easily accessed parts of the area and a general philosophy of minimum altitude changes during the mission.

Ultimately, this automatic mission planning tool can be used in various terrain types, with or without precise altitude limitations, for flying short or long missions. It packs the required software components to make sure that routes are obtained fast, are safe and are ready for use without further user-assistance in the GCS.

 

Your Contact:

Dr. Klaus Scho, CEO

Tel. + 49 (0)30 34 78 12 81

Back