Author Topic: Labyrinth maze solver  (Read 1917 times)

0 Members and 1 Guest are viewing this topic.

Offline yamanoorsaiTopic starter

  • Beginner
  • *
  • Posts: 1
  • Helpful? 0
Labyrinth maze solver
« on: June 24, 2011, 11:15:09 AM »
Hello All,

I am building an automatic maze solver using the following as an inspiration:

Automatic control of maze game
I have built the maze control with steppers and I am using the following stepper motor control board:

I am using a vision system to control the maze solver. I also found a link where this problem has been solved:

They have used template matching to identify the ball. The team mentioned in the above link also uploaded a video where it looks like they have canny edge detection for finding the path and executing a PID algorithm.

OpenCV labyrinth

Now, I have also established template matching and edge detection in opencv. I have also established controls of my stepper via USB serial port. How do I implement the navigation algorithm? How do I implement the PID control? I know the concept of PID control theoretically but I just don't know to implement it using the information from the camera. I am just clueless about making the ball follow the line.


Offline growler

  • Jr. Member
  • **
  • Posts: 24
  • Helpful? 0
Re: Labyrinth maze solver
« Reply #1 on: June 26, 2011, 11:46:03 AM »
So do you have some kind of coordinate data for the balls location and for the projected line of travel?

This is how I would try it, not saying that there is no better way.

First, I would determine the speed I want the ball to travel along the projected path. You need to keep track of this speed as well as the time since starting the run in order to determine where the ball should be at any given moment. Unfortunately just being on that line isn't the goal, the goal is being at a particular place at a particular time, then getting the program to know how to go from one place to the next in the line during the time it takes to run a control loop (ideally).

So you are at position 0, where you want to start, you know your loop takes x seconds to run, and  you want your ball to travel at y cm/seconds so you update the desired position to position 0 + ((y cm/seconds) * (x seconds)) then run the control loop to try to actually get the ball there.

Once you have an idea of where the ball should be at any given time I would think the calculations would go as follows:

1. divide the position error (where the ball is - where the ball should be) into an x and y component, you need both components because you have the 2-axis control.

2. do the pid calculations on each of the x and y compontents,

3. adjust stepper position based on PID

4. Update the desired position and do it again as fast as possible as practical (maybe synced to video data update rate).

Major difficulties I can think of:
I'm not sure what kind of resolution you have in determining error, and in your stepper control. Lower resolution will mean jerkier response which seems bad for this application.

Tuning your PID constants seems like it could be difficult. They will depend on the frequency of your control loop, the output resolution on your steppers (steps/rotation * some factor dealing with mechanical linkage between stepper and tilt mechanism), gravity, various frictional forces, local gravity and other things I haven't thought of so modeling is kind of hard.  Guess and check i guess.

Watch you conversions between absolute error and the x and y components of the error as depending on your variable types I can see rounding errors becoming an issue depending on how you keep track of the current desired position.

Just some ideas off the top of my head, hope its somewhat helpful.

Edit: Ok I was thinking about this some more and I'm not sure PID alone is the best answer here.

Modeling the change in position of the ball over short periods of time with simple equations should be pretty accurate.
Since the ball is rolling you don't really have to worry about the difference between static and dynamic frictional forces and the speeds its going to reach means frictional forces in general won't be varying much.

So I'm guessing you can get a very linear plot of how much force the ball is feeling in a horizontal plane as a function of table tilt.  This could be determined empiricaly with a scale for the mass of the ball, a tilting table and a timer along with some math.

Then you can model the amount of force needed to move the mass of the ball to a given place at a given time at a given velocity.

Then determine the actual output to your steppers as a weighted average of the output called for by your model and from the x and y axis pid controllers.

The reasoning for the model being that the PID controller needs error before it produces any output which means if that is all you are using you are by definition defining in some level of operational error.  I think you would get much smoother results if you also anticipated to some degree what the output should be.
« Last Edit: June 26, 2011, 07:04:44 PM by growler »


Get Your Ad Here