if you need a hammer you use a hammer and not an oscilloscope. - Andrew Schreiber [more]
 Chief Delphi Curve Driving Generator
 portal register members calendar search Today's Posts Mark Forums Read FAQ rules

#1
03-29-2012, 09:26 PM
 theNerd Registered User FRC #3329 (Cam Bots) Team Role: Programmer Join Date: Jan 2011 Rookie Year: 2110 Location: St. Marys Posts: 50
Curve Driving Generator

Ok, I've run into a great problem for all you math and programming guys. I've been working at it since December but I have made no progress. Any help would be so very appreciated. Here goes:

I am trying to create a code that will give the robot the ability to drive curves. Essentially I want to give the function a coordinate - namely a polar vector - and have it spit out the left and right speeds that the robot needs to travel to drive in a smooth curve. If there is any way possible to integrate a starting tangent line to the curve - as in say "I want a curve that crosses x and x+dx such that dy/dx @ x is equal to some number -say b" - that would be very advantageous in that I could link two curves together to have the robot not only drive in a smooth curve but also face a certain direction when it reaches its final point.

So far I have figured that we would need to consider a). the currents current speed, b). the robots current direction that it is facing and c). the arc length that the curve would need to be. I have also figured that the distance that right wheel would travel (Rd), the distance the left wheel would travel (Ld) and the speeds of the wheels (Rv and Lv) are related in this manner: Ld/Rd = Lv/Rv. ---> this relationship was based on assuming that the time for each wheel to travel a distance would be the same (and thus the velocities are different).

Note: I'm trying to keep the curves as simple as possible. For now I just want to deal with curves going to the 1st and 2nd quadrants - assuming the current robot's position is at the origin. I DO NOT want to deal with the robot driving to points to where it has to turn past (+-)PI/2 (90 degrees).

PS: Lets not discuss why we would or would not do this but instead, focus on how. Thanks!

Last edited by theNerd : 03-29-2012 at 09:30 PM.
#2
03-29-2012, 11:13 PM
 DriftVelocity Formerly known as PAR_WIG1350 AKA: Alan Wells FRC #1350 (Rambots) Team Role: Alumni Join Date: Dec 2009 Rookie Year: 2009 Location: Rhode Island Posts: 1,209
Re: Curve Driving Generator

Um... what kind of drive configuration are you using? If you are using swerve, I could probably help.
__________________
#3
03-30-2012, 12:12 PM
 theNerd Registered User FRC #3329 (Cam Bots) Team Role: Programmer Join Date: Jan 2011 Rookie Year: 2110 Location: St. Marys Posts: 50
Re: Curve Driving Generator

Quote:
 Originally Posted by PAR_WIG1350 Um... what kind of drive configuration are you using? If you are using swerve, I could probably help.
We are using a tank drive.
#4
03-30-2012, 12:07 AM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 9,126
Re: Curve Driving Generator

If you have coordinates and tangents at each endpoint, you can fit a cubic polynomial to those constraints. The result will be a smooth curve which connects the endpoints and has the desired tangent at each end.
Attached Thumbnails

Last edited by Ether : 03-30-2012 at 01:22 AM.
#5
03-30-2012, 12:20 AM
 Hawiian Cadder Registered User AKA: Isaak FRC #0159 (Alpine Robotics) Team Role: CAD Join Date: Feb 2010 Rookie Year: 2003 Location: Fort Colins Colorado Posts: 573
Re: Curve Driving Generator

I worked on a control scheme for a vex robot that assumes the robot is always traveling in a curve with radius R. The difference in power between the sides of the skid steer then becomes K(1/R), thus as the radius of the curve goes to infinity the difference between wheel speeds approaches 0. R had a realistic minimum in my setup (navigating a black tape maze with a light sensor) and so the algorithm worked well. For FRC it would need modification for points where R approached 0.

To achieve smooth controll I would use a PID loop where the direct control was how far side to side the robot was off course. This would control the path, planned such that the arc would cross the intended path at some fraction of the remaining distance to travel. By controlling the average of the two wheel speeds in skid steer, as wheel as the radius of the turn one could achieve any possible path. This would require closed loop motor control, as well as some method to determine where the robot actually was, as opposed to where it needed to be.

Last edited by Hawiian Cadder : 03-30-2012 at 12:51 AM. Reason: Additional info on the aplication to this probelm
#6
03-30-2012, 12:28 AM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 9,126
Re: Curve Driving Generator

Quote:
 Originally Posted by Ether If you have coordinates and tangents at each endpoint, you can fit a cubic polynomial to those constraints. The result will be a smooth curve which connects the endpoints and has the desired direction at each end.
Once you know the equation of the polynomial connecting the starting point and the destination, you can compute the radius of curvature (and thus the required rate of rotation) at any point along the curve.

