A Short Guide to Robot Path Planning

Editors note: For my Advanced Robot Control midterm, I had to write a report answering four questions related to the class. For your reading pleasure, I now present the fruits of my labor. Note, super technical content to follow. Also note, this post is paginated. You can also download the PDF.

In Chapters 2 through 7, Choset has presented a number of different approaches to path planning. Explain in your own words the progression from Chapter 2 to 7. Include brief (synopsis) explanations of each approach (i.e., the main topic of each chapter).

Chapter 2 covers the two bug algorithms, Bug 1 and Bug 2. The Bug 1 algorithm is perhaps one of the most basic of navigating algorithms. The robot begins at the start and proceeds toward the goal until an obstacle is encountered. Once an obstacle is encountered, the robot will completely circumnavigate the obstacle before proceeding toward from the point on the perimeter that has the shortest distance to the goal.

The Bug 2 algorithm is very similar to the Bug 1 algorithm. The primary difference from Bug 1 is that an imaginary line, the M-line, is draw between the start and goal. When the robot encounters an obstacle, it will circumnavigate the obstacle until it reaches the M-line. Once it reaches the M-line, it will start moving toward the goal again; it does not completely circumnavigate the obstacle.

The primary benefits of Bug 1 and Bug 2 is that very little information is needed: a starting point, goal, and a series of touch sensors to determine when the robot runs into an obstacle.

A more advanced version of Bug 2 is the Tangent Bug. Tangent Bug utilizes a sensor of some range from zero to infinity to detect obstacles. When an obstacle is detected, the robot will start moving around the obstacle. The robot will continue its motion-to-goal routine as soon as it has cleared the obstacle.

In order to describe more complicated path planners, we need to be able to specify the position of the robot and the space it occupies. This is known as the configuration space and is the primary topic of chapter two. We used the new idea of configuration space to develop a set of equations that allow us describe the position of multi-joint planar arms. We extended the equations we used to define the movement of planar arms to define points in both R2 and R3. These equations allow us to define the position and orientation of a single point, as well as one point relative to another.

With our new ability to describe robots in a workspace, we can now begin working with more complicate path planning techniques. Path planning is quite different from the previous navigation algorithms we discussed, such as Bug 1, because path planning requires foreknowledge of the obstacles before the robot begins movement. Chapter four starts with a brief discussion on gradients. Gradients are a well studied mathematical function in undergraduate engineering university, which makes them a great introduction for more complex path planning methods. Gradients work by changing the repulsive potential as a robot gets closer to an obstacle. The start point is given a medium gradient potential, the end point is given a low gradient potential, and the obstacles are given high gradient potentials. All the robot needs to do is “roll down the hill.”

The Brushfire Algorithm is a discrete version of the aforementioned gradient algorithm and involves the use of a grid to determine the potential of cells. A variation on the Brushfire Algorithm is the Wave-Front Planner.

The Wave-Front Planner uses a grid, just like the Brushfire Algorithm, and assigns a “1” to each cell that has an obstacle (or part of an obstacle). The start point is labeled “2” and the “wave” propagates from that point. Each adjacent cell, if empty, is given an incrementally higher number until all the cells have a number. If the goal has a number in its cell, the goal is reachable in that many moves minus one. Adjacency can be computed using either four-point connectivity (where only the north, south, east, and west cells are considered adjacent) or eight-point connectivity (where north, south, east, west, and the diagonal cells are considered adjacent).

Sphere space and Star space are essentially extensions of the generalized potential path planning method with one critical difference: they only have one local minimum. Having one local minimum is a desirable quality as it greatly aids in path planning and avoiding dead ends.

Chapter five introduces roadmaps, which is effectively a way to break up the workspace into distinct stages or paths. The Visibility Graph plots straight line paths between the start, goal, and all the vertices of the all the objects in the workspace. The paths may cross over each other; however, they may not intersect an object. Once constructed, the visibility graph can be searched for the shortest path from the start to the goal.

The Generalized Voronoi Diagram extends the idea of the distinct paths by drawing equidistant “roads” between obstacles and the boundaries of the workspace. A similar technique to the GVD is the Silhouette Method, which works by determining the critical points of obstacles within the workspace. A tangent line extends from each critical point, and around the workspace edge. The path from the start to the goal “snaps” to these paths.

