B.Tech Project · Woxsen University · Foundations of AI

Smart Vacuum Cleaner Agent: An Intelligent Grid Simulation

Autonomous Pathfinding and State-Space Search in Dynamic Environments

Start Learning Jump to live simulation
  • 0Grid world
  • 0Fewer moves vs. random walk*
  • 0Obstacle collisions*
  • 0Reachable cells covered*

*Averages over 500 simulated 10×10 grids (illustrative results – see Section 05).

01 Problem Statement & Objectives

How does a robot clean a room it cannot see?

Autonomous navigation in a dirty room is the classic vacuum world of Russell & Norvig, a deliberately small task environment in which every core idea of intelligent-agent design can be studied, measured and compared.

The problem

Consider a rectangular room discretised into an R × C grid. Every cell is in exactly one of three states: clean, dirty or blocked by an obstacle (furniture, walls, clutter). A vacuum agent is dropped into the room with no map. It perceives only its immediate surroundings, and its battery, modelled as a budget of moves, is finite.

The task is to design an agent function that maps what the agent has perceived so far to an action, so that all reachable dirt is removed with as little wasted motion as possible, and without ever driving into an obstacle.

Seen through the lens of state-space search, the problem has a precise formulation:

Initial state
Agent at (0, 0); an unknown dirt configuration.
Actions
UP, RIGHT, DOWN, LEFT, SUCK, HALT.
Transition model
Deterministic; moves into walls/obstacles leave the agent in place (a bump).
Goal test
No reachable dirty cell remains.
Path cost
1 per move, plus a penalty per collision.

Objectives

  1. O1
    Maximise dirt cleaned

    Remove 100 % of the dirt that is physically reachable, a completeness requirement.

  2. O2
    Minimise energy

    Every move drains the battery, so revisits and random dithering must be avoided.

  3. O3
    Avoid obstacles

    Drive the collision rate to zero by reasoning about the map before acting.

  4. O4
    Terminate correctly

    Detect "nothing left to do" (or "I am boxed in") and halt instead of looping.

  • Partially observable
  • Deterministic
  • Sequential
  • Static
  • Discrete
  • Single-agent

The PEAS framework

Every task environment is specified by its Performance measure, Environment, Actuators and Sensors. Hover, focus or tap a card to flip it.

P

Performance

How do we judge success?

Performance measure

  • +10 per dirt cell removed
  • −1 per move (energy cost)
  • −5 per collision with an obstacle or wall
  • Score = 10·D − M − 5·K
  • Secondary: % reachable cells covered
E

Environment

Where does the agent live?

Environment

  • R × C grid, border treated as wall
  • Cell states: 0 clean · 1 dirt · 2 obstacle
  • Static & deterministic: dirt does not respawn
  • Layout is unknown to the agent at start
  • Start cell (0, 0) is always free
A

Actuators

How does it act?

Actuators

  • Drive wheels: UP, RIGHT, DOWN, LEFT (one cell per tick)
  • Suction unit: SUCK, cleans the current cell
  • Controller: HALT, ends the episode
  • Each drive action consumes one unit of energy
S

Sensors

What can it perceive?

Sensors

  • Dirt sensor: is my cell dirty?
  • Proximity / bump sensors: state of the 4 neighbours (clear, dirt, obstacle, wall)
  • Odometry: current (row, col) from dead-reckoning
  • Range is local only: no global map

02 Literature Review

Seven decades of making machines move on purpose

From shortest-path theory to commercial robot vacuums and deep reinforcement learning, the agents that clean floors are built on a lineage of search, planning and control research.

