08-15-2014 11:28 PM

RyanCahoon

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

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

08-15-2014 11:42 PM

MARS_James

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

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.

08-15-2014 11:47 PM

BBray_T1296

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

This is very interesting. I'm glad someone took the time to analyze this mathematically. Thanks

08-15-2014 11:51 PM

Michael Hill

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

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.

08-15-2014 11:53 PM

BBray_T1296

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

Quote:

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.

08-15-2014 11:58 PM

MARS_James

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

Quote:

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.

08-16-2014 11:58 AM

Mr. N

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

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.

08-16-2014 12:51 PM

James Kuszmaul

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

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.

08-16-2014 01:09 PM

Jared

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

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.

08-16-2014 01:52 PM

Aren Siekmeier

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

Quote:

Originally Posted by Jared ...

08-16-2014 02:07 PM

Mr. N

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

Very nice work!

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

Quote:

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.

08-16-2014 02:16 PM

Mr. N

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

Quote:

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.

08-16-2014 03:05 PM

Jared

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

Quote:

Originally Posted by Mr. N Very nice work! I think, in fact, we're in good agreement. Here are some points of clarification:

     Time: 4.784024461201024
     Distance: 37.531625864027085
     Average Speed: 7.845199406569258

     Time: 4.520517763673839
     Distance: 35.3518031718333
     Average Speed: 7.820299580706168

 
     Time: 4.142848102721899
     Distance: 23.413771473152483
     Average Speed: 5.6516123431533405

     Time: 1.5516701850414147
     Distance: 6.099594833091013
     Average Speed: 3.9309866825392485

08-16-2014 03:49 PM

Mr. N

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

Quote:

Originally Posted by Jared A great example of where a line would be much faster:

08-16-2014 04:40 PM

Michael Hill

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

Swerve drive teams are laughing at this thread

08-16-2014 06:23 PM

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

Quote:

Originally Posted by Michael Hill Swerve drive teams are laughing at this thread

08-17-2014 12:32 PM

Jared Russell

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

