Master’s Thesis: Multi-objective A* Route Optimization for Terrain Vehicles

Master’s Thesis in cooperation with KTH, the Royal Institute of Technology in Stockholm, Sweden.

Background

To investigate the extent for which the A* algorithm could find non-dominated routes, A* was compared to the NAMOA* algorithm for multi-objective terrain route optimization. NAMOA* is a multi-objective generalization of A*. NAMOA* has previously been proven to return all non-dominated routes. The algorithms were compared on a terrain route problem inspired by military planning. The minimization objectives were distance, travel time, accumulated forest volume, and accumulated likelihood of detection by static observers. The likelihood of detection by static observers depended on if the vehicle was within any observer’s line of sight. The algorithms were evaluated on four scenarios that were based on geodata. A* minimized an objective function created by weighting the minimization objectives. A* was executed multiple times with 200 randomized weights and 7 set weights to obtain a set of solution routes. The solution routes were compared geographically, through visualization of the Pareto front, and using the hyper volume indicator. The distribution of A* routes was similar to the distribution of NAMOA* routes. The A* routes were not always non-dominated, but close to non-dominated except for outliers. A possible preference for extremes in the likelihood of detection objective was identified for A*.

A picture from the thesis report showing alternate routes through terrain calculated using different optimization approaches.

Summary of the results

For the following results, the average refers to the mean of the evaluation scenarios. The hyper volume was on average 17.4% lower for A*, likely due to it having a lower number of routes compared to NAMOA*. The execution time of A* was on average 518 times faster than NAMOA*, which was expected since NAMOA* returns all non-dominated routes.

More information

Li, Lisa. Multi-Objective A* Route Optimization for Terrain Vehicles. 2020, http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-285951.