Project: 15 Puzzle, $A^{*}$, and Coordinated Motion Planning · Optimal Coordinated Motion Planning with $A^{*}$

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Programming problem. Find a collision-free schedule for robots with minimum number of steps.

  • Input format.  The first line contains two integers \(n\) and \(k\) (\(2\le n\le12\), \(1\le k\le4\)). The next \(n\) lines use \(\texttt{.}\) for a free cell and \(\texttt{\#}\) for an obstacle. Each of the next \(k\) lines contains \(s_{x},s_{y},t_{x},t_{y}\) for one robot; coordinates range from \(0\) to \(n-1\). Starts are pairwise different, as are targets; all specified cells are free. A schedule exists and has at most \(30\).

  • Output format.  Output the minimum number of steps \(T\) and then \(T\) strings of length \(k\), one per step, in the input robot order. Letters \(\texttt{U}\), \(\texttt{D}\), \(\texttt{L}\), and \(\texttt{R}\) move a robot in the corresponding direction; \(\texttt{W}\) means wait.

This problem can only be submitted at Cogniterra.
Public samples
Public sample 1
Input
2 4
..
..
0 0 0 1
0 1 1 1
1 1 1 0
1 0 0 0
Expected output
1
RDLU
Public sample 2
Input
3 2
...
...
...
1 0 1 2
1 2 1 0
Expected output
4
WU
WL
RL
RD