A modern approach to AI · Chapter 26

Robotics

Robots couple perception, planning, and action in a physical world where sensors are noisy and actions may not have their intended effects.

Chapter guide

26.1 Robots — A robot senses and acts through physical components to accomplish tasks in an environment.
26.2 Robot Hardware — Sensors, actuators, computation, and mechanical design constrain what a robot can observe and do.
26.3 What kind of problem is robotics solving? — Robotics is decision-making under dynamics, uncertainty, and real-time constraints.
26.4 Robotic Perception — Sensor data supports state estimation, mapping, and recognition, often by fusing imperfect measurements.
26.5 Planning and Control — Planning selects a route or action sequence; feedback control corrects motion as new observations arrive.
26.6 Planning Uncertain Movements — Probabilistic models account for uncertain state and action outcomes.
26.7 Reinforcement Learning in Robotics — Trial-and-error can tune behavior, but physical exploration must be bounded and safe.
26.8 Humans and Robots — Collaboration requires understandable intent, predictable interaction, and appropriate authority.
26.9 Alternative Robotic Frameworks — Reactive, deliberative, and hybrid designs balance fast response with explicit planning.
26.10 Application Domains — Robots support manufacturing, logistics, field work, health, and exploration under distinct safety needs.

Interactive: plan around an obstacle

Use breadth-first search on a grid to find a shortest four-direction route. Move the robot one planned cell at a time.

Robot at start. Select Plan route.

Planning is not control. This demo assumes a known, static grid and perfect movement; a physical robot must use feedback to cope with localization error and changing obstacles.

Why breadth-first search finds a shortest route

The grid is an unweighted graph: each open cell is a vertex and each legal four-direction move is an edge of equal cost. Breadth-first search (BFS) explores a FIFO queue by distance layers. It marks a cell when first discovered and stores its predecessor; therefore the first discovered route to the goal has the fewest moves. Here the robot starts at index 24 and the goal is index 5; blocked cells are excluded. Once found, predecessor links are followed backward to reconstruct the route, then Move one step advances the displayed robot.

queue ← [start]; parent[start] ← none
while queue not empty:
  u ← pop front
  for each open neighbor v of u:
    if v unseen: parent[v] ← u; enqueue(v)
reconstruct goal-to-start using parent

Complexity and assumptions

Let V=WH be the number of grid cells and E the number of legal neighbor links. BFS takes O(V+E) time and O(V) auxiliary space for the queue and predecessor map; on a four-neighbor grid E=O(V), so both are O(WH). Route reconstruction and route-set construction take O(V) time and space in the worst case. The visible grid is O(V) DOM memory, separate from BFS workspace. The BFS bound assumes an unweighted static map and a FIFO queue; movement is assumed perfect, so a real robot needs feedback and replanning when its pose or obstacles differ. Each Move one step redraws the entire grid in O(V) visualization time, so showing a route of up to O(V) moves can take O(V²) total UI work even though the route search itself is O(V+E).