Drag, scroll or use the arrows →
  1. 1959
    Search

    Dijkstra's shortest path

    Edsger Dijkstra gives the first rigorous algorithm for shortest paths in a weighted graph. Grid worlds are graphs, so every later navigation planner inherits this foundation. With unit step costs it reduces to breadth-first search, the planner our agent uses.

  2. 1966–72
    Planning

    Shakey the Robot (SRI)

    The first mobile robot to reason about its own actions. It combined vision, a symbolic world model and the STRIPS planner, showing that sense → model → plan → act is a workable architecture.

  3. 1968
    Heuristic search

    A* algorithm

    Hart, Nilsson and Raphael introduce A*, which expands nodes by f(n) = g(n) + h(n). With an admissible heuristic it is optimal and typically explores far fewer nodes than uninformed search, the standard tool for goal-based navigation.

  4. 1986
    Reactive

    Subsumption architecture

    Rodney Brooks argues that robots can act intelligently with layered condition–action behaviours and no world model. Fast and robust, but purely reactive. This is the lineage of the simple reflex agent.

  5. 1995
    Theory

    The agent taxonomy (AIMA)

    Russell & Norvig formalise the rational agent and its four designs: simple reflex, model-based reflex, goal-based and utility-based, using the two-cell vacuum world as the running example.

  6. 1998–2001
    Coverage

    Coverage path planning

    Choset & Pignon's boustrophedon decomposition and Gabriely & Rimon's spanning-tree coverage formalise "visit every free cell". Choset's 2001 survey frames coverage as the core problem of cleaning robots.

  7. 2002 → 2015
    Industry

    Robot vacuums go mainstream

    The first Roomba (2002) relied on reactive bump-and-turn behaviours. Later models added mapping and visual SLAM, which means an internal model of the home, the same shift from reflex to model-based control studied in this project.

  8. 2015 →
    Learning

    Deep reinforcement learning

    Mnih et al.'s DQN learns control policies directly from experience. Learned coverage and navigation policies now compete with hand-designed planners, and are our long-term future scope.

Three agent designs, compared

Select an architecture to see what it perceives, remembers and decides in the vacuum world.


              
In the vacuum world: 

            

            

              
Memory of the past

              
Foresight / planning

              
Coverage completeness

              
Computational cost

              
Illustrative qualitative scores (0–100).

            

          

          

            

              Comparison of simple reflex, model-based and goal-based agents
              
PropertySimple ReflexModel-Based ReflexGoal-Based

              
                
Decision usesCurrent percept onlyPercept + internal stateState + goal + look-ahead search

                
MemoryNoneMap, visited setMap + plan

                
Handles partial observabilityPoorlyYesYes

                
Typical algorithmIF–THEN rulesState update + rulesBFS, Dijkstra, A*

                
WeaknessLoops forever; wastes energyGreedy, may backtrackSearch cost grows with state space

              
            

          

          
Our design is a model-based reflex agent with a goal-directed fallback: it reacts locally using its map, and when the local neighbourhood is exhausted it runs BFS (A* with h = 0) to the nearest unexplored cell.

        

      

    


    
    

      

        

          
03 Proposed Methodology

          
The agent's decision loop, node by node

          
Each tick the agent senses, updates its internal model, applies prioritised condition–action rules, and falls back to path planning only when it has to. Click any node of the flowchart to see its logic and highlight what comes next.

        


        

          

            

              
              
              
            

            

              
            

          


          
        


        

          

            
Mapping the 2-D grid matrix

            
The environment is a list of lists where grid[r][c] holds one integer per cell. The agent never sees this array directly. It builds its own copy, known, one percept at a time.

            

              
              
    
                
  • 0 clean
    • 
                
  • 1 dirt
    • 
                
  • 2 obstacle
    • 
                
  • agent @ (0,0)
    • 
              

            

            
Out-of-range indices are treated as OBSTACLE, so the border needs no special-case logic. Four neighbours are read with offset vectors (−1,0), (0,+1), (+1,0), (0,−1).

          


          

            
Condition–action rules (priority order)

            

              

                
#ConditionAction

                
                  
1cell == DIRTSUCK

                  
2neighbour free ∧ unvisitedMOVE to it

                  
3no local candidate ∧ BFS finds frontierFOLLOW shortest path

                  
4frontier == ∅HALT

                
              

            

            
Rule 1 outranks movement because cleaning is the only action that raises the score. Obstacle avoidance is not a separate rule. It is a filter applied to every candidate move, which is why collisions never occur.

          

        

      

    


    
    

      

        

          
04 Implementation & Execution

          
From pseudocode to a running agent

          
The agent is written in plain Python with nothing but 2-D lists, tuples, sets and a deque. The simulation on the right runs the same logic in your browser. Switch between agents and watch the difference.

        


        
    
          
  • Python 3 core language
    • 
          
  • 2-D Arrays list-of-lists grid
    • 
          
  • collections.deque BFS queue
    • 
          
  • set / dict visited & known map
    • 
          
  • random seeded world generator
    • 
          
  • Matplotlib optional visualisation
    • 
        


        

          
          

            

              
              

                
                
                
              

            

            

            
Python 3.12UTF-80 lines

          


          
          

            

              

                
                
              

              
    
                
    • 
                
    • 
                
    • 
              

            

            

              
              
            

            
    
              
  • Moves0
    • 
              
  • Dirt cleaned0/0
    • 
              
  • Collisions0
    • 
              
  • StatusReady
    • 
            

            

              
              
              
              
              
            

            
            

          

        


        

          

            environment_setup()
            