Trapezoidal Decomposition, which is the start of chapter six, extends the concept of the Silhouette Method. However, the obstacles (and workspace) must be represented as trapezoids. A vertical extension marks each vertex, separating the workspace into cells. The cells are mapped from the start to goal using an adjacency graph. The path planner plans a path by connecting the midpoints of the vertical extensions. Morse Cell and Boustrophedon Decomposition follow the same concept as Trapezoidal Decomposition. However, the goal in Morse Cell and Boustrophedon is path coverage rather than path planning.

Path coverage, which seeks to optimize the coverage of the workspace, leads into visibility-based decompositions for pursuit and evasion, which deals with how a pursuer attempts to capture prey and how the prey attempts to evade the predator. Specifically discussing how to clear rooms to make them “uncontaminated” and how to determine the number of predators that are required to check a system based on the number of edges in the workspace.

As this point, the path planning algorithms are becoming fairly complex and computationally intensive. So far, our examples have been using small workspaces with only a handful of obstacles. As the workspace size and number of obstacles increase, the time required to find a solution also increases, usually exponentially. Sampling-based Algorithms work by using a best-guess and check method. A path is calculated and then checked to see if it collides with any obstacles. Specific types of planners include Probabilistic Roadmaps (PRM), Randomized Path Planner (RPP), Expanisve-Spaes Trees (EST), Rapidly-exploring Random Trees (RRT), and Single-query, Bi-directional, Lazy collision-checking (SBL). In all examples of sample-based path planning, the chances of finding a successfully path approach zero as the number of samples increase.

Pages: 1 2 3 4

In Seattle For Two Days Only!

My alert sent me an email last night for a last minute, mid-week special on flights to Seattle. It’s been a rather stressful and exhausting last couple of weeks (and it doesn’t look to let up soon either), so I decided to jump on it. Timing couldn’t be better; all the professors tend to let up a little bit right before EDays, so I’m not missing out on much.

Flying in on Alaska 677 which arrives just after 9am this morning and I’ll be taking off tomorrow afternoon at 12:45pm on Alaska 672…just in time for EDays to start.

Who wants to hit up Thai Tom for lunch?

Track my flight: Alaska 667
Track my flight: Alaska 672


EDays 2009: Diamond AnnivarsarE-Days

EDays is upon us once again. And once again, I’ll be taking photos! I’m the official EDays photographer for The Oredigger and the EDays Committee. Last year was great and I got some great photos. But this year. This year is going to be epic. This year, I’ll be renting a Nikon D90 and a Nikkor 12-24 f/4G DX, both from Pro Photo Rental up in Boulder. Thanks to Jared for the hookup and working out all the details with me!

So yes, that means that I’ll be shooting with two cameras. My D70 with an 18-70 (or 50mm) and the rented D90 with 12-24.

I also made up this years new press pass. It’s very similar to last years press pass, but with an updated picture, ID#, and expiration date (natch). I also added some text on the back of the pass.
Total cost: 10 cents for the color laserjet print at school plus $1.25 for the lamination at FedEx Kinko’s.
My enjoyment: Priceless.


I will also, however, have my legitimate concert backstage access/press pass, just like the last three years1, special thanks to Tim Weilert for helping me out with this.

My goal this year is two-fold: shoot more people pictures and take video (which I can do using the D90…in HD no less). I really just hope I have less than 2000 photos to edit.

The Oredigger also published the E-Digger, a guide to Engineering Days. I got2 two full page photos and a double truck3 wide! It’s pretty awesome and I recommend you check out a copy if you’re on campus.

27.0 mm || 1/4000 || f/3.8 || ISO400 || NIKON D70

10.5 mm || 3.3 sec || f/16.0 || ISO200 || NIKON D70
Golden, Colorado, United States

10.5 mm || 18 sec || f/16.0 || ISO200 || NIKON D70
Golden, Colorado, United States

10.5 mm || 1/80 || f/3.5 || ISO1600 || NIKON D70
Golden, Colorado, United States

10.5 mm || 1/1000 || f/7.1 || ISO200 || NIKON D70
Golden, Colorado, United States

I also know there are a couple of Facebook groups that are using my photos too, I basically have the market cornered on “csm edays fireworks.” It’s all good though.

Over the last 5 EDays, I’ve published over 1000 photos4. I’ve gathered them all into one collection over at Flickr: A collection of all EDays photos I’ve ever taken

