Title: Multi-agent Multi-objective Ergodic Search

Abstract: 

In order to find points of interest in a given domain, many planners use a priori information to guide the search to expedite the detection of targets. We present an approach to direct multiple agents (MA) to search a given domain subject to multiple objectives (MO), each characterized by its own information map. Our approach embraces an information-based method, called ergodic search (ES). In this thesis, we introduce the Multi-Agent Multi-Objective Ergodic Search (MA-MO-ES) problem and prescribe computationally efficient methods to solve it. The primary goal of this work is to determine the trajectories for all agents such that the worst-case objective or highest ergodic metric on any information map is minimized (minmax objective). This requires determining which information maps should be considered when optimizing the trajectory of a particular agent. In other words, this work computes the optimal allocation, of information maps to agents, that minimizes the maximum ergodic metric on the given information maps.

The main challenge in determining the optimal allocation is the exponential growth of the number of possible allocations with the number of maps and agents. 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 the optimal allocation. To reduce the branching factor in branch and bound, we propose two approaches for clustering information maps before allocation: k-means and minimum bounding sphere clustering. These clustering approaches leverage the similarity between information maps to approximate the cluster of maps that should be assigned to a  single agent. Testing on 70 randomly generated test cases shows an order of magnitude improvement in runtime for our branch and bound approach compared to an exhaustive brute force approach. Using similarity clustering, the runtime further reduces by two orders of magnitude while maintaining good quality allocations with an average 20% deviation from the optimal minmax ergodic metric.

Committee:
Dr. Howie Choset (advisor)

Dr. Maxim Likhachev

Dr. Katia Sycara

Dr. Zhongqiang Ren