Go to Post ...there's nothing worse than a problem you can't solve because you don't even know about it. - Dave Flowerday [more]
Home
Go Back   Chief Delphi > ChiefDelphi.com Website > Extra Discussion
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Reply
 
Thread Tools Rating: Thread Rating: 3 votes, 5.00 average. Display Modes
  #1   Spotlight this post!  
Unread 17-08-2014, 18:33
DampRobot's Avatar
DampRobot DampRobot is offline
Physics Major
AKA: Roger Romani
FRC #0100 (The Wildhats) and FRC#971 (Spartan Robotics)
Team Role: College Student
 
Join Date: Jan 2012
Rookie Year: 2010
Location: Stanford University
Posts: 1,277
DampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond reputeDampRobot has a reputation beyond repute
Re: paper: Driving a Robot — Fastest Path from A to B

Quote:
Originally Posted by Mr. N View Post
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.
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?
__________________
The mind is not a vessel to be filled, but a fire to be lighted.

-Plutarch
Reply With Quote
  #2   Spotlight this post!  
Unread 17-08-2014, 22:47
artK artK is offline
Just Another Person
AKA: Art Kalb
no team (No Team)
 
Join Date: Dec 2011
Rookie Year: 2010
Location: Rochester, NY
Posts: 119
artK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond reputeartK has a reputation beyond repute
Re: paper: Driving a Robot — Fastest Path from A to B

Quote:
Originally Posted by Jared View Post
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
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?
__________________
Art Kalb
Team 254 (2011-2014): Head Scout, Programmer
2011, 2014 World Champions

Last edited by artK : 18-08-2014 at 02:22.
Reply With Quote
  #3   Spotlight this post!  
Unread 18-08-2014, 08:57
Jared's Avatar
Jared Jared is offline
Registered User
no team
Team Role: Programmer
 
Join Date: Aug 2013
Rookie Year: 2012
Location: Connecticut
Posts: 602
Jared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond reputeJared has a reputation beyond repute
Re: paper: Driving a Robot — Fastest Path from A to B

Quote:
Originally Posted by artK View Post
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?
Unfortunately, I don't remember exact what numbers I used for that example, but here are two path with their times. For all these, I'm assuming I have a maximum acceleration of 10, maximum deceleration of 15, maximum speed of 10, and a robot width of 2 feet.
The lower point is 8 feet away from the upper point.
This takes 3.926 seconds to drive, averaging 5.86 feet per second, on a path that is 23.00 feet long.



After adding pi to both headings, the path was only 7.2 feet long, took 1.573 seconds to drive, and averaged 4.57 feet per second.

-Note- the acceleration counts on the top of these images are not correct, as there's some lag when using an online GIF maker, and these values are calculated in real time for the preview, just to make sure I didn't mess up calculating the values for the path file. In the actual path file, acceleration never goes below -15.
Quote:
Originally Posted by Mr. N View Post
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?
Thanks for the suggestions- I like the idea of calculating acceleration/velocity limits on the wheel that is travelling the fastest.
I also really like dividing based on inflection points, instead of the sharpest corner of the curve.
I do see three potential issues/questions with this approach-
1. I do not always want to be accelerating/jerking at the maximum amount. If I am coming out of a tight turn, full acceleration may end up making me go too fast for the turn. Ideally, the path is straight enough that this isn't a problem, or we can just use the turn's acceleration limit in place of the robot's acceleration limit in the case of the turn's acceleration limit being lower.

2. When creating a quadratic to interpolate speeds between transitions zones, I am not sure if it can be done with just a quadratic. I need to make sure that acceleration will be a continuous function, so when interpolating, I need to be able to specify the location and first derivative of the endpoints. For this, I need at least a cubic. I also need to make sure that my acceleration and jerk never exceed certain numbers. I have no idea how I'd interpolate a curve like this, and to make it more complicated, it's more than just finding a curve whose first and second derivative are smaller than some numbers because it's a velocity vs. distance graph, so the derivatives aren't acceleration and jerk. This is the main problem I was struggling with in my second attempt.

3. When the transition zones do intersect, it becomes a very time consuming process for the computer to figure out what values will result in a slow enough turn, as it has to generate the entire path many times in a row. It is also a challenge to slow down just one part of the path, and have the robot behave following acc. and jerk limits.

I can get pretty close by always picking the smallest velocity in the overlap zone (as soon as we go too fast to make the second turn, start following the second turn's velocity curve), but this ignores the jerk limit, and acceleration jumps.


To be honest, I think that solving this problem with acceleration and jerk limits is beyond my ability. I think I'll just settle with ignoring the jerk limit between curves. I'll still be able to follow all the curves while keeping in mind acceleration and velocity limits, of both the robot and the curves on the path, but jerk will be forgotten at some points between tight curves.

Last edited by Jared : 18-08-2014 at 09:00.
Reply With Quote
  #4   Spotlight this post!  
Unread 15-08-2014, 23:47
BBray_T1296's Avatar
BBray_T1296 BBray_T1296 is offline
I am Dave! Yognaut
AKA: Brian Bray
FRC #1296 (Full Metal Jackets)
Team Role: Mentor
 
Join Date: Jan 2011
Rookie Year: 2010
Location: Rockwall, TX
Posts: 947
BBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond reputeBBray_T1296 has a reputation beyond repute
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
__________________
If molecular reactions are deterministic, are all universes identical?

RIP David Shafer: you will be missed


Reply With Quote
Reply


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT -5. The time now is 23:29.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi