Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is B also changing velocity? Is B actively trying to avoid being caught? Does A want to stop at some point where B is, or to match velocities with B? Certainly B can avoid A stopping at its position by keeping moving fast enough that A can't stop in one time step. –  Ross Millikan Mar 8 '11 at 15:19
    
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. –  ucclaw Mar 8 '11 at 15:43
add comment

1 Answer 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.

share|improve this answer
    
Yeah, I got something like this when I tried, but I can't work out how to solve for t. "A knows where B will be at a given time, so meet it there." "Meet it there when?" "How ever long it takes to get there." "To get where?" "To B's position when you reach it." etc. It's not really the basic laws of motion that are stumping me here, it's the math in between the basic laws and the function I'm looking for in my original post that I have trouble with, eg: that the motion is a vector, that it needs to work if A already has a velocity –  ucclaw Mar 8 '11 at 17:42
    
In response to updated answer: you've left the right hand side of the equation in a single dimension, which misses out direction or acceleration on the other axis, depending on how you look at it. There are three unknowns: x acceleration, y acceleration and time, but only two equations - postion of $A$ and $B$ with respect to time. I think this means I'll have to do a derivation of... something and optimise for $t$, but that's what I'm having trouble with. –  ucclaw Mar 9 '11 at 12:16
    
The equation is to find $t$. Having found that, you can plug into the motion of B to find where to go, which gives the direction. Then the acceleration is maximum until you hit the maximum speed, zero for a while (as shown in the original response) then maximum negative to stop. I assumed you had far enough to go that you would hit maximum velocity. –  Ross Millikan Mar 9 '11 at 14:55
    
Ok, I think I understand your approach now and I feel silly for not getting it earlier :-) Thanks. You're also right that it gets a lot messier if A has a starting velocity, which it does: your solution works by having a function for the maximum distance $A$ can travel in $t$ but with a starting velocity 'how far $A$ can go' depends on where it wants to go. I am attempting to do it anyway but the algebra is taking a long time to simplify. I'm not really sure that I'm doing the right thing either. –  ucclaw Mar 9 '11 at 16:21
    
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 (math.stackexchange.com/questions/26172/…) which is more mathematical. When I get to the bottom of this I'll post the solution. –  ucclaw Mar 10 '11 at 9:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.