So, I want to make a robot that is able to navigate through an unknown maze. The only information provided to it would be a monochromatic bitmap image of the maze , and the robot has to identify the start and end points from it, the boxes in which it has to pot the balls it carries, and as well plan its path in the maze. It has to do all of it from that bmp image of the maze. Here's a link to a sample Bitmap Image of a Maze.
I will be using arduino due to do all of this processing. For now, I have read this BMP into a 2D character array, Link to the character array, made a connectivity map/graph from it so that a path planning algorithm could be applied on it (Dijkstra or Breadth First Search).
The problem however is the following, the size of this bitmap is 96x56 pixels. That means the size of the connectivity map/ graph would be [5376][5376] which is very large. To declare this large of an array would require memory in MB whereas the SRAM of the arduino due is only 96KB.
What should I do? Please suggest. I am just a first year electrical engineering student and so don't know much about all of this stuff. One thing that I thought of was to delete the rows that are same (please see the 2D array). However then I thought it, itself will require lots of processing power since I will have to compare every row to others, element by element. The problem here basically are the memory and processing constraints.
I would grateful!
You actually don't have to explicitly store your entire graph in memory. Alternatively, each time the algorithm visits a state, you can query the bitmap to see which neighbors are occupied are not, and generate the valid transitions/costs accordingly. This will take more processing power but will keep the motion model within the memory limitations of the processor.
However, for BFS or Dijkstra's algorithm, you will also have to store a queue of visited states, which could grow exponentially. You might want to consider use of A* instead of Dijkstra's algorithm because A* will explore fewer states than Dijkstra's algorithm to find the optimal solution.