A-Star algorithm implementation for the traversing of Digital Elevation Maps
The objective of this study was to implement a solution for the global path planning of mobile robots based on terrain image data. This was to be done by applying the A* graph search algorithm on a graph extracted from a Digital Elevation Map (DEM). Considering the hypothetical scenario of this algorithm running on an embedded system, assumptions were made about the required software architecture and design decisions.
As a result of these assumptions, it was decided that the algorithm must be written in the C++ language, should work as a fully configurable independent software module and have some level of optimization. It was also concluded that the “shortest path” should be regarded in terms of “least energy required” as opposed to “shortest distance”.
The resultant implemented software module (named Altair after the 12th brightest star), is compiled as a Dynamically Linked Library and can be easily integrated into existing C++ code. The Altair library takes a DEM image in the form array, the start and ending coordinates as well at the dynamic variables, namely: Rolling coefficient, gravitational constant, vehicle mass and the vertical and horizontal pixel to physical distance proportions of the original image. The output of the library is an array of connected pixel coordinates, which define the energy wise optimal path. Optionally, the library can provide the physical length, as well as the energy requirement with and without regenerative breaking, of the found optimal path.
To prove the functionality of the Altair library, the software was subjected to both verification and validation measures. The verification was performed by software unit tests, implemented via the Google Test library. The validation was done by comparing the optimal path, to a line of sight path, in terms of energy requirements. This was executed for multiple randomized start and end coordinates.
The verification and validation measures proved that the A* algorithm was implemented correctly for the relevant task and was effective at finding optimal global paths based on topological images.
Top Right: Input image, Top Left: Start of A*, Bottom Left: Finished A*, Bottom Right: Contures of DEM
Log (spdlog lib) of energy requirements of path
Unit Test (GTest) of energy calculations