Personal tools
You are here: Home CG seminar 2020 Fast Near-Optimal Heterogeneous Task Allocation via Homogeneous Decomposition
« September 2020 »
September
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930
Log in


Forgot your password?
 

Fast Near-Optimal Heterogeneous Task Allocation via Homogeneous Decomposition

Wednesday, July 1st, 2020, 16:10, 17:10 Israel time

Checkpoint 480

Zoom: Request the link from Dan Halperin or Golan Levy

underline

Fast Near-Optimal Heterogeneous Task Allocation via Homogeneous Decomposition

Kiril Solovey, Stanford

Abstract:

Multi-robot systems are uniquely well-suited to perform complex tasks such as patrolling (and tracking), information gathering, and pick-up and delivery problems, offering significantly higher performance than single-robot systems. A fundamental building block in most multi-robot systems is task allocation: assigning robots to tasks (e.g., patrolling an area or servicing a transportation request) as they appear based on the robots' states to maximize reward. In many practical situations, the allocation must account for potentially heterogeneous capabilities (e.g., availability of appropriate sensors or actuators) to ensure the feasibility of execution, and exploit predictive information concerning the likelihood of future tasks to promote a higher reward over a long time horizon.

To this end, we present an efficient algorithm for heterogeneous task-allocation achieving an approximation factor of at least 1/2 of the optimal reward. Our approach demonstrates that the problem can be decomposed into several homogeneous subproblems that can be solved efficiently using min-cost flow. Through simulation experiments, we show that our algorithm is faster by several orders of magnitude than a MILP-based approach.

This is joint work with Saptarshi Bandyopadhyay, Federico Rossi, Michael T. Wolf, and Marco Pavone.
Document Actions