A* Algorithm for Robot Vacuum Pathfinding: Use
Cases and a Lightweight Implementation Plan
Dinh Hoang Viet
CS 3331
1. Problem and Core Idea
Given a grid-based or graph-based map G = (V, E, w) where w(e) ≥ 0 for all edges and a start node
s ∈ V, the goal is to find the lowest-cost path from s to a target node t ∈ V using both the actual
path cost and a heuristic function that estimates the remaining distance. The A* algorithm maintains
two costs: g(n), the cost from the start to node n, and h(n), the heuristic estimate from n to the goal.
The total evaluation function is f(n) = g(n) + h(n). Nodes are expanded in order of increasing f(n).
With an admissible and consistent heuristic, A* guarantees an optimal path.
2. Use Cases
2.1 Robot Vacuum Navigation
Problem. Enable a robot vacuum to plan an efficient cleaning path or return to its charging dock.
Graph modeling. Grid cells → nodes; adjacent traversable cells → edges; obstacles (walls,
furniture) removed. Cost function. Usually uniform; may depend on terrain (e.g., carpet, tile).
Constraints. Dynamic obstacles (humans, pets) may appear; path replanning is needed. Output. A
collision-free, near-optimal path for navigation or coverage. Why A*. Combines Dijkstra’s optimality
with heuristic efficiency; ideal for map-based robotic planning.
2.2 Warehouse or Factory Robots
Problem. Move from a loading zone to a drop zone efficiently. Graph modeling. Floor grid → nodes;
blocked zones → removed edges. Cost function. Terrain-dependent (safety, proximity to obstacles).
Constraints. Mostly static; updated periodically if obstacles change. Output. A shortest feasible path
under given constraints. Why A*. Provides optimality with better computational efficiency than
Dijkstra.
2.3 Game AI Pathfinding
Problem. Guide an agent to its goal avoiding obstacles. Graph modeling. Game map grid → nodes;
adjacency defines movement. Cost function. Movement cost or distance. Why A*. Standard in
real-time strategy and simulation games due to balance between speed and accuracy.
3. Agent Framing (PEAS) for a Robot Vacuum
Performance: Minimize total travel distance, avoid collisions, complete full coverage, return to dock
efficiently.
Environment: Indoor grid with obstacles (walls, furniture), possibly dynamic entities (pets, humans).
Actuators: Wheels (differential drive), suction motor, steering, brake, sensors alignment.
Sensors: Lidar or camera (for mapping), bumper sensors, odometry, IMU, infrared docking beacon.
4. Pseudocode
Algorithm 1: A* (G, s, t) 1: Input: Graph G = (V, E), start node s, goal node t
2: Output: Optimal path from s to t
3: for v ∈ V do
4: g[v] ← ∞, parent[v] ← ∅
5: end for
6: g[s] ← 0
7: f[s] ← h(s)
8: PQ ← min-priority queue of (f[v], v)
9: push (f[s], s) into PQ
10: while PQ not empty do
11: (d, u) ← pop-min(PQ)
12: if u == t then break
13: for each (u, v) ∈ E do
14: tentative ← g[u] + w(u, v)
15: if tentative < g[v] then
16: g[v] ← tentative
17: f[v] ← g[v] + h(v)
18: parent[v] ← u
19: push (f[v], v) into PQ
20: end if
21: end for
22: end while
23: return reconstructed path via parent[t]
5. Implementation Notes
• Grid-based model: Each traversable cell is a node; edges connect adjacent cells (4 or 8
directions).
• Heuristic: Manhattan distance for 4-way grids, Euclidean for 8-way.
• Priority queue: Use heapq in Python or std::priority_queue in C++.
• Replanning: When dynamic obstacles appear, recalculate from current position.
• Modularity: Separate modules for MapBuilder, AStarPlanner, and PathExecutor.
• Optimization: Cache heuristic and neighbor lookups; limit search area near last known goal.
• Comparison: Dijkstra expands all reachable nodes; A* prunes search with heuristic guidance.
6. Mini Demo and Evaluation Plan
Scenario: 30×30 indoor grid with random furniture obstacles and a fixed dock position.
Metrics: Path length, time to compute, nodes expanded, number of replans.
Comparison: Run Dijkstra and A* (Manhattan heuristic) on same maps to highlight efficiency.
Visualization: Color visited cells; overlay final path; mark start, goal, and obstacles.
Expected: A* visits 30–50% fewer nodes and finds the same optimal path as Dijkstra.
7. Conclusion
A* offers a powerful and efficient solution for robot vacuum navigation by combining the optimality
of Dijkstra’s algorithm with heuristic-driven efficiency. Its grid-based simplicity, compatibility with
SLAM-generated maps, and adaptability to dynamic replanning make it a core component of
modern autonomous cleaning systems. For highly dynamic environments, incremental algorithms
such as D* Lite or Anytime Repairing A* can be integrated for continuous real-time performance.