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 .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.