Table of Contents

What is a search problem? Learn how to represent graphs, states, and transitions — the foundation of every algorithm on this site.

Explores as deep as possible before backtracking. Simple to implement and useful for understanding recursive graph traversal.

Explores level by level and finds shortest paths on unweighted graphs. The canonical baseline for completeness.

Generalises BFS to weighted graphs by always expanding the cheapest frontier node. Guaranteed optimal on non-negative-weight graphs.

Guides search purely by a heuristic estimate to the goal. Very fast in practice but sacrifices optimality guarantees.

Select a few landmark nodes and precompute all-pairs distances to them. Use the triangle inequality to derive tight lower bounds at query time.

A precomputed lookup table of optimal first moves, compressed to stay in memory. Enables near-perfect heuristics at low overhead.

Embeds the graph into Euclidean space and uses the embedding distance as a heuristic — fast to compute and compact to store.

Eliminates symmetrically equivalent paths on uniform-cost grids by jumping over uninformative intermediate nodes.

A cleaned-up reformulation of JPS with improved pruning rules and clearer termination conditions.

Adds offline preprocessing to JPS so jump points can be identified in O(1) during online search.

Extends jump point search to three-dimensional grid environments with 26-connected neighbours.

Adapts JPS for grids where only the four cardinal moves are permitted — no diagonals.

An intuition-first introduction to planning with time: why the state space explodes and what techniques tame it.

Runs A* on a time-expanded graph where each node encodes both position and timestamp, enabling exact temporal planning.

Plans efficiently around dynamic obstacles by computing safe time intervals at each cell and treating them as graph nodes.

What is multi-agent pathfinding? Learn the formal definition, cost models, and why MAPF is computationally hard in general.

Assign a priority order and plan each agent in sequence, treating higher-priority agents as moving obstacles.

Searches the joint configuration space of all agents simultaneously. Optimal, but exponential in the number of agents.

Interleaves individual agent moves within the joint search to reduce the effective branching factor significantly.

A two-level search: find individual plans, detect collisions, add constraints, and re-plan. Optimal and widely used in practice.

An anytime variant of CBS that uses focal search to quickly find bounded-suboptimal solutions for large instances.

Dynamically assigns priorities during search rather than fixing them upfront, achieving better completeness than naïve prioritised planning.

Iteratively destroys and repairs subsets of agent paths to escape local optima — scales to hundreds of agents.

A lazy approach that adds collision constraints only when needed, enabling extremely fast solution construction at scale.