We study the problem of distributing a single global task between a group ofheterogeneous robots. We view this problem as a fair division game. In this setting,every robot defines a preference function over parts of the task according to its sens-ing and motion capabilities. These preferences are described by density functionsover the task. We want to find an allocation of the global task that maximizes theprobability of task completion. We first formulate the task distribution problem as afair subdivision problem and provide a centralized algorithm to compute the alloca-tions for each robot. We provide a complexity analysis and computational results ofthe algorithm. We also provide a decentralized approach, based on the decentralizedcomputations of non-differentiable linear programs using the subgradient methodand discuss its convergence properties. / Nous étudions le problème de distribution d'une simple tâche globale entre un groupe de robots hétérogènes. Nous nous représentons ce problème comme un jeu de division juste. Dans ce contexte, chaque robot définit une fonction de préférence qui règne sur certaines parties de la tâche selon ses capacités de détection et de mouvement. Ces préférences son décrites par des fonctions de densité qui gèrent la tâche. Nous cherchons à trouver une allocation de la tâche globale qui maximise la probabilité de complétion de la tâche. Premièrement, nous formulons le problème de distribution de la tâche comme un problème de subdivision juste auquel on fournit un algorithme centralisé qui calcule les allocations pour chaque robot. Nous fournissons une analyse de complexité et les résultats numériques de l'algorithme. De plus, nous fournissons une approche decentralisée basée sur la décentralisation des calculs de programmes linéaires non-dérivables utilisant la méthode sous-différentielle et discutons ses propriétés de convergence.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.117171 |
| Date | January 2013 |
| Creators | Gamboa Higuera, Juan Camilo |
| Contributors | Gregory L Dudek (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0023 seconds