paper: Driving a Robot — Fastest Path from A to B

[Mr. N]

Thread created automatically to discuss a document in CD-Media.

Driving a Robot — Fastest Path from A to B by Mr. N

[RyanCahoon]

What if you have a trajectory of three (or more) poses? It seems the simplifying assumption that "the robot reaches top speed very quickly" may create a false conclusion

[MARS_James]

I have such a strong desire to print this out and walk around pits handing it to other teams for two reasons one is because it honestly is an interesting read(I am a nerd leave me be) the other is because if it convinces teams this is true then defense became a whole lot easier.

[Michael Hill]

Interesting read. A couple things I would point out: 1.) There is another scenario to consider: Drive, turn, drive (Back up to a point coincident with a point on your final pose vector, turn to face the vector, then drive forward to the point), and 2.) This doesn't take into account real accelerations. There is an underlying assumption that speed is instant, meaning it takes 0 time to get to speed/reverse directions. With a spline path, there are no reversals in direction, so it might be something worth looking at.

[BBray_T1296]

Originally Posted by MARS_James

I have such a strong desire to print this out and walk around pits handing it to other teams for two reasons one is because it honestly is an interesting read(I am a nerd leave me be) the other is because if it convinces teams this is true then defense became a whole lot easier.

Well, with defense this whole calculation can be thrown out the window. Since there is a moving and smart (ie non arbitrary/random) blockade you end up in a situation where there is many "pose" A, B, C, D, ..., Z which is constantly changing to path around said blockade.

This is simply analyzing a situation where there is no interference.

[MARS_James]

Originally Posted by BBray_T1296

Well, with defense this whole calculation can be thrown out the window. Since there is a moving and smart (ie non arbitrary/random) blockade you end up in a situation where there is many "pose" A, B, C, D, ..., Z which is constantly changing to path around said blockade.

This is simply analyzing a situation where there is no interference.

Oh I know, it was a joke, though you know if someone read this and just read the final result atleast someone wouldn't take into account defense and just start driving "tetris style" as my old driver use to say

[Mr. N]

Thanks for reading the paper --- and for your feedback. You raise some very good points. Here are some additional thoughts in response to these points:

1) Acceleration

Very true, the analysis assumes instantaneous accelerations to make the problem more tractable. However, the assumption is based on models developed from speed trial data using our 2013 robot. In a straight-line test, the robot reached 75% of maximum speed within the following times/distances:

- In lo-speed gear (24:1): within 0.2 seconds/20 cm of travel
- In hi-speed gear (9.4:1): within 0.7 seconds/140 cm of travel

FRC robots, going full throttle from a standing start, do virtually all of their accelerating in a faction of a second.

So, the assumption is reasonable when talking about paths lasting several seconds covering several meters. Conversely, it is a poor assumption for very short, very quick paths.

2) Reversing to Get from A to B

This is a great point. When I developed a game simulator for the 2014 game using the "turn-straight-turn" strategy, I realized that the "delta theta" terms (i.e., the changes in heading) had an ambiguity for angles greater than 180 degrees. For example, you get to the same heading by turning +270 or -90. Clearly the second turn is faster. But it also requires the robot to travel backwards during its straight-line motion.

Although not explicitly mentioned in the paper, this result is entirely consistent with the conclusion. Consider the 2013 game: it is faster to travel in reverse from the shooting position at the pyramid to the feeding station, rather than turning 180 degrees first.

3) Multi-Segmented Paths

Given the qualifiers outline in (1), I would argue it is more efficient to plan a trip around a mid-field obstacle (e.g., a pyramid) as a series of straight segments rather than one curved, sweeping path.

4) Impact on Strategy vs. Tactics

Clearly, the findings are more relevant when planning overall game strategy that involves moving between key locations ("way points" or "way poses"), as opposed to tactical moves on the field when contending with defenders.

[James Kuszmaul]

Even assuming that, when accelerating as hard as possible, that acceleration is insignificant*, it should be noted that a human driver still has to control the robot for the in-place turn. And I doubt there are any drivers out there that can time it such that they switch from full acceleration to full deceleration at just the right time to turn a precise angle. The hardest part isn't accelerating as fast as possible; it's being as accurate as possible while moving at speed.
This still leaves the question of what the fastest path would be in autonomous, accounting for acceleration. Turn-Straight-Turn is certainly the simplest and reasonably fast if you get your control loops right.

*Keep in mind that if each acceleration takes a fraction of a second, you still have to accelerate/decelerate three times in a given maneuver, which can add up to a couple seconds over the course of a maneuver and even a second per maneuver adds up quickly when doing multiple maneuvers per cycle and multiple cycles per match.

