Minimize time spent when travelling a designated path

Question

This question is related to this one, it was derived from optimizing the path over a set of points. Situation here is as follows: An object travels a designated path consisting a list of 2D points. (More Ds are possible, but since each turn is technically 2D, solving for two dimensions will do.) At each point this object can change its velocity by a vector which maximum length is pre-determined (assigned to a point). Speed at the end of path is irrelevant. The question is, how to determine the minimal time spent travelling this path? Is there any efficient algorithm for this task? A greedy algorithm can eventually make the object slow down to a crawl in case of specially prepared data, or even not making the object able to turn to its next designated point. A backward-greedy algorithm is also flawed with the same error, it's not always good to reach the end at maximum speed.

An example: Point vector is: {(0,0), (0,1), (1,1), (2,2)} and maximum length vector is {2.0, 2.0, 3.0}. The point travels for example at (0,sqrt(2)) from p1 to p2, then at (sqrt(2),0) from p2 to p3, and with (s,s) at whatever maximum speed s is from p3 to p4. And this might be a suboptimal solution, say you slow down by a 0.01 from p1 to p2, allowing to speed up by a tad from p2 to p3, then by another tad at p3 to p4, with possible total time being less than by this set of speeds.

Answer 1

This is a convex optimization problem, solvable by common nonlinear optimization libraries. In SciPy:

import numpy as np
from scipy import optimize

points = np.array([[0., 0.], [0., 1.], [1., 1.], [2., 2.]])
movements = np.diff(points, axis=0)
lengths = np.linalg.norm(movements, axis=1)
directions = movements / lengths[:, np.newaxis]
max_acceleration = np.array([2., 2., 3.])

fun = lambda x: np.sum(lengths / x)
x0 = np.repeat(.5 * np.amin(max_acceleration), len(movements))
bounds = [(0., max_acceleration[0])] + [(0., None)] * (len(movements) - 1)
constraints = [
    dict(
        type='ineq',
        fun=lambda x, j: max_acceleration[j + 1] - np.linalg.norm(x[j] * directions[j] - x[j + 1] * directions[j + 1]),
        args=(i, )) for i in range(len(movements) - 1)
]
x = optimize.minimize(fun, x0, bounds=bounds, constraints=constraints).x
print(x)