Sparse Sensing in Ergodic Search
This work presents a novel, sparse sensing motion planning algorithm for autonomous mobile robots in resource limited coverage problems. Optimizing usage of limited resources while effectively exploring an area is vital in scenarios where sensing is expensive, has adverse effects, or is exhaustive.
This problem is approached using ergodic search techniques, which optimize how long a robot spends in a region based on the likelihood of obtaining informative measurements which guarantee coverage of a space. The ergodic search problem is recast to take into account when to take sensing measurements. This amounts to a mixed-integer program that optimizes when and where a sensor measurement should be taken while optimizing the agent's paths for coverage.
Using a continuous relaxation, this formulation performs comparably to dense sampling methods, collecting information-rich measurements while adhering to limited sensing measurements. Multi-agent examples demonstrate the capability of this approach to automatically distribute sensor resources across the team. Further comparisons show comparable performance with the continuous relaxation of the mixed-integer program while reducing computational resources.
Research Team: Ananya Rao, Ian Abraham, Guillaume Sartoretti, Howie Choset
Mixed-Integer Continuous Relaxation for Sparse Ergodic Optimization
Illustrated is the process with which we jointly optimize for trajectories and when to sample. The decision variable is relaxed to be continuous [0,1] where solutions are projected into the integer {0,1} space. As input, our approach takes information prior distributions which guide the planning and sensing. Output trajectory solutions (shown on the right) show concentrated samples over areas of high information with minimal use of sensor resources.
Trajectories are generated with a decision variable for when to take a sensor measurement.
Results show that sparse ergodic optimization has better coverage performance in terms of the ergodic metric when compared to standard ergodic optimization with uniformly distributed sparse measurements. The probabilistic heuristic results in comparable performance.
Trajectories for a multi-agent team are generated with a decision variable for when to take a sensor measurement.
Results show that multi-agent sparse ergodic optimization has better coverage performance in terms of the ergodic metric when compared to standard ergodic optimization with uniformly distributed sparse measurements and with sparse measurements distributed using a probabilistic heuristic.
Solving the mixed integer formulation of the sparse sensing problem leads to slightly better coverage performance (left), in terms of the ergodic metric, but has a much higher computational cost (right).