Robot Room Cleaner

Navigating the Maze: The code that helps to clean The Problem Understanding the problem Let us Solve!!!The Approach Strategizing the Solution The Cleaning Algorithm Explained Initial Setup Direction Definitions Recursive Cleaning Process Here’s a code snippet for the same:Let us see how it works!

Navigating the Maze: The code that helps to clean

Have you ever watched a robot cleaner methodically clean a room and wondered how it manages such a task autonomously? How does it work?

Despite having no prior knowledge of the room's layout, these robots navigate and clean effectively, showcasing a fascinating application of coding and algorithms in the real world.

How does it know where to go or when the cleaning was complete?

❕

Poor guy has no clue but still gets the work done!

In this blog, I'll explore a seemingly simple yet intriguingly complex problem: How does problem-solving in theoretical scenarios translate into real-world applications? This discussion on autonomous robot cleaners serves as just one example among many where coding meets practicality.

Recently, I encountered an intriguing challenge on leetcode - Robot Room Cleaner It sparked my interest, and I'm excited to share insights from this problem with you.

❓

No time to understand the approach, give me the code! Here is the code and here is the presentation

The Problem

You are given a robot class object that allows the following commands to navigate or interact with the robot and clean.

The 4 commands:

move: The robot moves forward in its current direction. If it's possible to move forward, the robot proceeds and returns True. If not, due to an obstacle, it returns False.

turnLeft: The robot rotates to its left without changing its position.

turnRight: The robot rotates to its right without changing its position.

clean: The robot cleans the spot it's currently on.

Now, Given the object to make the calls, Our task is to develop a strategy that ensures the robot cleans the entire room. This is akin to how typical robotic cleaners operate in unfamiliar environments.

The robot is at a place in the middle of nowhere(a room). It can move, turn and clean the spot it is in. Write a code that ensures the robot cleans the entire room. The first thought - WHAT? HOW?

Understanding the problem

From the problem statement we take these:

There is an m*n room of which we neither know the m nor the n

The robot is stationed at an empty position.

Assumptions

The robot is in a cartesian plane at (x, y). We can assume the current position to be origin - (0,0) for the sake of simplicity.

The robot is facing up .

And in our imaginary cartesian system or matrix, the obstacles are denoted by 1 and the open spaces are denoted by 0 .

❕

Our robot is the origin for all the cleaning

Let us Solve!!!

❓

How to move? How do we know that the room is cleaned?

The Approach

We assume the robot moves forward in its direction until it hits an obstacle or cannot move forward. Now we change the direction and move forward again and continue the same.

If we think again, it comes out to be a simple graph problem!!!

Let us incorporate our cartesian system and solve.

That all sounds good but how do we know when the room is cleaned?

It’s not like when it reaches the same position again the room is clean!

It’s not like the room is clean when it reaches the start position either!

Strategizing the Solution

The approach resembles solving a graph traversal problem:

Track Positions: We assume coordinates (x,y) for the robot's current position.

Movement and Memory: As the robot moves, it keeps track of cleaned positions.

⚖️

Robot’s principles → Will clean my current spot, before i check my neighboring spots. → No position uncleaned

The Cleaning Algorithm Explained

We will be employing the notorious backtracking with DFS(Depth First Search) strategy for solving the problem.

Let's break down the step-by-step algorithm that enables the robot to ensure the entire room is cleaned, despite starting without any knowledge of the room's layout:

Initial Setup

Start Position: The robot begins at coordinates (0, 0).

Tracking: We use a set, cleaned_positions, to keep track of which spots have been cleaned.

Orientation: The robot's initial direction is unknown, so we arbitrarily set a starting direction and adjust as needed.

Direction Definitions

For clarity, we define the robot's possible directions relative to its current position:

→ When the robot moves in a direction, the co-ordinates are changed based on the direction it moved.

If the robot is at (i, j) and it moves forward in the direction up , the co-ordinates will be (i+1, j).

Direction	Co-ordinate
up	(i+1, j)
left	(i, j-1)
down	(i-1, j)
right	(i, j+1)

Recursive Cleaning Process

Here’s how the recursive cleaning operates:

Clean Current Position: Start by cleaning the current spot and marking it in the cleaned_positions.

Exploring Directions: From the current spot, the robot considers each direction it could possibly move:

Iteration Over Directions: For each of the four possible moves (up, down, left, right), represented as coordinate changes:

Check Move Viability: Before moving, check if the new position is already cleaned (in cleaned_positions) and if the robot can physically move there (using the move() API).
Recursive Cleaning: If moving is possible, the robot proceeds, cleans the new position, and recursively continues this process from there.
Backtracking: After exploring one direction, the robot must return to the current position to continue exploring the next direction. This requires reversing the move and adjusting the orientation accordingly.

End of Recursion: The recursion terminates when no new positions are available for cleaning — essentially, when all reachable spaces have been cleaned.

Here’s a code snippet for the same:

TheTechCruise.com Pyodide Terminal

# pyodide: false
def cleanRoom(robot):
		# Assuming (0, 0) as it would make things simple. Feel free to have any point
    current_position = (0, 0)
    # set to keep track of the already cleaned positions
    cleaned_positions = set()
    # Advance when moved for each direction left, down, right, up
    # The order can be any way, make sure it is either clockwise or anti clock wise
    # as each turn is 90 in clock-wise or anti-clockwise direction

    direction_advance = [(0, 1), (-1, 0), (0, -1), (1, 0)]
    
    # Setting current direction's index to 0, so left
    direction = 0
     
    # Function to get the robot to it's former position or previous state
    def go_back(robot):
        robot.turnLeft()
        robot.turnLeft()
        robot.move()
        robot.turnLeft()
        robot.turnLeft()
    
    def check_and_clean(current_position, current_direction):
        cleaned_positions.add(current_position)
        robot.clean()
        for position in range(4):
            # Advance based on the current position 
            # as the robot can be turned up/right/down when it comes here
            # we use it's current direction to follow order in the way it cleans
            # modulus is self-explanatory as there are only fourth directions
            # and when it turns left when it is facing up, it is again left
            current_direction = (direction+position)%4
            # With the advance the x, y co-ordinates
            current_x = current_position[0] + direction_advance[current_direction][1]
            current_y = current_position[1] + direction_advance[current_direction][1]

            # Check if it is already cleaned and if it is possible to move
            if (current_x, current_y) not in cleaned_positions and robot.move():
                # Calling the function recursively
                check_and_clean((current_x, current_y), current_direction)
                # Going back to the previous position
                go_back(robot)
            # Turning to the next direction. 
            # Using only turnLeft for simplicity
            # Use either turnLeft or turnRight
            robot.turnLeft()
            
    check_and_clean(current_position, direction)

robot is the class object that is passed to the function. It has the methods for the API Calls move, turnLeft, turnRight, clean.

Algorithm Visualization

Initial State: Begin at (0, 0), with all directions unexplored.

Recursive Expansion: Explore each direction, cleaning and marking positions, and backtrack as necessary.

Completion: All reachable positions are marked as cleaned, and no further moves are available.

The robot is happy it could find a way to clean the room!

This structured approach ensures every part of the room is addressed, utilizing a depth-first search (DFS) strategy combined with backtracking to cover the entire area effectively.