Solving simultaneous vector equations

[whartung]

TL;DR Summary

I was able to solve using Newtons method a scalar equation, now I want to solve it as a vector.

I'm sorry, this touches so many areas, I just didn't know which pigeon hole to put it in, so I dropped it here in General.

Simple summary.

I have two physics equations. The problem I'm trying to solve is a follower is chasing a target that is moving at a fixed velocity. The follower is going faster than the target, and can decelerate. I want the acceleration (deceleration) and time necessary for the follower to match the targets position and velocity.

fv + a * t = tv
fx + fv * t + 1/2 * a * t^2 = tx + tv * t

The first equation is basically "followers velocity plus acceleration times time equals target velocity"

The second one is "give the followers initial position, time, and deceleration, move as far as the targets starting position plus the time and velocity of the target."

I have solved these for a and t, along the X axis, single dimension, using the numerical method Newtons method in a computer program. It seems to work. It uses a 2x2 Jacobian matrix with the partial differential against each of a and t for each equation. The numbers I get back are sane, and work. The follower ends up in the same X as the target, and with the same velocity. Bingo. Shazam.

This is how I derived my Jacobian matrix.

            double f1 = fx + fv * t + 0.5 * a * t * t - tx - tv * t;
            double f2 = fv + a * t - tv;
            double df1da = 0.5 * t * t;
            double df1dt = fv + a * t - tv;
            double df2da = t;
            double df2dt = a;

            // Calculate the Jacobian matrix
            double jacobian[][] = {
                {df1da, df1dt},
                {df2da, df2dt}
            };

            // Calculate the function vector
            double f[] = {f1, f2};

The df variables are the partial derivatives.

Now, it's my understanding that the basic physics equations work equally well with vectors (even if I don't).

If I was to convert my space from 1 Dimension to 2 Dimensions, then vectors it is.

The math is the same, save that the velocities, positions (fx, tx), and acceleration are all vectors. t remains a scalar.

I have converted my code to solve the new problem. By converting the equations to use the components of the vectors.

Now, with the vectors, the equation space explodes a bit. From a 2x2 matrix to a 3x4 matrix. I have gone from 2 equations with 2 unknowns (a and t) to 4 equations (x and y versions of each previous equation) with 3 unknowns (a.x, a.y, and t).

            double f1x = fpos.getX() + fv.getX() * t + 0.5 * av.getX() * t * t - tpos.getX() - tv.getX() * t;
            double f1y = fpos.getY() + fv.getY() * t + 0.5 * av.getY() * t * t - tpos.getY() - tv.getY() * t;
            double f2x = fv.getX() + av.getX() * t - tv.getX();
            double f2y = fv.getY() + av.getY() * t - tv.getY();

            double df1xdax = 0.5 * t * t;
            double df1xday = 0;
            double df1xdt = fv.getX() + av.getX() * t - tv.getX();

            double df1ydax = 0;
            double df1yday = 0.5 * t * t;
            double df1ydt = fv.getY() + av.getY() * t - tv.getY();

            double df2xdax = 1;
            double df2xday = 0;
            double df2xdt = t;

            double df2ydax = 0;
            double df2yday = 1;
            double df2ydt = t;
            // Calculate the Jacobian matrix           
            double jacobian[][] = {
                {df1xdax, df1xday, df1xdt},
                {df1ydax, df1yday, df1ydt},
                {df2xdax, df2xday, df2xdt},
                {df2ydax, df2yday, df2ydt}
            };

            // Calculate the function vector
            double f[] = {f1x, f1y, f2x, f2y};

So, first off, is my base assumption even correct. If I solve the simultaneous equations with vectors instead of scalars, then this should work in a 2D space, right? My basic thesis is correct? Or am I completely off base? I should be able to get an acceleration vector and a time that will let the follower match the targets position (x,y), and velocity vector after time t. Yes?

My problem is that my new version just flies off into the weeds to NaN land and does not converge. My test was to take the values I solved with the one dimensional routine, and plug them into this. The vectors and location just had their Y's zeroed out to be equivalent. My expectation as a result was an acceleration vector with the X component matching my previous result, the Y component to be zero, and the time value to be similar.

Newtons method even starts with "guesses", and when I put essentially the solution I was looking for as the initial guesses, it still flies off into the weeds.

I must also admit that a week ago I didn't know what a partial derivative was. I don't know calculus (though I read through a book the other night, just trying to absorb some vocabulary). Or a jacobian anything. If someone walked up to me and said "Oh, just solve it using the Newton–Raphson method with a Jacobian matrix filled with partial derivatives with regards to the vector components and reduced with Gaussian elimination to find the root" I would have stared at them blankly like Picard to Wesley Crusher. "Ok! Let's do that!"

This is cut and paste internet glory, with a few bounces off of Wolfram for derivatives.

I want to know if I'm on the right track. That this is the path to take, that the light at the end of the tunnel a) is lit and b) is not a train. Are these derivatives correct.

I can certainly post the entire routines. I admit that I'm not positive that the code that boils down the Jacobian matrix (reducing the coefficients?) is correct. I think it must be because I'm not getting any out of bounds errors on the code. It's not intuitive to uplift 2x2 to 3x4 code, not quite knowing which index is which. But it doesn't explode, so, that may be a spark of light. Just the numbers are all wrong.

