LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Automated Maze Solver - Real Time Path Planning Algorithm

Hi, I am planning to create an automated maze solver, (like the one shown below), using 2 servos and a webcam on the top. I am wondering if somebody could guide me a little bit about the NI module I need to use, the way to approach this problem and how to create an algorithm able to find the shortest path and somehow avoid the inner walls.

 

Thanks in advance

 

 

0 Kudos
Message 1 of 3
(3,072 Views)

You have two very different tasks.  One is designing a control mechanism to move the marble around the grid (I hope you have planned both "actuators" (tilters, shown) and "measurers" (something to tell you where the marble really is).  Depending on a number of features of your system, this could be an interesting exercise in DAQmx control.

 

The other is the "how do you solve a maze" question.  Have you thought at all about this?  Have you done any research (other than to ask here for help)?

 

There are a number of ways to approach this problem.  For simplicity, assume you are moving on an N x M grid, and can move left or right one number, up or down one number, but not diagonally.  Let's say you start at X, Y.  You have up to 4 moves -- (X-1, Y), (X+1, Y), (X, Y-1), (X, Y+1).  Some of these moves might be "impossible" -- it goes off the Grid, or it hits a wall.  Another possibility is you've already been there!  If any of these situations arises, then that particular move cannot be part of a solution.  So you have two possibilities -- either you have one (or more) possible moves from (X, Y), implying that this point might be part of the solution, or you have no possible moves, which tells you that (X, Y) is not part of the Solution.

 

If there's a move you can make, then make it, and repeat the above process starting from the new location.  If there is no move to make, go back to the move that brought you to (X, Y), mark that as "not part of the solution", and see if there are further moves to make from this earlier level.

 

Eventually, you will either arrive at the Goal or you will have exhausted all the possible moves (which means the Maze has no solution).

 

This type of algorithm where you start somewhere, do what you can from there and either succeed or "fail", and if you fail, go back to where you came from (sorry about the clumsy language) is called "Recursion", and is quite powerful.  Here's a simpler example -- I want to know all of the File Names in a Folder and all of its sub-Folders.  The recursive algorithm shown below will do just that.  We call List Folder to get a list of the Files and Folders in "Folder Path".  From the array of Files, we create an Array of Paths to those files.  From the array of Folders (the lower loop), we create an Array of sub-Folder Paths and call ourselves "recursively", getting (if the Magic works) an array of all of the File Paths in all of the sub-Folders.  Concatenate those together and we have all of the Files in this Folder and all its sub-Folders.
RECUR Find All Files.png

 

You can apply the same idea of Recursion to your Maze question.  "From where I am, if I'm not at the Exit, move a (legal) step if possible and call myself recursively, "failing" if I have no legal moves.

 

Good Luck on both parts of this project.

 

Bob Schor

 

P.S. -- the code is pretty much "out in the open" here (though you need to mark the VI "Share Clone Reentrancy" on the "Execution" tab), but I've attached the VI coded in LabVIEW 2016, if you're impatient ...

0 Kudos
Message 2 of 3
(3,044 Views)

Hi thank you for the information. Yes one servo is controlling the x axis and the other the y axis (independently of each other) and there is a webcam for ball and wall detection. Im using Myrio.

 

I have heard about the recursive algorithm but I am also wondering if the A* and the AD* algorithms can be implemented. I have seen that the NI Robotics Module have these 2 VIs but I am not sure whether they can be used for this purpose or it is just for simulations. What about using the "Robotic algorithms" from the Robotics Module for Myrio and roboRIO?

 

Thanks again

 

 

0 Kudos
Message 3 of 3
(3,028 Views)