Glossary

46 terms that recur across the curriculum. Skim before starting; refer back as needed.

algebraic connectivity

Lambda-2, the second-smallest Laplacian eigenvalue

The Fiedler value is positive if and only if the graph is connected, and its size sets the consensus convergence rate—error decays like e^(-lambda-2 * t). Larger means faster agreement.

alignment

Match the velocity of neighbors

The boids rule that steers a robot toward the average heading and speed of its neighbors, so the group moves coherently in the same direction.

assignment problem

Matching robots to tasks at minimum total cost

A bipartite matching that minimizes sum of c_ij * x_ij. Greedy nearest-task assignment is locally sensible but globally suboptimal; the Hungarian algorithm finds the true optimum in O(n^3).

auction algorithm

Distributed task allocation via bidding

Robots bid on tasks as value minus price; the highest bidder wins and the price rises. Prices coordinate the swarm toward a near-optimal assignment with no central controller.

boids

Reynolds' 1986 three-rule flocking model

A simulated flock where each agent obeys separation, alignment, and cohesion. Weighted together these local rules produce convincing global motion with no leader and no shared goal.

Byzantine failure

A robot that lies or sends arbitrary values

A faulty or malicious agent reporting wrong information. Mean consensus is corrupted by even one liar; robust aggregation like median or trimmed mean tolerates a minority of them.

cohesion

Steer toward the group's center

The boids rule that pulls a robot toward the average position of its neighbors, keeping the flock together as a single body.

communication graph

Nodes are robots, edges are who talks to whom

The topology of the swarm: each robot is a node and each communication link is an edge. The graph structure determines everything—consensus speed, fault tolerance, and whether agreement is even possible.

connectivity

Whether information can reach every robot

A graph is connected if a path exists between any two robots. Consensus and global agreement are impossible on a disconnected graph—isolated groups converge to different values.

consensus

Agreeing on a value with no leader

A distributed algorithm where each robot repeatedly averages its value with neighbors: x_i <- x_i + alpha * sum(x_j - x_i). On a connected graph everyone converges to the global average—the backbone of swarm coordination.

covariance

How much uncertainty we have

A number (or matrix) that describes how spread out our estimates are. High covariance = very uncertain, our guess could be way off. Low covariance = confident, we're pretty sure where it is.

cyclic pursuit

Each robot chases the next in a cycle

A simple rule—pursue your successor, optionally with a rotation angle—that makes a ring of robots settle into a rotating regular polygon. A vivid example of complex motion from one local rule.

drift

Error that accumulates over time

Some sensors have tiny errors that add up. If you integrate a gyroscope that's slightly off, after an hour you might think you've rotated 10° when you haven't moved at all. This accumulated error is drift.

emergence

Global behavior from local rules

Complex, coordinated swarm behavior that arises from each robot following simple local rules. No single agent knows the global plan—the flock, colony, or formation 'decides' as a whole.

exploration vs exploitation

Trying new options vs using the best known one

The fundamental tradeoff between gathering new information and acting on current knowledge. Strategies like UCB1 balance the two optimally, achieving logarithmic regret over time.

exteroception

External sensing (Sensing the world)

Sensors that look at the world around the robot. Examples: Cameras, Lidar, Radar, GPS. These allow the robot to correct drift by spotting known landmarks.

formation control

Maintaining relative positions while moving

Control laws keep robots at target inter-robot distances d_ij so the group moves and rotates as a rigid shape. Whether a formation holds depends on graph rigidity—2D rigidity needs at least 2n-3 edges.

frontier exploration

Send robots to the edge of the known map

A frontier is the boundary between explored and unexplored space. Dispatching robots to the nearest frontier maximizes information gain per step and minimizes redundant re-exploration.

Gaussian

Bell-curve shaped probability distribution

Also called 'normal distribution'. Most measurements cluster around the true value, with fewer measurements far away. The bell curve shape appears everywhere in nature - heights, test scores, measurement errors.

gossip protocol

Asynchronous pairwise averaging

Robots randomly pick a neighbor and average values, no global clock required. Slower than synchronous consensus but robust to packet loss and failures, which makes it practical for real swarms.

graph Laplacian

Matrix L = D - A that encodes the swarm graph