Stay tuned for this years report, it’s bound to epic.

  1. Holy crap, have I really been doing this for that long?! 

  2. my photos were used on 


  4. I suspect I’ve taken closer to 5000 

School Closed

  • Mines


Originally uploaded by mattmmatt

For the first time in 15 years1, the Colorado School of Mines has a snow day.

Due to severe weather and treacherous driving conditions, Colorado School of Mines will close today (March 26) at noon.

And it really wasn’t a full day either, just a half day. Still, I somehow feel my college experience is now more complete. Rumors are circulating that tomorrow may also be a snow day, but I have my doubts.

  1. says the lunch lady 

The Incubator

Just writing out what I know I need to accomplish in the next 15-45 days. I don’t think I’ve ever had this many projects go supernovae1 on me in such a short period of time.

  • Codename Shakespeare
  • Finish up and publish Rain :: Volume II
  • Finish School/Graduate
    • USOC Project
    • 3-ish short essays
    • 2-ish exams
    • 2-ish finals
    • 10-ish hw assignments
  • Graduation Party
    • Colorado
    • Seattle
  • Plan a two month trip to Europe
    • Visa
    • Lodging
    • Airplane tickets

Will update as needed.

  1. when a project goes supernova, it’s basically near completion, but there’s still a lot of work to be done. very near the deadline, the projects looks like it’s going to fail, but it ends up not. instead, the all the different parts of the project instanteously coalesce into a superdense point and spontaneously eject the completed project in all it’s glory, more or less 

Adam + Natalie, an Engagement Photoshoot

Way back in January, Adam, my friend and fellow schoolmate, asked if I would shoot Natalie and his engagement photos. I had been wanting to expand my experience into portrait-style photography, so of course I said I said, “Yes!”1

This is my first foray into engagment photogaphy and a steping stone to building a semi-professional photography career (Shameless plug, check out Andrew Ferguson Photography).

January isn’t a bad month to take engagement photos in, but Adam and Natalie wanted more of a spring feel. Se we waiting to schedule something until Spring Break in March. The day we picked couldn’t have been better. It was super nice out and not a cloud in the sky. I proposed2 several locations to them. We eventually decided on Red Rocks and Clear Creek.

It’s déjà vu all over again!

44.0 mm || 1/1000 || f/4.5 || ISO200 || NIKON D70
Morrison, Colorado, United States

This is one of my favorite photos from the set, the coloring reminds me of a HDR3 image, even though it’s not

Adam and Natalie
38.0 mm || 1/125 || f/11.0 || ISO200 || NIKON D70
Morrison, Colorado, United States

Photo they used for their wedding invitations

Natalie and Adam
70.0 mm || 1/500 || f/4.5 || ISO200 || NIKON D70
Morrison, Colorado, United States

18.0 mm || 1/2500 || f/3.5 || ISO200 || NIKON D70
Morrison, Colorado, United States

So cute

50.0 mm || 1/8000 || f/1.8 || ISO200 || NIKON D70
Morrison, Colorado, United States

70.0 mm || 1/1600 || f/4.5 || ISO200 || NIKON D70
Golden, Colorado, United States

I stuck a strobe back in the back of the tube with CTB4 gel, worked out really well if you ask me

22.0 mm || 1/100 || f/3.8 || ISO200 || NIKON D70
Golden, Colorado, United States

Okay, maybe this is my favorite shot. I’m just a sucker for people jumping…I have no idea why

Jump Composite
Morrison, Colorado, United States

Continue enjoying the awesomeness over at Flickr: Adam + Natalie, an Engagement Photoshoot

I’m looking for any feedback that anyone wants to give: the good, the bad, and the ugly. I promise not to take feedback the wrong way…I’d rather learn from my mistakes here than be doomed to repeat them again. Let them here or, preferably, on the appropriate Flickr image.

  1. …that’s what she said!! 

  2. pun fully intended 

  3. High Dynamic Range 

  4. Color Temperature Blue 

On Reaching the Mean and the Effect of Self-awareness

Editors note: Here’s a short essay that I wrote for my Introduction to Ethics course. It’s not profound or anything, but I think it’s worth sharing.

After discussing “The Particular Virtues of Character,” in Book II, Chapter 7, Aristotle wonders, “How Can We Reach the Mean?” In Book II, Chapter 9 of Nicoachean Ethics, Aristotle writes, “…virtue of character is a mean…between two vices, one of excess and one of deficiency; and that it is a mean because it aims at the intermediate condition in feelings and actions.” (Book II, Chapter 9, §1)

