1
$\begingroup$

First let me explain the problem.

This is a maze made only out of black lines on a white surface. The robot has only a few IR sensors which can sense the position of the line. No other sensory input is available.

This is a maze with many self-loops and so a simple LSRB or equivalent algorithm wont work. The robot is supposed to learn the maze and then solve it as optimally as possible .

The above figure represent the possible intersections as all the paths are at 90deg to each other.

As far as my understanding goes, the robot will first scan how many nodes there are, and what their connections to each other is, thus effectively constructing the graph. Next, implement any shortest path algorithm and make your robot follow it.

However, the main problem that i cant get my head around is this:

How will this blind robot know it isnt viewing the same node multiple times if it keeps coming back to the same point after getting caught in a loop?

Also, please suggest good approaches to solving this problems along with any experience anybody has. How does one shot searching methods like DFS , Iterative deepeing DFS , hill climbing work in such scenarios ?

The arrow indicates the direction of the robot and the black lines represent the track, which the robot has to follow .

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

How will this blind robot know it isn't viewing the same node multiple times if it keeps coming back to the same point after getting caught in a loop?

If you can assume the robot moves at constant velocity, you can measure the elapsed-time between intersections, and use this travel-time as a stand-in for segment length. A grid-representation should allow you to determine whether the robot has arrived at a node that is already present on the map.

Once you have the complete map of node connections, you can easily find a path to minimize travel distance.

Improve this answer
$\endgroup$
0
$\begingroup$

You have already suggested that a simple LSRB or equivalent won't work but could you please refer to this article, Coding a Line Follower Robot for Maze using LSRB Algorithm and finding its Shortest Path, which suggest a method for reducing the LSRB path with final optimisation. I am quoting the suggested shortest path finding step here,

LBR = B

LBS = R

RBL = B

SBL = R

SBS = B

LBL = S
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.