Warehouse Robot Path Planner: A*, Dijkstra and conflict-free fleets (3D)

The model

The warehouse is a 28 x 19 grid of 1 m cells. Rack cells (and any pallet you drop in an aisle) are blocked; every other cell is a node joined to its four neighbours. One simulation tick is one second, and an AGV covers one cell per tick (1 m/s nominal speed).

Single-robot search

Every algorithm expands nodes by the evaluation function f(n) = g(n) + w·h(n), where g is the cost paid so far and h estimates the remaining cost.

• Dijkstra: h = 0. Optimal for any non-negative costs, but expands a disc of cells around the start.
• Breadth-first search: a FIFO queue, optimal in number of moves only. With unit costs it equals Dijkstra, which is the independent reference used by the check.
• A* with the Manhattan heuristic h = |dx| + |dy|. On a 4-connected grid with cell cost ≥ 1 this h never overestimates (admissible) and satisfies h(a) ≤ c(a,b) + h(b) (consistent), so A* returns an optimal path and never reopens a node.
• Weighted A*, w > 1: expands fewer nodes but is only guaranteed to be within a factor w of optimal.
• Greedy best-first: f = h. Very few expansions, no optimality guarantee at all.

The optional slow zones (amber floor) cost 3 per cell instead of 1, which is where Dijkstra, A* and BFS visibly part ways: BFS minimises moves, the other two minimise cost.

Many robots: prioritised space-time A*

For the fleet each robot plans in the space-time graph (x, y, t) with five actions (four moves and wait), each costing one tick. A reservation table stores every cell-time pair already claimed by the robots planned before it; a robot may not use a reserved vertex (vertex conflict) nor swap two cells with another robot in the same tick (edge conflict). The goal must be free for the whole dwell (2 ticks to pick up or hand over) and afterwards, and a robot that has finished a leg is treated as parked on its last cell until it re-plans. The heuristic is the exact obstacle-aware distance (a breadth-first search from the goal), so the search is still A*. Planning priority rotates every tick so nobody always loses.

Honest simplifications

• Prioritised planning is not complete and not optimal: when a plan fails (a goal or aisle is blocked by a parked robot) the robot waits and retries; the counter is shown as "plan retries".
• Discrete time, constant speed, no acceleration, turning time, battery model or robot size; tasks (random aisle cell, then random packing dock) are illustrative, so the deliveries per minute are model numbers, not warehouse benchmarks.
• Cell costs other than 1 apply to the single-robot query only; the fleet always uses unit cost.

Checks run in the page

• Optimality: on 200 random start-goal pairs of the current map the A*, Dijkstra and BFS costs equal a separate plain breadth-first reference, and A* never expands more nodes than Dijkstra.
• Weighted floor: A* equals Dijkstra on 150 pairs with slow zones, and weighted A* (w = 1.5) stays within 1.5 times the optimum.
• Conflict-free fleet: the realised trajectories of all robots are scanned tick by tick for two robots on one cell or swapping cells; the planner is not involved in this scan.