Path Prediction given 4 pts?

henry hill

I'm doing a project on an autonomous tram and i need to able to predict the path of on coming objects. However for the moment I'm only concerned with calculating this in a 2D graph, with x repesenting the distance from the scanner and y the angle.

A scan is taken at equal intervals, eg. every 1 second. Considering isolating one object from the field, after four scans I should have enough info to calculate the predicted path of that object, and represent its path as a curve.

What math is involved to calculate the velocity, acceleration, jerk, and predicted path for the object, using the x and y co-ordinates?

This appears to be a straight forward physics question. Would anyone be able to help me. I'm also programming this in Matlab if anyone knows of any useful functions to aid me. Thanks

Sev

Ok, I dont know much about this.. and have never tried anything like this, but I can give you my ideas off the top of my head.

I assume it scans every second, so you'd want to calculate where the object is 1 second later, from the previous 3 seconds (4 scans as you say), cos after that youre getting another scan.. so I guess a reasonable approximation would be accurate.

In order to do this, some assumptions have to be made. The object might stop 0.1 seconds into the next second, because it jammed on the breaks. But you have to assume whatever force was acting on the object in the last 3 seconds to make it act like it did, is still acting on the object. (or in our case, since 4 scans offers us a slightly higher degree of accuracy we assume that the acceleration is changing at a steady rate)

Now from 4 scans, youve got a limited resolution, and only so much information you can get.

You know 4 positions, 3 velocities, 2 accelerations, and one change of acceleration.

Does that make sense? You get the velocity at 3 stages from the change of position with respect to time. You can calculate its acceleration at two stages by looking at how those velocities change with respect to time, and then youve got one piece of information that tells you that roughly midway through those 4 seconds, the acceleration (ie. force) acting on the object changed too.

You only know exactly what time corresponds with each of the 4 positions. The time that corresponds with each of the velocities/accelerations etc. has to be estimated. Eg. youre going to estimate that the object had velocity 'x1-x2'/t when it was midway between x1 and x2. (Where t is 1 second obviously).

Although a deeper mathematical study into might give more accurate ways to approximate these things, than just taking the midpoint. It's very like numerical integration, there are simple methods that give good results to decent approximation, and then there are ways you can refine it.

So now 4 seconds in... we have to make an assumption, that the force acting on the object is changing at t=4 at the same rate that it was during the last 4 seconds as we calculated.

We take our most recent result for position, velocity and acceleration, and change of acceleration. And then we integrate over the next second.

I would consider tackling this problem in one dimension before 2.

Sev

You may wish to leave the change of acceleration part out, because that information would become redundant if you were extrapolating based on the last 10 seconds of a car who's changes of acceleration are based entirely on the arbitrary decisions to turn or break.

I guess it all depends on how much you want to average things and over exactly what kind of past interval, these decisions might be completely arbitrary and you'd just need to experiment to find out what method gives best results. But I dont really know anything about this, so don't take what I say too seriously, read up on it. Try wikipedia extrapolation or something.

Sev

Oh, and if you did wikipedia 'extrapolation', as I just did myself. You'll find it mentions "polynomial" extrapolation. I think that is very similar to the ideas I described above and will give best results.

Maybe get a book out on it?

Sev

Also, I think Microsoft Excel can do this for you, if you plot a graph, and then fit a line to it, and choose polynomial line fit. You can tell it to print the equation of the line on the graph too.

Also, it may not be necessary to consider time, instead you could probably just consider how y changes with respect to x instead of independently considering how both dimensions change with respect to time.

I think spatially you will get the same results, but you wont know anything about time. Ive never done this before tho, so I'm not sure.

What you could do.. is with the aid of microsoft excel plot a graph of x against t, then fit a polynomial line to the plot, and get the equation.

Do the same thing with y against t.

Then together you have all the information for how the object moves in two dimensions with respect to time.

The polynomial equation you get is just like the simple equation for position given acceleration and velocity : x = 0.5at^2 + vt + c.. except the polynomial line fit takes higher orders into consideration, such as the change of acceleration, and the change of change of acceleration etc.

I think that's right.