Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It's well-known and obvious that if you have a spaceship and your sole constraint is an upper bound on magnitude of acceleration/deceleration, the fastest way to get to a distant star (a fixed location), starting and ending with zero velocity, is to accelerate at full thrust throughout the first half of the journey and decelerate at full braking power during the second half.

I'm interested in the slight generalization of that problem in which the initial velocity may be nonzero. (The target velocity is still zero-- I'm explicitly not considering the case where the target velocity is nonzero, since that opens up a large can of worms.)

We can take the target position to be the origin and the acceleration bound to be 1, so the problem statement is: given initial position p0 and initial velocity v0, find the smallest possible t1>=0 with trajectory p(t) (0<=t<=t1) such that:

    p(0) = p0
    p'(0) = v0
    p(t1) = 0
    p'(t1) = 0
    ||p''(t)|| <= 1 at all t

Two dimensions is adequate (for a given instance of this problem in 3d or higher, just work in the plane containing the origin, p0, and v0).

I've seen some papers on this under the heading "kinodynamic programming" in which numerical methods are developed for more general problems, having various other constraints such as obstacles and velocity bounds. So my problem is simpler than those, and I'm hoping for a closed-form solution.

What I've got so far is a hypothesis is that the velocity p'(t) traces out a catenary (that is, a scaled rotated translated cosh graph) parametrized by arc length, in velocity space. Specifically, it's the unique catenary passing through v0 and 0 whose integral is the required position displacement -p0. This hypothesis seems to be consistent with my experimental results so far in various cases. Notice that it's also consistent with the known answer in the degenerate 1d case (in particular the original easy problem described in my first paragraph); that is, in the 1d solution the velocity steadily increases in one direction, then at some point the acceleration switches direction and the velocity steadily goes back to zero; that may be interpreted as the velocity tracing out a degenerate catenary at constant speed in velocity space.

So overall this hypothesis seems promising, and I have not seen it mentioned in anything I've read.

Is this a known result? Is there anything else known about solutions to this problem?

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.