Multi-Agent Multi-Objective Ergodic Search Using Branch and Bound

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.

Authors

• Akshaya Kesarimangalam Srinivasan
• Geordan Gutow
• Zhongqiang Ren
• Ian Abraham
• Bhaskar Vundurthy
• Howie Choset

Keywords

• Runtime
• Costs
• Force
• Search problems
• Planning
• Resource management
• Task analysis
• Branch-and-bound
• Ergodic Search
• Optimal Allocation
• Multiple Agents
• Task Allocation
• Cost Allocation
• Number Of Allocations
• Upper Bound
• K-means
• State Space
• Multi-objective Optimization
• Tree Structure
• Exhaustive Search
• Root Node
• Auction
• Number Of Agents
• Pareto Optimal
• Trajectory Optimization
• Set Of Maps
• Fourier Coefficients
• Exhaustive Search Algorithm
• Set Of Agents
• Fourier Basis
• Robot State