Planification et ordonnancement probabilistes sous contraintes temporelles
Institution:
CaenDisciplines:
Directors:
Abstract EN:
This thesis is devoted to the problem of the planning and the scheduling of the tasks under temporal constraints and uncertainty. We deal with two categories of temporal constraints : qualitative and quantitative. Uncertainty over the duration of the tasks is presented in the form of a probability distribution on a finite set. The tasks and the constraints are represented by an AND/OR graph and the durations of the tasks depend on probabilities of execution. Those express an uncertainty on the exact knowledge of the execution time of the tasks which will be really known only during the effective execution. Thus, the execution task takes one of its possible execution durations with a certain probability. Given this graph, our objective is to determine a plan of tasks which satisfies all the constraints and which satisfies the selection criteria required by the user in term of time, cost and probability. The application of this plan must guaranties that the goal is reached while satisfying the constraints of the environment. We applied our method of planning on an example inspired from a real world application relatively complex which relates to the planning of a set of agents working together in order to achieve a goal while the deadlines and the constraints of the environment (time, cost, probability, availability, speciality,. . . ) are respected
Abstract FR:
Cette thèse est consacrée au problème de la planification et de l'ordonnancement des tâches sous contraintes temporelles et incertitude. Les contraintes temporelles que nous traitons sont de deux types : qualitatives et quantitatives. L'incertitude sur la durée des tâches se traduit par une distribution de probabilités sur un ensemble fini. Les tâches et les contraintes sont représentées à l'aide d'un graphe ET/OU et les durées des tâches sont pondérées par des probabilités d'exécution. Celles-ci expriment une incertitude sur la connaissance exacte des durées d'exécution des tâches qui ne seront réellement connues que lors de l'exécution effective. Ainsi, une tâche s'exécute durant l'une de ses durées d'exécution possibles avec la probabilité associée à celle-ci. Étant donné ce graphe, notre objectif est de déterminer un plan de tâches qui satisfait toutes les contraintes et qui répond aux critères de choix exigés par l'utilisateur en terme de temps, de coût et de probabilité. L'application de ce plan doit garantir le monde de façon que le but soit atteint tout en satisfaisant les contraintes du domaine. Nous avons appliqué notre méthode de planification à un cas pratique relativement complexe qui concerne la planification d'un ensemble d'agents travaillant ensemble dans un lieu afin d'atteindre un but donné tout en respectant les délais et les contraintes du domaine (temps, coût, probabilité, disponibilité, spécialité,. . . )