wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The shortest distance from A to B (M)
        
(Message started by: James Fingas on Aug 30^th, 2002, 8:42am)

Title: The shortest distance from A to B (M)
Post by James Fingas on Aug 30^th, 2002, 8:42am

I'm sure some people already know this, but here in Canada, we often measure distance in units of time. If you were to ask a Canadian "how far is it from Toronto to Ottawa?", they might answer "4 1/2 hours, if you drive fast". This pseudo-answer is both more and less useful than the actual distance answer.

Cathy is a young Canadian. She is in a large, empty parking lot with her bicycle. The parking lot is sloped, so that if she points her bike in the -Y direction, she will accelerate at a rate of g. There is no slope in the X direction. Furthermore, on the surface of the parking lot (as on most parking lots) is marked out a grid in the X and Y directions. Cathy can pedal with a force so that her acceleration (if she were going in the X direction) is f.

Cathy starts (at rest) at point A, location (xa, ya) on the grid, and wants to find the shortest distance to point B, location (xb, yb) on the grid. But because she's Canadian, she's not thinking about actual distance, but about finding the fastest way to get to B. We're looking for a description of her path, and if possible, her minimal time.

Zeroth scenario: What if g<<f?

First scenario: Assume Cathy wants a free ride. Of course, she can only go downhill: yb <= ya.

Second scenario: Now assume Cathy pedals with a constant force (as mentioned above).

Third scenario: Assume Cathy can pedal harder, but she doesn't want to. Minimize the integral (a(f(t))^2 + 1)dt, where f is Cathy's instantaneous acceleration due to pedalling.

Fourth scenario: What if the parking lot isn't uniformly sloped? The height as a function of x and y is h(x,y). Assume Cathy doesn't pedal, and ignore the secondary effect that the h(x,y) changes the path-length of a path on the parking lot surface. Write down the cost function in terms of state variables (including position, of course).