Any pointers are welcome. If the mods want to move this thread, feel free. (Is it a physics problem? a computer problem? Differential equations? Vector calculus?)

 

[FactChecker]

I don't know if this is applicable, but are you familiar with missile guidance proportional navigation?

 

[whartung]

No, I have not, thank you. I'll look at it, but this is a rendezvous problem (actual matching of vectors) not simply an intercept problem, so I don't know if its applicable or can be extended to this use case.

 

[FactChecker]

this is a rendezvous problem (actual matching of vectors) not simply an intercept problem, so I don't know if its applicable or can be extended to this use case.

Good point. I think you could gradually reduce the angle of approach to zero and gradually match velocities, but I don't know how hard it would be to satisfy your conditions.

 

[whartung]

I've looked at PN a little bit, and it certainly seems popular in this space of problem (though I don't know about the rendezvous issue yet), but I'm still very interested on how to solve this specific problem, just to give me another glimpse of the toolkit of solving equations like this.

 

[pasmith]

I don't think the acceleration will be constant; it would have to be towards the target, and that direction changes with time, unless the initial positions and velocities are collinear, in which case the problem is really one dimensional. Thus your equations will not be applicable.

The term to search for is "chase problem" or "pursuit problem"; see for example here.

 

[FactChecker]

I don't think the acceleration will be constant; it would have to be towards the target, and that direction changes with time, unless the initial positions and velocities are collinear, in which case the problem is really one dimensional. Thus your equations will not be applicable.

The OP does not say if the agreement in position and velocity only needs to be instantaneous. If so, the problem might be easier.

 

[whartung]

Thus your equations will not be applicable.

It certainly "works" in 1 dimension. You're suggesting that since the target bearing will always be changing, this is not the appropriate technique to solve this problem?

The OP does not say if the agreement in position and velocity only needs to be instantaneous.

In the 1 dimension version, I get a single acceleration, and a single time, that act as a constants until the follower reaches the target. Is that what you mean by instantaneous? vs having the acceleration constantly changing as the objects get closer to each other?

 

[FactChecker]

In the 1 dimension version, I get a single acceleration, and a single time, that act as a constants until the follower reaches the target. Is that what you mean by instantaneous? vs having the acceleration constantly changing as the objects get closer to each other?

I was wondering if a solution where the paths just touched for a brief instant with the same velocity vector would be acceptable.

 

[whartung]

I'm using this for "cinematic" purposes, for a game. I want my spaceship to fly across the system and arrive at the planet. I want to know how long it will take, I want to know the path that it takes. I'm simplifying it to ignore gravity because if I can't get it to work without gravity, what chance do I have to getting it to work with gravity.

I was looking for a "primitive" function that tells me that the planet is within the envelope of the ships engines to make planetfall. In the trivial case, the ship points itself towards the planet, lights up its drive, and accelerates while constantly checking this function until it finds that "if I use 90+% of my engine power, I will match the planet and arrive in XXX hours/minutes/seconds". The accelerate part is simply and iterative task until the function rings true, at which point the ship knows how much to decel, how long, and in which direction.

That was my hope. I've been fighting this problem for, literally, years off and on. Every few months I get a spark of whimsy and dig into again. When I stumbled across these simultaneous equations, I was like "Aha! I can work with this!".

But, it looks like this won't be the case, and I don't have the math background to adapt things like proportional navigation, nor anything else I've found, to this problem.

 

[pbuk]

So, first off, is my base assumption even correct. If I solve the simultaneous equations with vectors instead of scalars, then this should work in a 2D space, right? My basic thesis is correct? Or am I completely off base? I should be able to get an acceleration vector and a time that will let the follower match the targets position (x,y), and velocity vector after time t. Yes?

No. And if you think about it, you already know the reason why:

I have gone from 2 equations with 2 unknowns (a and t) to 4 equations (x and y versions of each previous equation) with 3 unknowns (a.x, a.y, and t).

You can't hit 4 targets at with 3 bullets^*.

Any pointers are welcome.

Learn from the advice already given in this thread: navigating a ship to a planet is done in (at least) two stages: first you need to get to the right place, then you need to get to the right velocity to get into an appropriate orbit. In the second stage the planet's gravity is particularly important.

A good way to get a feel for this without learning loads of maths is to play the game Kerbal Space Program.

^*You can if one of the targets is right behind another one: in the mathematical equivalent we would say that there is a linear dependency.

 

[Grelbr42]

The problem as described is very much simpler than an orbital transfer. If you don't insist on an optimal solution, there is a very simple one available.

First, you line up your velocity with the target. You thrust side-ways such as to make the target's velocity directly align with the vector between you and them.

This converts the whole thing to a one dimensional problem with an initial velocity and displacement. And that one is very easy to solve.

If the target is moving away, you add enough extra thrust time to bring the ship to rest relative to the target. Then it's just a very simple thing of accelerating half way, flipping, and decelerating half way.

If the target is moving towards you, you have a trick to solve the system. You project backwards to where you would have had to be to start from rest at constant acceleration, and solve the from-rest problem from there.