Algorithms & Data Structures for Robotics

A robot's sensors and motors are useless without an efficient decision-making process behind them. Algorithms are step-by-step procedures for solving a problem, and data structures are the ways we organize information so those procedures run fast. In robotics this shows up constantly: searching a grid map for a path, sorting sensor readings, or deciding which of many possible moves to try next. Choosing the right algorithm is the difference between a robot that reacts instantly and one that freezes while "thinking."

Big-O notation describes how an algorithm's running time grows as input size $n$ grows — this is how we compare algorithms before even running them:

Breadth-First Search (BFS) for path planning on a grid map:

queue = [start]
visited = {start}
while queue not empty:
    cell = queue.pop_front()
    if cell == goal: return path_to(cell)
    for neighbor in cell.neighbors():
        if neighbor not in visited and neighbor is not obstacle:
            visited.add(neighbor)
            queue.push_back(neighbor)

BFS explores the map layer by layer, guaranteeing the shortest path (in number of steps) on an unweighted grid.

1. Represent the robot's environment as a graph: each grid cell (or waypoint) is a node, and edges connect cells the robot can move between directly.
2. Start BFS from the robot's current cell, using a queue (first-in-first-out) to always expand the closest unexplored cells first.
3. Mark cells as visited so the algorithm never re-checks the same cell — this is what keeps BFS efficient at $O(V + E)$, where $V$ is the number of cells and $E$ is the number of connections.
4. Once the goal cell is dequeued, trace back through recorded parent pointers to reconstruct the shortest path.
5. For maps where moves have different costs (diagonal vs straight, rough vs smooth terrain), swap BFS for Dijkstra's algorithm, which always expands the lowest total-cost path first instead of just the fewest steps.

Robot vacuum cleaners and warehouse robots build an internal grid map of the space and run BFS- or Dijkstra-style search to plan the shortest route to a target or charging dock. Self-driving cars use more advanced versions of these same graph-search ideas (like A*, which adds a distance estimate to Dijkstra) to plan routes in real time while avoiding obstacles.

1. Why does BFS guarantee the shortest path on a grid where every move costs the same, but not on a grid where some moves are more "expensive" than others?
2. If a robot's map has 100 cells and each cell connects to up to 4 neighbors, roughly how does the BFS running time change if the map grows to 400 cells?