Fifth scenario: The parking lot is slippery (it's always winter in Canada, right?), but Cathy doesn't know how slippery. Therefore, she wants to minimize her acceleration, including acceleration due to turning, while still getting to point B fast. Note that she doesn't have to include her acceleration due to gravity. Minimize the integral of (a(f^2 + v^4/R^2) + 1)dt, where v is her instantaneous velocity, and R is her instantaneous radius of curvature.

Sixth scenario: As you probably know, cycling is mostly about overcoming friction. Assume that we can approximate friction by a rolling-resistance term (Cathy has knobbly tires). The friction force in that case is equal to -bv, where v is her instantaneous vector velocity. This term b also includes the mass of Cathy and her bicycle.

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by tim on Sep 1^st, 2002, 5:38pm

The zeroth and first scenarios aren't difficult.

I don't think I'll have much difficulty with the second one, either.

I'm not quite sure how to interpret the third scenario: I'm guessing that a is an arbitrary one-variable function, although there is some lingering doubt that you might have intended it to be a multiplied constant.

I can give a straightforward mathematical methodology (calculus of variations) for all of the scenarios. Since at least some of them involve arbitrary functions in the problem specification, it's difficult to know what would qualify as a "solution" though.

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by James Fingas on Sep 3^rd, 2002, 10:13am

a is just a constant, which describes Cathy's desired trade-off between getting there quickly and not pedalling hard.

I should learn how to draw functions more effectively...

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by Chronos on Sep 3^rd, 2002, 2:32pm

I take it that she starts off at rest? Does she have to come to rest at point B as well, and if so, does braking count as acceleration?

I suspect that the "acceleration due to turning" in scenario 5 is a red herring, since that'll probably be the gravitational acceleration which she can ignore.

And if you want a more realistic model for the friction, a bike suffers mostly from air resistance, which scales as v²

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by James Fingas on Sep 4^th, 2002, 8:33am

She starts at rest, as mentioned in the problem. She doesn't have to come to rest at point B--in reality, you can brake a lot easier than you can pedal, so I thought that would make the problem more complicated without adding realism.

I'm pretty sure the acceleration-due-to-turning doesn't disappear. Consider scenario #1. I am quite confident that these are not minimal-acceleration trajectories!

For the speeds she will see in her experiments, it is quite possible that rolling resistance is larger than air resistance--especially with knobbly tires.

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by Chronos on Sep 6^th, 2002, 5:49pm

OK, yeah, I missed the part about her starting at rest. Without that, she can just take a parabolic trajectory in scenario 5, with no (non-gravitational) acceleration at all. Even with starting at rest, it still seems like she should be able to use gravity to do her turning, though. But then, that's not necessarily optimal, either.

The thing is, I know how to use calculus of variations, but these being "riddles" and not "homework problems", it just seems that there should be some more elegant way to solve them. Absent knowing (yet) exactly what that elegant way is, I'm trying to apply intuition. I don't actually do calc. of variations unless I'm being graded or paid for it :). While I'm at it, I'm trying to make sure I fully understand the problem.

I also note, by the way, that in scenario 5, you can remove the objective of "while still getting there fast", and still have an interesting problem, since she will still need to apply some nonzero force to end up anywhere but the bottom of the hill.

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by James Fingas on Sep 9^th, 2002, 11:54am

Chronos,

I hope you don't mean an actual parabola when you say a parabolic path, because that's not quite right...

In Scenario 5, I don't mean that there's no friction. I'm just trying to say that too large a force will make Cathy slip and fall on her ass. Even winter-toughened Canadians hate falling on their asses on the ice. The solution should assume that Cathy doesn't slip.

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by Chronos on Sep 11^th, 2002, 8:34pm

Yes, I understood what you were saying. I was just pointing out that there's a simpler version of the problem which is nontrivial. Suppose that we do remove the requirement that she's in a hurry. If the parking lot is flat and she wants to keep from falling (we Montanans understand that, too), then the solution is just to apply almost no force and go reeeaaaalllly slow. But if she's on an incline, then an infinitesmally small force won't help her. She has to have some considerable force, but she still wants to keep it to a minimum to avoid splatting. An interesting problem.

And is there any way to do these without calc of variations?

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by James Fingas on Sep 12^th, 2002, 7:03am

Chronos,

I wouldn't like to give anything away, but when I made this question up I had just come from a control class in which we were discussing linear-quadratic optimal control ...

Title: Re: NEW PROBLEM: The shortest distance from A to B
Post by Chronos on Sep 15^th, 2002, 10:20pm

Quote:

I wouldn't like to give anything away, but when I made this question up I had just come from a control class in which we were discussing linear-quadratic optimal control ...

Don't worry about that. To a physicist (and, I suspect, to any non-CS), that hint does not, indeed, give anything away :). But I do take some comfort in the fact that there exists a simpler solution to these problems. This "linear-quadratic optimal control" stuff looks like it's pretty widely applicable... Maybe I ought to take a class on that some time. Because calc. of variations problems are very widespread in physics, and I'm always looking for cleverer ways to solve problems.

Title: Control Theory
Post by James Fingas on Sep 20^th, 2002, 1:33pm

Control theory is a very interesting field. You study linear systems and their inputs and outputs. Then you learn how to take the outputs from linear systems and feed them back to the inputs to control the system.

For instance, consider a car cruise control. The control system reads the speed of the vehicle and adjusts the throttle to keep the car at a roughly constant speed.

One possible strategy might be to compare the car's speed to a setpoint, and if the car is going slower, hit the gas as hard as possible. If the car is going faster, then let off the gas completely. This control strategy has certain benefits (very fast response, simple controller), but obviously certain drawbacks (as far as the passengers are concerned). Happily, there are better control strategies out there.

Linear-Quadratic optimal control provides the optimal tradeoff between performance and control "effort" (ie. magnitude of the control action), by minimizing the "cost function", a time integral which is a quadratic function of deviation from perfect tracking, and also a quadratic function of control effort. Optimal control depends on the solution of the Algebraic Ricatti equation, a matrix equation that isn't generally solvable (in closed form).