What you have brought up is a special case of a well known theorem from optimal control that says (essentially) that you always want to be saturating your inputs to get to the final state in a time optimal way. Intuitively, if your left and right motors are always going full speed in the right direction towards your setpoints (both position and angular, and you've found the right turn-straight-turn policy that ensures that this is true), you will always get there faster than if they are not going full speed all the time.

This property holds with an infinite acceleration limit and, indeed even with limits on acceleration, jerk, etc. - except in the latter case, you always want to be accelerating/jerking at the limit. The complication is that once you introduce higher order constraints, the "order of operations" policy becomes difficult to discover because of the nonlinear mapping between motor speeds and position/rotation. Once you have higher order constraints, finding a time-optimal path becomes a more difficult process, typically requiring iteration and search in a non-convex space.

If you look at 254's acceleration profile generation code from this year, you'll see this concept in action - using a triple integrator with an input that always switches between +1/-1, we obtain a limited-jerk, limited-acceleration, limited-velocity trajectory. We then applied this acceleration profile over a spatial spline, which of course broke the time optimality but was good enough in practice (with some safety margin to prevent saturation).

So...Yours is the right conclusion if you ignore practicalities like acceleration limits, wheel slip, battery usage, dynamics/momentum, and jerk to the robot and any load(s) it is carrying. Empirically, these are quite significant factors for FRC driving:

* Robots that have high enough maximum accelerations to allow you to assume instantaneous acceleration will frequently also be capable of slipping their wheels, harming control, acceleration, and accurate distance measurement. Moreover, by the time you are talking about full-weight, 15+fps robots, the infinite acceleration assumption breaks down severely.

* A robot that moves from one point to another along an arc does not need to repeatedly accelerate and decelerate the drive motors as in a turn-straight-turn case. This saves battery life, heat, and wear-and-tear over the course of a match. The battery life savings can be significant enough that it allows you to gear your robot faster overall.

* Momentum is a HUGE part of FRC driving at high speeds. If I take a 254 robot at 19fps and want to turn, I can do so on a dime simply by slowing down one side of the drive and letting the momentum whip the back end of the robot around the corner. Maintaining momentum through maneuvers is generally preferential to coming to a stop.

* Even if you have an infinitely accelerating robot that doesn't slip its wheels, has a perfect battery, and doesn't care about momentum, if you are carrying a game piece externally, you may want to reduce the accelerations and jerks experienced by them. Case in point: The balls we held on our bumpers during auto mode this year could be dislodged by a very abrupt stop or quick turn in place.

08-17-2014 01:06 PM

Jared

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

Quote:

Originally Posted by Jared Russell If you look at 254's acceleration profile generation code from this year, you'll see this concept in action - using a triple integrator with an input that always switches between +1/-1, we obtain a limited-jerk, limited-acceleration, limited-velocity trajectory. We then applied this acceleration profile over a spatial spline, which of course broke the time optimality but was good enough in practice (with some safety margin to prevent saturation).

08-17-2014 02:13 PM

Jared Russell

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

Quote:

Originally Posted by Jared One quick question- how does the code (or does it even do it?) limit acceleration, jerk, and velocity if the path goes straight long enough for the robot to reach full speed, then suddenly turn sharply? Do you go through the turn too quickly, ignore acceleration limits and stop too quickly, or do you somehow begin decelerating before you get there?

08-17-2014 05:18 PM

Jared

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

Quote:

Originally Posted by Jared Russell In 2014, by having conservative limits on these quantities and not having lots of sharp turns. (Inelegant but good enough.) For 2015 and beyond, by assigning maximum velocities to each point on the path based on curvature and working backwards to respect the other limits. This is the "correct" way to do it, and fairly straightforward for the limited acceleration/unlimited jerk case. But it can be very complicated for limited jerk control.

08-17-2014 05:32 PM

Mr. N

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

Quote:

Originally Posted by Jared Russell What you have brought up is a special case of a well known theorem from optimal control that says (essentially) that you always want to be saturating your inputs to get to the final state in a time optimal way.

08-17-2014 06:33 PM

DampRobot

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

Quote:

Originally Posted by Mr. N 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.

08-17-2014 06:45 PM

Mr. N

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

Quote:

Originally Posted by DampRobot For this simulation, are you taking into account the time needed to turn, or assuming that the robot starts and ends on the same heading it travels?

08-17-2014 07:18 PM

Mr. N

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

Quote:

Originally Posted by Jared Do you think you could help me figure out a good way to do this?

08-17-2014 10:47 PM

artK

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

Quote:

Originally Posted by Jared A great example of where a line would be much faster: Code: Time: 4.142848102721899 Distance: 23.413771473152483 Average Speed: 5.6516123431533405 A line for the same path: Code: Time: 1.5516701850414147 Distance: 6.099594833091013 Average Speed: 3.9309866825392485

08-18-2014 08:57 AM

Jared

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

Quote:

Originally Posted by artK I look at this and have to ask one question Jared: if you were to add PI to both of the headings, thus creating a new spline that should model a robot driving backwards, what do the numbers come out to?

Quote:

Originally Posted by Mr. N I realize this query wasn't directed at me, but perhaps I can contribute in a small way. Also, since I'm approaching this somewhat cold, apologies for any naïve suggestions. Problem Statement (as I understand it): You have defined a path for the center of the robot to follow, using a parametric curve that satisfies certain end constraints (position, heading). The path may have an arbitrary number of curved segments. You wish to find control inputs (i.e., left and right motor speeds) that will cause the robot to execute that path in minimum time, while adhering to speed, acceleration and jerk constraints imposed on the motors. Is this correct? Partition the Path You can partition the path into segments between inflection points (i.e., when the curve transitions from positive to negative curvature). In the absence of acceleration and jerk limits, you would assign Vmax to either the left or right motor, correct? That is: if curvature > 0 --> Set Vright = Vmax; if curvature < 0 --> Set Vleft = Vmax; if curvature = 0, Set both to Vmax. The opposite motor will be set at whatever speed is necessary to achieve the desired curvature. So, for each path segment, you know which motor should ideally be running at max speed. Define a "Transition Zone" Based on Acceleration/Jerk Limits In reality, at each inflection point, the motors cannot transition between speed settings instantaneously because of acceleration/jerk limits. In the worst case, a motor would be commanded to go from +Vmax to -Vmax. Given the acceleration/jerk limits, it is possible to calculate the minimum arc length over which this transition can happen. Use this arc length to define transition zones on either side of each inflection point. Interpolate between Segments For each motor, create a piece-wise continuous speed curve based on segments and transition zones: There are two cases to consider: 1. Transition Zones do not overlap: In this case, for each motor join the "before" and "after" speeds with a transition curve (a piece-wise quadratic) that joins the two segments. 2. Transition Zones overlap (i.e., segment arc length is shorter than transition arc length). In such a case, the max speed you originally set for that segment is impossible to achieve. (Well, since this is based on the worst case, this isn't strictly true in all cases --- but close enough). In this case, either scale the max speed down for this segment or alter the path to give it a gentler curve. Note: This algorithm will give a sub-optimal result in terms of time, but it should be close enough. Does this help at all?

08-18-2014 01:58 PM

Jared Russell

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

If you want to make sure that your path is both velocity and acceleration limited, here is a simple and widely used method:

1. For each point along the path, compute the maximum allowable velocity. For straight segments, this is simply the maximum motor velocity. For points along curves, you can compute the radius of curvature and from that derive the maximum linear speed that would let you follow the curve (based on setting the outside wheel's speed to the maximum).

You now have a discontinuous velocity profile that might look something like this:

Initial maximum velocities
Plot of waypoint # (x) vs. maximum velocity (y)

----      -----       ---------  (fast)
    ------             
               -------           (slow)

Intermediate maximum velocities
Plot of waypoint # (x) vs. maximum velocity (y)

----       ----         -------  (fast)
    ------/            /
               -------/          (slow)

Final maximum velocities respecting acceleration limits
Plot of waypoint # (x) vs. maximum velocity (y)

---        --           -------  (fast)
   ------/           /
              -------/          (slow)

08-18-2014 02:43 PM

Jared

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

Quote:

Originally Posted by Jared Russell If you want to make sure that your path is both velocity and acceleration limited, here is a simple and widely used method: 1. For each point along the path, compute the maximum allowable velocity. For straight segments, this is simply the maximum motor velocity. For points along curves, you can compute the radius of curvature and from that derive the maximum linear speed that would let you follow the curve (based on setting the outside wheel's speed to the maximum). You now have a discontinuous velocity profile that might look something like this: Code: Initial maximum velocities Plot of waypoint # (x) vs. maximum velocity (y) ---- ----- --------- (fast) ------ ------- (slow) 2. Now iterate through the path (beginning to end) and for each point, set max_velocity[i] = min(max_velocity[i], max_velocity[i - 1] + max_accel_over_distance_between_points). You will now have a profile that looks something like: Code: Intermediate maximum velocities Plot of waypoint # (x) vs. maximum velocity (y) ---- ---- ------- (fast) ------/ / -------/ (slow) 3. Iterate through the path from end to beginning, and for each point, set max_velocity[i] = min(max_velocity[i], max_velocity[i + 1] + max_decel_over_distance_between_points). Your final profile will look like: Code: Final maximum velocities respecting acceleration limits Plot of waypoint # (x) vs. maximum velocity (y) --- -- ------- (fast) ------/ / -------/ (slow)