GESCE: Graph-based Ergodic Search in Cluttered Environments

In this paper, we present a novel motion planning algorithm that inherits the strengths of both optimization and search-based planners. Optimization-based planners use the gradient of an objective function to generate a desired path, whereas search-based planners operate on a graph capturing the salient topology of a robot’s free space. A class of optimization-based planners leverages prior information, modeled as a probability distribution of target locations in an environment, to guide path generation. We embrace one specific measure, referred to as ergodicity, which encourages a robot to spend a proportion of its time, weighted by the distribution, where it is likely to find targets of interest. Methods that minimize ergodicity were not designed to handle obstacles in the environment, and augmented approaches that add "soft" constraints for obstacles to the cost function may still yield a path that collides with an obstacle. In this work, we present a hybrid approach that first generates a graph of the environment’s free space, followed by searching the graph with ergodicity as a heuristic. Our approach not only restricts the search to the free space, thereby avoiding obstacles by design, but also generates trajectories with low ergodicity values. Extensive testing on 125 test scenarios with varying degrees of clutter, information distribution, and robot start locations illustrate the efficacy of our algorithm.