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

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!

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.