Builds the world. It allocates an R × C list of lists, then walks every cell and uses a seeded random generator to place obstacles (~12 %) and dirt (~20 %). The seed makes every experiment reproducible, and the start cell is forced to be free.

            Time O(R·C) · Space O(R·C)
          

          

            sensor_read()
            
Simulates the sensors. It returns (is_dirty, neighbours), a dictionary giving the state of UP, RIGHT, DOWN and LEFT. The agent receives only this local percept and never the grid itself, which is what makes the task partially observable.

            Time O(1) · Space O(1)
          

          

            move_agent()
            
The agent function. It senses, updates the internal model, then applies the rules: SUCK if dirty, otherwise step to a free unvisited neighbour, otherwise follow a BFS path to the nearest frontier cell, otherwise HALT.

            Time O(1) local · O(R·C) when planning
          

        

      

    


    
    

      

        

          
05 Results & Analysis

          
Memory beats luck by an order of magnitude

          
We compare a Random-Walk agent against our Model-Based agent across 500 randomly generated 10×10 grids (20 % dirt, 12 % obstacles, start at (0, 0)).

          
 The figures below are hypothetical, illustrative results modelled on the expected behaviour of the two agents. Re-run the experiment script (or the live simulation) to obtain your own measurements.

        


        

          

            

              
Head-to-head metrics

              
  • Random-Walk
  • Model-Based

            


            

              
Average moves to clean 100 %lower is better

              
Random
0

              
Model
0

            


            

              
Energy efficiency (useful actions)higher is better

              
Random
0

              
Model
0

            


            

              
Obstacle collision ratelower is better

              
Random
0

              
Model
0

            


            
Energy efficiency = (SUCK actions + first-time cell visits) ÷ all actions. Collision rate = blocked move attempts ÷ move attempts.

          


          

            

              
Reliability dials

              
  • Random
  • Model

            

            

              

                
                
0

                
Runs finished within a 500-move budget
Random: 14 %

              

              

                
                
0

                
Collision-free move attempts
Random: 76.4 %

              

              

                
                
0

                
Energy efficiency
Random: 8.7 %

              

            

          


          

            

              
Cleaning progress over time

              
  • Random-Walk
  • Model-Based

            

            
            
Mean percentage of dirt removed after t moves. The random walk shows the diminishing returns of a coupon-collector process: the last few dirt cells take longest to stumble upon.

          

        


        

          
−88 %moves needed (134 vs 1,126)

          
≈ 8×higher energy efficiency

          
0collisions, because the map is checked before moving

          
100 %completion rate within budget

        

      

    


    
    

      

        

          
06 Conclusion & Future Scope

          
A small world that teaches big ideas

          
Adding just two ingredients to a reactive agent, memory of where it has been and a graph search for where to go next, converts a wasteful random wanderer into a complete, collision-free and energy-efficient cleaner.

        


        
What we achieved

        

          

            
            
Complete coverage

            
Because every free cell reachable from the start is eventually added to the frontier and visited, the agent is complete: it cannot miss reachable dirt, and it halts exactly when none remains.

          

          

            
            
Dramatic energy savings

            
Remembering visited cells and planning shortest backtracking paths cut the average cost from ~1,126 to ~134 moves, an 88 % reduction over the memoryless baseline.

          

          

            
            
Safe by construction

            
Obstacle avoidance is a filter over candidate actions using the internal map, so the collision rate falls from ~24 % to zero in a static world.

          

        


        
Future scope

        

          

            
            
Dynamic environments

            
Introduce moving obstacles (pets, people) and re-appearing dirt. The static-world assumption breaks, so the agent needs incremental replanning (D* Lite, LPA*) and a model that expires stale information.

            
  • Time-stamped map cells
  • Replan on blocked path
  • Predict obstacle motion

          

          

            
            
Multi-agent cooperation

            
Deploy two or more vacuums. This requires task allocation (partition the frontier, e.g. by Voronoi regions or auction), shared map fusion and conflict-free routing (multi-agent path finding).

            
  • Shared / merged maps
  • Region partitioning
  • Deadlock & collision avoidance

          

          

            
            
Deep Reinforcement Learning

            
Replace hand-written rules with a policy learned by DQN or PPO. The state is the local grid tensor, and the reward mirrors our performance measure: +10 dirt, −1 move, −5 collision.

            
  • Reward shaping from PEAS
  • Generalise across layouts
  • Sim-to-real transfer

          

        


        
