go_away

### Author Topic: How does a robot take a second turn in a maze?  (Read 801 times)

0 Members and 1 Guest are viewing this topic.

#### kiranvasudev

• Beginner
• Posts: 5
• Helpful? 0
##### How does a robot take a second turn in a maze?
« on: June 11, 2013, 11:12:51 AM »
I am doing a new project for my university this semester. In this i am going to be taking a picture of a maze though an android phone and by using suitable algorithms i obtain the shortest path between the start and finish. Now i have one problem, now if the robot has to take the second left turn in the maze how do i program it ? any ideas? im trying to break my head on this issue

i have attached a sample maze. i need to make the robot take the turn shown by the arrow and skipping the first turn.
Thanks

#### olivthill

• Jr. Member
• Posts: 23
• Helpful? 0
##### Re: How does a robot take a second turn in a maze?
« Reply #1 on: June 11, 2013, 03:47:37 PM »
You say you have the shortest parth. Maybe that path needs to be converted into instructions that the robot will understand. For instance, that path could be written as: move forwards for four units, then turn left, then move forwards for two units ...

#### jwatte

• Supreme Robot
• Posts: 1,343
• Helpful? 81
##### Re: How does a robot take a second turn in a maze?
« Reply #2 on: June 11, 2013, 06:26:14 PM »
You need sensors ahead, left, and right. This will let the robot sense whether there are walls or gaps on the sides, and whether it's about to hit a wall ahead. The robot can then use the map that you provide it to track its progress by correlating those sensors to the map as it moves forward.
Making turns shouldn't be any different no matter how many turns you've made before. All you need is the current location in the map, the direction you're currently facing, and the direction you want to be facing. Turn if needed, go forward until the next signpost position, repeat.

#### kiranvasudev

• Beginner
• Posts: 5
• Helpful? 0
##### Re: How does a robot take a second turn in a maze?
« Reply #3 on: June 11, 2013, 11:50:34 PM »
i got the instruction part.  But the thing is distances in the image are not 1:1 mapping of the real distances. So if i give instructions in units it might hit a wall sometime or it may move too much in front.

#### kiranvasudev

• Beginner
• Posts: 5
• Helpful? 0
##### Re: How does a robot take a second turn in a maze?
« Reply #4 on: June 12, 2013, 12:04:35 AM »
and one more thing is if i take a picture at an angle or the picture is a bit tilted it will still be quite difficult to map 1:1.

#### woody_294

• Jr. Member
• Posts: 7
• Helpful? 0
##### Re: How does a robot take a second turn in a maze?
« Reply #5 on: June 12, 2013, 12:29:45 AM »
Not sure if this will help but when we drive around with a co-driver he always says "option right/left" when you pass a turn you don't want to take, the co-driver is looking at a map and knows the route.

Just thinking you can have the instructions contain a no action/information commands telling the robot to ignore a turn. Apologies if this is no use at all

#### jwatte

• Supreme Robot
• Posts: 1,343
• Helpful? 81
##### Re: How does a robot take a second turn in a maze?
« Reply #6 on: June 12, 2013, 10:08:07 AM »
Quote
if i give instructions in units it might hit a wall sometime or it may move too much in front

That's why I suggested that you add three sensors, rather than to drive on dead reckoning.
Also, that's why I suggested navigating based on sensed features ("opening left") rather than dead reckoning.
Could you re-read my suggestion and perhaps ask about whatever parts seem unclear?

#### kiranvasudev

• Beginner
• Posts: 5
• Helpful? 0
##### Re: How does a robot take a second turn in a maze?
« Reply #7 on: June 12, 2013, 11:06:01 AM »
yeah i got that but suppose i need to take the opening left,  how will the robot know how to take the opening left? I dont want to give the directions myself. All processing will be done by the phone. let me show u an example:

the image with the red line is the one where the shortest path is calculated using an algorithm. the other is the original image. so now i need to know how can an algorithm or a piece of code figure out if its the first, second... and so on turn to take. Any algorithm or method to solve this?

PS: the image is processed on the phone itself and the red line is calculated(shortest distance)

#### jwatte

• Supreme Robot
• Posts: 1,343
• Helpful? 81
##### Re: How does a robot take a second turn in a maze?
« Reply #8 on: June 12, 2013, 01:27:28 PM »
Quote
how will the robot know how to take the opening left?

In what context?

"How does the robot detect there's an opening on the left" ?
"How does the robot detect that there is sufficient clearance to move through an opening on the left" ?
"How does the robot turn itself 90 degrees left and then keep moving forward" ?
"How does the robot decode the map information to determine that it should be looking for an opening on the left" ?
Something else?

Specifically, it would be helpful if you told us what is actually working right now, and what you believe your current problem is, and what you've already tried to do, what happens, and what you think *should* happen.

#### kiranvasudev

• Beginner
• Posts: 5
• Helpful? 0
##### Re: How does a robot take a second turn in a maze?
« Reply #9 on: June 12, 2013, 10:31:51 PM »
our current problem is to convert the path into directions.
for eg.
the output we need is
2-left
3-right
1-left

something similar. basically we need to convert the red line into appropriate directions.
« Last Edit: June 12, 2013, 10:33:52 PM by kiranvasudev »

#### jwatte

• Supreme Robot
• Posts: 1,343
• Helpful? 81
##### Re: How does a robot take a second turn in a maze?
« Reply #10 on: June 12, 2013, 10:47:37 PM »
What representation do you have for the path right now? Just a bitmap?

Typically, you will assign one number to each cardinal direction. Then, you will store the "current direction" of the bot, and work relative to that.

So, if 0 == east, 1 == north, 2 == west and 3 == south on the map, and the robot uses 0 == forward, 1 == left, 2 == U-turn, 3 == right, then you just add the two together and mod by 4 (just mask the two lower bits) to get a "new" direction from an "old" direction plus a turn.

If the robot is going south (3) and turns left (1) then the new direction is ((3+1)&3) == 0 == east.

To generate good instructions for the robot, you need to segment your maze into cells. Each cell should either be "an intersection" or "a straightaway." Then connect the cells in a graph with each of the four cardinal directions either leading to another node, or having NULL in a direction for "here is a wall." Straightaways have two parallel walls; intersections are all other nodes.

Now, solve this maze as a graph, rather than as a bitmap. This should make it very easy to turn the solution directly into instructions for the robot.

Get Your Ad Here

data_list