Last edited by Ether : 03-30-2012 at 01:08 AM.
#7
03-30-2012, 01:12 AM
 ewhitman Registered User FRC #3504 (Girls of Steel) Team Role: Mentor Join Date: Jun 2011 Rookie Year: 2004 Location: Carnegie Mellon University Posts: 12
Re: Curve Driving Generator

Ether is right that the first thing you need to do is plan a path. A polynomial will work find for many situations - you need a 4th order polynomial (y= ax^3+bx^2+cx+d) to fit position and slope at both ends. However, polynomials can give you weird behavior in some situations and can't handle others - you can't get a semi-circle for example.

The math is more complex, but I would recommend looking into splines as a more versatile tool for path planning. Alternately, you could try composing your trajectories entirely of circular arcs and straight segments.

Once you have a path, you can compute the curvature of the path everywhere along it. From the path curvature and the speed, you can compute angular rotation rate (degrees/second). From the rotation rate and the speed, you can get your wheel velocities (using the geometry of your robot).
__________________
2004 - student 1257
2005 - mentor 1257
2006 - mentor 1257
2011 - mentor 3504
2012 - mentor 3504
2013 - mentor 3504
#8
03-30-2012, 02:08 AM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 9,126
Re: Curve Driving Generator

Quote:
 Originally Posted by Ether Once you know the equation of the cubic connecting the starting point and the destination, you can compute the radius of curvature (and thus the required rate of rotation) at any point along the curve.
Attached is an example for starting point = (0,0) with a slope of 1/6
and a finish point = (3,9) with a slope of 2.

The blue line is the path and the red line is the reciprocal of the radius at each point along the curve.

If you download and install Maxima, you can play with the endpoints and see the curve that results.

Quote:
 Originally Posted by ewhitman you need a 4th order polynomial (y= ax^3+bx^2+cx+d)
For the record, that's a third-order polynomial (cubic).

Quote:
 you can't get a semi-circle
semi-circle would be a turn of pi. The OP limited the turn to pi/2.

Quote:
 polynomials can give you weird behavior in some situations... The math is more complex, but I would recommend looking into splines as a more versatile tool for path planning.
If your starting and ending points are such that a single cubic results in a less-than-desirable curve, you can use intermediate waypoints to get to your destination (i.e. cubic splines). I suspect that in this application for many (most?) cases a single cubic will be satisfactory.
Attached Thumbnails

Attached Files
 cubic.pdf (14.5 KB, 66 views)

Last edited by Ether : 03-30-2012 at 02:25 AM.
#9
03-30-2012, 08:28 AM
 dbeckwith Lead Programmer AKA: Daniel Beckwith FRC #3205 (The Patriots) Team Role: Programmer Join Date: Jan 2010 Rookie Year: 2009 Location: USA Posts: 84
Re: Curve Driving Generator

I personally think that Bezier curves are the easiest to deal with, especially if you want a particular tangent on the endpoints. I would recommend reading this.
Once you understand that, programming them in shouldn't be too difficult, you would just advance the t value as the robot goes along to get the next direction you need to drive. The only challenge I really see is converting the coordinates given by the Bezier curve into drive commands, but it shouldn't be too difficult.
__________________
q = (2*b) | ~(2*b);

if (life.getLemons() != null) this.lemonade = new Drink(life.getLemons());
else throw new NoLemonsException("What now?");

#10
03-30-2012, 12:08 PM
 theNerd Registered User FRC #3329 (Cam Bots) Team Role: Programmer Join Date: Jan 2011 Rookie Year: 2110 Location: St. Marys Posts: 50
Re: Curve Driving Generator

Quote:
 Originally Posted by dbeckwith I personally think that Bezier curves are the easiest to deal with
I did some research last night and I was looking at that. However, I'm not sure as to how more efficient bezier curves are to a polynomial - only testing would tell of course.

@Ether: Your idea is great! I like its simplicity, however, I do have a question: What if I don't want the robot to move in a cubic curve? Can this method still be used to create a path that looks similar to x^(1/2) - except with a bit more curve. Also, what if the current heading angle was a slope of infinity? And, instead of using matrices (as my knowledge is extremely rustic and could use some brushing up ) could I use a Taylor polynomial instead and achieve the same result - what I mean is I have no idea how to solve for the parameters using matrices.

Last edited by theNerd : 03-30-2012 at 12:15 PM.
#11
03-30-2012, 07:24 PM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 9,126
Re: Curve Driving Generator

Quote:
 Originally Posted by theNerd I have no idea how to solve for the parameters using matrices.
You don't have to use matrix math if you don't want to. You can use plain ole algebra.

Attached PDF has the cookbook formulas for computing a, b, c, d.

a=-(-2*y2+2*y1+(m2+m1)*x2+(-m2-m1)*x1)/(-x2^3+3*x1*x2^2-3*x1^2*x2+x1^3);

b=(-3*x2*y2+x1*((m2-m1)*x2-3*y2)+(3*x2+3*x1)*y1+(m2+2*m1)*x2^2+(-2*m2-m1)*x1^2)/(-x2^3+3*x1*x2^2-3*x1^2*x2+x1^3);

