A Newton-like algorithm for the shortest path based on the method of evolving junctions

Shui-Nee Chow, Wuchen Li, Haomin ZhouCommunications 2016 · DOI

TL;DR

This paper introduces a significantly faster Newton-like algorithm for finding the shortest path around complex obstacles. By reformulating the problem as an angle minimization and employing an approximated Newton method, the authors achieve a dramatic reduction in computation time compared to existing methods, while still retaining the ability to find global solutions.

What Problem Does This Paper Address?

Finding the shortest path between two points in a space cluttered with obstacles is a fundamental problem in robotics, computer graphics, and beyond. When obstacles are simple polygons, traditional graph-based methods like Dijkstra's algorithm work well. However, for environments with non-polygonal obstacles (e.g., smooth curves), these methods fail. Existing approaches for such complex environments often rely on differential equations (like Hamilton-Jacobi equations) or optimization techniques that can be computationally expensive, especially with many obstacles, and may only find local minima. The "method of evolving junctions" (MEJ) was proposed as a way to handle these complex scenarios by converting the infinite-dimensional pathfinding problem into a finite-dimensional optimization problem. However, the original MEJ, while capable of finding global solutions, could still be slow. This paper aims to accelerate the MEJ by replacing its gradient-based update step with a more efficient Newton-like method.

Methods

The core innovation lies in a new approximated Newton-like algorithm that replaces the gradient flow in the existing Method of Evolving Junctions (MEJ).

Here's a breakdown of the key methodological aspects:

  • Method of Evolving Junctions (MEJ) Framework: The paper builds upon the MEJ, which models the shortest path as a sequence of line segments and boundary curves connecting "junctions" (points where the path meets an obstacle boundary). This transforms the problem into a finite-dimensional optimization problem over the coordinates of these junctions.
  • Reformulation as Angle Minimization: A novel aspect is reframing the shortest path problem not just as minimizing path length, but as minimizing the angle between line segments and obstacle tangents at junctions. This is achieved by posing the problem as minimizing $1 - g(\theta_i, \theta_j)^2$, where $g$ relates to the cosine of the angle between the line segment and the tangent.
  • Approximated Newton Method: Instead of using a gradient descent (which can get stuck in local minima and is slow), the paper proposes using a Newton-like method to directly solve the condition for a local minimizer. This involves solving for the roots of the second derivative of the cost function, $J^{(2)}(\theta) = 0$.
  • Approximated Jacobian: The Jacobian matrix for the Newton method is approximated using the third derivative of the cost function, $H(\theta) = \text{diag}(J^{(3)}(\theta))$. This simplification is crucial for computational efficiency.
  • Intermittent Diffusion (ID): The algorithm retains the intermittent diffusion component from the original MEJ. This stochastic element allows the solution to "jump" out of local minima, increasing the probability of finding the global shortest path. The Newton-like method is used when the diffusion coefficient $\sigma(t)$ is zero, focusing on finding local minima efficiently, while the diffusion is active to explore the solution space.

Datasets

Not discussed in the paper. The paper uses synthetic examples with defined obstacle shapes and positions for numerical experiments.

Key Insights and Ideas

  • Newton's Method for Pathfinding: Applying a Newton-like method, typically used for solving systems of equations, to the shortest path problem is a novel approach. It leverages the structure of the problem to find local minima much faster than gradient descent.
  • Angle Minimization as a Core Principle: Reframing the problem as minimizing the angle between path segments and obstacle tangents provides a new geometric intuition and a more direct way to derive the optimality conditions.
  • Dramatic Speedup: The combination of the Newton-like update and the MEJ framework leads to a significant reduction in computation time, as demonstrated by the numerical examples. This is a major practical improvement.
  • Retaining Global Optimization Capability: Crucially, the paper shows that by retaining the intermittent diffusion component of MEJ, the algorithm can still escape local minima and find the global shortest path, a significant advantage over purely deterministic Newton methods.

Key Results

  • Computational Speedup: The proposed Newton-like algorithm achieves a speedup of over 200 times compared to the previous MEJ method in one of the examples. For instance, it reduced computation time from 485.777 seconds to 1.75 seconds.
  • Efficient Local Minimizer Finding: The Newton method finds local minimizers in typically under 10 steps, whereas gradient flow methods often require many more.
  • Global Minimizer Probability: By using intermittent diffusion with a larger number of intervals ($m$), the probability of finding the global minimizer increases. For example, with $m=20$, the global minimizer was found 5 out of 10 times; with $m=50$, it was found 7 out of 10 times.
  • Superlinear Convergence: The paper theoretically proves that the algorithm converges superlinearly under certain conditions (smooth, non-zero curvature obstacles).

Limitations and Future Work

  • 3D Extension Complexity: Extending the Newton-like algorithm to 3D shortest path problems is challenging. The paper notes that junctions in 3D are described by two parameters, leading to more complex formulas and potentially non-degenerate Jacobian matrices, which would require significant modifications to the current approach.
  • Diagonal Jacobian Assumption: The current Newton-like algorithm relies on the Jacobian matrix of the second derivative being diagonal. It's unclear if this holds true for 3D problems.
  • Zero-Curvature Points: The theoretical convergence proof assumes no zero-curvature points on the obstacles. While the paper suggests adjustments for such cases (e.g., adding a small identity matrix to the Hessian), it's an area that might require further investigation for robustness.
  • Future Work: The authors suggest exploring the angle minimization viewpoint further for more efficient computation methods and investigating the extension to 3D.

Summary updated

BibTeX
@inproceedings{chow2016newton,
  author = {Shui-Nee Chow and Wuchen Li and Haomin Zhou},
  title = {{A Newton-like algorithm for the shortest path based on the method of evolving junctions}},
  booktitle = {Communications},
  year = {2016},
  doi = {10.4310/cms.2016.v14.n4.a15},
}

Loading related content...

Figure