Multi-Agent Multi-Objective Ergodic Search Using Branch and Bound
Akshaya Kesarimangalam Srinivasan, Geordan Gutow, Zhongqiang Ren, Ian Abraham, Bhaskar Vundurthy, Howie Choset
Abstract
Search and rescue applications often need multiple agents to complete a set of conflicting tasks. This paper studies a Multi-Agent Multi-Objective Ergodic Search (MA-MO-ES) approach to this problem where each objective or task is to cover a domain subject to an information map. The goal is to allocate coverage tasks to agents so that all maps are explored ergodically. The combinatorial nature of task allocation makes it computationally expensive to solve for optimal allocation using brute force. Apart from a large number of possible allocations, computing the cost of a task allocation is itself an expensive planning problem. To mitigate the computational challenge, we present a branch and bound-based algorithm with pruning techniques that reduce the number of allocations to be searched to find optimal coverage task allocation. We also present an approach to leverage the similarity between information maps to further reduce computation. Extensive testing on 147 randomly generated test cases shows an order of magnitude improvement in runtime compared to an exhaustive brute force approach.
BibTeX
@inproceedings{iros2023_multiagentmultio,
title = {Multi-Agent Multi-Objective Ergodic Search Using Branch and Bound},
author = {Akshaya Kesarimangalam Srinivasan and Geordan Gutow and Zhongqiang Ren and Ian Abraham and Bhaskar Vundurthy and Howie Choset},
booktitle = {IROS 2023},
year = {2023}
}