[Jared]

Looks pretty cool.

That said, I don't agree. I have done a ton of work this summer with this sort of curve generation, and curve cannot be simplified to simple cubic curves. A trajectory can contain a large number of parametric quintic curves, which can have specified end headings, specified end heading derivatives, as well as (because they're parametric) dy/dt, which affects how sharp the curves are. If these are optimized, I believe it is faster to drive in a curve.

It is also not accurate to disregard robot acceleration.

I am also taking into account an actual robot's velocity, acceleration (both acceleration and deceleration, a robot can decelerate faster than it can accelerate), and jerk limits, as well as the actual speed the robot can take a turn at.

[url=https://imgflip.com/gif/b7pa0]
This path takes 1.77 seconds to drive, and travels 5 feet down and 5 feet to the left.

Using the same exact acceleration, velocity, and jerk limits as well as the same code to generate the path, I made this path:

[url=https://imgflip.com/gif/b7pex]

It takes 1.67 to drive, and ends up in the same location.

The straight path must do two 45 degree turns in addition to the straight line. This leaves .05 second for the robot to rotate 45 degrees. A 2 ft wide robot turns in a circle with a radius of 1 foot, so the distance the wheel must travel is 2*pi*1/4 = pi/2 feet = 1.571 feet in .05 seconds = 31 fps, with instantaneous acceleration. Not possible for a robot.

What if I do something like this? (Total distance 60 feet, average speed 5.5 feet per second)

To stop and turn at each waypoint would be really slow.

[Aren Siekmeier]

Originally Posted by Jared

...

To further back this up. Even if you are going to do a simple turn-straight-turn, it's going to be faster to turn about one drive side rather than the center of the robot because this moves your center further along the path, and doesn't require direction reversals for either drive side.

The curvilinear path, when considering the speeds of each side, is generalizing this by allowing each side of the drive to stay at a positive speed and minimized their accelerations while still accomplishing the heading changes and displacements needed.

[Mr. N]

Originally Posted by compwiztobe

To further back this up. Even if you are going to do a simple turn-straight-turn, it's going to be faster to turn about one drive side rather than the center of the robot because this moves your center further along the path.

In fact, the analysis takes this into account.

Turning about a point other than the center does indeed made the center of the robot move faster. However, it simultaneously creates a longer path in every case. This is the central question: Does the increased speed compensate for the extra length? The answer is no (within the context of the working assumptions).

[Mr. N]

Very nice work!

I think, in fact, we're in good agreement. Here are some points of clarification:

Originally Posted by Jared

...curve cannot be simplified to simple cubic curves. A trajectory can contain a large number of parametric quintic curves, which can have specified end headings, specified end heading derivatives, as well as (because they're parametric) dy/dt, which affects how sharp the curves are. If these are optimized, I believe it is faster to drive in a curve.

Yes, a trajectory can be defined by an arbitrary parametric curve. I was merely pointing out that the lowest order polynomial spline that satisfies the end conditions is a cubic. However, the analysis is generalized for any function that has either (1) no inflection points or (2) one inflection point (a curve with more inflection points has superfluous arc length and is always longer). So, within the context of the original assumptions, the conclusions hold true for any spline.

It is also not accurate to disregard robot acceleration.

Agreed. However, in my earlier post, I attempted to set out general boundaries for when the assumption is still valid. For longer paths --- on the order of many meters --- there is closer agreement to real results than for shorter paths. It also depends on what gear you're in. The assumption is closer to reality for low-speed gears.

...a robot can decelerate faster than it can accelerate...

Very true, but a faster deceleration is in fact closer to my "instantaneous" assumption.

...and jerk limits...

This I'm really curious about. In my dynamic model, the velocity/acceleration limits are set by the motor characteristics. Speed and torque are coupled. However, I don't see how third-order derivatives (jerk) enter into it.

...This path takes 1.77 seconds to drive, and travels 5 feet down and 5 feet to the left...

In your example, the total path length is a little over 7 feet or about 2.2 meters. In my previous post, I point out that, in hi-speed gear, it takes about 1.4 meters to accelerate (and likely something similar to decelerate). So, this example is what I would classify as a "short" path (where acceleration definitely matters).

Can you re-run your example for 25x25 foot run (e.g., a cross-field maneuver) with similar rates of turn (remembering that the speed constraint must be imposed on the outermost bank of wheels during a turn, not the centroid).

What if I do something like this? To stop and turn at each waypoint would be really slow.

Agreed , but is this representative of a real game strategy? I would argue that a typical game involves significantly fewer way points per scoring cycle that what you've shown.

--- --- ---

All that said, it looks like your research and programming has led to a very powerful and useful modelling tool. Congrats!

[Jared]

Originally Posted by Mr. N

Very nice work!

I think, in fact, we're in good agreement. Here are some points of clarification:

Me too. After reading this post, I agree with what you've said, that curves and drive-then-turn both have their uses, especially considering that curves are much more difficult to implement. For a single spline, the time difference is pretty small. Once you start joining many splines, or using weirder splines, it becomes a different problem.
[quote]

This I'm really curious about. In my dynamic model, the velocity/acceleration limits are set by the motor characteristics. Speed and torque are coupled. However, I don't see how third-order derivatives (jerk) enter into it.

I implement the jerk limit not because it's needed, but because it makes the path a little smoother. It prevents the motor power from going full forward to full reverse instantly, preventing tripped breakers and slipping wheels. It can also stop a top heavy robot from doing little tips as it stops. It has a very small effect on time.

In your example, the total path length is a little over 7 feet or about 2.2 meters. In my previous post, I point out that, in hi-speed gear, it takes about 1.4 meters to accelerate (and likely something similar to decelerate). So, this example is what I would classify as a "short" path (where acceleration definitely matters).

True. The longer the lines are, the faster they are, compared to curves. For something with one or two lines with small turns, lines could be faster. For something with 5 or 6 curves that are pretty short, curves could be faster.

Can you re-run your example for 25x25 foot run (e.g., a cross-field maneuver) with similar rates of turn (remembering that the speed constraint must be imposed on the outermost bank of wheels during a turn, not the centroid).

Yes. The speed constraint problem is one I don't have a great solution for. Currently, I generate the curve through the points, calculate speeds/accelerations at each point for the center, then the two sides where the wheels are, and if any point is too high, it adjusts a parameter and tries again, and repeats until it's within range. The iterating solver tries to adjust the "curviness" of the splines as well as adding a factor to cheat and increase the calculated radius of curvature at each point, which is used to limit the speed through curves. The end result is that the robot will slow down more on tighter curves, thinking they are tighter than they really are, but driving on curves/straight parts with a large radius of curvature is not slowed down.

Agreed , but is this representative of a real game strategy? I would argue that a typical game involves significantly fewer way points per scoring cycle that what you've shown.

Probably not.


Here's my setup for the bigger run
Start Point: (0,0)
End Point: (25, -25)
Max Velocity: 10 ft/s
Max Acceleration: 10 ft/s^2
Max Deceleration: 15 ft/s^2
Robot Width: 2 feet

Trial 1:
Start Heading: 0 (facing right)
End Heading: 0
Path Type: Quintic Parametric
Results:

     Time: 4.784024461201024
     Distance: 37.531625864027085
     Average Speed: 7.845199406569258

Trial 2:
Start Heading: -pi/4 (diagonal down and to the right)
End Heading: - pi/4
Path Type: Line

Results:

     Time: 4.520517763673839
     Distance: 35.3518031718333
     Average Speed: 7.820299580706168

A great example of where a line would be much faster:

 
     Time: 4.142848102721899
     Distance: 23.413771473152483
     Average Speed: 5.6516123431533405

A line for the same path:

     Time: 1.5516701850414147
     Distance: 6.099594833091013
     Average Speed: 3.9309866825392485

[Mr. N]

Originally Posted by Jared

A great example of where a line would be much faster:

Ha! Agreed!

Thanks very much for the detailed answer. Great work!

One thing: The acceleration limit you used (10 ft/s/s) may be little low. Based on our speed trials, we were getting something more like 22 ft/s/s (Supershifter, hi-speed gear).

I worked up a similar example using the math from my paper (I probably should have included this in the paper itself). I used a 25x25 foot path with a similarly shaped curve. I set my upper speed at 10ft/s and robot wheel base to 2 ft.

Although I don't take acceleration into account, keep in mind that (a) the path is long enough that the effects of acceleration are minimized, and (b) both the linear and curved path benefit from the "instantaneous" acceleration assumption -- they are both slightly faster than real life, by about the same amount.

Here are my results:

- Turn-Straight-Turn: 3.69 seconds, total arc length = 35.36 feet, total heading adjustment = 90 degrees

- Curve: 4.00 seconds, total arc length = 37.79, total heading adjustment = 126 degrees

The curved path takes 8.3% (or 0.31 seconds) longer to execute.

Although this doesn't sound like a lot, over 6 scoring cycles, that 1.84 seconds --- almost 2 seconds from optimizing just one part of a path.

[Michael Hill]

Swerve drive teams are laughing at this thread