Moving a Robot, Part 2: Heading Issues

So in our previous episode, we discussed how to move a two wheeled robot. However, we mentioned that there’s a problem with computing the angle delta:

\Delta \phi = \phi_{new} - \phi

The problem is angle wraparound.

There are two primary ways of representing a heading:  either as an angle in the closed interval [-π, π] or an angle in the closed interval [0, 2π].  If you compute the difference between two angles in either representation, you will likely end up with an angle that is outside the interval due to wraparound, and you will have to correct it.  This correction can be tricky and fraught with peril, since you’ll likely be chasing after special cases.

So, let’s keep it simple, instead.

First, we’ll keep our headings in the interval [-π, π].  Why? Because there’s a nifty trick you can use with the four-quadrant arctangent function, atan2(), that forces any angle to this interval, to wit:

\phi_{corrected} = \mathrm{atan2}(\sin \phi, \cos \phi)

Once we’ve corrected \phi_{new} and \phi, we compute the difference as usual, plus an additional delta:

\Delta \phi_1 = \phi_{new} - \phi

\Delta \phi_2 = 2 \pi - |\Delta \phi_1|

Now, if \Delta \phi_1 is greater than zero, \Delta \phi_2 will need to be negated.  Once that is done, we return the appropriate result, based on whether the absolute value of \Delta \phi_1 is less than the absolute value of \Delta \phi_2.  If it is, we use \Delta \phi_1, otherwise, use \Delta \phi_2.

When we’re done, we’ll have a properly corrected \Delta \phi that can be used in a controller, or for any other application that requires angle steering.

And that’s it!  Later: all that “real” steering stuff.

Posted in General | Tagged , | 1 Comment

Montana

As it has been for the past few years, I traveled with some of my work compatriots to Big Sky, Montana for the IEEE Aerospace Conference.  A conference that is more likely better known for being held at a ski resort than for the technical content.

So, Montana.

Let me preface this by saying that I’m from the middle Georgia area. It’s a slightly hilly region in some places, but overall, relatively flat and covered with trees.

And then I travel to Montana.

Wide open plains with few trees; tall mountains blue and white on the horizon; great rock walls punctuated by houses erected in their shadow; rivers flowing down, down along their sides; grand snow-covered peaks.

A place where the people are happy to say that, yes, they’re all cowboys and cowgirls in Montana.

Montana has…Montana has gravitas. 

I think that is the best way that I can describe it.

It’s a place where the adventuring spirit still thrives, if you know where to look for it.

One of these days, when not attached to a conference, I’d like to go back to Montana and just explore.  What I’ve been unknowingly searching for all these years is surely there, somewhere.

Posted in General | Tagged , | Comments Off on Montana

Moving a robot, part 1

So you decide that you want to move a wheeled robot around because you happen to have a wheeled robot that needs programming.  That’s great!  Let’s talk about that a little.

Preliminaries

Let’s assume that your robot can obtain a rough estimate of where it is located in some Cartesian coordinate system.  For example, it has wheel encoders that allow you to measure how far it has traveled, and from this, dead reckoning can be used to compute an (x, y) position. The robot can also determine its orientation (i.e., heading), which we’ll refer to as φ (phi).  We’ll reference its orientation to the x-axis; that is, the robot is at zero degrees heading if its “head” is sitting on the x-axis.

The goal: we want to travel from some starting point (x0, y0) to a waypoint (xd, yd).

Should be pretty straightforward, right?  Well, here are some things to keep in mind:

  1. The robot’s position is a rough estimate, remember? Therefore, there is uncertainty in the position.
  2. This uncertainty will accumulate as the robot travels, and for a simple dead reckoning process without some way of reducing this uncertainty (e.g., a measurement of GPS position fused with your dead reckoning), this uncertainty will grow without bound.
  3. There is always uncertainty in the position no matter how hard you try, because of nonlinearities in the way the robot moves.
  4. Because of the above, your robot has a very high likelihood of just driving by the goal point without even knowing it.
  5. GPS will not save you because there’s always at least 1 meter of error unless you’ve got something crazy like RTK-GPS, which is friggin’ expensive and not something you can mount on your little two-wheeled robot.  Also, you’re probably doing this inside, so forget GPS in general.

Checkpointing

After all that, you might be saying to yourself, “Well, crap.”

Not to worry! There are some simple things you can do to mitigate this uncertainty.

Here’s the main one we’ll mention: do not attempt to travel from your starting point to your goal point in one fell swoop.  Take it in little steps – generate checkpoints between the start and goal, and drive to each of those checkpoints in turn.  This will prevent positional errors from messing your robot up too much since they won’t accumulate as quickly between points.

An algorithm for doing so is as follows:

  1. Pick the maximum distance you want between checkpoints.
  2. Pick the maximum number of checkpoints you want between your current position and the goal.
  3. Set the initial checkpoint to be the goal.
  4. For each potential checkpoint:
    1. Compute the distance between the current robot position and the checkpoint.
    2. If the distance is less than or equal to the maximum checkpoint distance, you’re done, you have your checkpoint.
    3. Otherwise, calculate the midpoint between the current robot position and the checkpoint, and try again.

