An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles - Robotics Institute Carnegie Mellon University

An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles

Pankaj K. Agarwal, Kyle Fox, and Oren Salzman
Conference Paper, Proceedings of 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16), pp. 1179 - 1192, 2016

Abstract

We study a path-planning problem amid a set O of obstacles in ℝ2, in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a nearest obstacle in O. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let eps ∊ (0, 1]. Our algorithm computes in time O(frac{n^2}{eps^2} log (n/eps)) a path of total cost at most (1 + eps) times the cost of the optimal path.

BibTeX

@conference{Agarwal-2016-5298,
author = {Pankaj K. Agarwal and Kyle Fox and Oren Salzman},
title = {An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles},
booktitle = {Proceedings of 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16)},
year = {2016},
month = {January},
pages = {1179 - 1192},
}