The aim is to guide a bot from Source S to Goal G while passing through all the checkpoints @ (in any order). The cells marked as # cannot be accessed. The bot can move on locations marked .
########
#@....G#
##.##@##
#..@..S#
#@.....#
########
One way to solve it would be to select one checkpoint as goal from current state and then guide the bot to it. Then select the next checkpoint as goal and current checkpoint as source and guide the bot to its new goal. Eventually guide it to the state G from the last checkpoint.
But this technique relies heavily on the order of checkpoints traversed.
I would like to know if a good heuristic can be found to decide which checkpoint to go to next?
I think this problem can be reduced to travelling salesman. Let S, G and @ be the nodes of the graph. Then compute the minimum distance between each pair of nodes, taking any walls into account. Then you have a graph with weighted distances between the points. Now this is TSP, with the small difference that you know the first and last node.