Minimize the time spent traveling along the designated path

Question

This question is related to this ; it was obtained from optimizing the path over a set of points. The situation here is this: the object moves along a selected path containing a list of two-dimensional points. (Perhaps more Ds, but since each rotation is technically 2D, this will be solved for two measurements.) At each point, this object can change its speed with a vector whose maximum length is predefined (assigned to the point). Speed ​​at the end of the path does not matter. The question is how to determine the minimum time spent traveling along this path. Is there an efficient algorithm for this task? A greedy algorithm may ultimately cause the object to slow down the scan in case of specially prepared data or even not make the object able to move to the next designated point. The inverse greed algorithm is also erroneous with the same error that it is not always convenient to reach the end at maximum speed.

Example: point vector: {(0,0), (0,1), (1,1), (2,2)} , and the maximum length is {2.0, 2.0, 3.0} . The point moves, for example, at the point (0,sqrt(2)) from p1 to p2, then at (sqrt(2),0) from p2 to p3 and (s,s) at any maximum speed s from p3 to p4. And this may be a suboptimal solution, say, you slow down by 0.01 from p1 to p2, which allows you to accelerate the transition from p2 to p3, and then to another tad in p3-p4, and the possible total time is less than this set of speeds.

Answer 1

This is a convex optimization problem solvable by common non-linear 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)