Programming a robot to explore a grid

Question

In my project I'm simply trying to make a robot which explores as much of the grid as it can, without taking the same path twice. Also, it has a sensor to see if an object is lying in its way(the object can only be in a corridor). But I'm having trouble trying to make the robot avoid taking the same path.

I tried resolving this issue by creating a 2D array for storing an integer value for each square in the grid. A value of 0 means the robot has not been on that square in the grid yet, a value of 1 means that square is blocked in the grid and a value of 2 means that the robot has been on that square before. If the robot sees that the square ahead of its current heading has value 2, then it would keep rotating to find a square with a value of 0, but if no square of value 0 around the robot exists, then it begins to backtrack.

My problem can be explained more clearly with this example:

The triangle represents the robot and its start position, the bottom left corner is assumed to be the position (0,0) in my grid. The green circles represent items blocking it's path. The red square is the target for the robot. the robot can only move onto white squares in the grid.

When I start my programme the robot, moves forward(east since that is its current heading) till it gets to the junction just before the green circles. It looks ahead and detects an object in the way, so it rotates 90 degree anticlockwise and checks for another blockage, which again occurs hence it rotates anticlockwise again. So now the robot is at position (0,2) heading west. It can only move west to avoid leaving the grid or hitting an object, so it arrives back at its initial position but still heading west. It'll now keep rotating 90 degrees clockwise till it can find a direction which will keep it on the grid, i.e till it's facing east again. So the grid now looks like:

But now I want to ignore going ahead and onto the same path by ignoring that direction and rotating 90 degrees anticlockwise again to face north, so my robot can move north into a new path. I could simply ignore the direction and just keep rotating to find a new path, but what if I'm surrounded by been before paths and I want my robot to backtrack to its last junction. How can I efficiently do this. Also how can I efficiently detect when I need to backtrack.

Thank you

Answer 1

Solving the predicament in picture 2 could be as simple as checking for other white squares around the robot before you make a move. In picture 2 the robot would see that the square he is facing is "greyed out" and decide to check all other directions and eventually find that there is an empty white square to the North of him.

Edit : Didn't realize it was an actual robot.

Since the only way of learning what is in a cell is by turning to that cell and using the sensor, the robot will have to do some amount of turning no matter what you do. When it encounters a wall or green object, it will have to turn until it finds a new path to travel. You could optimize it by disregarding the walls of the enclosure. For example, when the robot arrives back in his starting position facing west, you already know there is a wall to the south because of its coordinate position is (0,-1), which is invalid. This allows you to figure out that the open tile is to the north because you have already visited the tile to the east, requiring only one turn.

Furthermore, when the robot eventually travels all the way to the north, tile (0,6) you know there is a wall to the north and to the west because of its position. You could then intelligently guess that the open slot has to be to the east because the western tile (-1,6) is not valid and (0,7) is not valid either.

Without changing the sensor to see 2 blocks or installing more sensors on the robot (ie one on every side), there is not much more optimization that can be done due to the limited availability of information.