Limitations. The current study assumes a static, deterministic world, noise-free sensors and perfect odometry on a small discrete grid. Relaxing each assumption is a research direction in its own right.

      

    


    
    

      

        

          
07 Presentation & Q&A

          
Expected questions from the evaluation panel

          
Five questions an examiner is likely to ask, with well-reasoned answers. Open one at a time.

        


        

          

            Q1Why not use a simple reflex agent?
            

              
A simple reflex agent decides from the current percept only. In a partially observable grid that is fatal for three reasons:

              
    
                
  • It cannot detect completion. With no memory it never knows that a cell was already cleaned, so it has no principled stopping condition and keeps moving forever.
    • 
                
  • It loops. A rule like "if the right neighbour is free, go right; else go down" can trap the agent in cycles. Randomising the choice escapes loops but is exactly the inefficient random walk we benchmarked.
    • 
                
  • It wastes energy. It revisits clean cells at the same rate as unexplored ones.
    • 
              

              
Adding an internal state (a visited set and a known map) is a tiny change in code but moves the agent from reactive to rational, and the results show an 88 % reduction in moves.

            

          


          

            Q2How does the agent handle being completely boxed in by obstacles?
            

              
Being boxed in is detected through the model, not by crashing around. After sensing, all four neighbours are marked OBSTACLE (or boundary). Rule 2 finds no candidate, and the BFS in rule 3 explores zero cells, so the frontier is empty. The agent then executes HALT and reports its status.

              
The same logic handles a partial enclosure: if the agent has cleaned everything reachable and the rest of the room is sealed off by obstacles, the frontier empties and it halts. It cannot know the sealed region contains dirt, and no agent could clean it, so that dirt is outside the reachable goal definition. Our world generator also removes dirt sealed in unreachable pockets so the performance metric stays well defined.

              
Crucially, the agent terminates. A reflex agent in the same situation would bump into walls indefinitely.

            

          


          

            Q3What is the time complexity of the agent's decision loop?
            

              
Let N = R × C be the number of cells.

              
    
                
  • Sensing and model update: four neighbours, so O(1).
    • 
                
  • Local rule check (SUCK / unvisited neighbour): O(1).
    • 
                
  • BFS planning (only when the neighbourhood is exhausted): O(V + E) = O(N), as each cell has at most 4 edges.
    • 
              

              
The plan is cached and followed step by step, so a BFS runs at most once per frontier jump, and there are at most N such jumps. In the worst case the full run costs O(N²) time, and in practice far less because most steps are O(1) local moves. Space is O(N) for the known map, visited set and BFS queue. A random-walk agent has O(1) cost per step, but its expected number of steps grows much faster, roughly O(N log² N) for covering a 2-D grid.

            

          


          

            Q4Is your agent optimal? Why BFS rather than A*?
            

              
Two different questions hide here.

              
Path optimality. Each BFS returns a shortest path to the nearest frontier cell, since all moves cost 1. Dijkstra and A* give the same result here. A* with a Manhattan heuristic only helps when there is a single known target. Our target is "the nearest unvisited cell", a set of targets, so a heuristic gives little pruning and BFS is the simplest correct choice (equivalently A* with h = 0).

              
Global optimality. The agent is not globally optimal. Visiting all cells in the fewest moves is a variant of the Travelling Salesman / Hamiltonian-path problem, which is NP-hard, and the layout is initially unknown anyway. Repeatedly going to the nearest frontier is a greedy nearest-neighbour heuristic, giving a good but not minimal tour. It is, however, complete and terminates in polynomial time. Spanning-tree coverage gives a stronger guarantee (at most twice the optimal in the known-map setting), and is a natural extension.

            

          


          

            Q5What assumptions limit your results, and would they hold in the real world?
            

              
Classifying the task environment makes the assumptions explicit: partially observable, deterministic, sequential, static, discrete, single-agent. The key limitations are:

              
    
                
  • Perfect actuation and odometry. Real wheels slip, so position drifts. Real robots need SLAM or localisation against landmarks.
    • 
                
  • Static world. People and pets move. This is why dynamic obstacles are our first future-scope item, using incremental planners such as D* Lite.
    • 
                
  • Discretisation. Real rooms are continuous, so a grid is an abstraction, and cell size trades accuracy against computation.
    • 
                
  • Hypothetical benchmark. The reported numbers are illustrative and use a simplified random-walk baseline. The ordering of the agents is robust, but the exact magnitudes should be confirmed empirically across many seeds and grid sizes.
    • 
              

              
The architecture (sense → update model → rules → plan) still transfers directly. Only the sensing and mapping modules change in a real robot.