Using an optimal number of agents, maximise coverage of an area while minimising distance travelled

Question

I'm a CS Year 2 student working on a team project which requires a solution to the following problem:

Given a starting position on the edge of an irregular shape (example above) and a maximum number of available agents, maximise the area covered (meaning the number of squares visited inside the shape*) while minimising the distance travelled (euclidian distance - travelling diagonally inside a square is not the same as along an edge of the square) by the agents. It is also important to note that the agents have to return to the starting position and they also have a limited travel distance (they must return to the starting point before that maximum travel distance is reached).

*A square is considered to be "visited" if the agent travelled through a small enough vicinity around its center.

I am aware that this is a NP-hard problem and I am not looking for a revolutionary algorithm.

Finding the most efficient paths to cover an area from multiple starting locations

I also found this post which seems to be a variation of the problem I'm trying to solve and it suggests looking at metaheuristics and genetic algorithms.

What I am asking for is a starting point (articles, models, concepts, working solutions for variations of this problem) which would help me and my team develop a feasible but not extremely complex solution.

Thank you!

Image source: https://socratic.org/questions/58d82905b72cff79ad7811e9

Answer 1

First, note that if the shape is convex, the problem has a pretty easy heuristic solution: if each agent goes in a straight line from the start point, they can cover as much as possible by splitting the possible directions they can move in over the $n$ agents. If the maximum distance they can travel is less than the size of the region, then they'll visit a conical region, for example.

If the shape is not convex, then perhaps it can be approximated as a union of convex regions, and then the problem could be solved by assigning some subset of the agents to the nearest point in each convex subregion and then execute the algorithm above.

One way to approximate a shape by a union of convex regions is by calculating a Voronoi diagram. There's undoubtedly a rich literature on this that I unfortunately don't know much about.

Another thing that might help is routing the agents to each Voronoi cell starting from the farthest, so that you can take advantage of the fact that they will cover cells on the way. A primitive that could help with this is creating a graph that has a node per cell and edges between neighboring cells representing straight line moves, which you then run Dijkstra's algorithm on. If a cell has already been visited, you remove that node from the graph.

Ultimately the best solution is going to be strongly dependent on the geometry of the region, the distance that the agents can move, and how many agents there are. For example, if the number of agents is very small compared to the number of cells to visit, the problem is relatively easy.