Solving a grid maze with blocked paths

Question

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!

Answer 1

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.

Edited to add response to comments

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.