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.
