Multi-Agent Path Finding (naive encoding)

cell(1..M, 1..N) :- size(M, N).
timeStep(1..T) :- timeLimit(T).

% force start and end locations.
location(A, 1, I, J) :- start(A, I, J).
location(A, T, I, J) :- target(A, I, J), timeLimit(T).

% no teleportation
allowedMove(I, J, I, J) :- cell(I, J).
allowedMove(I, J, I, J+1) :- cell(I, J), cell(I, J+1).
allowedMove(I, J, I, J-1) :- cell(I, J), cell(I, J-1).
allowedMove(I, J, I+1, J) :- cell(I, J), cell(I+1, J).
allowedMove(I, J, I-1, J) :- cell(I, J), cell(I-1, J).

% generate possible locations
{ location(A, T, I, J) } :- agent(A), cell(I, J), timeStep(T).
:- location(A, T, I, J), location(A, T+1, K, L), not allowedMove(I, J, K, L).

% no ubiquity
:- location(A, T, I, J), location(A, T, I', J'), I != I'.
:- location(A, T, I, J), location(A, T, I', J'), J != J'.

% no disappearing
located(A, T) :- location(A, T, I, J).
:- agent(A), timeStep(T), not located(A, T).

% rule out map conflicts
:- location(A, T, I, J), blocked(I, J).

% rule out vertex conflicts
:- location(A, T, I, J), location(B, T, I, J), A != B.

% rule out edge conflicts
:- location(A, T, I, J), location(A, T+1, K, L), location(B, T, K, L), location(B, T+1, I, J), A != B.

#show location/4.