8

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.

Community
  • 1
  • 1
Vesper
  • 18,599
  • 6
  • 39
  • 61
  • how do you know that general turns in 3D are effectively 2D? what about half-spirals etc? –  Jul 04 '16 at 08:19
  • @willywonkadailyblah This task doesn't care about cycles, and any single turn is able to be interpreted as 2D by using a 2D plane that contains all three points and two lines between previous, current and next point. So using more than two dimensions here is pointless, whie the exact expanded task can use as many dimensions as needed. – Vesper Jul 04 '16 at 09:48
  • I don't mean cycles, I mean shapes of turns which can't be represented as a planar curve, e.g. part of a spiral –  Jul 04 '16 at 10:52
  • @willywonkadailyblah I've got you, it's just the shape of path is irrelevant to the task, the object still needs to visit all the points in the path, even if its starting point is just beside the finish. – Vesper Jul 04 '16 at 11:46
  • Interesting variation. I would suggest using something like the N nearest neighbours to limit your search, pre-calculate the possible triples of points with their costs, and try to stitch those together something like a TSP or VRP. – TimChippingtonDerrick Jul 04 '16 at 13:42
  • @TimChippingtonDerrick That could be an approach to the related task, but not this one. Here the path is already defined, but the velocities aren't, and I want to know is there any efficient algorithm that would provide the optimal speeds at each line to achieve minimum total time. The costs for triples can be indeed precalculated, but stitching them together will produce contradicting results if their common edge's optimun speeds differ by more than acceleration value on either center point. – Vesper Jul 04 '16 at 14:17
  • @Vesper - could you please clarify the following statement in your question: *"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."*. Some example would be a very good idea. – Shital Shah Jul 19 '16 at 23:24
  • @ShitalShah The object travels in 2D space with a certain velocity, **v**. At each point on the path the object can change the velocity by a vector **dv** which length is limited by a value that's different per point. The resultant **v+dv** should point at the next path milestone, therefore, an object can arrive at this point with **v** limited by length as well, or else the set of valid vectors to redirect the object to the next path point will be empty. – Vesper Jul 20 '16 at 06:33
  • @vesper Let's say you have 4 points {p1, p2, p3, p4}. Are you saying we have |dv| attached to each points, say {1.1, 2, 0, -1.5}. So when you arrive at point p2, your velocity must increase by magnitude 2 in whatever is your next direction. Similarly when you arrive at p4 then velocity must decrease by -1.5 and then go towards whatever is your next milestone. Is this correct way to specify problem? Or are you saying that change in magnitude is dependent on where you come from as well (in which case there should be a matrix instead of array specifieng change in magnitude between pair of points) – Shital Shah Jul 20 '16 at 17:14
  • @ShitalShah The points are in 2D space, for example `{(0,0), (0,1),(1,1),(2,2)}` and dv's are all more than 0, say `{2.0, 2.0, 3.0}`, the last point's dv is irrelevant. Your velocity **vector** must change at each point by a **vector** of magnitude not more than the point's dv, AND must point to the next point in path, for example, at p2 the arrival vector is `(0,vy)` and departure vector sohuld be `(vx,0)` because p3 is to the right of p2. Original problem has a set of points and the task to find the fastest path, this problem is a fixed path and fastest passage. – Vesper Jul 21 '16 at 06:18
  • Sorry, I don't think I clearly understand your problem. It looks like now you are saying path is already given so I am confused what your output is. I would suggest write down concrete end-to-end example, clearly define your inputs, constraints and outputs. Keep example small but non trivial and show how would you solve it manually. – Shital Shah Jul 21 '16 at 10:25
  • The points provided are a *linear path* that has to processed left to right? Since the traveller has no choices about "next point", best time/speed would be obtained by optimizing speed between points, so you'd want to take current velocity and make it as large as possible. In this case, why isn't simply walking over the points, taking v+dv as the next speed, and computing the time to next point, then summing, produce the best answer? What is actually hard about this problem? – Ira Baxter Jan 15 '17 at 09:15
  • Where did you see linear @IraBaxter? The path is on a 2D grid, it has turns at waypoints. – Vesper Jan 16 '17 at 04:43
  • Yes, I understand the points are in N-space. I'm trying to verify that the specified *path* is a linear chain of points: first go to point1, then to point2, then.. finally to last point. Can the specified path be interpreted any other way? – Ira Baxter Jan 16 '17 at 04:45
  • ... this would be easier if you modified you question to show a short path, that correct answer, and explain why that correct answer is hard to get. – Ira Baxter Jan 16 '17 at 04:47
  • 2
    It's not so hard to calculate the maximum viable speeds for each segment, and the minimum viable speeds are always just > 0. It looks like figuring out exactly the best speeds between those bounds is pretty tough, but getting a numerical approximation to within a small error would be doable. – Matt Timmermans Jan 16 '17 at 20:45
  • Currently thinking 2nd order→convex, hill-climbing, steepest descent. – greybeard Jan 16 '17 at 21:10
  • @NelsonYeung Well, you cannot accelerate OR decelerate enroute from A to B, and then you have to get towards C which is to the side from vector A-B. It's not as if you're travelling on Earth, it's more like you travel from star A to B then to C, having laser acceleration stations on each star's orbits that propel you no harder than a given vector due to their own power capacity. This example is still flawed as you can do a slingshot maneuver around the star, but still. – Vesper Jan 17 '17 at 04:32
  • @MattTimmermans Agreed, and the question is exactly what algorithm(s) should I use to get the exact set of speeds at each segment if possible. I understand that this task can be solved numerically to a certain level, as it looks like optimizing the path by slight adjustments should eventually converge. – Vesper Jan 17 '17 at 04:36
  • @NelsonYeung There is quite a serious feat to determine the actual upper bound for each of the segments. For example, a path might contain a V-turn with the angle of more than 90 degrees, or two of them in a Z-shape, forcing the traveller to brake twice, and the length of the middle line in that Z would actually affect the entire path both before and after the Z-sequence. I think in your example you miss that you're approaching each but the first station with a certain speed already, so propelling along the path needs to account that you first need to brake, then propel to next target. – Vesper Jan 17 '17 at 09:52
  • Both these actions are limited by total magnitude of a vector, so if you're moving at the "speed limit" you have determined as the highest available on route from A to B, you will end up with speed from B to C close to zero, this will seriously cut into total time spent, making this solution far from optimal. – Vesper Jan 17 '17 at 09:54

1 Answers1

5

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)
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • @NelsonYeung Yes, that's the nonstandard notion of "acceleration" defined by this problem. – David Eisenstat Jan 18 '17 at 13:33
  • Hmm, I wonder what other values does `optimize.minimize()` generate. Gonna test this, at first it looks like it's the actual solution, albeit numerical instead of analytical. Anyway, the task is pretty hard to expect analytical solution to always exist. – Vesper Jan 19 '17 at 04:41
  • 2
    @Nelson I think you need to read the question again. The travel between two points IS in a straight line, and the acceleration IS instantaneous when you arrive at a point. The path SHOULD comprise of straight lines and non-physical sharp corners. – et_l Jan 19 '17 at 12:46