A Tale of Two Velocities

Once you have your checkpoint, we need to steer the robot toward it and move there.  Now how exactly do we do that?

As we said before, we have the robot’s heading.  So what we want to do is turn the robot toward the point and move to the point, generally at the same time.  Therefore, we have two degrees of freedom for controlling the robot’s speed: the linear velocity (denoted by v) and the turn rate/angular velocity (denoted by ω).

How do we compute the appropriate velocities to get us to our point smoothly and (mostly) error-free?

We start by mentioning that our robot has certain performance parameters: it likely can’t move faster than some certain speed, and certainly can’t move slower than a certain speed.  These are tied directly to how fast it can turn, as well.

Therefore, to navigate to a point in a nice smooth fashion without building up errors, we can gradually speed up until we reach a maximum speed, and slow down as we approach the point.  We do this by sliding the velocities between the minima and maxima, based on the current distance from a given heading and a given point.

The robot’s current state is:

\mathbf{x}_{robot} = (x_{current}, y_{current}, \phi)

First, we compute the distance between the current position and our destination:

\Delta x = x_{dest} - x_{current}

\Delta y = y_{dest} - y_{current}

d = \sqrt{\Delta x^2 + \Delta y^2}

We next compute the heading that the robot must have to move in the direction of the point:

\phi_{new} = \mathrm{atan2}(\Delta y, \Delta x)

where atan2() is the four-quadrant arctangent function.

Figure out how far we need to go in angle:

\Delta \phi = \phi_{new} - \phi

(There are some subtleties in computing this angle delta; i.e., it’s incredibly easy to get this wrong in some way even though it looks so deadly simple.  We’ll examine these subtleties in a future post.)

We can now compute the appropriate angular velocity based on the robot’s angular velocity limits:

\omega = \omega_{min} + \frac{|\Delta \phi|}{\pi} (\omega_{max} - \omega_{min})The weighting factor causes the robot to add increments of angular velocity in terms of π-units.

We can also compute the linear velocity:

v = v_{min} + \frac{d}{d_{sep}\sqrt{2}} (v_{max} - v_{min})

The weighting factor in this case has a “separation distance” dsep that is used to control the “units” of speed added, similar to that for angular velocity. The \sqrt{2} is merely an additional weighting factor.

And that’s it! We keep driving the robot and recomputing these velocities as we go, until we reach our destination.*

What we’ve really done here is developed a very simple pair of set-point, proportional, feedback controllers.  Simple, but they get the job done, as you can see.

(* There are subtleties in calculating these velocities as well, much like computing the \Delta \phi …mostly with respect to the what the robot can actually do.  We’ll talk about those later, as well)

That Waypoint Uncertainty Thing

Of course, once you get to the waypoint, as said before, there’s some uncertainty there.  The robot could drive right past it because of: numerical errors in computation, nonlinearities in the motors, nonlinearities in the encoders, so on and so forth.

Therefore, what we do is establish a region of convergence around a waypoint.  That’s a pretty complicated term for “draw a circle around the waypoint”, or “when the robot gets within a certain distance of the waypoint, it is the same as having arrived right on top of the waypoint.”

Uncertainty problem? Handled.  Not fixed, but handled.  That’s good enough for what we’re trying to do here.

Conclusion

And there you go, that’s how you can drive a wheeled robot around.  You even learned a little control theory!

Tune in next time when I finally get around to talking about all those subtleties I kept mentioning.  It’s probably good that you do, because these subtleties can really ruin your day if you’re not careful.

Also, we’ll talk about how to translate those velocities into something a robot can actually use at a low level.

Posted in General | Tagged , | 1 Comment

Followup to the previous.

So yesterday’s post was an attempt at spoken word in blog format; not so sure how it will age, but it was worth a try.

And yes, I really do have those odd little neuroses.  Although what I wrote may seem to imply it, they don’t exactly rule my life. They just like to pop in and make faces at me from time to time. Everyone has their own, I’m sure of it. Mine were just borne of a not very fun time in my earlier life.

There you go.

Posted in General | Tagged | Comments Off on Followup to the previous.

On Bullying.

