Mechanically Inclined

Useful

It turns out that the best way to get the ball in the labyrinth game  move the way that I want it is to have to have a really good understanding of how it behaves physically. I also need to be able to determine ahead of time if the ball is going to collide with a wall (and react accordingly). Of course I could fiddle with the program endlessly until it sort of does what I want, or I could do the (un)natural thing – crack open some reference books and base it on theory which is liable to save me time and ultimately give the best results (e.g. play the game at superhuman speeds). I’ll post updates as things progress – progress will almost certainly slow now that term has begun and I have 2 (required) other hardcore design projects competing for time. Currently I’m making some cool changes to the algorithm that finds the path for the ball – it will (hopefully) generate essentially a racing line for the ball, the fastest possible path through all turns when considering momentum.

I’ve had the orange book (not to be confused with the orange box) for a while so I’m pretty excited to finally get to read it.

I’ve gotten the PID control system implemented and tuned, and guess what? It’s terrible. The robot doesn’t behave like this anymore, but is slow and boring. The PID control system is good at bringing the ball to a certain point and holding it there, but it is absolutely horrible at taking the ball around corners at high speed because it has no knowledge of inertia and how the ball will respond to control input, resulting in major overshoot if I try to take a corner quickly. So what is the solution? Feed forward – it is essentially giving the control system a knowledge of how the ball will behave, allowing it to predict where it will go and control it well. Which is perfect for me because I want the robot to beat the level FAST (e.g. impressive). I’ll post a video once I implement the feed forward. The performance under PID control just isn’t satisfactory (PIDiful).

*EDIT* After discussing the issue with a professor I realize there is a lot more that I need to do other than feed forward. In fact, calling what I need to do feed forward may in fact be a misnomer. Whatever it’s called I have a decent idea of what it is, I’ll post updates as things progress.

My little game beating robot just beat its first game of labyrinth. It’s a good step, but let met tell you – it wasn’t pretty. I’m using a PID feedback loop except I’ve only implemented the proportional control part with the gain a complete guess. If you’ve ever seen a control system go unstable, you’ve seen what my robot was doing – if you haven’t, it sort of looks like this without the crash. I’ll grab a video once I tame the beast.

In order to have a computer navigate a labyrinth level using my robot I first had to figure out how to get the computer to determine where the walls are, and where the ball and goal is, and then somehow generate a path for the ball to follow. The first step was to get an image into the computer. To do that I used OpenCV to get the video data from the webcam.

Yeah I know, the camera position needs refinement

It turns out that image processing algorithms really like to work with black and white images. So the next step was to convert the image to grayscale.

Conver the image to grayscale before processing

The next thing that I did with was to extract the positions of the ball and the goal. It turns out that there is a technique called a Hough Transform that can extract certain desired shapes (such as a circle) from images, and OpenCV has the ability to use it built in, saving me from having to write a single line of code – well actually thats a lie, I wrote one line, the line used to find the circles (amongst many others). It turns out that the Hough transform was returning a lot of false positives so I blurred the image to get rid of any speckles or small edges using a gaussian blur (built into OpenCV) and then did the Hough Transformation to find round objects to extract the ball and goal locations (as they are both round).

The Image After Blurring

You can see the extracted circle locations drawn on the image below. Drawing the circles on the image is another great feature of OpenCV!

The extracted circle locations drawn on the image

The next step is to extract the positions of the walls – I found the most reliable method was to use an edge finding algorithm. I used the Canny Edge Detector algoritm built into OpenCV, which produced the output seen below (I filled in the circles above the goal and the ball to prevent detecting them as edges). Note that the blurring used in finding the ball and goal also helped false edges from being found.

The edges extracted using a canny filter

Once I had detected the edges, I used a flood fill near the goal to fill what would be any place I could potentially roll on with white, with the assumption being that there would be a path between the ball and the goal. Any place filled with white is a place the ball could potentially go.

Fill the space between the walls with white. This is the locations the ball can roll

At this point I have reduced the image to a monochromatic representation of walls and potential places to roll, as well as retrieved the locations of the ball and the goal. The next step was to reduce it into something that the computer can more easily digest for the path finding routine (where I figure out the best way to get from the ball to the goal).  What I did was to create a two dimensional array 1/16 the size of the image filled with integers. The image from the webcam is 640×480 pixels meaning the array I created was 40×30. I then went across the image horizontally and vertically checking the color of the pixel every 16 pixels. If it was white I filled in the corresponding cell of the array with a 1, otherwise it was a zero. I also filled in the locations of the ball and the goal with a 2. This is confusing. A visualization of the array can be seen below. You can see that it has captured fairly well the locations of the walls and the balls.

The image reduced to 1s and 0s (and 2s).

Now that I had an array of simple integers that represented the geometry of the course I ran an implementation of the A* Search Algoritm which unfortunately did not come with OpenCv so I had to write it. A visulization of the found path can be seen in the image below. The squares filled in with a “7″ correspond to the path that the ball will take through the course. I have highlighted the path in green and the walls in red to help the eye strain. The matrix is good for the computer, bad for humans. You can see that the path is wavy and not actually the most efficient path. This is a result of me leaving out a portion of the A* search algorithm because I was getting OK results and was eager to get to the next step. I will go back and fix it soon.

The path found visualized

