Abstract:
This paper describes a new approach for finding an approximate Euclidean shortest path with additional constraints, which we call a multi-criterion shortest path, between two given points that avoids vertical obstacles in a three-dimensional space. Currently, there does not exist any polynomial-time algorithm that solves this problem exactly, even without additional constraints. Furthermore, existing approximation algorithms mostly focus on reducing the running time at the expense of the accuracy. Here, we aim at increasing the accuracy of an approximate shortest path. To this end, our new algorithm is based on geometric principles to determine all obstacle segments and partial obstacle segments that are visible to each other. Using this information, we employ Mixed Integer Linear Programming to compute an approximate shortest path between two given points. We test our algorithm on a number of test cases and find that our method returns approximate shortest paths that are shorter than those returned by other currently available algorithms. Moreover, our method is more flexible since it allows users to define additional constraints or criteria in exploring different types of optimal paths.
