Method and system for improved coverage path planning

A method for determining a path for a robotic device, comprising:

• obtaining, by a processing device of the robotic device, a navigation map of an environment, wherein the navigation map is divided into a grid of vertices, an adjacency list that identifies a distance between each vertex in the grid of vertices and each neighboring vertex that is adject to the vertex, and a super adjacency list that includes elements representing a shortest distance and path turns between each pair of vertices in the navigation map;
• using the super adjacency list to perform a modified Ant Colony Optimization (ACO) process that generates an ACO path for an ant that starts at a starting vertex and uses heuristic and pheromone values to determine the next vertex to visit until all vertices in the navigation map have been visited;
• determining a total distance and number of turns in the ACO path;
• repeating the operations of using the super adjacency list to perform the ACO process and determining the total distance and number of turns in the ACO path traced by an ant until a threshold number of iterations has been performed;
• sorting ACO paths by distance and number of turns;
• updating pheromone information associated with each vertex for a fraction of paths with best distance and turn information;
• and
• saving one or both of shortest or fastest ACO path in a current iteration.