Since the matrix was generated by sampling the image every 16 pixels, taking the location of each point of the path found in the matrix and multiplying it by 16 gives the desired location of the ball at each point in screen coordinates (e.g. if I want the next location for the ball to move to is cell 4,8 in the matrix above, that means I want the ball to roll to position 64,128 in the image returned from the camera.

So thats how I go from an image from the webcam to a set of sequential coordinates that I need to move the ball to get through the course. I will post the code eventually – at the moment it is not fit for human consumption.

I’ve gotten my program talking to the arduino over serial (a nightmare to be described at a later time), and am working on the control system to get the ball to go where I want. I’ll post more info as things progress.

The ball linkages for the robot finally came (3 weeks after ordering). It feels really good to get rid of the horrendously ugly bent wires, and the terrible slop that they provided. As with the bearings RC helicopter parts make fantastic and affordable components that work well. Speaking of good components that work well – if you are having trouble finding a certain component for a small project I recommend taking a look at smallparts, they have all sorts of goodies for a wide range of applications.

I realized that it would be very difficult to work on computer vision without giving the computer an eye to see with, so I quickly went to the shop and made the arm that holds the webcam above the iPhone screen. The webcam had a sort of ball joint that attached the camera to a small universal bracket to hold it on a monitor. After removing the bracket I was able to cut the ball off and glue in a tapped aluminum rod to securely screw the camera to the mount (See images below).

I’ve since began working on the program. To have the computer navigate through a labyrinth course, I have to know where the walls are, where the ball is, and where the goal is (as well as any other things such as things that “kill me”), then compute a path for the ball to follow to get to the goal. I’ve been able to extract the position of the ball, the goal, and the positions of the walls from the images, and am about half way through baking up a rudimentary pathfinding algorithm to find the shortest path from the ball to the goal. I’ll post the details whence I get the pathfinding working reliably.

Now that I have the mechanics of the robot finished it is time to move to the software side of things. Ultimately I plan to write a program to play a fast paced shooter game with enemies that spawn and chase you – but since I have no experience with pathfinding, I’m going to start by creating a a program that finds a path through the static environment of a labyrinth game then steers the ball through. It will give me a chance to get a feel for the robot and fine tune its performance –  as well as get used to the computer vision library that I’m using – OpenCV.

The first problem that needed to be addressed before I could start writing code was how to get the images from the webcam into my program… I’ve never written code that communicates over USB, and I’ve heard that it isn’t trivial, so I was hoping to find a library that would abstract all of those details away and present me with an array of pixels from the camera 30 times a second. It turns out exactly what I needed exists – OpenCV. The installation was sort of tricky to get right, but it was well worth it – I’m not only easily getting the images from the webcam, but displaying them, and have quite a lot of powerful image processing tools at my disposal. If you are looking at doing real time computer vision you should take a look at OpenCV. Now to write some real code…

Today the case that will be bonded to the robot to hold the iPhone finally came, allowing me to test the system. I got the cheapest most affordable case that I could find, and it shows. It was supposed to be a white case, but it turns out that it is a clear case painted white with cheap paint that chips (seen in the image below). If you want a colored case, I recommend getting a tinted plastic one, as they are not painted, and will thus not peel.

I recorded a short video of the robot under manual control, including a bit of me playing a game while holding the camera and watching the phone through the camera screen. Its a bit twitchy but completely playable – tuning the logarithmic controls, and possibly adding some filtering should make manual control much better, though the computer shouldn’t have any problem controlling it either way.

I just realized that I’ve made a mechanism to play tilt based phone games with a joystick. Neat.

The 4mm rods came today from mcmaster, finally enabling me to assemble my pieces. I used precision ground tool steel rod. I measured the rod to be 0.01mm under 4mm but I still had to take off 0.03mm to get the bearings onto it – the disadvantage to cheap bearings. The ball linkages that I ordered still haven’t come, so as you can see in the images I’ve quickly rigged some wire linkages to get the system running. I repeat: I quickly rigged some wire linkages to get it running until the ball linkages arrive – it was not designed to have sloppy wire linkages, so don’t judge. I’m also in the processes of getting shorter set screws.

It’s an empowering feeling to command the system to precisely tilt my phone for me – what used to take two hands, now takes one finger, and pretty soon I’ll have the computer doing it for me.

The weakest link of the system is definitely the servos. They center fairly well, but they aren’t optimal, and have exhibited a bit of jitter. We’ll have to see if it impacts the performance.

The shaft that I need to finish the robot should be coming this evening. Since I don’t have the control software built, I built a simple controller that moves the iPhone according to how I move a joystick (e.g. tilt right the phone tilts right, tilt forward, the phone tilts forward etc). An arduino reads the voltage from the center tap of the joystick potentiometers, then converts it to the degrees that the servo should be rotated. It gives the choice of linear control mapping where the rotation of the phone corresponds exactly to the control stick movement, and exponential mapping where the joystick movements around center move the servos less, ramping up as your get away from center – which gives more precision for small movements.

Excuse the unnatural look of the images – I was a bit over zealous with the sharpness tool in photoshop.

Some people complain that arduinos are for ‘noobs’, but I disagree. The arduino allowed me to create a completely programmable test controller for the robot in the span of about 2 hours. Contrast that with fully analog control circuit for my Jr. Design robot, pictured below, which does almost exactly the same function as the circuit I made today (without the awesome exponential control mapping) -except it took 3 months and about 250 hours to make. Of course if I was making 10,000 test controllers the arduino wouldn’t be suitable, and it would be worth engineering a low cost board, but for just one, the arduino rules.