In the game of Sokoban, a robot has to push boxes to a goal in a map. He has only the ability to move in four directions (left, right, up, down) and the map is small (15x15 fields) so it looks like an easy task. I have implemented the game with one robot, a single box and without any obstacles in the programming language Python.
The idea is, to use the RRT (Rapidly-exploring random tree) algorithm for planning the movements of the robot. He can move in four directions, so a graph is created which stores possible sequences of actions. New nodes are added to the graph with an external random subgoal. This explores the graph in a uniform way which has a speed improvement over selecting a random node in the graph.
But there is a problem. It takes to long to bring the box to the goal. My standard PC is running at 100% cpu consumption, and the algorithm needs around 1 minute, until he has calculated the movements for the robot. What can i do to improve the Sokoban solver?