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.
Image source: https://socratic.org/questions/58d82905b72cff79ad7811e9