Fair Subdivision of Multi-Robot Tasks

Juan Camilo Gamboa HigueraGregory Dudek

School of Computer Science, McGill University




Use ← and → to navigate. Press m to see the list of slides.

Motivation

Small and diverse team of robots

Single Global Task

  • Target search
  • Exploration
  • Coverage

Autonomous work subdivision


Motivation

A coverage task




  • Optimize task performance
    • Best robot for each region
  • Balance workloads
    • Most capable robots work more
  • Satisfy energy constraints

The scenario

A coverage task \(T\) and \(n\) robots,

Robots start with no information

The scenario

A coverage task \(T\) and \(n\) robots,

Robots agree on an allocation

The scenario

A coverage task \(T\) and \(n\) robots,

But as new information comes in...

old allocation might not be the best
(bad estimates, failures, unexpected events)

Main questions



In this work



How should the robots divide the task?

  • Optimize task performance
    • Best robot for each region
  • Balance workloads
    • Most capable robots work more
  • Satisfy energy constraints

Previous and related work:
Task Assignment

[1]    L. Liu and D. Shell. (2012)
Large-scale multi-robot task allocation via dynamic partitioning and distribution.

[2]    B.P. Gerkey and M.J. Mataric.(2002)
Sold!: auction methods for multirobot coordination.

[3]    C. Rossi, L. Aldama, and A. Barrientos. (2009)
Simultaneous task subdivision and allocation for teams of heterogeneous robots.

[4]    F. Tang and L. E. Parker. (2005)
Asymtre: Automated synthesis of multi-robot task solutions through software reconfiguration.

Previous and related work:
Environment partitioning

[5]    M. Pavone, A. Arsie, E. Frazzoli, and F. Bullo (2011).
Distributed algorithms for environment partitioning in mobile robotic networks.

[6]    J. G. Carlsson. (2011)
Dividing a territory among several vehicles.

[7]    M. Schwager, M. P. Vitus, D. Rus, and C. J. Tomlin. (2011)
Robust adaptive coverage for robotic sensor networks.

[8]    S. Bhattacharya, N. Michael, and V. Kumar. (2010)
Distributed coverage and exploration in unknown non-convex environments.

Our approach

Model as a fair division problem

Fair: balanced utilities and costs

Robots have a continuous "preference" over task space

Fair Division

Non-zero sum game

Can be formulated as a convex optimization problem (Dubins-Spanier,1961) (Dall'Aglio,2001)

Fair Task Subdivision

A coverage task \(T\) and \(n\) robots,

find allocation of subtasks \(A_i \subset T \) for \(i \in \lbrace 1..n \rbrace\)

Fair Task Subdivision

Find allocation of subtasks \(A_i \subset T \) for \(i \in \lbrace 1..n \rbrace\)

Abstract task performance as utility
  • minimizing expected coverage time
  • balancing workload
  • satisfying energy constraints
  • Maximize minimum utility, with constraints on allocation sizes

    The algorithm

    Complexity analysis

    • Runtime depends on:
      • how preference functions are stored
      • how the utilities are evaluated
      • the approximation factor \(\epsilon\)

    • If \(T\) is discretized as a grid, the runtime is: $$ O\left(\left(\frac{n}{\epsilon}\right)^2|T|\right)$$ \( |T| \): cell size

    Increasing number of robots

    Coverage of a random polygonal region with n robots

    Increasing number of robots

    Coverage of a random polygonal region with n robots

    Sample run of the algorithm

    Coverage of a square region (200x200 mts) with three robots, \(f_i(x) = -\frac{1}{\textrm{speed}_i(x)} \)

    Allocated areas (squared meters): (12101.5, 15878.5, 12020.0)
    Expected coverage times (seconds): (5778, 5778, 5778)

    Sample run of the algorithm

    Coverage of a square region (200x200 mts) with three robots (\(p_i\) is robot i position) \(f_i(x) = - (1-k) \frac{1}{\textrm{speed}_i(x)} - k \, (\textrm{distance}(p_i,x))^2 \)

    Allocated areas (squared meters): (12558.75, 14299.25, 13142.0)
    Expected coverage times (seconds): (6000, 5185, 6520)

    Sample run of the algorithm

    Coverage of a square region (200x200 mts) with three robots (\(p_i\) is robot i position) \(f_i(x) = - (1-k) \frac{1}{\textrm{speed}_i(x)} - k \, (\textrm{distance}(p_i,x))^2 \)

    Allocated areas (squared meters): (12838.0, 12930.75, 14231.25)
    Expected coverage times (seconds): (6177, 4620, 12556)

    Sample run of the algorithm

    Coverage of a square region (200x200 mts) with three robots (\(p_i\) is robot i position) \(f_i(x) = - \textrm{distance}^2(p_i,x)\)

    Allocated areas (squared meters): (12888.5, 12836.25, 14275.25)
    Expected coverage times (seconds): (6210, 4578, 15020)

    Extending the fair division model

    Summary

    What follows

    What follows

    Questions?

    Fair Subdivision of Multi-Robot Tasks

    Juan Camilo Gamboa HigueraGregory Dudek

    School of Computer Science, McGill University


    http://cim.mcgill.ca/~gamboa/
    http://cim.mcgill.ca/~mrl/

    #