Path finder

2013-11-28

This demo uses a finite approximation of calculus of variations to optimize the blue path through a set of points. Click to add some obstacle points.

If your path gets stuck in a local minimum, you can try to generate a completely new path:

generate new path

Let’s call the blue points on our path ξ0,ξ1,ξ2,⋯\xi_0, \xi_1, \xi_2, \cdots and the pink obstacle points p0,p1,p2,⋯p_0, p_1, p_2, \cdots. Suppose the cost evaluated at a point ξ\xi is the sum of Gaussians centered at each pink obstacle point, evaluated at ξ\xi.

1 G(ξi)=∑jexp⁡(∥ξi−pj∥2σ2)\begin{aligned}G(\xi_i) = \sum_j \operatorname{exp}\left(\frac{\|\xi_i - p_j\|^2}{\sigma^2}\right)\end{aligned}

Then the overall cost is the sum of the individual costs, plus a term that penalizes the distance between every consecutive pair of path points.

2 cost⁡=∑i(G(ξi)+C∥ξi−ξi−1∥2)\begin{aligned}\operatorname{cost} = \sum_i \left(G(\xi_i) + C\|\xi_i - \xi_{i-1}\|^2\right)\end{aligned}

On each iteration of the algorithm, we simply perform a gradient descent step with some small step size, by simultaneously moving each path point. In this sense, path points are repelled from the obstacle points, but attracted to their neighbouring path points.