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
- 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)
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
- rugged vs. smooth
- cluttered vs. uncluttered
- reachable regions
- unassigned regions
- demand for abilities or services
Fair Division
Non-zero 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 (Dubins-Spanier,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)^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
- 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)^2|T|\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)
←
→
#