Fair Subdivision of MultiRobot 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
 How do robots model and measure their abilities?
 How should the robots divide the task?
 When should the robots decide to update allocation?
In this work
 How do robots model and measure their abilities?
 How should the robots divide the task?
 When should the robots decide to update allocation?
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)
Largescale multirobot 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 multirobot 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 nonconvex environments.
Our approach
Model as a fair division problem
Fair: balanced utilities and costs
Robots have a continuous "preference" over task space
 rugged vs. smooth
 cluttered vs. uncluttered
 reachable regions
 unassigned regions
 demand for abilities or services
Fair Division
Nonzero sum game

Split a divisible object \(T\) among \(n\) interested players
(a piece of land, an inheritance, a cake)

Players have different opinion on what is valuable
(a utility density over subsets of \(T\))

Every player \(i\) should receive at least some allocation \(\ u_i\) of the object
(usually \(1/n\) of the total value)
Can be formulated as a convex optimization problem (DubinsSpanier,1961) (Dall'Aglio,2001)
 Maximize the total utility
 Maximize the minimum utility between players
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\)
 minimizing expected coverage time
 balancing workload
 satisfying energy constraints
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

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)^2T\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) =  (1k) \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) =  (1k) \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
 Formulation of spatial task subdivision as fair division problem
A coverage task \(T\) and \(n\) robots,
workload balancing, energy constraints, heterogeneity
 Iterative approximation algorithm for finding allocation
Search for weights on dual space
 Complexity analysis of the algorithm
\(O\left(\left(\frac{n}{\epsilon}\right)^2T\right)\)
What follows
 Updating the robot "preferences" \(f_i\) from data
 Comparison with fully decentralized subdivision
 Motion planning based on subdivision scheme and viceversa (kinematic constraints, obstacles)
 "Meeting" time and location scheduling (Meghjani and Dudek, 2012)
What follows
 Updating the robot "preferences" \(f_i\) from data
 Comparison with fully decentralized subdivision
 Motion planning based on subdivision scheme and viceversa (kinematic constraints, obstacles)
 "Meeting" time and location scheduling (Meghjani and Dudek, 2012)
←
→
#