Alex's SLE Project

Between my now and my last post, I’ve decided to cut back on the scale of my senior learning experience. Cheaply creating my own swarm bot platform implies doing tons of things that could easily count as standalone projects, including writing a low level mesh network protocol and learning about distributed algorithms. While I feel that I’m capable of doing these things, I just wouldn’t be able to do them in span of my SLE.

So, instead, I’ve decided to focus on creating just one robot, with the ultimate goal of efficiently solving a motion planning problem. In this problem, I will start my robot at a starting point point, S, and then move to my destination point, D. However, the space between the two points will be filled with rectangular obstacles, like so:

As I’ve found in my initial research, there are two major ways to approach this problem: either through grids, or through geometry. With a grid based search, my robot would overlay a grid on the configuration space, and then test each grid box for being passable. Then, with this grid, it would apply a search algorithm, like A* or Dijkstra’s algorithm to find the shortest path. However, this solution does not yield the most optimal shortest path, as it limits turns to conform to geometry of the grid.

For a geometric solution, a visibility graph can be used to reduce the configuration space to a graph of each possible path movement through the obstacles, and then a shortest path can be found with a search algorithm like Dijkstra’s. I spatially and “holistically” understand this method, but I’m still cloudy about the specifics, which are pretty important.

Anyway, speaking in terms of physical things, and real plans, and real schedules, and not theoretical gobbledygook: I got the parts I ordered from Sparkfun today!

I’ll post pictures tomorrow, but for now, here’s a quick inventory of the cooler stuff I got:

• ATMega328 (robot brains)
• Ultrasonic ranger finder (robot eyes)
• Really nice gearmotors (robot legs)
• Wheels and encoders (I can’t really think of an anology, but maybe: “robot feel-where-I-am”s?)

Sparkfun is a really nice company. For someone who has a limited experience in electronics, Sparkfun makes the process easy and non-intimating. I’m not an electrical engineer, and for now, an arcane PDF datasheet doesn’t address my concerns as well as Sparkfun does.

Sadly, I still need a USB compatible AVR programmer to really get started. Tomorrow, while I wait for one rush-shipped (15 bucks, ouch), I’ll continue to bone up on my C, write another blog post (with pictures), and read more of my graph theory book.