# Navigation solution for frictionless vehicles.

Looked around a bit and couldn't seem to find a similar question. (either that or it was worded with vocabulary above the multivariable calculus I've taken. :))

Roughly worded: I would like to develop an algorithm (either in the form of "action to take each discrete time step" or "do these actions at exactly these times") for navigating a rigid body vehicle time-optimally in a frictionless environment from point A to point B.

This specific instance happens to be a Spaceship, whom I want to get from point A to point B utilizing Forward thrusters, reverse thrusters (for braking), torque thrusters, and an omnidirectional thruster for minor position/velocity corrections. The environment is 2 dimensional, though if someone knows preexisting work in 3 dimensions I can extrapolate a simpler solution from that. I've looked around the web a bit, and was unable to find anything other than some work on steering behaviors, which always assume point particles and thus do not factor torque into the equations.

I've worked for a couple of days on this problem using standard Newtonian equations, (p(t) = at^2/2 + vt + p(0)), but the entire problem is polluted by the torque calculations, such that torque is applied to turn towards and then slow down and stop at an angle that changes based on the objects velocity and the time it would take to turn to that angle. :-S 9 pages of scribbling and several frustrated nights later, a friend Reccomend I ask here.

A generic solution (which incorporates initial velocity and angle) with a high degree of accuracy would be preferred, though in the end if I have to just "fake it" to look nice (space based RTS), that would be fine too.

• I think you might want to add some more of the mathy details, but as far as physics/applied math questions go, this is one of the better ones. – Harry Gindi Jan 15 '10 at 7:17
• Leonid: Velocity isn't necessarily (1,0), it could be (though in a majority of the cases it will be (0,0)). Also, I'm not familiar with phase spaces, but that looks right (though it might be missing acceleration and rotation?) As for final conditions, velocity should be zero, though angular momentum need not be (it can arrive at the location, and THEN stop rotating at an arbitrary time in the future). – Quantumplation Jan 15 '10 at 8:14
• Harry: :-S Part of my problem solving it is I'm not too familiar with the "mathy details", and thus any reading of optimal-control documents brushes over my head quite a bit. ^^ I'm mainly a programmer with a love of math, as opposed to a Mathematician with a love of programming. :) – Quantumplation Jan 15 '10 at 8:15
• Also, as to the stopping conditions, in a perfect world I could configure those (to abstract the problem into "fly by" strategies later) – Quantumplation Jan 15 '10 at 10:27

The optimal solution is given by the proportional navigation guidance law, see for example the Wikipedia page: on proportional navigation. This solution applies for the general case where the target point B is moving. In our case it is fixed which doesn't change the character of the solution. The principle of the solution is as follows: If the velocity vector happens to be in the direction of the line of sight that is in the direction connecting the current position with the point B, then the vehicle should proceed in the same direction, otherwise, the line of sight has a rate of rotation which can be computed using using the instantaneous geometry; in this case the navigation law requires accelarting the vehicle perpendicular to the line of sight by a force proportional to rate of rotation of the line of sight. This solution leads to a minimum time to reach the point B.

• Your solution seems promising, but I'm having trouble following the algorithm. Could you provide a clearer description? – Quantumplation Jan 15 '10 at 11:45
• The rate of rotation of the line of sight is given by: lambda_dot = V sin(theta)/R , where R is the distance from B , theta is the angle between the line of sight and the velocity vector and V is the speed. Now, one needs to use an omnidirectional thruster to produce an acceleration in the direction perpendicular to the velocity vector given by: an = N lambda_dot * V, where N is a constant. In this solution forces are applied only perpendicular to the velocity vector, thus the speed will remain constant and B will be reached at a speed equal to the initial speed. – David Bar Moshe Jan 16 '10 at 5:37
• Oo, clever. Do you have a modification of the algorithm for accelerating and slowing down? For example, if the object is at rest, it's speed is 0, and thus would never be able to reach the target. Likewise, If I want to "approach" the target to land on it, I would need to find the time at which I would need to start decelerating. – Quantumplation Jan 16 '10 at 10:15
• Also, Is there a better method for choosing the constant N other than tweaking it until it "feels" right? – Quantumplation Jan 16 '10 at 10:17
• Let's prepare (compute) a "motion plan" on a straight line (starting from rest) such that in the first half only the forward thruster is operated and in the second half only the reverse thruster is operated. Then B is reached at rest. Let's call this trajectory the "planned trajectory" and compute it's instantaneous distance from B: R_planned(t). Then at any moment of the "real trajectory" an ominidirectional thruster in the direction of the line of sight should be applied with a force proportional to the difference between the planned and the actual distances. – David Bar Moshe Jan 17 '10 at 4:10

(Note: I'm not an expert.)

I would recommend either a variational method (in the absence of constraints) or a fast marching method if there are obstructuions.

• Fast Marching method is overkill for this problem, as the obstructions are sparse (MAYBE a circular obstruction or two) and easily solved by "chaining" destination points or something similar. As for variational method, I took a look at the link and 90% of it went way over my head. :-S – Quantumplation Jan 15 '10 at 8:18

There's a research group between UCLA and Caltech that does some experiments with remote-controlled miniature hovercraft. They sound similar to your case, in that there are two thrusters on the vehicle and they have to account for the rotation of the vehicle.

I haven't followed it closely in a while, but some of the references might get you started. Can't find a group homepage at the moment, but one of the professors is Andrea Bertozzi - search for "control" or "vehicle" on her publications page and you might find something interesting.

Hope that helps.

• Just looked over the list of papers (ironically lots of stuff on fluids which is what i was researching last year), but most of it was boundary estimation and cooperative tracking. Thanks for the reference though, I'll start looking at some of them more closely. – Quantumplation Jan 15 '10 at 9:30