Built from the degree matrix D and adjacency matrix A. The Laplacian drives consensus dynamics (x' = -Lx) and its eigenvalues reveal how well-connected the swarm is.

graph rigidity

Enough constraints to lock a formation's shape

A formation is rigid when its distance constraints uniquely determine all positions up to translation and rotation. Too few edges leave it under-constrained and the shape collapses.

landmark

A recognizable feature in the environment

Something the robot can see and recognize - a door, a corner, a unique pattern. By measuring distances to known landmarks, the robot can figure out where it is (like navigating by stars).

Laplacian flow

Continuous-time consensus, x' = -Lx

The smooth analogue of discrete consensus, where each robot's value changes at a rate proportional to its disagreement with neighbors. Equivalent to gradient descent on the disagreement energy; like heat flowing between connected rooms.

local minimum

An energy valley that traps a robot

A point where the gradient is zero but it is not the global best. Robots following a potential field can get stuck here—like a ball settling in a bowl—because all nearby forces point inward.

local sensing

Each robot only perceives nearby neighbors

A robot senses only agents within its sensing radius, not the whole world. This partial view is what makes swarms scalable: adding 1000 robots still leaves each processing only a handful of neighbors.

loop closure

Recognizing you've returned to a place you've been before

When mapping, errors accumulate as you travel. But if you recognize 'I've been here before!', you can correct all the accumulated drift. This 'closing the loop' snaps the whole map into consistency.

noise

Random errors in sensor measurements

Real sensors aren't perfect. They give slightly different readings each time, even when measuring the same thing. This randomness is called noise. Think of static on a radio - the signal is there, but with interference.

odometry

Estimating position by counting wheel rotations or steps

Calculating where you are based on how much you've moved. Like counting steps in the dark. It is accurate over short distances but drifts over time as small errors add up.

partial observability

Seeing part of the world, not all of it

Each robot knows only its local surroundings—neighbors inside its radius—and never the full global state. Algorithms must coordinate the swarm despite no agent having the complete picture.

particle

One guess about what the state might be

Instead of tracking one estimate, we track hundreds of guesses (particles). Each particle is a hypothesis: 'maybe the robot is HERE'. Particles that match sensor readings survive; wrong guesses die off.

pheromone

A virtual trail robots deposit and follow

A scalar field laid down by robots and sensed by others. Trails accumulate where many agents pass, decay over time so stale paths fade, and diffuse to spread information—letting the shortest path self-reinforce.

potential field

An energy landscape robots flow downhill on

A function U(p) assigns energy to each point; robots move along the negative gradient (a = -grad U) to minimize it. Attraction pulls agents together, repulsion pushes them apart—producing natural, water-like motion.

proprioception

Internal sensing (Sensing self)

Sensors that measure what the robot is doing internally. Examples: Encoders (wheel speed), IMU (acceleration/rotation). These don't need the outside world to work, but they drift.

rendezvous

Consensus applied to positions

Each robot moves toward the average position of its neighbors; on a connected graph the whole swarm converges to the centroid. The building block for formation assembly.

robust consensus

Agreement that survives faults and liars

Consensus built on outlier-resistant aggregation. Median consensus tolerates fewer than 50% malicious robots; Byzantine agreement in general requires more than two-thirds honest participants.

scalability

Adding robots without redesigning the system

Because each robot relies only on local sensing and local rules, a swarm grows by simply spawning more agents. Communication and computation stay bounded per robot no matter how large the swarm.

sensing radius

How far a robot can detect neighbors

The distance r within which a robot can sense other agents. The neighbor set is N_i = { j : ||p_i - p_j|| <= r }. Larger radius means more connections and better coordination; too small fragments the swarm.

sensor fusion

Combining multiple sensors to get a better estimate

Each sensor has strengths and weaknesses. By combining them intelligently, we can get an estimate that's better than any single sensor alone. Like using both your eyes for depth perception.

separation

Steer away from crowded neighbors

The boids rule that pushes a robot away from neighbors that are too close, preventing collisions and preserving personal space. Repulsion strength grows as neighbors get nearer.

state

Everything we want to know about the system

For a robot, the state might be: position (x, y), orientation (which way it's facing), and velocity (how fast it's moving). The filter's job is to estimate this state from noisy sensor data.

step size

The alpha that scales each consensus update

The gain alpha in the consensus update. Too large and values overshoot and oscillate; too small and convergence crawls. Stability requires 0 < alpha < 2 / lambda_max(L).

stigmergy

Coordination by modifying the environment

Agents communicate indirectly by changing a shared medium—like ants depositing pheromone—rather than messaging each other. It scales to enormous swarms because there is no direct communication overhead.

stochasticity

Injecting randomness to escape getting stuck

Adding random 'kicks' or occasional random walks lets a deterministic swarm escape local minima. It trades efficiency for the ability to keep exploring and find the global optimum.

swarm intelligence

Distributed problem-solving by many simple agents

The collective capability of a large group of simple agents to solve problems no individual could. Inspired by ant colonies, bird flocks, and fish schools; the basis for scalable swarm robotics.

Voronoi coverage

Lloyd's algorithm for optimal area coverage

Partition space so every point belongs to its nearest robot (a Voronoi cell), then move each robot to its cell's centroid and repeat. This minimizes coverage error for tasks like surveillance and search.