OCCRA
Go to Post Many people follow that advice, as if Ohio is Mordor or something. - Travis Hoffman [more]
Home
Go Back   Chief Delphi > Technical > Programming
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Closed Thread
 
Thread Tools Rate Thread Display Modes
  #1   Spotlight this post!  
Unread 03-29-2012, 09:26 PM
theNerd's Avatar
theNerd theNerd is offline
Registered User
FRC #3329 (Cam Bots)
Team Role: Programmer
 
Join Date: Jan 2011
Rookie Year: 2110
Location: St. Marys
Posts: 51
theNerd is an unknown quantity at this point
Lightbulb 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   Spotlight this post!  
Unread 03-29-2012, 11:13 PM
PAR_WIG1350's Avatar
PAR_WIG1350 PAR_WIG1350 is offline
Registered User
AKA: Alan Wells
FRC #1350 (Rambots)
Team Role: Alumni
 
Join Date: Dec 2009
Rookie Year: 2009
Location: Rhode Island
Posts: 1,205
PAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond reputePAR_WIG1350 has a reputation beyond repute
Re: Curve Driving Generator

Um... what kind of drive configuration are you using? If you are using swerve, I could probably help.
__________________
  #3   Spotlight this post!  
Unread 03-30-2012, 12:12 PM
theNerd's Avatar
theNerd theNerd is offline
Registered User
FRC #3329 (Cam Bots)
Team Role: Programmer
 
Join Date: Jan 2011
Rookie Year: 2110
Location: St. Marys
Posts: 51
theNerd is an unknown quantity at this point
Re: Curve Driving Generator

Quote:
Originally Posted by PAR_WIG1350 View Post
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   Spotlight this post!  
Unread 03-30-2012, 12:07 AM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,723
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
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
Click image for larger version

Name:	cubic.jpg
Views:	491
Size:	110.3 KB
ID:	12467  

Last edited by Ether : 03-30-2012 at 01:22 AM.
  #5   Spotlight this post!  
Unread 03-30-2012, 12:20 AM
Hawiian Cadder's Avatar
Hawiian Cadder Hawiian Cadder is offline
Registered User
AKA: Isaak
FRC #0159 (Alpine Robotics)
Team Role: CAD
 
Join Date: Feb 2010
Rookie Year: 2003
Location: Fort Colins Colorado
Posts: 573
Hawiian Cadder is a name known to allHawiian Cadder is a name known to allHawiian Cadder is a name known to allHawiian Cadder is a name known to allHawiian Cadder is a name known to allHawiian Cadder is a name known to all
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   Spotlight this post!  
Unread 03-30-2012, 12:28 AM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,723
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Curve Driving Generator

Quote:
Originally Posted by Ether View Post

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   Spotlight this post!  
Unread 03-30-2012, 01:12 AM
ewhitman ewhitman is offline
Registered User
FRC #3504 (Girls of Steel)
Team Role: Mentor
 
Join Date: Jun 2011
Rookie Year: 2004
Location: Carnegie Mellon University
Posts: 12
ewhitman is an unknown quantity at this point
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   Spotlight this post!  
Unread 03-30-2012, 02:08 AM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,723
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Curve Driving Generator

Quote:
Originally Posted by Ether View Post
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 View Post
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
Click image for larger version

Name:	graph.png
Views:	200
Size:	14.1 KB
ID:	12469  
Attached Files
File Type: pdf cubic.pdf (14.5 KB, 52 views)

Last edited by Ether : 03-30-2012 at 02:25 AM.
  #9   Spotlight this post!  
Unread 03-30-2012, 08:28 AM
dbeckwith's Avatar
dbeckwith dbeckwith is offline
Lead Programmer
AKA: Daniel Beckwith
FRC #3205 (The Patriots)
Team Role: Programmer
 
Join Date: Jan 2010
Rookie Year: 2009
Location: USA
Posts: 84
dbeckwith is an unknown quantity at this point
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   Spotlight this post!  
Unread 03-30-2012, 12:08 PM
theNerd's Avatar
theNerd theNerd is offline
Registered User
FRC #3329 (Cam Bots)
Team Role: Programmer
 
Join Date: Jan 2011
Rookie Year: 2110
Location: St. Marys
Posts: 51
theNerd is an unknown quantity at this point
Re: Curve Driving Generator

Quote:
Originally Posted by dbeckwith View Post
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   Spotlight this post!  
Unread 03-30-2012, 07:24 PM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,723
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Curve Driving Generator

Quote:
Originally Posted by theNerd View Post
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
File Type: pdf formulas for abcd.pdf (10.4 KB, 78 views)

Last edited by Ether : 03-30-2012 at 07:29 PM.
  #12   Spotlight this post!  
Unread 03-30-2012, 09:01 PM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,723
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Curve Driving Generator

Quote:
Originally Posted by theNerd View Post
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   Spotlight this post!  
Unread 03-30-2012, 09:09 PM
Whippet's Avatar
Whippet Whippet is offline
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,207
Whippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond reputeWhippet has a reputation beyond repute
Send a message via Yahoo to Whippet
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   Spotlight this post!  
Unread 03-30-2012, 09:45 PM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,723
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Curve Driving Generator

Quote:
Originally Posted by Whippet View Post
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 View Post
Lets not discuss why we would or would not do this but instead, focus on how. Thanks!
  #15   Spotlight this post!  
Unread 03-30-2012, 10:06 PM
MichaelBick MichaelBick is offline
Registered User
FRC #1836 (MilkenKnights)
Team Role: Alumni
 
Join Date: Oct 2011
Rookie Year: 2010
Location: Los Angeles
Posts: 756
MichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant futureMichaelBick has a brilliant future
Re: Curve Driving Generator

Quote:
Originally Posted by Whippet View Post
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 follow Team 1836 on Facebook, go to http://www.facebook.com/MilkenKnights
To go to our website, go to http://milkenknights.com/index.html
Closed Thread


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 05:33 PM.

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