Algorithms for Robust Path-Planning

Master’s Thesis in cooperation with Saab AB and Chalmers University of Technology, Gothenburg, Sweden.

Background

Route optimization is a commonly studied field of optimization resulting in path planning algorithms. In this project, alternative route generation and robustness analysis were conducted for common road networks and off-road terrains.

This was done using Open Street Map data and high-resolution terrain data provided by Vricon and Lantmäteriet. Alternative routes were generated using a constructed 2-way search algorithm.

Robustness analysis was split into a physical robustness index and a non-physical robustness simulation. The generated routes conform to the constructed robustness-index, which is sensitive to weather conditions when traversing terrain.

The simulation is applied to the generated routes to visualize additional penalty times where the user can identify critical points along said route. This is done using a robustness simulation which creates obstacles along the chosen path and calculates the additional time needed.

A picture from the thesis report showing alternative routes generated by 2-way search.

Summary of the results

The final result is a complete Java program connected to Carmenta Engine, a map engine provided by Carmenta. The resulting program showed conceptually promising routes, providing reasonable alternatives while accounting for current weather conditions.

More information

Jonsson Damgaard, Thomas & Åkerlund, Jens. Algorithms for Robust Path-Planning. 2020. https://hdl.handle.net/20.500.12380/301942