Robot chessboard lab

The pieces drive themselves to the next puzzle: no teleporting, no touching. The default planner moves as many pieces at once as it can to make each reset as short as possible.

Space random · ← → previous / next · R reset · P paths
Starting position
All 32 pieces on their home squares.
ready

Planner comparison on the last transition

Runs every planner on the same change of position. Times are at the current speed. The lower bound is the longest single trip under the best possible assignment; no planner can beat it.

The comparison appears after the first transition.

How each planner thinks

Fastest reset

Built to minimize the time until the last piece arrives. Pieces are matched to targets so that the longest trip is as short as possible (bottleneck assignment). Then many priority orders are tried within about a second: the piece that arrives last is moved to the front and the plan is rebuilt. Moves are checked with exact geometry, so pieces may slip past each other whenever the gap is wide enough for their real size.

Pieces step aside

No grid: pieces are circles and positions are continuous. Each trip takes the route that disturbs least. A piece too close to it slides off by the least that lets the moving circle pass, pushes a neighbour only if it touches it, and returns home once the circle has gone by. Trips start as soon as they collide with nothing already under way.

Cooperative A* (parallel)

Every piece is a robot. Pieces are planned one by one in space-time: each reserves the squares it occupies at each moment, and later pieces route around them or wait. Uses the strict square-based rules below and a single greedy priority order.

PIBT (parallel, reactive)

No long-term plan: at each step every robot steps toward its target; if a higher-priority robot needs the square, it pushes the one in the way, which inherits the priority. Very fast to compute, but paths come out longer.

Optimized sequential

One magnet under the board, so one piece at a time. Optimal matching (Hungarian algorithm), an order that keeps empty magnet travel short, A* with diagonals and a turn cost, rounded corners and a trapezoidal speed profile.

Naive, one piece at a time

One magnet, pieces taken in board order, each to the first free target of its type, orthogonal moves only, stopping on every square. Roughly the clumsy choreography you noticed on the real board.

Collision rules. The strict rules used by Cooperative A*, PIBT and the sequential planners work on whole squares: you may enter an occupied square only if its occupant leaves in exactly the same direction, like train cars, and a diagonal step needs both side squares empty before and after. The fastest-reset planner instead computes the closest approach of every pair of moving pieces during each step and only requires it to stay above the piece diameter you set. Every plan is checked continuously afterwards; the result is shown as minimum clearance.