# Solving a grid maze with blocked paths

I have to build two robots (virtual) that will solve a grid maze that has blocked paths colored in red. The robots cannot go on these red paths in any case. There are several white patches in some random places on the grid and they consist of coins of two colors (yellow, blue). Positions of these small white patches can differ from positions in below grid.

The robots have to pick these coins, take blue coins to the Right side big white starting square, and yellow coins to the Left side big white starting square. There are 6 coins altogether. (3- Yellow, 3- Blue) Robots can only carry one coin at once. Communication between robots is optional. (But I think it's better to have communication between the two robots)

The robots do not know the grid map ahead. Are there any specific algorithms that can be used for this mapping purpose?

Are there any algorithms that can be used for solving this kind of problem? I did some searching but I was unable to find any algorithms that can be used for such a problem. Could you please guide me on how to solve this?

Time the robot takes to complete the task is the key performance factor here.

Any help is much appreciated. Thank you!

You didn't specify any performance requirement. That admits the simple algorithm:

do forever:
move at random
if in a destination square
if carrying coin that matches destination
drop coin
else if at a coin and not carrying one
pick up coin


Also you didn't specify

• whether the robots know the grid map ahead of time, or if they have to discover it for themselves
• whether the robots know how many coins there are
• whether the robots move in discrete steps from one intersection to the next
• whether the two robots supposed to cooperate

If the map is known (or becomes known through sufficient exploration) I would start with Dijkstra's shortest path algorithm. That would help a robot get from where it is, to where a coin is. Then get from there to the destination square. Then repeat that process until all the coins get to their destination. If the number of coins is unknown, then the robots will keep track of what paths they have covered--if all paths have been covered without finding any coins, they're done.

By "move in discrete steps" I mean the considerably simpler case where you could consider the grid to be a graph. That is to be distinguished from a somewhat more physical simulation where the robot moved at X meters/second along a path Y meters long and needed to recognize when it had a choice of paths to take. That gets into localization and SLAM and all that, which is complicated enough that I infer that's not what you meant!

A discrete graph would have nodes (grid intersections, plus the two special destination squares) and edges (paths connecting the nodes). Blocked paths don't even need to be represented. A discrete move would be a single instantaneous operation, taking the robot from one node, along an edge, to another node.

You could assume (or specify) that each robot knows:

• where it is
• what edges (paths) and nodes (intersections) it has visited

Then it would be good to read about graph traversal algorithms. That would provide an efficient way to explore the graph (grid). Once all the coins are discovered (if not transported), you could even stop it early, without mapping the entire graph.

That should result in "sufficient exploration" to get into shortest path planning.

I suspect that a more able algorithmicist than I am might find ways to bias the exploration vs transport to take early advantage of information as it is discovered. But that's a brainstorm for another day.

• I'm sorry about that. Time the robot takes to complete the task is the key performance factor here. No, the robots do not know the grid map ahead. Is there any specific algorithms that can be used for this mapping purpose? There are 6 coins altogether. (3- Yellow, 3- Blue) I did not understand your question about moving in discrete steps. Communication between robots is optional. Oct 26 '21 at 20:00
• I edited my question. I did some Googling but I was unable to find any algorithms that can be used for mapping when there are blocked paths in the grid. Oct 26 '21 at 20:06
• I edited my answer, adding more detail. BTW, Stack Exchange suggests that if you find an answer useful, hit that green checkmark. Oct 27 '21 at 18:09