Pruned Simulation-Based Optimal Sailboat Path Search Using Micro HPC Systems

Simulation-based optimal path search algorithms are often solved using dynamic programming, which is typically computationally expensive. This can be an issue in a number of cases including near-real-time autonomous robot or sailboat path planners. We show the solution to this problem which is both effective and (energy) efficient. Its three key elements – an accurate and efficient estimator of the performance measure, two-level pruning (which augments the estimator-based search space reduction with smart simulation and estimation techniques), and an OpenCL-based spmd-parallelisation of the algorithm – are presented in detail. The included numerical results show the high accuracy of the estimator (the medians of relative estimation errors smaller than 0.003), the high efficacy of the two-level pruning (search space and computing time reduction from seventeen to twenty times), and the high parallel speedup (its maximum observed value was almost 40). Combining these effects gives (up to) 782 times faster execution. The proposed approach can be applied to various domains. It can be considered as an optimal path planing framework parametrised by a problem specific performance measure heuristic/estimator.