# programming problems in memory

i am trying to make a maze solving robot which takes some data from the sensors… keep it in its memory … sort it to find the shortest route and execute.
but there are three problems:

A) how to write a program that will store the data from the sensors…

B) how to write a program that will sort the data…

C) how to write a program that will execute the sorted data…

You probably need to back up a little from this complex project and work through some of the simple stuff to get an idea of how this stuff works. The nature of your questions makes it sound like you are trying to jump right into the deep end of the pool before you even learn to swim.

A) What have you written so far? B) What sensors are you talking about? C) How many sensors are there? D) How frequent do they make measurements? E) What data do they produce? F) What do you mean by sorting that data? Sorting makes no sense for certain kinds of data? G) What do you mean by executing sorted data?

luv_anu: i am trying to make a maze solving robot which takes some data from the sensors.... keep it in its memory ..... sort it to find the shortest route and execute.

First you will need to have a data structure that stores the maze.

I.e. for a 2D maze this could be a 2D array, where "1" represents "wall" and "0" represents "free".

This maze would consist of a 10x10 2D array, has one IN and one OUT position where the robot can walk in and out:

``````byte maze [10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,0,0,1,0,0,1,0,0}, OUT
{1,0,0,0,1,0,0,1,0,1},
{1,0,0,0,1,0,0,1,0,1},
{1,0,0,0,0,0,0,1,0,1},
{1,0,0,1,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,0,1,1,1,1,1,1,1},
}    IN
``````

Each position in the array is represented by a (row, column) index into the array. This maze example has two solution where it is possible to walk from IN to OUT: A shorter and a longer path.

You will need an algorithm to find the shortest path from IN to OUT.

And your robot and the sensors need a way to sense the position in the maze. If the maze is known, the only thing you will have to store besides of the maze is the robot position (row, column) within the maze. The difficulty then is - to sense the robot position - to direct the robot to walk where you want (shortest path IN to OUT)

yes , i know that i am a rookie in arduino programming..... that is why i need help of you people for proper guidance.........

and about my project.... in detail..... it is a line maze solving robot .. which will follow white line on a black surface..... where i am going to use 3 infrared sensors to take the input signal and two wheals to turn raght or left. thats all thank you :)

luv_anu: yes , i know that i am a rookie in arduino programming..... that is why i need help of you people for proper guidance.........

Again, this is like someone who can't swim at all trying to cross the Atlantic ocean and saying, "Yeah, I know I can't swim that's why I need the Coast Guard." You're going to fail and eventually the Coast Guard will get tired of rescuing you and you drown.

Start simple. Otherwise this just turns into US writing some code that you will never understand.

so from where should i start.... i know basic arduino programming ...... like reading data, using that data to execute some other functions....... but basically this memory thing is quite new for me, so that is why i am asking you people to guide me... so i can move forward in completing this project.

Do you understand response #3 from @jurs?

luv_anu: so from where should i start.... i know basic arduino programming ...... like reading data, using that data to and about my project.... in detail..... it is a line maze solving robot .. which will follow white line on a black surface..... where i am going to use 3 infrared sensors to take the input signal and two wheals to turn raght or left.

A line-on-the-floor-maze is also a 2D maze, just as the walls-around-room-maze I showed above.

But possibly you want to mark the line in your data structure and not the walls (as I showed above).

If you absolutely don't know anything about data structures, algorithms and programming, it would possibly be a better idea if you NOT wanted to find "the shortest path", but if you do it simpler: "find any path out", no matter whether the path is long or short.

Do you have a picture of an example maze?

So a linefollowing robot has a maze instead of just a line. That implies there are intersections or branches. Can your detectors detect intersections? I would start coding for that. It will be more difficult than you expect.

Then the data structure to 'solve' the maze will just be a list of choices taken at intersections. A simple list of left and right unless there are cross intersections.

yes @MorganS, we can detect intersections, as i said earlier, i am going to use 3 infra red sensors which will be detecting the white line, therefore for example, if i came across a ‘T’ intersection, my sensors will read ‘0-0-0’ and if i came across right turn on my straight path, it will sense ‘1-0-0’ … like that…

so i am also uploading a pic of our sample maze… have a look at it and suggest something.

