2
$\begingroup$

I have recently come across this problem trying to visualise a certain economic model and I'm finding the solution is just beyond my reach. As far as I can tell there is a simplification of the problem which is easier and would still be good to have answered.

There are two moving point particles A and B on a Cartesian plane. Particle A is trying to reach B as quickly as possible, it can do so by applying acceleration in any direction. Its acceleration and speed have constant upper limits. Particle A knows the position and velocity of itself and of B, and can continuously[1] adjust its acceleration (which doesn't have to be continuous). What function of the particles' position and velocity should A use to reach and stop at B in as little time as possible?

In the simplest version B is moving with a constant velocity, which I think will produce a better result for the complete version too, in which B can have acceleration. For many nodes targeting each other my current approach of "accelerate as fast as possible to B's current position" quickly resembles chaos for a few particles targeting each other in a chain. I know why that's a poor approach, I just don't know how to make a better one.

If I haven't been clear enough, I'd be happy to provide a visualisation of the problem and my not-working solution.

EDIT: Pretty please work this all the way through. I've shown a lot of people this problem and the pattern has been for them solve it for a single dimension then tell me that it should be easy to just do it for both dimensions. It really isn't, there's almost certainly a derivation and optimisation equation in there somewhere since there are three unknowns: acceleration on each axis and time but only two equations to solve them with (position of both particles with respect to time). Another way of looking at it is that the dimensions can't be considered separately assuming they can move with maximum acceleration, since the magnitude of the acceleration is limited there is a trade-off there. As is probably clear from my fumbling explanations, I'm not math savvy enough to translate this idea into number and figures.

[1] Not actually continuous, since it runs on a computer in discrete (but tiny) steps.

  • 0
    Ah, I made a mistake in the description (now updated) - B has a constant velocity in the simplified version rather than A. Eventually I'll have to solve for them both having variable velocity. A wants to follow B, if B comes to a stop then it should settle at the same location. If there are n nodes targeting each other in a cycle they should converge eventually.2011-03-08

1 Answers 1

1

If B has constant velocity, then A can predict B's location at any point in time. A can then calculate the maximum distance it can cover in any amount of time, including the need to slow and stop. Let $a$ be the maximum acceleration of A and $v$ be the maximum velocity. So if A starts with zero velocity, it can accelerate at $a$ for a time span of $\frac{v}{a}$, covering distance $\frac{v^2}{2a}$ in the process. Then it can go along at $v$ as long as it wants, then decelerate and stop. So in time $t$ it can go $\frac{v^2}{a} + v(t-\frac{2v}{a})$ for time greater than $\frac{2v}{a}$. A can find a point where B will be at that time and go there. Some correction is needed for short times, but they should be easy to figure out.

Added in response to comment: Working in 2D, The position of B is $(B_x+v_{Bx}t,B_y+v_{By}t)$. Assume A starts at the origin. Then the distance from where A is now to where B will be is $\sqrt{(B_x+v_{Bx}t)^2+(B_y+v_{By}t)^2}$. So we solve for $t$ in $\sqrt{(B_x+v_{Bx}t)^2+(B_y+v_{By}t)^2}=\frac{v^2}{a} + v(t-\frac{2v}{a})$ and meet B there.

If A is moving at $t=0$, the same philosophy will work, but things are much messier.

  • 0
    Thing were indeed a lot messier. There's no such thing as 'how far we can go in a given amount of time' when you have initial velocity and you don't know where you need to go yet. I've worked it through quite a bit and arrived at a new question (http://math.stackexchange.com/questions/26172/find-minimum-in-a-constrained-three-variable-equation) which is more mathematical. When I get to the bottom of this I'll post the solution.2011-03-10