Abstract:
This paper describes a new approach for finding an approximate Euclidean
shortest path with additional constraints, which we call a multi-criteria 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. Furthermore, existing approximation algorithms mostly fo-
cus on reducing the running time at the expense of the accuracy with respect to
the optimal length. Here, we aim at finding approximate shortest paths with re-
duced lengths. 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 fi nd 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 defi ne
additional constraints or criteria in exploring different types of optimal paths. Our
results can apply into path planning for unmanned aircraft vehicles or other sys-
tems that require a near optimal shortest path.