It will be more difficult than you expect. Get that part working first.

So how are you expected to "solve" the maze? Do you get given a picture and your software has to plan out a set of moves in advance? Or is the maze "unknown" and the robot has to discover the maze by itself?

For an unknown maze, use an algorithm like "follow the left wall": always take every left turn whenever possible. It's surprising how good this is compared to the complex algorithms. Anything more complex must explore the maze so it has to cover more territory than the simple algorithm. The only time that "follow the left wall" doesn't work is when the goal is in the centre.

yes @MorganS........ i was going to follow the algorithm of "follow the left wall" or in my case " follow the left line" ... the maze is to be discovered by the bot itself. the logic that i am going to use is that, if my bot makes a "U" turn from a dead end after a intersection.... like "S-U-L" that is straight ,u-turn and then left.... should be replaced by a right "R"... and in a loop,"L -R-R-L" shold be replaced by "S" (straight)

but i am unable to apply my logic into the coding. this s where i am stuck :(

but i am unable to apply my logic into the coding

What have you written so far?

Remember to use code tags.

luv_anu: the maze is to be discovered by the bot itself.

In case the maze is unknown in the beginning and has to be explored by the robot, you never can make sure to "find the shortest route".

While it is possible that the robot finds the shortest route by chance, it is more likely that in a non-trivial maze the robot will find a longer route than the shortest possible route.

You never can avoid a longer than the shortest possible route when navigating through an unknown maze. So I don't understand why you mentioned "the shortest route" in your initial posting. For finding "the shortest route" you will need to have a map of the maze first.

luv_anu: but i am unable to apply my logic into the coding. this s where i am stuck

Do you have a "line follower" code ready, which can follow a single straight line with no turns?

Do you have a "line follower" code ready, which can follow a single line which contains 90° angle turns, but no T-junctions and no line crossings?

First step would be to create a code that can follow a line. 1.) Follow a single straight line 2.) Follow a single line with 90°-turns and U-turn at the end of the line 3.) Follow a line and create 90°-turns at T-junctions and crossings 4.) "Solving a maze" would be the last step of development, I'd say. What is your robot able to do?

okay @jurs … i will try doing this. actually i have a "line follower"code ready, but it is only consisting of one infra-red sensor… now i have to accommodate three IR sensors in that code…

i’ll try and let you know

luv_anu: yes @MorganS........ i was going to follow the algorithm of "follow the left wall" or in my case " follow the left line" ... the maze is to be discovered by the bot itself. the logic that i am going to use is that, if my bot makes a "U" turn from a dead end after a intersection.... like "S-U-L" that is straight ,u-turn and then left.... should be replaced by a right "R"... and in a loop,"L -R-R-L" shold be replaced by "S" (straight)

but i am unable to apply my logic into the coding. this s where i am stuck :(

Why do you need to reduce S-U-L to R? Once the robot has discovered the exit, isn't its task complete? Or does it have to go back to the beginning via the slightly-shortened path?

yes @MorganS… actually the task is of two rounds… first is the dry run where the bot will run into the maze through all the paths and reach the finish point…

in the second round, the bot needs to reach the finish point by using shortest possible path from the starting end…

that is why it needs to hold up turns in its memory that the bot takes… so that he doesn’t repeat them, and eventually correct them…

in the second round, the bot needs to reach the finish point by using shortest possible path from the starting end.......

Does that really mean that robot needs to find the shortest path? Or, does it mean that the robot must simply repeat the path that it eventually found, from start to end, with no wrong turns? The programming is quite different.

I read it as sending the bot out into the maze to map it and then processing the map. When it finds the exit on the first pass it should U-turn and keep exploring. (How does it detect that it is an exit and not a dead end?) If just using the follow-left-wall algorithm, then it will know two paths from the entrance to the exit.

By reducing wrong turns S-U-L to R then it has two candidate paths to select for distance or time. (Corners may be slower so the shortest path may not be the fastest.) So it also needs to measure distance between each intersection. That is a surprisingly difficult task on its own.

That kind of map processing requires a high level language. Perhaps you need to make your own. That won't be a good fit for Arduino. You need a big computer with a proper screen to be able to monitor the algorithm and tweak it.

This seems like a big project, but fun.