c=-(x1*((2*m2+m1)*x2^2-6*x2*y2)+6*x1*x2*y1+m1*x2^3+(-m2-2*m1)*x1^2*x2-m2*x1^3)/(-x2^3+3*x1*x2^2-3*x1^2*x2+x1^3);

d=(x1^2*((m2-m1)*x2^2-3*x2*y2)+x1^3*(y2-m2*x2)+(3*x1*x2^2-x2^3)*y1+m1*x1*x2^3)/(-x2^3+3*x1*x2^2-3*x1^2*x2+x1^3);

Attached Files
 formulas for abcd.pdf (10.4 KB, 104 views)

Last edited by Ether : 03-30-2012 at 07:29 PM.
#12
03-30-2012, 09:01 PM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 9,126
Re: Curve Driving Generator

Quote:
 Originally Posted by theNerd what if the current heading angle was a slope of infinity?
Pick a coordinate system whose origin is the starting point and whose positive X axis aligns with the starting direction of motion.

Compute the ending point (X2,Y2) and slope m2 in that coordinate system.

Then the cubic becomes simply Y = aX3 + bX2

and the formulas for a and b are simply

a = (m2X2 - 2Y2)/X23

b = (3Y2 - m2X2)/X22
#13
03-30-2012, 09:09 PM
 Whippet Still Addicted to Chief Delphi AKA: Luis Trueba FRC #4301 (New Tech Narcissists) Team Role: Alumni Join Date: Feb 2011 Rookie Year: 2011 Location: Cambridge, MA Posts: 1,214
Re: Curve Driving Generator

Why not use tank control mode? That way, you can drive curves, but it takes a little more practice to use. It's just a matter of willingness to learn, but will save a lot of time programming. So it's kind of a double-edged sword.

Last edited by Whippet : 03-30-2012 at 09:38 PM.
#14
03-30-2012, 09:45 PM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 9,126
Re: Curve Driving Generator

Quote:
 Originally Posted by Whippet Why not use tank control mode? That way, you can drive curves, but it takes a little more practice to use. It's just a matter of willingness to learn, but will save a lot of time programming.
That's not what the OP wants to discuss:

Quote:
 Originally Posted by theNerd Lets not discuss why we would or would not do this but instead, focus on how. Thanks!
#15
03-30-2012, 10:06 PM
 MichaelBick Registered User FRC #1836 (MilkenKnights) Team Role: Alumni Join Date: Oct 2011 Rookie Year: 2010 Location: Los Angeles Posts: 771
Re: Curve Driving Generator

Quote:
 Originally Posted by Whippet Why not use tank control mode? That way, you can drive curves, but it takes a little more practice to use. It's just a matter of willingness to learn, but tank mode can do curves, and will save a lot of time programming. So it's kind of a double-edged sword.
I agree. One of the reasons that a lowered center drive(I'm assuming not 4 wheel or treads, as I would not try these maneuvers with those drivetrains) is so competitive, is because it needs very little programming. Sure, some teams have more complex code(I'm thinking 254 with their physics engine for turn radius) that is really nice, it is not worth the effort for the negligible gain, unless you have extra time(like maybe getting a camera working and shooting accurately).
__________________
Team 1836 - The Milken Knights
2013 LA Regional Champions with 1717 and 973
2012 LA Regional Finalists with 294 and 973
To go to our website, go to http://milkenknights.com/index.html

 Thread Tools Display Modes Rate This Thread Hybrid Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 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 User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Announcements     User Announcements FIRST     General Forum     Rumor Mill     Career     Robot Showcase Technical     Technical Discussion     Robotics Education and Curriculum     Motors     Electrical         CAN     Programming         NI LabVIEW         C/C++         Java         Python     Sensors     Control System     Pneumatics     Kit & Additional Hardware     CAD         Inventor         SolidWorks         Creo     IT / Communications         3D Animation and Competition         Website Design/Showcase         Videography and Photography         Computer Graphics Competition     Awards         Chairman's Award     Rules/Strategy         Scouting     Team Organization         Fundraising         Starting New Teams         Finding A Team         College Teams     Championship Event     Regional Competitions     District Events     Off-Season Events     Thanks and/or Congrats     FRC Game Design     OCCRA         OCCRA Q&A Other     Chit-Chat         Games/Trivia         Fantasy FIRST     Car Nack's Corner     College & University Education     Dean Kamen's Inventions     FIRST-related Organizations         The Blue Alliance     FIRST In the News...     FIRST Lego League     FIRST Tech Challenge     VEX     Televised Robotics     Math and Science     Robot in 3 Days (RI3D)     NASA Discussion ChiefDelphi.com Website     CD Forum Support     Extra Discussion

All times are GMT -5. The time now is 04:44 AM.

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

 -- English (12 hour) -- English (24 hour) Contact Us - Chief Delphi - Rules - Archive - Top