Multi-objective A' Route Optimization for Terrain Vehicles

Sammanfattning: 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 hypervolume 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 nondominated except for outliers. A possible preference for extremes in the likelihood of detection objective was identified for A'. For the following results, the average refers to the mean of the evaluation scenarios. The hypervolume 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.