(Inspired by this wonderful video that everyone who has ever been bullied or not must watch.

There has been a lot of dialogue recently about bullying. A lot of that dialogue is coming from the mouths of some very beautiful people.  They’re people I’m not sure that have ever really been bullied.

At least, the kind of bullying they’re talking about, of course.

Do the beautiful people know what it’s really like?

Do they know what it’s like when you’re called names just because you have something that is only a little different, like wearing glasses?

The names are dumb, but they’re said with such force.

Do they know this force?  Do they know how it presses against you?

Do they know how it makes your heart crack?

Let me tell you a story.

Continue reading

Posted in General | Tagged | Comments Off on On Bullying.

Stuck at home.

So, uh, well. I have no good excuses for my recent behavior as of late.

This behavior being having read all of Homestuck for the past few days.  This was purely out of curiosity, since I attempted to read Homestuck once before, but I stopped somewhere near the beginning.

Curiosity can do bad things, such as killing cats.

Now, excuse me, I’m going to rave like a lunatic for a moment.  I haven’t had a good rave in a while.  This’ll be a good one.

Here we go:

omg

omg

omg it’s like

it’s like

it’s like I CAN SEE THE FNORDS

on the internet

the fnords

they are everywhere

that is

the fnords are HOMESTUCK REFERENCES.

EVERYWHERE.

I SEE THEM EVERYWHERE  NOW

EVERY. WHERE.

I CAN SEE THE HIDDEN PATTERNS OF THE WEB

i may have

i may have been making references WITHOUT EVEN KNOWING

AAAaaAAAAahAGHGHAH–

…Okay, that’s enough.

I can see why Homestuck has the fanbase it does, although I will make no attempts to understand that fanbase, because I believe it may be beyond comprehension.  The comic (if you can even call it that; it’s more like an elaborate art project at times) seems to have some interesting things to say.

And, at least now I understand why I saw so many people wearing white shirts with a single symbol on them at Dragon*Con last year.  So much Homestuck cosplay. So much.

 

Posted in Comics | Tagged | Comments Off on Stuck at home.

Climbing Up on Solsbury Hill.

I can’t seem to stop listening to this Peter Gabriel classic as of late:

https://www.youtube.com/watch?v=9fF8wU4Nl9Y

Reminds me an awful lot of how things were for me several years ago, before I decided to do what I’m doing now.

Posted in General | Tagged | Comments Off on Climbing Up on Solsbury Hill.

Back to art.

So, I’ve been wanting a digital tablet for quite some time.  Back in the elder days, I had a Wacom Graphire, buuuut it was the Graphire of the elder days.

What do I mean by that?

The active area was about five inches wide and three inches tall.

You…do the math.  In sum, it wasn’t terribly useful.

I’d been looking at the Cintiq for sometime in the future, because of my poor experience with that Graphire. I didn’t think I could draw without looking directly at the pencil, so to speak.  But I was willing to try again, so I started looking at the Intuos again.

I did not think to look at a tablet that was not made by Wacom. I wasn’t even sure they existed!  But, look, here’s one that Monoprice produces. Monoprice makes things other than extremely cheap cables? They do!

I heard some glowing reviews of this particular tablet, and just look at that price! Is it even possible for it to be that good for that price?

IT IS. I am absolutely in love with this thing, and I’ve only had it two days. I had availed myself of the Manga Studio deal that came out in late 2012, and have just been…spending so much free time drawing with it.

There are some caveats and quirks: for some reason, if the tablet is on a hub and you disable a device, it’ll disable the tablet portion and not the hotkey portion until you plug it back in again. A bit bothersome, but it’s not too much of a problem for a tablet you paid less than $100 for.

I’m still working out the quirks of drawing this way, but I do have some sample work, after the joomp.

In sum, this Monoprice tablet is pretty good stuff! I’m having a ball.

Continue reading

Posted in General | Tagged , | Comments Off on Back to art.

The Graduate. …Student.

So, for the past couple of years, if you were not aware, I’ve been back at Georgia Tech working toward my PhD in electrical and computer engineering (ECE).

Therefore, I’ve been living the life of the not-so-esteemed graduate student.

Much has been written about this…interesting…way a person chooses to live their life.  In fact, there’s even a well-known comic about it.

But I’m now choosing to share my experience with it with you.

Being a graduate student is many things.  You’ll be able to explore ideas quite freely, if you can find time to do it.  You might get to do some neat things.  You might get your name on a neat publication.

You’ll notice the preponderance of “might” in here.

What you’ll mostly get is ambiguous stress that may or may not have a clear source, a need for approval even though that approval is often quite silly, and almost constant disappointment, if you’re not one of the lucky ones.

So one of the things you’ll have to develop as a graduate student is a tough skin.  Or some way to just not care about some things.  Unfortunately, with so much of what I do getting a little too close to my heart, it’s very hard to simply not care.

So yeah, if you choose to do what I’m doing, you might find yourself going through some pain.  Or almost certainly find yourself going through some pain.  Either way, there will be pain.

Although there’s that nice light at the end of the tunnel once you get through all of this.  I’m barely seeing it, myself.

Posted in General | Tagged , | Comments Off on The Graduate. …Student.

Ingress

So, this Ingress thing.

I’ve been playing this off and on for a little bit now. It’s clear that this is some sort of application for improving geodata by framing it within the context of an alternate reality game (ARG), but there are some interesting things going on here despite that.

I am a member of the Resistance, if you were curious.  The only reason why is because I like blue better than green. The stats are so evenly balanced between the two factions that it doesn’t really matter which one you choose.

With that having been said…

This feels very much like the concept of the virtual cache in geocaching.  The portals are generally placed at well-known landmarks (such as the Campanile at Georgia Tech), and often the journey to the portal is just as satisfying as hacking it and claiming it. Virtual geocaches are very much the same way: there is no box of things to find; just a journey to a spot, and then directions to follow to “claim” the cache.

The only difference here is that the claim remains until it is seized by the other team.  And, well, the fact that the cache can be fortified, and attacked, and, oh you know.

And I must say, linking three portals, resulting in a control field is a really neat feeling.

Posted in General | Tagged , , | Comments Off on Ingress