While Aristotle’s proposition seems to be simple at first glance, Aristotle admits that it is, in fact, “hard work to be excellent.” (Book II, Chapter 9, §2) Aristotle argues that finding the mean in virtuousness is not as easy as calculating the numeric intermediary of two numbers. In fact, Aristotle even admits that not everyone can find the intermediate. (Book II, Chapter 9, §2)

Since it is so hard to reach the exact intermediary, Aristotle suggests (among other things) that we try our best to get as close as we can, taking “the lesser of the evils.” (Book II, Chapter 9, §4) As a scientist (and engineer), I feel that this approach presents a unique paradox.

In quantum mechanics, the simple act of measuring a particle invariably affects its properties. For example, when a photon has a polarity, the only way to determine what polarity the photon has is to test it by filtering it through a like polarity filter. This, however, is a destructive (destroying the information, not the photon itself) test if the two polarities are dissimilar. In short, we have affected the property of our particle by simply measuring it.

In a similar way, one wonders how being consciously aware of one’s position relative to the intermediate affects one’s virtuousness. Although such influence does not have to be destructive, it could also be constructive.

Aristotle uses the examples of becoming angry, giving and spending money. In the case of giving money, Aristotle measures virtue by how well we give money “to the right person, in the right amount, at the right time, for the right end, and in the right way.” (Book II, Chapter 9, §2)

Let us suppose we have a cat that does not chase down mice; is the cat inherently unvirtuous? How could the cat be unvirtuous? It is not in this particular cat’s nature to pursue mice and, not being aware of itself, it does not know any better; even though cats are supposed to chase mice. So let us assume that the cat is not unvirtuous for this reason.

Now, let us suppose that I do not normally tithe, even though I am a church going person; that is to say that it is not in my nature to tithe. Does this make be inherently unvirtuous? Unlike the cat, I cannot claim ignorance, since I am self-aware. I know that in the Bible, Numbers 18:26 states that I “must present a tenth of that tithe as the LORD’s offering.” (NIV) I am aware that I have fallen short of my obligations, and thus I must be unvirtuous. Is it this self-realizing and self-correcting behavior that allows me to be unvirtuous? One could argue that it is because of my ability to know the difference between right and wrong that I am able to virtuous or not.


Electrical Engineering Presentation

  • Mines

Last semester, I was asked to do a presentation for WEBELOS Scout Badge Day on electrical engineering (go figure). Anyway, I was asked to do it again this semester because apparently I’m one of three electrical engineers on campus who they figure is up to the challenge1.

Unfortunately, I don’t have the 4 hours to spare this weekend so I had to pass on helping out. However, they still want to use my presentation2. I still had it on my computer, so wrote some notes in the presenters comments and I’m releasing it under a CC license.

The target audience is pretty young, so I skipped over all the words (at least as much as I could) and went straight to pictures and a couple of videos. The notes are far from complete, so you’ll need to have at least some sort of background in electrical engineering to be able to explain everything.

Let me know if you have any questions and enjoy!

I also a collection of electrical-related images that might be of interest as well:

You’ll need to download both video files and either the PPTX (preferred) or PPT file.

The presentation is released under a Creative Commons license:
Creative Commons License
Electrical Engineering by Andrew Ferguson is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.
Permissions beyond the scope of this license may be available at

  1. I actually have no idea if this is true or not. The email was just addressed to me and two other EE’s 

  2. Which I’m told was “really great” 

T-Shirts I’d Consider Wearing

Someone in my Advanced Robot Control class was wearing this t-shirt:

Engineer's Motto: If it isn't broken, take it apart and fix it.

Engineer's Motto: If it isn't broken, take it apart and fix it.

I had a really good chuckle because that’s totally me. Curious as to where my fellow engineer purchased the shirt, I did a bit of Googling and found a whole slew tshirts that I thought were entertaining to at least look at. I think realistically, I’d really only wear one or two of the t-shirts listed below. So enjoy some engineering humor while I procrastinate this essay as much as possible.

Scientists Dream. Engineers Do.

Scientists Dream. Engineers Do.

Engineer: The glass is twice the size it needs to be.

Engineer: The glass is twice the size it needs to be.

Never question the engineer's judgement.

Never question the engineer's judgement.

Think outside the box

Think outside the box

Engineer Inside

Engineer Inside