Return to search

Techniques for the allocation of resources under uncertainty

L’allocation de ressources est un problème omniprésent qui survient dès que
des ressources limitées doivent être distribuées parmi de multiples agents autonomes
(e.g., personnes, compagnies, robots, etc). Les approches standard pour déterminer
l’allocation optimale souffrent généralement d’une très grande complexité de calcul.
Le but de cette thèse est de proposer des algorithmes rapides et efficaces pour
allouer des ressources consommables et non consommables à des agents autonomes
dont les préférences sur ces ressources sont induites par un processus stochastique.
Afin d’y parvenir, nous avons développé de nouveaux modèles pour des problèmes de
planifications, basés sur le cadre des Processus Décisionnels de Markov (MDPs), où
l’espace d’actions possibles est explicitement paramétrisés par les ressources disponibles.
Muni de ce cadre, nous avons développé des algorithmes basés sur la programmation
dynamique et la recherche heuristique en temps-réel afin de générer des allocations de
ressources pour des agents qui agissent dans un environnement stochastique.
En particulier, nous avons utilisé la propriété acyclique des créations de tâches
pour décomposer le problème d’allocation de ressources. Nous avons aussi proposé
une stratégie de décomposition approximative, où les agents considèrent des interactions
positives et négatives ainsi que les actions simultanées entre les agents gérants
les ressources. Cependant, la majeure contribution de cette thèse est l’adoption de la
recherche heuristique en temps-réel pour l’allocation de ressources. À cet effet, nous
avons développé une approche basée sur la Q-décomposition munie de bornes strictes
afin de diminuer drastiquement le temps de planification pour formuler une politique
optimale. Ces bornes strictes nous ont permis d’élaguer l’espace d’actions pour les
agents.
Nous montrons analytiquement et empiriquement que les approches proposées
mènent à des diminutions de la complexité de calcul par rapport à des approches
de planification standard. Finalement, nous avons testé la recherche heuristique en
temps-réel dans le simulateur SADM, un simulateur d’allocation de ressource pour une
frégate. / Resource allocation is an ubiquitous problem that arises whenever limited resources
have to be distributed among multiple autonomous entities (e.g., people, companies,
robots, etc). The standard approaches to determine the optimal resource allocation are
computationally prohibitive.
The goal of this thesis is to propose computationally efficient algorithms for allocating
consumable and non-consumable resources among autonomous agents whose
preferences for these resources are induced by a stochastic process. Towards this end,
we have developed new models of planning problems, based on the framework of Markov
Decision Processes (MDPs), where the action sets are explicitly parameterized by the
available resources. Given these models, we have designed algorithms based on dynamic
programming and real-time heuristic search to formulating thus allocations of resources
for agents evolving in stochastic environments.
In particular, we have used the acyclic property of task creation to decompose the
problem of resource allocation. We have also proposed an approximative decomposition
strategy, where the agents consider positive and negative interactions as well as
simultaneous actions among the agents managing the resources. However, the main
contribution of this thesis is the adoption of stochastic real-time heuristic search for a
resource allocation. To this end, we have developed an approach based on distributed
Q-values with tight bounds to diminish drastically the planning time to formulate the
optimal policy. These tight bounds enable to prune the action space for the agents.
We show analytically and empirically that our proposed approaches lead to drastic
(in many cases, exponential) improvements in computational efficiency over standard
planning methods. Finally, we have tested real-time heuristic search in the SADM
simulator, a simulator for the resource allocation of a platform.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QQLA.2007/24957
Date12 1900
CreatorsPlamondon, Pierrick
ContributorsChaib-draa, Brahim
PublisherUniversité Laval
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageFrench
TypeElectronic Thesis or Dissertation
Formattext/html, application/pdf
Rights© Pierrick Plamondon, 2007

Page generated in 0.0106 seconds