Spectral-Based Distributed Ergodic Coverage for Heterogeneous Multi-Agent Search
This work develops a multi-agent heterogeneous search approach that leverages the sensing and motion capabilities of different agents to improve search performance (i.e., decrease search time and increase coverage efficiency). To do so, we build upon recent results in ergodic coverage methods for homogeneous teams, where the search paths of the agents are optimized so they spend time in regions proportionate to the expected likelihood of finding targets, while still covering the whole domain, thus balancing exploration and exploitation.
This work introduces a new method to extend ergodic coverage to teams of heterogeneous agents with varied sensing and motion capabilities. Specifically, we investigate methods of leveraging the spectral decomposition of a target information distribution to efficiently assign available agents to different regions of the domain and best match the agents' capabilities to the scale at which information needs to be searched for in these regions.
Our numerical results show that distributing and assigning coverage responsibilities to agents based on their dynamic sensing capabilities leads to approximately 40% improvement with regard to a standard coverage metric (ergodicity) and a 15% improvement in time to search over a baseline approach that jointly plans search paths for all agents, averaged over 500 randomized experiments.
Research Team: Guillaume Sartoretti*, Ananya Rao*, Howie Choset (*equal contribution)
Multi-agent search scenario with two types of agents
There are two type of agents depicted: differential-drive agents with short-range, high fidelity sensors (represented by the red and orange circles), and omnidirectional agents with long-range, low fidelity sensors (represented by the blue and green circles). The different colored lines represent the paths followed by the different agents. The underlying distribution shows the likelihood of finding targets throughout the domain.
Example spectral reconstruction of a given map (center), based on only its lower-order coefficients only (left), or higher-order ones only (right). Yellow regions correspond to regions of high information, while darker blue regions correspond to regions of low information (here, high/low likelihood of finding targets).
Search performance comparison between the different agent assignments and the baseline, in terms of coverage performance (using the ergodic metric, lower is better) and time to find all targets (lower is better).
Sensitivity to the team size, comparing the coverage performance between our optimal assignment and the baseline. Gaussian maps (top), and road network (bottom). As expected, note the improved performance for smaller teams.
Sensitivity to the number of sampled paths, comparing the coverage performance between our optimal assignment and the baseline. Gaussian maps (top), and road network (bottom). There again, and as expected, note that our distributed search approach specifically improves performance with small numbers of samples.