Finding the most efficient paths to cover an area from multiple starting locations
If I understand your description correctly, there is no polynomial-time algorithm that solves each instance optimally. Intuitively, if you had an efficient algorithm for your problem, we could use it to find a Hamiltonian cycle (i.e., a cycle that visits each vertex exactly once) in a grid graph which is known to be NP-complete [1]. (The paper also contains hardness results for various "grids"; see whether some of the definitions actually capture your concept of a "grid").

In other words, we can reduce the problem of determining whether a grid graph has a Hamiltonian cycle to your problem where we have single circle.

You should not be discouraged too much by such a result though. It is perfectly possible you can do considerably better than your current algorithm, i.e., perhaps maybe even most of your instances are actually quite simple to solve. For instance, you could look at various metaheuristics and consider using (say) a genetic algorithm to find a good solution.



[1] Arkin, Esther M., Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph SB Mitchell, Yurai Núñez-Rodríguez, Valentin Polishchuk, David Rappaport, and Henry Xiao. "Not being (super) thin or solid is hard: A study of grid Hamiltonicity." Computational Geometry 42, no. 6-7 (2009): 582-605.