Bi-objective path planning using deterministic algorithms

Path planning has become a central problem in motion planning. The classic version of the problem aims to find an obstacle-free path with the minimum length for a given workspace containing a set of obstacles and two sources and destination points. However, some real world applications consider maximizing the path clearance (i.e., the distance between the robot and obstacles) as the secondary objective. This bi-objective path planning problem has been studied using evolutionary and other heuristic algorithms which do not guarantee achieving Pareto optimal paths. In this paper, we first study this problem using deterministic algorithms. Next, we propose an efficient algorithm for the problem in the grid workspace. We then propose an O(n3) time algorithm for the problem under the Manhattan distance in a continuous workspace containing n vertical segments as obstacles. Finally, we show the obtained solutions are proper approximation for the problem under the Euclidean distance.