Search
MGMPSolver.py
In contrast to a classical path planning (from A to B), we need to estimate all distances between the given points in the multi-goal path planning problem. It can be done by existing algorithm:
Notice that algorithms from the first two groups have to be called multiple times to get the full distance matrix.
Download prepared codes and configuration files. Then download and compile LKH solver (implementation of the Lin–Kernighan heuristic algorithm) as follows:
cd lkh ./install.sh cd -
Now, you should be able to run Packman example.
./task9_eval.py
The result should be similar to:
This scenario is prepared with a working example which finds the shortest tour (TSP solution) based on the Euclidean distance. However, the obstacles in the environment are not considered and, therefore, the final trajectory collides with the walls, see the image above.
Our task is to replace the Euclidean distance by the shortest feasible trajectory in the maze. Since the original Pac-man can move only in 4 direction, we also utilizes the same 4 moves during the planning phase and discard all diagonal moves. In the prepared codes, a naive implementation is provided using A* from previous lectures. The A* algorithm needs to be called $\mathcal(n^2)$ times which is the main drawback of this approach.