Given an image and two points $A$ and $B$ on that image, how could we find a path from $A$ to $B$?

Question

If we have a search or path-finding problem, A* and Dijkstra's algorithm require that we formulate it as a search in a graph with nodes and connections between these nodes. If there are obstacles, we also need to encode this information in the graph, so that they are not traversed. Additionally, there may be costs/weights on the connections between points. If such weights/costs are high, the algorithms won't take that path.

I've been using A* and Dijkstra's algorithm this way so far. However, it's a bit cumbersome to always have to define the nodes/points and the relationships (or connections) between them. There's no learning here. I just define a graph and the algorithms search on this graph.

Let's say I have a white image, a green blob in the middle, and points $A$ and $B$ at either side of the blob, I need to get from $A$ to $B$. I don't have a search space represented as a graph here. I just have this image.

Could I use machine learning to solve this problem (and would it generalize to more complex maps)? If so, are there any research works on this topic? Or is that the wrong route to take (pardon the pun)?

Answer 1

Let's say I have a white image, a green blob in the middle, and points $A$ and $B$ at either side of the blob, I need to get from $A$ to $B$. I don't have points to traverse. I just have this image.

If your image is as "simple" as you describe here, with very easily distinguishable colours, the easiest solution would likely be to construct a graph as expected by algorithms such as A* as follows:

• Every pixel becomes a node in the graph, with connections to all adjacent pixels
• Green pixels (the green blob in the middle) are marked as non-traversable (or simply don't have connections to adjacent pixels) (I assume this thing is your obstacle).
• Pixels belonging to the points on either side of the obstacle are marked as starting and goal vertices.

Then, you have the graph that a traditional pathfinding algorithm like A* would expect, and can simply run the algorithm there.

---

If you get less "clear" images (i.e. not brightly coloured, easily distinguishable things, but more like real-life top-down images of an area), then the above won't really work anymore. In such cases, you'd likely want to look into Reinforcement Learning approaches, where you give an agent a reward when it successfully manages to find a connection between start and goal. In particular, you'd need Deep Reinforcement Learning approaches, because otherwise you're not going to be able to handle complex images.

Note that these approaches are not going to be simple to implement or immediately understand for 100% if you're a beginner. There won't be any "beginner-friendly" approaches for the problem you describe, it simply is quite a complex problem (requiring a mix of "decision-making" and "understanding" images).